00001
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