wibble
0.1.28
|
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