Instigate Open Source Documentation

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_FIND_END_HPP
00008 #define INSTIGATE_STL_FIND_END_HPP
00009 
00056 // Headers from this project
00057 #include "concept.hpp"
00058 #include "_search.hpp"
00059 #include "_advance.hpp"
00060 #include "_distance.hpp"
00061 
00062 // Headers from other project
00063 
00064 // Headers from standard library
00065 
00066 // Forward declaration
00067 namespace instigate {
00068         namespace stl {
00069                 template <typename F1, typename F2>
00070                 F1 find_end(F1 b, F1 e, F2 f, F2 l);
00071 
00072                 template <typename F1, typename F2, typename BP>
00073                 F1 find_end(F1 b, F1 e, F2 f, F2 l, BP p);
00074                 namespace implementation {
00075                         template <typename F1,typename F2>
00076                         F1 find_end_aux(F1 b, F1 e, F2 f, F2 l, 
00077                                 instigate::stl::forward_iterator::tag,
00078                                 instigate::stl::forward_iterator::tag);
00079 
00080                         template <typename B1,typename B2>
00081                         B1 find_end_aux(B1 b, B1 e, B2 f, B2 l, 
00082                                 instigate::stl::bidirectional_iterator::tag,
00083                                 instigate::stl::bidirectional_iterator::tag);
00084 
00085                         template <typename F1,typename F2, typename BP>
00086                         F1 find_end_aux(F1 b, F1 e, F2 f, F2 l, BP p,
00087                                 instigate::stl::forward_iterator::tag,
00088                                 instigate::stl::forward_iterator::tag);
00089 
00090                         template <typename B1,typename B2, typename BP>
00091                         B1 find_end_aux(B1 b, B1 e, B2 f, B2 l, BP p,
00092                                 instigate::stl::bidirectional_iterator::tag,
00093                                 instigate::stl::bidirectional_iterator::tag);
00094 
00095                         template <typename B1, typename B2, typename BP>
00096                         B1 search_end(B1 b, B1 e, B2 f, B2 l, BP p);
00097                 } // namespace implementation
00098         } // namespace stl
00099 } // namespace instigate
00100 
00146 template <typename F1, typename F2>
00147 F1 instigate::stl::find_end(F1 b, F1 e, F2 f, F2 l)
00148 {
00149         typename instigate::stl::incrementable_iterator::interface<F1>::
00150                 iterator_category category1;
00151         typename instigate::stl::incrementable_iterator::interface<F2>::
00152                 iterator_category category2;
00153         return implementation::find_end_aux(b, e, f, l, category1, category2);
00154 }
00155 
00160 template <typename F1,typename F2>
00161 F1 instigate::stl::implementation::find_end_aux(F1 b, F1 e, F2 f, F2 l, 
00162                 instigate::stl::forward_iterator::tag,
00163                 instigate::stl::forward_iterator::tag)
00164 {
00165         namespace RI = instigate::stl::readable_iterator; 
00166         namespace EQ = instigate::generic::equality_comparable;
00167         typedef typename RI::interface<F1>::value_type value_type1;
00168         CHECK(EQ::requirements<value_type1>);
00169         typedef typename RI::interface<F2>::value_type value_type2;
00170         CHECK(EQ::requirements<value_type2>);
00171         if(equal(f, l)) {
00172                 return e;
00173         }
00174         else {
00175                 char k[sizeof(F1)];
00176                 F1* r;
00177                 assign(r, copy_constructor(k, e));
00178                 char j[sizeof(F1)];
00179                 while (1) {
00180                         F1* new_r;
00181                         assign(new_r, copy_constructor(j, 
00182                                     instigate::stl::search(b, e, f, l)));
00183                         if (equal(*new_r, e))
00184                                 return *r;
00185                         else {
00186                                 assign(*r, *new_r);
00187                                 assign(b, *new_r);
00188                                 increment(b);
00189                         }
00190                 }
00191         }
00192 }
00193 
00198 template <typename B1,typename B2>
00199 B1 instigate::stl::implementation::find_end_aux(B1 b, B1 e, B2 f, B2 l, 
00200                 instigate::stl::bidirectional_iterator::tag,
00201                 instigate::stl::bidirectional_iterator::tag)
00202 {
00203         namespace RI = instigate::stl::readable_iterator; 
00204         namespace BI = instigate::stl::bidirectional_iterator; 
00205         namespace EQ = instigate::generic::equality_comparable;
00206         CHECK(RI::requirements<B1>);
00207         CHECK(BI::requirements<B1>);
00208         CHECK(RI::requirements<B2>);
00209         CHECK(BI::requirements<B2>);
00210         typedef typename RI::interface<B1>::value_type value_type1;
00211         CHECK(EQ::requirements<value_type1>);
00212         typedef typename RI::interface<B2>::value_type value_type2;
00213         CHECK(EQ::requirements<value_type2>);
00214         typedef std::reverse_iterator<B1> RevIter1;
00215         typedef std::reverse_iterator<B2> RevIter2;
00216         RevIter1 re(b);
00217         RevIter2 rl(f);
00218         RevIter1 r_r;
00219         assign(r_r, instigate::stl::search(RevIter1(e), re, RevIter2(l), rl));
00220         if (equal(r_r, re)) {
00221                 return e;
00222         } else {
00223                 char k[sizeof(B1)];
00224                 B1* r;
00225                 assign(r, RI::interface<B1>::copy_constructor(k, r_r.base()));
00226                 instigate::stl::advance(*r, -instigate::stl::distance(f, l));
00227                 return *r;
00228         }
00229 }
00230 
00273 template <typename F1, typename F2, typename BP>
00274 F1 instigate::stl::find_end(F1 b, F1 e, F2 f, F2 l, BP p)
00275 {
00276         typename instigate::stl::incrementable_iterator::interface<F1>
00277                 ::iterator_category category1;
00278         typename instigate::stl::incrementable_iterator::interface<F2>
00279                 ::iterator_category category2;
00280         return implementation::find_end_aux(b, e, f, l, p, category1,category2);
00281 }
00282 
00287 template <typename F1,typename F2, typename BP>
00288 F1 instigate::stl::implementation::find_end_aux(F1 b, F1 e, F2 f, F2 l, BP p,
00289         instigate::stl::forward_iterator::tag,
00290         instigate::stl::forward_iterator::tag)
00291 {
00292         namespace RI = instigate::stl::readable_iterator; 
00293         namespace DF = instigate::generic::default_constructible; 
00294         namespace FI = instigate::stl::forward_iterator; 
00295         namespace EQ = instigate::generic::equality_comparable;
00296         namespace BPI = instigate::stl::binary_predicate;
00297         CHECK(RI::requirements<F1>);
00298         CHECK(FI::requirements<F1>);
00299         CHECK(RI::requirements<F2>);
00300         CHECK(FI::requirements<F2>);
00301         CHECK(BPI::requirements<BP>);
00302         typedef typename RI::interface<F1>::value_type value_type1;
00303         typedef typename RI::interface<F2>::value_type value_type2;
00304         typedef typename BPI::interface<BP>::first_argument_type 
00305                 first_argument_type;
00306         typedef typename BPI::interface<BP>::second_argument_type
00307                 second_argument_type;
00308         CHECK_CONVERTIBILITY(value_type1, first_argument_type);
00309         CHECK_CONVERTIBILITY(value_type2, second_argument_type);
00310         if(equal(f, l)) {
00311                 return e;
00312         } else {
00313                 char k[sizeof(F1)];
00314                 F1* r = 0;
00315                 assign(r, copy_constructor(k, e));
00316                 char j[sizeof(F1)];
00317                 while (1) {
00318                         F1* new_r = 0;
00319                         assign(new_r, copy_constructor(j, 
00320                                 instigate::stl::search(b, e, f, l, p)));
00321                         if (*new_r == e) {
00322                                 return *r;
00323                         } else {
00324                                 assign(*r, *new_r);
00325                                 assign(b, *new_r);
00326                                 increment(b);
00327                         }
00328                 }
00329         }
00330 }
00331 
00336 template <typename B1,typename B2, typename BP>
00337 B1 instigate::stl::implementation::find_end_aux(B1 b, B1 e, B2 f, B2 l, BP p, 
00338                 instigate::stl::bidirectional_iterator::tag,
00339                 instigate::stl::bidirectional_iterator::tag)
00340 {
00341         namespace RI = instigate::stl::readable_iterator; 
00342         namespace BI = instigate::stl::bidirectional_iterator; 
00343         namespace EQ = instigate::generic::equality_comparable;
00344         namespace BPI = instigate::stl::binary_predicate;
00345         CHECK(RI::requirements<B1>);
00346         CHECK(BI::requirements<B1>);
00347         CHECK(RI::requirements<B2>);
00348         CHECK(BI::requirements<B2>);
00349         CHECK(BPI::requirements<BP>);
00350         typedef typename RI::interface<B1>::value_type value_type1;
00351         CHECK(EQ::requirements<value_type1>);
00352         typedef typename RI::interface<B2>::value_type value_type2;
00353         CHECK(EQ::requirements<value_type2>);
00354         return instigate::stl::implementation::search_end(b, e, f, l, p);
00355 }
00356 
00360 template <typename I, typename V>
00361 inline I _find(I b, I e, const V& v)
00362 {
00363                 using namespace instigate::stl;
00364                 char c[sizeof(I)];
00365                 I* k = 0;
00366                 assign(k, copy_constructor(c, e));
00367                 while(!equal(b, e))
00368                 {
00369                         if(equal(const_dereference(e), v)) {
00370                                 return e;
00371                         }       
00372                         decrement(e);
00373                 }
00374                 return *k;
00375 }                                       
00376 
00377 
00381 template <typename B1, typename B2, typename BP>
00382 B1 instigate::stl::implementation::search_end(B1 b, B1 e, B2 f, B2 l, BP p)
00383 {
00384         if (equal(b, e) || equal(f, l)) {
00385                 return e;
00386         }
00387         decrement(l);
00388         if(equal(l, f)){
00389                 return _find(b, e, const_dereference(l));
00390         }
00391         char c1[sizeof(B1)];
00392         B1* k = 0;
00393         assign(k, copy_constructor(c1, e));
00394         decrement(e);
00395         char c2[sizeof(B2)];
00396         B2* j = 0;
00397         assign(j, copy_constructor(c2, l));
00398         while(! equal(b, e)) {
00399                 while(invoke_predicate(p, *l, *e)) {
00400                         if(equal(f, l)) {
00401                                 return e;
00402                         }
00403                         decrement(e);
00404                         if(equal(b, e)) {
00405                                 return *k;
00406                         }
00407                         decrement(l);
00408                 }
00409                 assign(l, *j);
00410                 decrement(e);
00411         }
00412         return *k;
00413 }
00414 
00415 // vim:et:tabstop=8:shiftwidth=8:cindent:fo=croq:textwidth=80:
00416 
00417 #endif // INSTIGATE_STL_FIND_END_HPP
src/stl/_find_end.hpp
