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 int 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 F f;
00249 typedef typename F::result_type Type;
00250
00251 Type head() const {
00252 return f( l.head() );
00253 }
00254
00255 Map tail() const {
00256 Map m;
00257 m.l = l.tail();
00258 m.f = f;
00259 return m;
00260 }
00261
00262 bool empty() const {
00263 return l.empty();
00264 }
00265
00266 Map() {}
00267 Map( const List &_l, const F &_f )
00268 : l( _l ), f( _f )
00269 {}
00270 };
00271
00272 template< typename T >
00273 struct Empty {
00274 typedef T Type;
00275 T head() const { return T(); }
00276 bool empty() const { return true; }
00277 Empty tail() const { return Empty(); }
00278 };
00279
00280 template< typename T >
00281 struct Singular {
00282 typedef T Type;
00283 T m_value;
00284 bool m_empty;
00285
00286 Singular() : m_empty( true ) {}
00287 Singular( T i ) : m_value( i ), m_empty( false ) {}
00288 T head() const { return m_value; }
00289 bool empty() const { return m_empty; }
00290 Singular tail() const { return Singular(); }
00291 };
00292
00293 template< typename T1, typename T2 >
00294 struct Append {
00295 typedef typename T1::Type Type;
00296 T1 m_1;
00297 T2 m_2;
00298
00299 Append() {}
00300 Append( T1 a, T2 b ) : m_1( a ), m_2( b ) {}
00301 Type head() const {
00302 if ( m_1.empty() )
00303 return m_2.head();
00304 return m_1.head();
00305 }
00306
00307 bool empty() const { return m_1.empty() && m_2.empty(); }
00308 Append tail() const {
00309 Append t = *this;
00310 if ( !t.m_1.empty() )
00311 t.m_1 = t.m_1.tail();
00312 else
00313 t.m_2 = t.m_2.tail();
00314 return t;
00315 }
00316
00317 };
00318
00319 template< typename X >
00320 Singular< X > singular( const X &x ) {
00321 return Singular< X >( x );
00322 }
00323
00324 template< typename X, typename Y >
00325 Append< X, Y > append( const X &x, const Y &y ) {
00326 return Append< X, Y >( x, y );
00327 }
00328
00329 template< typename List >
00330 size_t count( List l ) {
00331 size_t count = 0;
00332 while ( !l.empty() ) {
00333 l = l.tail();
00334 ++ count;
00335 }
00336 return count;
00337 }
00338
00339 #undef foreach // Work around Qt braindamage.
00340
00341 template< typename List, typename F >
00342 void foreach( List l, F f ) {
00343 size_t count = 0;
00344 while ( !l.empty() ) {
00345 f( l.head() );
00346 l = l.tail();
00347 }
00348 }
00349
00350 template< typename List, template< typename > class F >
00351 void foreach( List l, F< typename List::Type > f ) {
00352 size_t count = 0;
00353 while ( !l.empty() ) {
00354 f( l.head() );
00355 l = l.tail();
00356 }
00357 }
00358
00359 template< typename List, typename Pred >
00360 Filtered< List, Pred > filter( List l, Pred p )
00361 {
00362 return Filtered< List, Pred >( l, p );
00363 }
00364
00365 template< typename List, template< typename > class Pred >
00366 Filtered< List, Pred< List > > filter( List l, Pred< List > p )
00367 {
00368 return Filtered< List, Pred< List > >( l, p );
00369 }
00370
00371 template< typename List, typename F >
00372 Map< List, F > map( const List &l, const F &f )
00373 {
00374 return Map< List, F >( l, f );
00375 }
00376
00377 template< typename List >
00378 Sorted< List > sort( List l )
00379 {
00380 return Sorted< List >( l );
00381 }
00382
00383 template< typename List >
00384 Unique< List > unique( List l )
00385 {
00386 return Unique< List >( l );
00387 }
00388
00389 template< typename List >
00390 Take< List > take( int t, List l )
00391 {
00392 return Take< List >( l, t );
00393 }
00394
00395 template< typename List >
00396 ListIterator< List > begin( List l ) {
00397 return ListIterator< List >( l );
00398 }
00399
00400 template< typename List >
00401 ListIterator< List > end( List ) {
00402 return ListIterator< List >();
00403 }
00404
00405 }
00406 }
00407
00408 #endif