wibble  0.1.28
list.h
Go to the documentation of this file.
00001 // -*- C++ -*-
00002 #include <memory>
00003 #include <vector>
00004 #include <iterator>
00005 #include <algorithm>
00006 #include <cstddef>
00007 
00008 #ifndef WIBBLE_LIST_H
00009 #define WIBBLE_LIST_H
00010 
00011 namespace wibble {
00012 namespace list {
00013 
00014 template< typename List >
00015 struct ListIterator
00016 {
00017     typedef std::forward_iterator_tag iterator_category;
00018     typedef typename List::Type value_type;
00019     typedef ptrdiff_t difference_type;
00020     typedef value_type &pointer;
00021     typedef value_type &reference;
00022 
00023     List l;
00024 
00025     ListIterator &operator++() {
00026         l = l.tail();
00027         return *this;
00028     }
00029 
00030     ListIterator operator++(int) {
00031         ListIterator i = *this;
00032         operator++();
00033         return i;
00034     }
00035 
00036     typename List::Type operator*() {
00037         return l.head();
00038     }
00039 
00040     bool operator==( const ListIterator &o ) const {
00041         return l.empty() && o.l.empty();
00042     }
00043 
00044     bool operator!=( const ListIterator &o ) const {
00045         return !(l.empty() && o.l.empty());
00046     }
00047 
00048     ListIterator( List _l = List() ) : l( _l )
00049     {}
00050 
00051 };
00052 
00053 template< typename List >
00054 struct Sorted
00055 {
00056     typedef std::vector< typename List::Type > Vec;
00057     struct SharedVec {
00058         int refs;
00059         Vec vec;
00060         SharedVec() : refs( 1 ) {}
00061         void _ref() { ++refs; }
00062         void _deref() { --refs; }
00063     };
00064 
00065     struct SharedPtr {
00066         SharedVec *vec;
00067         SharedPtr( bool a = false ) { vec = a ? new SharedVec : 0; }
00068 
00069         SharedPtr( const SharedPtr &o ) {
00070             vec = o.vec;
00071             if ( vec )
00072                 vec->_ref();
00073         }
00074 
00075         SharedPtr &operator=( const SharedPtr &o ) {
00076             vec = o.vec;
00077             if ( vec )
00078                 vec->_ref();
00079             return *this;
00080         }
00081 
00082         operator bool() { return vec; }
00083         Vec &operator*() { return vec->vec; }
00084         Vec *operator->() { return &(vec->vec); }
00085 
00086         ~SharedPtr() {
00087             if ( vec ) {
00088                 vec->_deref();
00089                 if ( !vec->refs )
00090                     delete vec;
00091             }
00092         }
00093     };
00094 
00095     typedef typename List::Type Type;
00096     List m_list;
00097     mutable SharedPtr m_sorted;
00098     size_t m_pos;
00099 
00100     void sort() const {
00101         if ( m_sorted )
00102             return;
00103         m_sorted = SharedPtr( true );
00104         std::copy( ListIterator< List >( m_list ), ListIterator< List >(),
00105                    std::back_inserter( *m_sorted ) );
00106         std::sort( m_sorted->begin(), m_sorted->end() );
00107     }
00108 
00109     Type head() const {
00110         sort();
00111         return (*m_sorted)[ m_pos ];
00112     }
00113 
00114     Sorted tail() const {
00115         sort();
00116         Sorted s = *this;
00117         s.m_pos ++;
00118         return s;
00119     }
00120 
00121     bool empty() const {
00122         sort();
00123         return m_pos == m_sorted->size();
00124     }
00125 
00126     Sorted( const Sorted &o ) : m_list( o.m_list ), m_sorted( o.m_sorted ),
00127                                 m_pos( o.m_pos ) {}
00128 
00129     Sorted &operator=( const Sorted &o ) {
00130         m_sorted = o.m_sorted;
00131         m_list = o.m_list;
00132         m_pos = o.m_pos;
00133         return *this;
00134     }
00135 
00136     Sorted( List l = List() ) : m_list( l ), m_sorted( 0 ), m_pos( 0 ) {}
00137 };
00138 
00139 template< typename List, typename Predicate >
00140 struct Filtered
00141 {
00142     typedef typename List::Type Type;
00143     mutable List m_list;
00144     Predicate m_pred;
00145 
00146     bool empty() const {
00147         seek();
00148         return m_list.empty();
00149     }
00150 
00151     Type head() const {
00152         seek();
00153         return m_list.head();
00154     }
00155 
00156     void seek() const
00157     {
00158         while ( !m_list.empty() && !m_pred( m_list.head() ) )
00159             m_list = m_list.tail();
00160     }
00161 
00162     Filtered tail() const
00163     {
00164         Filtered r = *this;
00165         r.seek();
00166         r.m_list = r.m_list.tail();
00167         return r;
00168     }
00169 
00170     Filtered( List l, Predicate p )
00171         : m_list( l ), m_pred( p )
00172     {
00173     }
00174 
00175     Filtered() {}
00176 };
00177 
00178 template< typename List >
00179 struct Unique
00180 {
00181     typedef typename List::Type Type;
00182     mutable List m_list;
00183 
00184     bool empty() const {
00185         seek();
00186         return m_list.empty();
00187     }
00188 
00189     Type head() const {
00190         seek();
00191         return m_list.head();
00192     }
00193 
00194     void seek() const
00195     {
00196         if ( m_list.empty() )
00197             return;
00198         if ( m_list.tail().empty() )
00199             return;
00200         if ( m_list.head() == m_list.tail().head() ) {
00201             m_list = m_list.tail();
00202             return seek();
00203         }
00204     }
00205 
00206     Unique tail() const
00207     {
00208         Unique r = *this;
00209         r.seek();
00210         r.m_list = r.m_list.tail();
00211         return r;
00212     }
00213 
00214     Unique( List l = List() )
00215         : m_list( l )
00216     {
00217     }
00218 };
00219 
00220 template< typename List >
00221 struct Take {
00222     List l;
00223     int remaining;
00224 
00225     typedef typename List::Type Type;
00226 
00227     Type head() const {
00228         return l.head();
00229     }
00230 
00231     bool empty() const {
00232         return l.empty() || remaining == 0;
00233     }
00234 
00235     Take tail() const {
00236         Take t;
00237         t.remaining = remaining - 1;
00238         t.l = l.tail();
00239         return t;
00240     }
00241 
00242     Take( List _l, int m ) : l( _l ), remaining( m ) {}
00243     Take() : remaining( 0 ) {}
00244 };
00245 
00246 template< typename List, typename F >
00247 struct Map {
00248     List l;
00249 
00250     char f_space[ sizeof( F ) ];
00251     F &f() {
00252         return *(F *)f_space;
00253     }
00254     const F &f() const {
00255         return *(const F *)f_space;
00256     }
00257 
00258     typedef typename F::result_type Type;
00259 
00260     Type head() const {
00261         return f()( l.head() );
00262     }
00263 
00264     Map tail() const {
00265         Map m;
00266         m.l = l.tail();
00267         m.f() = f();
00268         return m;
00269     }
00270 
00271     bool empty() const {
00272         return l.empty();
00273     }
00274 
00275     Map() {}
00276     Map( const List &_l, const F &_f ) 
00277         : l( _l )
00278     {
00279         f() = _f;
00280     }
00281 };
00282 
00283 template< typename T >
00284 struct Empty {
00285     typedef T Type;
00286     T head() const { return T(); }
00287     bool empty() const { return true; }
00288     Empty tail() const { return Empty(); }
00289 };
00290 
00291 template< typename T >
00292 struct Singular {
00293     typedef T Type;
00294     T m_value;
00295     bool m_empty;
00296 
00297     Singular() : m_empty( true ) {}
00298     Singular( T i ) : m_value( i ), m_empty( false ) {}
00299     T head() const { return m_value; }
00300     bool empty() const { return m_empty; }
00301     Singular tail() const { return Singular(); }
00302 };
00303 
00304 template< typename T1, typename T2 >
00305 struct Append {
00306     typedef typename T1::Type Type;
00307     T1 m_1;
00308     T2 m_2;
00309 
00310     Append() {}
00311     Append( T1 a, T2 b ) : m_1( a ), m_2( b ) {}
00312     Type head() const {
00313         if ( m_1.empty() )
00314             return m_2.head();
00315         return m_1.head();
00316     }
00317 
00318     bool empty() const { return m_1.empty() && m_2.empty(); }
00319     Append tail() const {
00320         Append t = *this;
00321         if ( !t.m_1.empty() )
00322             t.m_1 = t.m_1.tail();
00323         else
00324             t.m_2 = t.m_2.tail();
00325         return t;
00326     }
00327 
00328 };
00329 
00330 template< typename X >
00331 Singular< X > singular( const X &x ) {
00332     return Singular< X >( x );
00333 }
00334 
00335 template< typename X, typename Y >
00336 Append< X, Y > append( const X &x, const Y &y ) {
00337     return Append< X, Y >( x, y );
00338 }
00339 
00340 template< typename List >
00341 size_t count( List l ) {
00342     size_t count = 0;
00343     while ( !l.empty() ) {
00344         l = l.tail();
00345         ++ count;
00346     }
00347     return count;
00348 }
00349 
00350 #undef foreach // Work around Qt braindamage.
00351 
00352 template< typename List, typename F >
00353 void foreach( List l, F f ) {
00354     size_t count = 0;
00355     while ( !l.empty() ) {
00356         f( l.head() );
00357         l = l.tail();
00358     }
00359 }
00360 
00361 template< typename List, template< typename > class F >
00362 void foreach( List l, F< typename List::Type > f ) {
00363     size_t count = 0;
00364     while ( !l.empty() ) {
00365         f( l.head() );
00366         l = l.tail();
00367     }
00368 }
00369 
00370 template< typename List, typename Pred >
00371 Filtered< List, Pred > filter( List l, Pred p )
00372 {
00373     return Filtered< List, Pred >( l, p );
00374 }
00375 
00376 template< typename List, template< typename > class Pred >
00377 Filtered< List, Pred< List > > filter( List l, Pred< List > p )
00378 {
00379     return Filtered< List, Pred< List > >( l, p );
00380 }
00381 
00382 template< typename List, typename F >
00383 Map< List, F > map( const List &l, const F &f )
00384 {
00385     return Map< List, F >( l, f );
00386 }
00387 
00388 template< typename List >
00389 Sorted< List > sort( List l )
00390 {
00391     return Sorted< List >( l );
00392 }
00393 
00394 template< typename List >
00395 Unique< List > unique( List l )
00396 {
00397     return Unique< List >( l );
00398 }
00399 
00400 template< typename List >
00401 Take< List > take( int t, List l )
00402 {
00403     return Take< List >( l, t );
00404 }
00405 
00406 template< typename List >
00407 List drop( int t, List l )
00408 {
00409     while ( t > 0 ) {
00410         l = l.tail();
00411         -- t;
00412     }
00413     return l;
00414 }
00415 
00416 template< typename List, typename Out >
00417 void output( List l, Out it ) {
00418     std::copy( ListIterator< List >( l ), ListIterator< List >(), it );
00419 }
00420 
00421 template< typename List >
00422 ListIterator< List > begin( List l ) {
00423     return ListIterator< List >( l );
00424 }
00425 
00426 template< typename List >
00427 ListIterator< List > end( List ) {
00428     return ListIterator< List >();
00429 }
00430 
00431 }
00432 }
00433 
00434 #endif