00001
00002 #ifndef _INSTIGATE_STL_INTERNAL_HEADER_IN_ALGORITHM
00003 #error This is an internal header file used to implement Instigate STL.\
00004 It should never be included directly by a program.
00005 #endif
00006
00007 #ifndef INSTIGATE_STL_LOWER_BOUND_HPP
00008 #define INSTIGATE_STL_LOWER_BOUND_HPP
00009
00059
00060 #include "concept.hpp"
00061 #include "_basis.hpp"
00062 #include "_distance.hpp"
00063 #include "_advance.hpp"
00064
00065
00066 #include <generic/base.hpp>
00067
00068
00069
00070
00071 namespace instigate {
00072 namespace stl {
00073 namespace implementation {
00074 template <typename F, typename L, typename D>
00075 F lower_bound_aux(F b, F e, const L& v, D*);
00076 template <typename F, typename L, typename C, typename D>
00077 F lower_bound_aux(F b, F e, const L& v, C c, D*);
00078 }
00079 template <typename F, typename L>
00080 inline F lower_bound(F b, F e, const L& v);
00081 template <typename F, typename L, typename C>
00082 inline F lower_bound(F b, F e, const L& v, C c);
00083 }
00084 }
00085
00125 template <typename F, typename L>
00126 inline F instigate::stl::lower_bound(F b, F e, const L& v)
00127 {
00128 namespace FI = instigate::stl::forward_iterator;
00129 typedef typename instigate::stl::readable_iterator::interface<F>::
00130 value_type value_type;
00131 CHECK(FI::requirements<F>);
00132 CHECK(instigate::stl::readable_iterator::requirements<F>);
00133 CHECK(instigate::generic::less_than_comparable::requirements<L>);
00134 CHECK_SAME_TYPE(value_type, L);
00135 typename FI::interface<F>::difference_type* k = 0;
00136 return instigate::stl::implementation::lower_bound_aux(b, e, v, k);
00137 }
00138
00140 template <typename F, typename L, typename D>
00141 F instigate::stl::implementation::lower_bound_aux(F b, F e, const L& v, D*)
00142 {
00143 namespace FI = instigate::stl::forward_iterator;
00144 typedef typename FI::interface<F>::difference_type difference_type;
00145 CHECK_CONVERTIBILITY(D, difference_type);
00146 D len = 0;
00147 assign(len, instigate::stl::distance(b, e));
00148 D half = 0;
00149 char k[sizeof(F)];
00150 F* middle = 0;
00151 assign(middle, initialize<F>(k));
00152 while (0 < len) {
00153 assign(half, len >> 1);
00154 assert(0 != middle);
00155 assign(*middle, b);
00156 instigate::stl::advance(*middle, half);
00157 if (less_than(const_dereference(*middle), v)) {
00158 assign(b, *middle);
00159 increment(b);
00160 assign(len, len - half -1);
00161 } else {
00162 assign(len, half);
00163 }
00164 }
00165 return b;
00166 }
00167
00212 template <typename F, typename L, typename C>
00213 inline F instigate::stl::lower_bound(F b, F e, const L& v, C c)
00214 {
00215 namespace FI = instigate::stl::forward_iterator;
00216 typedef typename instigate::stl::readable_iterator::interface<F>::
00217 value_type value_type;
00218 CHECK(FI::requirements<F>);
00219 CHECK(instigate::stl::readable_iterator::requirements<F>);
00220 CHECK(instigate::generic::less_than_comparable::requirements<L>);
00221 CHECK(instigate::stl::binary_predicate::requirements<C>);
00222 CHECK_SAME_TYPE(value_type, L);
00223 typename FI::interface<F>::difference_type* k = 0;
00224 return instigate::stl::implementation::lower_bound_aux(b, e, v, c, k);
00225 }
00226
00228 template <typename F, typename L, typename C, typename D>
00229 F instigate::stl::implementation::lower_bound_aux(F b, F e, const L& v, C c, D*)
00230 {
00231 namespace FI = instigate::stl::forward_iterator;
00232 typedef typename FI::interface<F>::difference_type difference_type;
00233 CHECK_CONVERTIBILITY(D, difference_type);
00234 D len = 0;
00235 assign(len, instigate::stl::distance(b, e));
00236 D half = 0;
00237 char k[sizeof(F)];
00238 F* middle = 0;
00239 assign(middle, initialize<F>(k));
00240 while (0 < len) {
00241 assign(half, len >> 1);
00242 assert(0 != middle);
00243 assign(*middle, b);
00244 instigate::stl::advance(*middle, half);
00245 if (invoke_predicate(c, const_dereference(*middle), v)) {
00246 assign(b, *middle);
00247 increment(b);
00248 assign(len, len - half - 1);
00249 } else {
00250 assign(len, half);
00251 }
00252 }
00253 return b;
00254 }
00255
00256
00257
00258 #endif // INSTIGATE_STL_LOWER_BOUND_HPP
00259