wibble 0.1.28
|
00001 00006 #include <iostream> // for noise 00007 #include <iterator> 00008 #include <vector> 00009 #include <set> 00010 #include <algorithm> 00011 #include <ext/algorithm> 00012 00013 #include <wibble/iterator.h> 00014 #include <wibble/exception.h> 00015 00016 #ifndef WIBBLE_RANGE_H 00017 #define WIBBLE_RANGE_H 00018 00019 namespace wibble { 00020 00021 template< typename _ > struct Range; 00022 template< typename _ > struct Consumer; 00023 00024 // FOO: there was no test catching that we don't implement -> 00025 // auxilliary class, used as Range< T >::iterator 00026 template< typename R > 00027 struct RangeIterator : mixin::Comparable< RangeIterator< R > > { 00028 typedef typename R::ElementType T; 00029 00030 struct Proxy { 00031 Proxy( T _x ) : x( _x ) {} 00032 T x; 00033 const T *operator->() const { return &x; } 00034 }; 00035 00036 RangeIterator() {} 00037 RangeIterator( const R &r ) : m_range( r ) {} 00038 00039 typedef std::forward_iterator_tag iterator_category; 00040 typedef T value_type; 00041 typedef ptrdiff_t difference_type; 00042 typedef T *pointer; 00043 typedef T &reference; 00044 typedef const T &const_reference; 00045 00046 Proxy operator->() const { return Proxy( *(*this) ); } 00047 00048 RangeIterator next() const { RangeIterator n( *this ); ++n; return n; } 00049 typename R::ElementType operator*() const { return m_range.head(); } 00050 typename R::ElementType current() const { return *(*this); } 00051 RangeIterator &operator++() { m_range.removeFirst(); return *this; } 00052 RangeIterator operator++(int) { return m_range.removeFirst(); } 00053 bool operator<=( const RangeIterator &r ) const { 00054 return m_range.operator<=( r.m_range ); 00055 } 00056 protected: 00057 R m_range; 00058 }; 00059 00060 // the common functionality of all ranges 00061 template< typename T, typename Self > 00062 struct RangeMixin : mixin::Comparable< Self > 00063 { 00064 typedef Self RangeImplementation; 00065 typedef T ElementType; 00066 const Self &self() const { return *static_cast< const Self * >( this ); } 00067 typedef IteratorMixin< T, Self > Base; 00068 typedef RangeIterator< Self > iterator; 00069 friend struct RangeIterator< Self >; 00070 00071 iterator begin() const { return iterator( this->self() ); } // STL-style iteration 00072 iterator end() const { Self e( this->self() ); e.setToEmpty(); return iterator( e ); } 00073 00074 // range terminology 00075 T head() { return self().head(); } 00076 Self tail() const { Self e( this->self() ); e.removeFirst(); return e; } 00077 // Self &tail() { return self().tail(); } 00078 00079 void output( Consumer< T > t ) const { 00080 std::copy( begin(), end(), t ); 00081 } 00082 00083 bool empty() const { 00084 return begin() == end(); 00085 } 00086 00087 ~RangeMixin() {} 00088 }; 00089 00090 // interface to be implemented by all range implementations 00091 // refinement of IteratorInterface (see iterator.h) 00092 // see also amorph.h on how the Morph/Amorph classes are designed 00093 template< typename T > 00094 struct RangeInterface { 00095 virtual T head() const = 0; 00096 virtual void removeFirst() = 0; 00097 virtual void setToEmpty() = 0; 00098 virtual ~RangeInterface() {} 00099 }; 00100 00101 template< typename T, typename W > 00102 struct RangeMorph: Morph< RangeMorph< T, W >, W, RangeInterface< T > > 00103 { 00104 typedef typename W::RangeImplementation Wrapped; 00105 RangeMorph( const Wrapped &w ) : Morph< RangeMorph, Wrapped, RangeInterface< T > >( w ) {} 00106 virtual void setToEmpty() { this->wrapped().setToEmpty(); } 00107 virtual void removeFirst() { this->wrapped().removeFirst(); } 00108 virtual T head() const { return this->wrapped().head(); } 00109 }; 00110 00111 // the Amorph of Ranges... if you still didn't check amorph.h, go and 00112 // do it... unless you don't care in which case i am not sure why you 00113 // are reading this anyway 00114 00115 /* 00116 Range< T > (and all its Morphs (implementations) alike) work as an 00117 iterable, immutable range of items -- in a way like STL 00118 const_begin(), const_end() pair of iterators. However, Range packs 00119 these two in a single object, which you can then pass as a single 00120 argument or return as a value. There are many Range implementations, 00121 some of them use STL containers (or just a pair of iterators) as 00122 backing (IteratorRange, BackedRange), some use other ranges. 00123 00124 The latter are slightly more interesting, since they provide an 00125 "adapted" view on the underlying range(s). See FilteredRange, 00126 TransformedRange, UniqueRange, CastedRange , IntersectionRange. 00127 00128 GeneratedRange has no "real" backing at all, but use a pair of 00129 functors and "generates" (by calling those functors) the complete 00130 range as it is iterated. 00131 00132 Example usage: 00133 00134 // create a range from a pair of STL iterators 00135 Range< int > i = range( myIntVector.begin(), myIntVector.end() ); 00136 // create a range that is filtered view of another range 00137 Range< int > j = filteredRange( i, predicate ); 00138 std::vector< int > vec; 00139 // copy out items in j into vec; see also consumer.h 00140 j.output( consumer( vec ) ); 00141 // vec now contains all items from i (and thus myIntVector) that 00142 // match 'predicate' 00143 00144 You don't have to use Range< int > all the time, since it's fairly 00145 inefficient (adding level of indirection). However in common cases 00146 it is ok. In the uncommon cases you can use the specific 00147 implementation type and there you won't suffer the indirection 00148 penalty. You can also write generic functions that have type of 00149 range as their template parameter and these will work more 00150 efficiently if Morph is used directly and less efficiently when the 00151 Amorph Range is used instead. 00152 */ 00153 template< typename T > 00154 struct Range : Amorph< Range< T >, RangeInterface< T > >, 00155 RangeMixin< T, Range< T > > 00156 { 00157 typedef Amorph< Range< T >, RangeInterface< T > > Super; 00158 00159 template< typename C > 00160 Range( const C &i, typename IsType< int, typename C::RangeImplementation >::T fake = 0 ) 00161 : Super( RangeMorph< T, C >( i ) ) { (void)fake; } 00162 Range() {} 00163 00164 T head() const { return this->implementation()->head(); } 00165 void removeFirst() { this->implementation()->removeFirst(); } 00166 void setToEmpty() { this->implementation()->setToEmpty(); } 00167 00168 template< typename C > operator Range< C >(); 00169 }; 00170 00171 /* template< typename R > 00172 Range< typename R::ElementType > rangeMorph( R r ) { 00173 return Range< typename R::ElementType > uRangeMorph< typename R::ElementType, R >( r ); 00174 } */ 00175 00176 } 00177 00178 // ----- individual range implementations follow 00179 #include <wibble/consumer.h> 00180 00181 namespace wibble { 00182 00183 // a simple pair of iterators -- suffers the same invalidation 00184 // semantics as normal STL iterators and also same problems when the 00185 // backing storage goes out of scope 00186 00187 // this is what you get when using range( iterator1, iterator2 ) 00188 // see also range() 00189 template< typename It > 00190 struct IteratorRange : public RangeMixin< 00191 typename std::iterator_traits< It >::value_type, 00192 IteratorRange< It > > 00193 { 00194 typedef typename std::iterator_traits< It >::value_type Value; 00195 00196 IteratorRange() {} 00197 IteratorRange( It c, It e ) 00198 : m_current( c ), m_end( e ) {} 00199 00200 Value head() const { return *m_current; } 00201 void removeFirst() { ++m_current; } 00202 00203 bool operator<=( const IteratorRange &r ) const { 00204 return r.m_current == m_current && r.m_end == m_end; 00205 } 00206 00207 void setToEmpty() { 00208 m_current = m_end; 00209 } 00210 00211 protected: 00212 It m_current, m_end; 00213 }; 00214 00215 // first in the series of ranges that use another range as backing 00216 // this one just does static_cast to specified type on all the 00217 // returned elements 00218 00219 // this is what you get when casting Range< S > to Range< T > and S is 00220 // static_cast-able to T 00221 00222 template< typename T, typename Casted > 00223 struct CastedRange : public RangeMixin< T, CastedRange< T, Casted > > 00224 { 00225 CastedRange() {} 00226 CastedRange( Range< Casted > r ) : m_casted( r ) {} 00227 T head() const { 00228 return static_cast< T >( m_casted.head() ); 00229 } 00230 void removeFirst() { m_casted.removeFirst(); } 00231 00232 bool operator<=( const CastedRange &r ) const { 00233 return m_casted <= r.m_casted; 00234 } 00235 00236 void setToEmpty() { 00237 m_casted.setToEmpty(); 00238 } 00239 00240 protected: 00241 Range< Casted > m_casted; 00242 }; 00243 00244 // explicit range-cast... probably not very useful explicitly, just 00245 // use the casting operator of Range 00246 template< typename T, typename C > 00247 Range< T > castedRange( C r ) { 00248 return CastedRange< T, typename C::ElementType >( r ); 00249 } 00250 00251 // old-code-compat for castedRange... slightly silly 00252 template< typename T, typename C > 00253 Range< T > upcastRange( C r ) { 00254 return CastedRange< T, typename C::ElementType >( r ); 00255 } 00256 00257 // the range-cast operator, see castedRange and CastedRange 00258 template< typename T > template< typename C > 00259 Range< T >::operator Range< C >() { 00260 return castedRange< C >( *this ); 00261 } 00262 00263 // range( iterator1, iterator2 ) -- see IteratorRange 00264 template< typename In > 00265 Range< typename In::value_type > range( In b, In e ) { 00266 return IteratorRange< In >( b, e ); 00267 } 00268 00269 template< typename C > 00270 Range< typename C::iterator::value_type > range( C &c ) { 00271 return range( c.begin(), c.end() ); 00272 } 00273 00274 template< typename T > 00275 struct IntersectionRange : RangeMixin< T, IntersectionRange< T > > 00276 { 00277 IntersectionRange() {} 00278 IntersectionRange( Range< T > r1, Range< T > r2 ) 00279 : m_first( r1 ), m_second( r2 ), 00280 m_valid( false ) 00281 { 00282 } 00283 00284 void find() const { 00285 if (!m_valid) { 00286 while ( !m_first.empty() && !m_second.empty() ) { 00287 if ( m_first.head() < m_second.head() ) 00288 m_first.removeFirst(); 00289 else if ( m_second.head() < m_first.head() ) 00290 m_second.removeFirst(); 00291 else break; // equal 00292 } 00293 if ( m_second.empty() ) m_first.setToEmpty(); 00294 else if ( m_first.empty() ) m_second.setToEmpty(); 00295 } 00296 m_valid = true; 00297 } 00298 00299 void removeFirst() { 00300 find(); 00301 m_first.removeFirst(); 00302 m_second.removeFirst(); 00303 m_valid = false; 00304 } 00305 00306 T head() const { 00307 find(); 00308 return m_first.head(); 00309 } 00310 00311 void setToEmpty() { 00312 m_first.setToEmpty(); 00313 m_second.setToEmpty(); 00314 } 00315 00316 bool operator<=( const IntersectionRange &f ) const { 00317 find(); 00318 f.find(); 00319 return m_first == f.m_first; 00320 } 00321 00322 protected: 00323 mutable Range< T > m_first, m_second; 00324 mutable bool m_valid:1; 00325 }; 00326 00327 template< typename R > 00328 IntersectionRange< typename R::ElementType > intersectionRange( R r1, R r2 ) { 00329 return IntersectionRange< typename R::ElementType >( r1, r2 ); 00330 } 00331 00332 template< typename R, typename Pred > 00333 struct FilteredRange : RangeMixin< typename R::ElementType, 00334 FilteredRange< R, Pred > > 00335 { 00336 typedef typename R::ElementType ElementType; 00337 // FilteredRange() {} 00338 FilteredRange( const R &r, Pred p ) : m_range( r ), m_current( r.begin() ), m_pred( p ), 00339 m_valid( false ) {} 00340 00341 void find() const { 00342 if (!m_valid) 00343 m_current = std::find_if( m_current, m_range.end(), pred() ); 00344 m_valid = true; 00345 } 00346 00347 void removeFirst() { 00348 find(); 00349 ++m_current; 00350 m_valid = false; 00351 } 00352 00353 ElementType head() const { 00354 find(); 00355 return *m_current; 00356 } 00357 00358 void setToEmpty() { 00359 m_current = m_range.end(); 00360 } 00361 00362 bool operator<=( const FilteredRange &f ) const { 00363 find(); 00364 f.find(); 00365 return m_current == f.m_current; 00366 // return m_pred == f.m_pred && m_range == f.m_range; 00367 } 00368 00369 protected: 00370 const Pred &pred() const { return m_pred; } 00371 R m_range; 00372 mutable typename R::iterator m_current; 00373 Pred m_pred; 00374 mutable bool m_valid:1; 00375 }; 00376 00377 template< typename R, typename Pred > 00378 FilteredRange< R, Pred > filteredRange( 00379 R r, Pred p ) { 00380 return FilteredRange< R, Pred >( r, p ); 00381 } 00382 00383 template< typename T > 00384 struct UniqueRange : RangeMixin< T, UniqueRange< T > > 00385 { 00386 UniqueRange() {} 00387 UniqueRange( Range< T > r ) : m_range( r ), m_valid( false ) {} 00388 00389 void find() const { 00390 if (!m_valid) 00391 while ( !m_range.empty() 00392 && !m_range.tail().empty() 00393 && m_range.head() == m_range.tail().head() ) 00394 m_range = m_range.tail(); 00395 m_valid = true; 00396 } 00397 00398 void removeFirst() { 00399 find(); 00400 m_range.removeFirst(); 00401 m_valid = false; 00402 } 00403 00404 T head() const { 00405 find(); 00406 return m_range.head(); 00407 } 00408 00409 void setToEmpty() { 00410 m_range.setToEmpty(); 00411 } 00412 00413 bool operator<=( const UniqueRange &r ) const { 00414 find(); 00415 r.find(); 00416 return m_range == r.m_range; 00417 } 00418 00419 protected: 00420 mutable Range< T > m_range; 00421 mutable bool m_valid:1; 00422 }; 00423 00424 template< typename R > 00425 UniqueRange< typename R::ElementType > uniqueRange( R r1 ) { 00426 return UniqueRange< typename R::ElementType >( r1 ); 00427 } 00428 00429 template< typename Transform > 00430 struct TransformedRange : RangeMixin< typename Transform::result_type, 00431 TransformedRange< Transform > > 00432 { 00433 typedef typename Transform::argument_type Source; 00434 typedef typename Transform::result_type Result; 00435 TransformedRange( Range< Source > r, Transform t ) 00436 : m_range( r ), m_transform( t ) {} 00437 00438 bool operator<=( const TransformedRange &o ) const { 00439 return m_range <= o.m_range; 00440 } 00441 00442 Result head() const { return m_transform( m_range.head() ); } 00443 void removeFirst() { m_range.removeFirst(); } 00444 void setToEmpty() { m_range.setToEmpty(); } 00445 00446 protected: 00447 Range< Source > m_range; 00448 Transform m_transform; 00449 }; 00450 00451 template< typename Trans > 00452 TransformedRange< Trans > transformedRange( 00453 Range< typename Trans::argument_type > r, Trans t ) { 00454 return TransformedRange< Trans >( r, t ); 00455 } 00456 00457 template< typename T, typename _Advance, typename _End > 00458 struct GeneratedRange : RangeMixin< T, GeneratedRange< T, _Advance, _End > > 00459 { 00460 typedef _Advance Advance; 00461 typedef _End End; 00462 00463 GeneratedRange() {} 00464 GeneratedRange( const T &t, const Advance &a, const End &e ) 00465 : m_current( t ), m_advance( a ), m_endPred( e ), m_end( false ) 00466 { 00467 } 00468 00469 void removeFirst() { 00470 m_advance( m_current ); 00471 } 00472 00473 void setToEmpty() { 00474 m_end = true; 00475 } 00476 00477 T head() const { return m_current; } 00478 00479 bool isEnd() const { return m_end || m_endPred( m_current ); } 00480 00481 bool operator<=( const GeneratedRange &r ) const { 00482 if ( isEnd() == r.isEnd() && !isEnd() ) 00483 return m_current <= r.m_current; 00484 return isEnd() <= r.isEnd(); 00485 } 00486 00487 protected: 00488 T m_current; 00489 Advance m_advance; 00490 End m_endPred; 00491 bool m_end; 00492 }; 00493 00494 template< typename T, typename A, typename E > 00495 GeneratedRange< T, A, E > generatedRange( T t, A a, E e ) 00496 { 00497 return GeneratedRange< T, A, E >( t, a, e ); 00498 } 00499 00500 } 00501 00502 #endif