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_SEARCH_HPP
00008 #define INSTIGATE_STL_SEARCH_HPP
00009
00058
00059 #include "concept.hpp"
00060 #include "_find.hpp"
00061 #include "_basis.hpp"
00062
00063
00064
00065
00066
00067
00068 namespace instigate {
00069 namespace stl {
00070 template <typename F1, typename F2, typename BP>
00071 void check_prerequisites();
00072 template <typename F1, typename F2>
00073 void check_prerequisites();
00074 template <typename F1, typename F2>
00075 F1 search(F1 b, F1 e, F2 f, F2 l);
00076 template <typename F1, typename F2, typename BP>
00077 F1 search(F1 b, F1 e, F2 f, F2 l, BP p);
00078 }
00079 }
00080
00084 template <typename F1, typename F2>
00085 void instigate::stl::check_prerequisites()
00086 {
00087 namespace RI = instigate::stl::readable_iterator;
00088 namespace FI = instigate::stl::forward_iterator;
00089 namespace EQ = instigate::generic::equality_comparable;
00090 namespace DI = instigate::generic::default_constructible;
00091 CHECK(RI::requirements<F1>);
00092 CHECK(FI::requirements<F1>);
00093 CHECK(RI::requirements<F2>);
00094 CHECK(FI::requirements<F2>);
00095 typedef typename RI::interface<F1>::value_type value_type1;
00096 CHECK(EQ::requirements<value_type1>);
00097 typedef typename RI::interface<F2>::value_type value_type2;
00098 CHECK(EQ::requirements<value_type2>);
00099 }
00100
00143 template <typename F1, typename F2>
00144 F1 instigate::stl::search(F1 b, F1 e, F2 f, F2 l)
00145 {
00146 check_prerequisites<F1, F2>();
00147 if (equal(b, e) || equal(f, l)) {
00148 return b;
00149 }
00150 char z[sizeof(F2)];
00151 F2* t = 0;
00152 assign(t, copy_constructor(z, f));
00153 assert(0 != t);
00154 increment(*t);
00155 if (equal(*t, l)) {
00156 return instigate::stl::find(b, e, const_dereference(f));
00157 }
00158 char k[sizeof(F2)];
00159 F2* p1 = 0;
00160 assign(p1, copy_constructor(k, f));
00161 assert(0 != p1);
00162 char x[sizeof(F2)];
00163 F2* p = 0;
00164 assign(p, initialize<F2>(x));
00165 assert(0 != p);
00166 increment(*p1);
00167 char y[sizeof(F1)];
00168 F1* c = 0;
00169 assign(c, copy_constructor(y, b));
00170 while (!equal(b, e)) {
00171 assign(b, instigate::stl::find(b, e, const_dereference(f)));
00172 if (equal(b, e)) {
00173 return e;
00174 }
00175 assign(*p, *p1);
00176 assert(0 != c);
00177 assign(*c, b);
00178 increment(*c);
00179 if (equal(*c, e)) {
00180 return e;
00181 }
00182 while (equal(const_dereference(*c), const_dereference(*p))) {
00183 increment(*p);
00184 if (equal(*p, l)) {
00185 return b;
00186 }
00187 increment(*c);
00188 if (equal(*c, e)) {
00189 return e;
00190 }
00191 }
00192 increment(b);
00193 }
00194 return b;
00195 }
00196
00200 template <typename F1, typename F2, typename BP>
00201 void instigate::stl::check_prerequisites()
00202 {
00203 namespace RI = instigate::stl::readable_iterator;
00204 namespace FI = instigate::stl::forward_iterator;
00205 namespace EQ = instigate::generic::equality_comparable;
00206 namespace BPI = instigate::stl::binary_predicate;
00207 namespace DI = instigate::generic::default_constructible;
00208 CHECK(RI::requirements<F1>);
00209 CHECK(FI::requirements<F1>);
00210 CHECK(RI::requirements<F2>);
00211 CHECK(FI::requirements<F2>);
00212 CHECK(BPI::requirements<BP>);
00213 typedef typename RI::interface<F1>::value_type value_type1;
00214 typedef typename RI::interface<F2>::value_type value_type2;
00215 typedef typename BPI::interface<BP>::
00216 first_argument_type first_argument_type;
00217 typedef typename BPI::interface<BP>::
00218 second_argument_type second_argument_type;
00219 CHECK_CONVERTIBILITY(value_type1, first_argument_type);
00220 CHECK_CONVERTIBILITY(value_type2, second_argument_type);
00221 }
00222
00266 template <typename F1, typename F2, typename BP>
00267 F1 instigate::stl::search(F1 b, F1 e, F2 f, F2 l, BP p)
00268 {
00269 check_prerequisites<F1, F2, BP>();
00270 if (equal(b, e) || equal(f, l)) {
00271 return b;
00272 }
00273 char z[sizeof(F2)];
00274 F2* t = 0;
00275 assign(t, copy_constructor(z, f));
00276 assert(0 != t);
00277 increment(*t);
00278 if (equal(*t, l)) {
00279 while ((!equal(b, e)) && (!invoke_predicate(p,
00280 const_dereference(b),
00281 const_dereference(f))))
00282 {
00283 increment(b);
00284 }
00285 return b;
00286 }
00287 char k[sizeof(F2)];
00288 F2* r1 = 0;
00289 assign(r1, copy_constructor(k, f));
00290 assert(0 != r1);
00291 char x[sizeof(F2)];
00292 F2* r = 0;
00293 assign(r, initialize<F2>(x));
00294 assert(0 != r);
00295 increment(*r1);
00296 char y[sizeof(F1)];
00297 F1* c = 0;
00298 assign(c, copy_constructor(y, b));
00299 assert(0 != c);
00300 while (!equal(b, e)) {
00301 while (!equal(b, e)) {
00302 if (invoke_predicate(p, const_dereference(b),
00303 const_dereference(f)))
00304 {
00305 break;
00306 }
00307 increment(b);
00308 }
00309 while ((!equal(b, e)) && (!invoke_predicate(p,
00310 const_dereference(b),
00311 const_dereference(f))))
00312 {
00313 increment(b);
00314 }
00315 if (equal(b, e)) {
00316 return e;
00317 }
00318 assign(*r, *r1);
00319 assign(*c, b);
00320 increment(*c);
00321 if (equal(*c, e)) {
00322 return e;
00323 }
00324 while (invoke_predicate(p, const_dereference(*c),
00325 const_dereference(*r)))
00326 {
00327 increment(*r);
00328 if (equal(*r, l)) {
00329 return b;
00330 }
00331 increment(*c);
00332 if (equal(*c, e)) {
00333 return e;
00334 }
00335 }
00336 increment(b);
00337 }
00338 return b;
00339 }
00340
00341
00342
00343 #endif // INSTIGATE_STL_SEARCH_HPP