00001
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