wibble  0.1.28
range.h
Go to the documentation of this file.
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