00001
00006 #include <iostream>
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
00025
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
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() ); }
00072 iterator end() const { Self e( this->self() ); e.setToEmpty(); return iterator( e ); }
00073
00074
00075 T head() { return self().head(); }
00076 Self tail() const { Self e( this->self() ); e.removeFirst(); return e; }
00077
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
00091
00092
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
00112
00113
00114
00115
00116
00117
00118
00119
00120
00121
00122
00123
00124
00125
00126
00127
00128
00129
00130
00131
00132
00133
00134
00135
00136
00137
00138
00139
00140
00141
00142
00143
00144
00145
00146
00147
00148
00149
00150
00151
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
00172
00173
00174
00175
00176 }
00177
00178
00179 #include <wibble/consumer.h>
00180
00181 namespace wibble {
00182
00183
00184
00185
00186
00187
00188
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
00216
00217
00218
00219
00220
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
00245
00246 template< typename T, typename C >
00247 Range< T > castedRange( C r ) {
00248 return CastedRange< T, typename C::ElementType >( r );
00249 }
00250
00251
00252 template< typename T, typename C >
00253 Range< T > upcastRange( C r ) {
00254 return CastedRange< T, typename C::ElementType >( r );
00255 }
00256
00257
00258 template< typename T > template< typename C >
00259 Range< T >::operator Range< C >() {
00260 return castedRange< C >( *this );
00261 }
00262
00263
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;
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
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
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