• Main Page
  • Namespaces
  • Classes
  • Files
  • File List
  • File Members

list.h

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

Generated on Tue May 10 2011 16:51:50 for wibble by  doxygen 1.7.1