wibble  1.1
range.h
Go to the documentation of this file.
1 
6 #include <iostream> // for noise
7 #include <iterator>
8 #include <vector>
9 #include <set>
10 #include <algorithm>
11 
12 #include <wibble/iterator.h>
13 #include <wibble/exception.h>
14 
15 #ifndef WIBBLE_RANGE_H
16 #define WIBBLE_RANGE_H
17 
18 namespace wibble {
19 
20 template< typename _ > struct Range;
21 template< typename _ > struct Consumer;
22 
23 // FOO: there was no test catching that we don't implement ->
24 // auxilliary class, used as Range< T >::iterator
25 template< typename R >
26 struct RangeIterator : mixin::Comparable< RangeIterator< R > > {
27  typedef typename R::ElementType T;
28 
29  struct Proxy {
30  Proxy( T _x ) : x( _x ) {}
31  T x;
32  const T *operator->() const { return &x; }
33  };
34 
36  RangeIterator( const R &r ) : m_range( r ) {}
37 
38  typedef std::forward_iterator_tag iterator_category;
39  typedef T value_type;
40  typedef ptrdiff_t difference_type;
41  typedef T *pointer;
42  typedef T &reference;
43  typedef const T &const_reference;
44 
45  Proxy operator->() const { return Proxy( *(*this) ); }
46 
47  RangeIterator next() const { RangeIterator n( *this ); ++n; return n; }
48  typename R::ElementType operator*() const { return m_range.head(); }
49  typename R::ElementType current() const { return *(*this); }
50  RangeIterator &operator++() { m_range.removeFirst(); return *this; }
51  RangeIterator operator++(int) { return m_range.removeFirst(); }
52  bool operator<=( const RangeIterator &r ) const {
53  return m_range.operator<=( r.m_range );
54  }
55 protected:
57 };
58 
59 // the common functionality of all ranges
60 template< typename T, typename Self >
61 struct RangeMixin : mixin::Comparable< Self >
62 {
63  typedef Self RangeImplementation;
64  typedef T ElementType;
65  const Self &self() const { return *static_cast< const Self * >( this ); }
68  friend struct RangeIterator< Self >;
69 
70  iterator begin() const { return iterator( this->self() ); } // STL-style iteration
71  iterator end() const { Self e( this->self() ); e.setToEmpty(); return iterator( e ); }
72 
73  // range terminology
74  T head() { return self().head(); }
75  Self tail() const { Self e( this->self() ); e.removeFirst(); return e; }
76  // Self &tail() { return self().tail(); }
77 
78  void output( Consumer< T > t ) const {
79  std::copy( begin(), end(), t );
80  }
81 
82  bool empty() const {
83  return begin() == end();
84  }
85 
87 };
88 
89 // interface to be implemented by all range implementations
90 // refinement of IteratorInterface (see iterator.h)
91 // see also amorph.h on how the Morph/Amorph classes are designed
92 template< typename T >
94  virtual T head() const = 0;
95  virtual void removeFirst() = 0;
96  virtual void setToEmpty() = 0;
97  virtual ~RangeInterface() {}
98 };
99 
100 template< typename T, typename W >
101 struct RangeMorph: Morph< RangeMorph< T, W >, W, RangeInterface< T > >
102 {
103  typedef typename W::RangeImplementation Wrapped;
104  RangeMorph( const Wrapped &w ) : Morph< RangeMorph, Wrapped, RangeInterface< T > >( w ) {}
105  virtual void setToEmpty() { this->wrapped().setToEmpty(); }
106  virtual void removeFirst() { this->wrapped().removeFirst(); }
107  virtual T head() const { return this->wrapped().head(); }
108 };
109 
110 // the Amorph of Ranges... if you still didn't check amorph.h, go and
111 // do it... unless you don't care in which case i am not sure why you
112 // are reading this anyway
113 
114 /*
115  Range< T > (and all its Morphs (implementations) alike) work as an
116  iterable, immutable range of items -- in a way like STL
117  const_begin(), const_end() pair of iterators. However, Range packs
118  these two in a single object, which you can then pass as a single
119  argument or return as a value. There are many Range implementations,
120  some of them use STL containers (or just a pair of iterators) as
121  backing (IteratorRange, BackedRange), some use other ranges.
122 
123  The latter are slightly more interesting, since they provide an
124  "adapted" view on the underlying range(s). See FilteredRange,
125  TransformedRange, UniqueRange, CastedRange , IntersectionRange.
126 
127  GeneratedRange has no "real" backing at all, but use a pair of
128  functors and "generates" (by calling those functors) the complete
129  range as it is iterated.
130 
131  Example usage:
132 
133  // create a range from a pair of STL iterators
134  Range< int > i = range( myIntVector.begin(), myIntVector.end() );
135  // create a range that is filtered view of another range
136  Range< int > j = filteredRange( i, predicate );
137  std::vector< int > vec;
138  // copy out items in j into vec; see also consumer.h
139  j.output( consumer( vec ) );
140  // vec now contains all items from i (and thus myIntVector) that
141  // match 'predicate'
142 
143  You don't have to use Range< int > all the time, since it's fairly
144  inefficient (adding level of indirection). However in common cases
145  it is ok. In the uncommon cases you can use the specific
146  implementation type and there you won't suffer the indirection
147  penalty. You can also write generic functions that have type of
148  range as their template parameter and these will work more
149  efficiently if Morph is used directly and less efficiently when the
150  Amorph Range is used instead.
151  */
152 template< typename T >
153 struct Range : Amorph< Range< T >, RangeInterface< T > >,
154  RangeMixin< T, Range< T > >
155 {
157 
158  template< typename C >
160  : Super( RangeMorph< T, C >( i ) ) { (void)fake; }
161  Range() {}
162 
163  T head() const { return this->implementation()->head(); }
164  void removeFirst() { this->implementation()->removeFirst(); }
165  void setToEmpty() { this->implementation()->setToEmpty(); }
166 
167  template< typename C > operator Range< C >();
168 };
169 
170 /* template< typename R >
171 Range< typename R::ElementType > rangeMorph( R r ) {
172  return Range< typename R::ElementType > uRangeMorph< typename R::ElementType, R >( r );
173  } */
174 
175 }
176 
177 // ----- individual range implementations follow
178 #include <wibble/consumer.h>
179 
180 namespace wibble {
181 
182 // a simple pair of iterators -- suffers the same invalidation
183 // semantics as normal STL iterators and also same problems when the
184 // backing storage goes out of scope
185 
186 // this is what you get when using range( iterator1, iterator2 )
187 // see also range()
188 template< typename It >
189 struct IteratorRange : public RangeMixin<
190  typename std::iterator_traits< It >::value_type,
191  IteratorRange< It > >
192 {
193  typedef typename std::iterator_traits< It >::value_type Value;
194 
196  IteratorRange( It c, It e )
197  : m_current( c ), m_end( e ) {}
198 
199  Value head() const { return *m_current; }
200  void removeFirst() { ++m_current; }
201 
202  bool operator<=( const IteratorRange &r ) const {
203  return r.m_current == m_current && r.m_end == m_end;
204  }
205 
206  void setToEmpty() {
207  m_current = m_end;
208  }
209 
210 protected:
211  It m_current, m_end;
212 };
213 
214 // first in the series of ranges that use another range as backing
215 // this one just does static_cast to specified type on all the
216 // returned elements
217 
218 // this is what you get when casting Range< S > to Range< T > and S is
219 // static_cast-able to T
220 
221 template< typename T, typename Casted >
222 struct CastedRange : public RangeMixin< T, CastedRange< T, Casted > >
223 {
225  CastedRange( Range< Casted > r ) : m_casted( r ) {}
226  T head() const {
227  return static_cast< T >( m_casted.head() );
228  }
229  void removeFirst() { m_casted.removeFirst(); }
230 
231  bool operator<=( const CastedRange &r ) const {
232  return m_casted <= r.m_casted;
233  }
234 
235  void setToEmpty() {
236  m_casted.setToEmpty();
237  }
238 
239 protected:
241 };
242 
243 // explicit range-cast... probably not very useful explicitly, just
244 // use the casting operator of Range
245 template< typename T, typename C >
248 }
249 
250 // old-code-compat for castedRange... slightly silly
251 template< typename T, typename C >
254 }
255 
256 // the range-cast operator, see castedRange and CastedRange
257 template< typename T > template< typename C >
259  return castedRange< C >( *this );
260 }
261 
262 // range( iterator1, iterator2 ) -- see IteratorRange
263 template< typename In >
265  return IteratorRange< In >( b, e );
266 }
267 
268 template< typename C >
270  return range( c.begin(), c.end() );
271 }
272 
273 template< typename T >
274 struct IntersectionRange : RangeMixin< T, IntersectionRange< T > >
275 {
278  : m_first( r1 ), m_second( r2 ),
279  m_valid( false )
280  {
281  }
282 
283  void find() const {
284  if (!m_valid) {
285  while ( !m_first.empty() && !m_second.empty() ) {
286  if ( m_first.head() < m_second.head() )
287  m_first.removeFirst();
288  else if ( m_second.head() < m_first.head() )
289  m_second.removeFirst();
290  else break; // equal
291  }
292  if ( m_second.empty() ) m_first.setToEmpty();
293  else if ( m_first.empty() ) m_second.setToEmpty();
294  }
295  m_valid = true;
296  }
297 
298  void removeFirst() {
299  find();
300  m_first.removeFirst();
301  m_second.removeFirst();
302  m_valid = false;
303  }
304 
305  T head() const {
306  find();
307  return m_first.head();
308  }
309 
310  void setToEmpty() {
311  m_first.setToEmpty();
312  m_second.setToEmpty();
313  }
314 
315  bool operator<=( const IntersectionRange &f ) const {
316  find();
317  f.find();
318  return m_first == f.m_first;
319  }
320 
321 protected:
322  mutable Range< T > m_first, m_second;
323  mutable bool m_valid:1;
324 };
325 
326 template< typename R >
329 }
330 
331 template< typename R, typename Pred >
332 struct FilteredRange : RangeMixin< typename R::ElementType,
333  FilteredRange< R, Pred > >
334 {
335  typedef typename R::ElementType ElementType;
336  // FilteredRange() {}
337  FilteredRange( const R &r, Pred p ) : m_range( r ), m_current( r.begin() ), m_pred( p ),
338  m_valid( false ) {}
339 
340  void find() const {
341  if (!m_valid)
342  m_current = std::find_if( m_current, m_range.end(), pred() );
343  m_valid = true;
344  }
345 
346  void removeFirst() {
347  find();
348  ++m_current;
349  m_valid = false;
350  }
351 
352  ElementType head() const {
353  find();
354  return *m_current;
355  }
356 
357  void setToEmpty() {
358  m_current = m_range.end();
359  }
360 
361  bool operator<=( const FilteredRange &f ) const {
362  find();
363  f.find();
364  return m_current == f.m_current;
365  // return m_pred == f.m_pred && m_range == f.m_range;
366  }
367 
368 protected:
369  const Pred &pred() const { return m_pred; }
371  mutable typename R::iterator m_current;
372  Pred m_pred;
373  mutable bool m_valid:1;
374 };
375 
376 template< typename R, typename Pred >
378  R r, Pred p ) {
379  return FilteredRange< R, Pred >( r, p );
380 }
381 
382 template< typename T >
383 struct UniqueRange : RangeMixin< T, UniqueRange< T > >
384 {
386  UniqueRange( Range< T > r ) : m_range( r ), m_valid( false ) {}
387 
388  void find() const {
389  if (!m_valid)
390  while ( !m_range.empty()
391  && !m_range.tail().empty()
392  && m_range.head() == m_range.tail().head() )
393  m_range = m_range.tail();
394  m_valid = true;
395  }
396 
397  void removeFirst() {
398  find();
399  m_range.removeFirst();
400  m_valid = false;
401  }
402 
403  T head() const {
404  find();
405  return m_range.head();
406  }
407 
408  void setToEmpty() {
409  m_range.setToEmpty();
410  }
411 
412  bool operator<=( const UniqueRange &r ) const {
413  find();
414  r.find();
415  return m_range == r.m_range;
416  }
417 
418 protected:
420  mutable bool m_valid:1;
421 };
422 
423 template< typename R >
426 }
427 
428 template< typename Transform >
429 struct TransformedRange : RangeMixin< typename Transform::result_type,
430  TransformedRange< Transform > >
431 {
432  typedef typename Transform::argument_type Source;
433  typedef typename Transform::result_type Result;
435  : m_range( r ), m_transform( t ) {}
436 
437  bool operator<=( const TransformedRange &o ) const {
438  return m_range <= o.m_range;
439  }
440 
441  Result head() const { return m_transform( m_range.head() ); }
442  void removeFirst() { m_range.removeFirst(); }
443  void setToEmpty() { m_range.setToEmpty(); }
444 
445 protected:
447  Transform m_transform;
448 };
449 
450 template< typename Trans >
453  return TransformedRange< Trans >( r, t );
454 }
455 
456 template< typename T, typename _Advance, typename _End >
457 struct GeneratedRange : RangeMixin< T, GeneratedRange< T, _Advance, _End > >
458 {
459  typedef _Advance Advance;
460  typedef _End End;
461 
463  GeneratedRange( const T &t, const Advance &a, const End &e )
464  : m_current( t ), m_advance( a ), m_endPred( e ), m_end( false )
465  {
466  }
467 
468  void removeFirst() {
469  m_advance( m_current );
470  }
471 
472  void setToEmpty() {
473  m_end = true;
474  }
475 
476  T head() const { return m_current; }
477 
478  bool isEnd() const { return m_end || m_endPred( m_current ); }
479 
480  bool operator<=( const GeneratedRange &r ) const {
481  if ( isEnd() == r.isEnd() && !isEnd() )
482  return m_current <= r.m_current;
483  return isEnd() <= r.isEnd();
484  }
485 
486 protected:
488  Advance m_advance;
490  bool m_end;
491 };
492 
493 template< typename T, typename A, typename E >
495 {
496  return GeneratedRange< T, A, E >( t, a, e );
497 }
498 
499 }
500 
501 #endif
virtual ~RangeInterface()
Definition: range.h:97
bool operator<=(const GeneratedRange &r) const
Definition: range.h:480
void setToEmpty()
Definition: range.h:310
void find() const
Definition: range.h:388
CastedRange(Range< Casted > r)
Definition: range.h:225
W::RangeImplementation Wrapped
Definition: range.h:103
Value head() const
Definition: range.h:199
Iterator< typename I::value_type > iterator(I i)
Definition: iterator.h:123
TransformedRange< Trans > transformedRange(Range< typename Trans::argument_type > r, Trans t)
Definition: range.h:451
Definition: range.h:274
bool operator<=(const IntersectionRange &f) const
Definition: range.h:315
R::ElementType operator*() const
Definition: range.h:48
Range(const C &i, typename IsType< int, typename C::RangeImplementation >::T fake=0)
Definition: range.h:159
Advance m_advance
Definition: range.h:488
R::iterator m_current
Definition: range.h:371
void setToEmpty()
Definition: range.h:357
R::ElementType ElementType
Definition: range.h:335
bool operator<=(const UniqueRange &r) const
Definition: range.h:412
const T * operator->() const
Definition: range.h:32
void find() const
Definition: range.h:283
RangeIterator()
Definition: range.h:35
~RangeMixin()
Definition: range.h:86
_T T
Definition: cast.h:26
T head() const
Definition: range.h:476
const Pred & pred() const
Definition: range.h:369
Range< typename In::value_type > range(In b, In e)
Definition: range.h:264
T head()
Definition: range.h:74
FilteredRange< R, Pred > filteredRange(R r, Pred p)
Definition: range.h:377
iterator end() const
Definition: range.h:71
_Advance Advance
Definition: range.h:459
Range< Source > m_range
Definition: range.h:446
bool m_valid
Definition: range.h:323
It m_current
Definition: range.h:211
UniqueRange< typename R::ElementType > uniqueRange(R r1)
Definition: range.h:424
void removeFirst()
Definition: range.h:200
T value_type
Definition: range.h:39
Definition: range.h:332
RangeIterator(const R &r)
Definition: range.h:36
T m_current
Definition: range.h:487
R m_range
Definition: range.h:56
_End End
Definition: range.h:460
Definition: range.h:429
Range< Casted > m_casted
Definition: range.h:240
End m_endPred
Definition: range.h:489
Definition: range.h:222
IntersectionRange< typename R::ElementType > intersectionRange(R r1, R r2)
Definition: range.h:327
bool operator<=(const TransformedRange &o) const
Definition: range.h:437
void removeFirst()
Definition: range.h:298
bool operator<=(const FilteredRange &f) const
Definition: range.h:361
T head() const
Definition: range.h:403
Definition: range.h:189
Definition: range.h:101
const T & const_reference
Definition: range.h:43
ListIterator< List > begin(List l)
Definition: list.h:420
Definition: range.h:26
IntersectionRange(Range< T > r1, Range< T > r2)
Definition: range.h:277
T & reference
Definition: range.h:42
void setToEmpty()
Definition: range.h:472
Definition: range.h:29
Definition: range.h:383
bool m_valid
Definition: range.h:373
Definition: amorph.h:272
bool operator<=(const IteratorRange &r) const
Definition: range.h:202
T x
Definition: range.h:31
void output(Consumer< T > t) const
Definition: range.h:78
T ElementType
Definition: range.h:64
std::forward_iterator_tag iterator_category
Definition: range.h:38
ElementType head() const
Definition: range.h:352
T head() const
Definition: range.h:226
Range< T > m_first
Definition: range.h:322
Definition: iterator.h:57
Range< T > m_second
Definition: range.h:322
IntersectionRange()
Definition: range.h:276
FilteredRange(const R &r, Pred p)
Definition: range.h:337
Proxy operator->() const
Definition: range.h:45
void removeFirst()
Definition: range.h:442
iterator begin() const
Definition: range.h:70
virtual T head() const
Definition: range.h:107
virtual void removeFirst()
Definition: range.h:106
Definition: range.h:61
Range< T > m_range
Definition: range.h:419
R::ElementType current() const
Definition: range.h:49
GeneratedRange(const T &t, const Advance &a, const End &e)
Definition: range.h:463
void setToEmpty()
Definition: range.h:206
IteratorRange()
Definition: range.h:195
Transform m_transform
Definition: range.h:447
CastedRange()
Definition: range.h:224
UniqueRange()
Definition: range.h:385
Definition: range.h:93
Range< T > castedRange(C r)
Definition: range.h:246
bool isEnd() const
Definition: range.h:478
TransformedRange(Range< Source > r, Transform t)
Definition: range.h:434
void removeFirst()
Definition: range.h:164
T head() const
Definition: range.h:163
Definition: mixin.h:13
void setToEmpty()
Definition: range.h:235
R::ElementType T
Definition: range.h:27
R m_range
Definition: range.h:370
bool m_end
Definition: range.h:490
Pred m_pred
Definition: range.h:372
RangeIterator operator++(int)
Definition: range.h:51
Transform::result_type Result
Definition: range.h:433
IteratorRange(It c, It e)
Definition: range.h:196
-*- C++ -*-
T * pointer
Definition: range.h:41
void removeFirst()
Definition: range.h:468
T head() const
Definition: range.h:305
bool m_valid
Definition: range.h:420
void removeFirst()
Definition: range.h:397
IteratorMixin< T, Self > Base
Definition: range.h:66
Range()
Definition: range.h:161
RangeIterator next() const
Definition: range.h:47
ptrdiff_t difference_type
Definition: range.h:40
Result head() const
Definition: range.h:441
Definition: amorph.h:17
virtual void setToEmpty()
Definition: range.h:105
Proxy(T _x)
Definition: range.h:30
Definition: range.h:20
UniqueRange(Range< T > r)
Definition: range.h:386
void removeFirst()
Definition: range.h:346
void setToEmpty()
Definition: range.h:443
Self RangeImplementation
Definition: range.h:63
Range< T > upcastRange(C r)
Definition: range.h:252
-*- C++ -*-
It m_end
Definition: range.h:211
bool operator<=(const CastedRange &r) const
Definition: range.h:231
bool empty() const
Definition: range.h:82
Definition: consumer.h:17
RangeIterator< Self > iterator
Definition: range.h:67
Definition: amorph.h:141
std::iterator_traits< It >::value_type Value
Definition: range.h:193
Definition: range.h:457
Self tail() const
Definition: range.h:75
RangeIterator & operator++()
Definition: range.h:50
ListIterator< List > end(List)
Definition: list.h:425
Amorph< Range< T >, RangeInterface< T > > Super
Definition: range.h:156
RangeMorph(const Wrapped &w)
Definition: range.h:104
void setToEmpty()
Definition: range.h:408
bool operator<=(const RangeIterator &r) const
Definition: range.h:52
Transform::argument_type Source
Definition: range.h:432
GeneratedRange()
Definition: range.h:462
void removeFirst()
Definition: range.h:229
void find() const
Definition: range.h:340
GeneratedRange< T, A, E > generatedRange(T t, A a, E e)
Definition: range.h:494
void setToEmpty()
Definition: range.h:165