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:
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 {
226  T head() const {
227  return static_cast< T >( m_casted.head() );
228  }
230 
231  bool operator<=( const CastedRange &r ) const {
232  return m_casted <= r.m_casted;
233  }
234 
235  void 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:
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() ); }
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:
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
-*- C++ -*-
-*- C++ -*-
Definition: amorph.h:17
Range< typename In::value_type > range(In b, In e)
Definition: range.h:264
GeneratedRange< T, A, E > generatedRange(T t, A a, E e)
Definition: range.h:494
IntersectionRange< typename R::ElementType > intersectionRange(R r1, R r2)
Definition: range.h:327
Range< T > upcastRange(C r)
Definition: range.h:252
TransformedRange< Trans > transformedRange(Range< typename Trans::argument_type > r, Trans t)
Definition: range.h:451
Iterator< typename I::value_type > iterator(I i)
Definition: iterator.h:123
Range< T > castedRange(C r)
Definition: range.h:246
FilteredRange< R, Pred > filteredRange(R r, Pred p)
Definition: range.h:377
UniqueRange< typename R::ElementType > uniqueRange(R r1)
Definition: range.h:424
Definition: amorph.h:272
const Interface * implementation() const
Definition: amorph.h:361
Definition: range.h:223
void setToEmpty()
Definition: range.h:235
void removeFirst()
Definition: range.h:229
CastedRange()
Definition: range.h:224
CastedRange(Range< Casted > r)
Definition: range.h:225
T head() const
Definition: range.h:226
Range< Casted > m_casted
Definition: range.h:240
bool operator<=(const CastedRange &r) const
Definition: range.h:231
Definition: consumer.h:67
Definition: range.h:334
void removeFirst()
Definition: range.h:346
bool operator<=(const FilteredRange &f) const
Definition: range.h:361
R m_range
Definition: range.h:370
R::iterator m_current
Definition: range.h:371
FilteredRange(const R &r, Pred p)
Definition: range.h:337
R::ElementType ElementType
Definition: range.h:335
const Pred & pred() const
Definition: range.h:369
bool m_valid
Definition: range.h:373
void find() const
Definition: range.h:340
Pred m_pred
Definition: range.h:372
void setToEmpty()
Definition: range.h:357
ElementType head() const
Definition: range.h:352
Definition: range.h:458
T m_current
Definition: range.h:487
Advance m_advance
Definition: range.h:488
bool isEnd() const
Definition: range.h:478
End m_endPred
Definition: range.h:489
GeneratedRange(const T &t, const Advance &a, const End &e)
Definition: range.h:463
bool operator<=(const GeneratedRange &r) const
Definition: range.h:480
T head() const
Definition: range.h:476
GeneratedRange()
Definition: range.h:462
_Advance Advance
Definition: range.h:459
bool m_end
Definition: range.h:490
void removeFirst()
Definition: range.h:468
_End End
Definition: range.h:460
void setToEmpty()
Definition: range.h:472
Definition: range.h:275
Range< T > m_second
Definition: range.h:322
bool m_valid
Definition: range.h:323
IntersectionRange(Range< T > r1, Range< T > r2)
Definition: range.h:277
Range< T > m_first
Definition: range.h:322
IntersectionRange()
Definition: range.h:276
void removeFirst()
Definition: range.h:298
bool operator<=(const IntersectionRange &f) const
Definition: range.h:315
void find() const
Definition: range.h:283
T head() const
Definition: range.h:305
void setToEmpty()
Definition: range.h:310
_T T
Definition: cast.h:26
Definition: iterator.h:58
Definition: range.h:192
IteratorRange(It c, It e)
Definition: range.h:196
void setToEmpty()
Definition: range.h:206
bool operator<=(const IteratorRange &r) const
Definition: range.h:202
Value head() const
Definition: range.h:199
It m_current
Definition: range.h:211
std::iterator_traits< It >::value_type Value
Definition: range.h:193
It m_end
Definition: range.h:211
void removeFirst()
Definition: range.h:200
IteratorRange()
Definition: range.h:195
Definition: amorph.h:144
const Wrapped & wrapped() const
Definition: amorph.h:181
Definition: range.h:93
virtual void removeFirst()=0
virtual ~RangeInterface()
Definition: range.h:97
virtual void setToEmpty()=0
virtual T head() const =0
Definition: range.h:29
const T * operator->() const
Definition: range.h:32
Proxy(T _x)
Definition: range.h:30
T x
Definition: range.h:31
Definition: range.h:26
std::forward_iterator_tag iterator_category
Definition: range.h:38
R m_range
Definition: range.h:56
T value_type
Definition: range.h:39
RangeIterator operator++(int)
Definition: range.h:51
T * pointer
Definition: range.h:41
bool operator<=(const RangeIterator &r) const
Definition: range.h:52
Proxy operator->() const
Definition: range.h:45
RangeIterator(const R &r)
Definition: range.h:36
R::ElementType current() const
Definition: range.h:49
R::ElementType T
Definition: range.h:27
RangeIterator()
Definition: range.h:35
R::ElementType operator*() const
Definition: range.h:48
RangeIterator next() const
Definition: range.h:47
ptrdiff_t difference_type
Definition: range.h:40
RangeIterator & operator++()
Definition: range.h:50
const T & const_reference
Definition: range.h:43
T & reference
Definition: range.h:42
Definition: range.h:62
bool empty() const
Definition: range.h:82
T head()
Definition: range.h:74
void output(Consumer< T > t) const
Definition: range.h:78
RangeIterator< Self > iterator
Definition: range.h:67
T ElementType
Definition: range.h:64
IteratorMixin< T, Self > Base
Definition: range.h:66
iterator begin() const
Definition: range.h:70
Self RangeImplementation
Definition: range.h:63
~RangeMixin()
Definition: range.h:86
iterator end() const
Definition: range.h:71
Self tail() const
Definition: range.h:75
Definition: range.h:102
W::RangeImplementation Wrapped
Definition: range.h:103
RangeMorph(const Wrapped &w)
Definition: range.h:104
virtual void removeFirst()
Definition: range.h:106
virtual void setToEmpty()
Definition: range.h:105
virtual T head() const
Definition: range.h:107
Definition: range.h:155
void removeFirst()
Definition: range.h:164
Range()
Definition: range.h:161
T head() const
Definition: range.h:163
Amorph< Range< T >, RangeInterface< T > > Super
Definition: range.h:156
Range(const C &i, typename IsType< int, typename C::RangeImplementation >::T fake=0)
Definition: range.h:159
void setToEmpty()
Definition: range.h:165
Definition: range.h:431
bool operator<=(const TransformedRange &o) const
Definition: range.h:437
void removeFirst()
Definition: range.h:442
Result head() const
Definition: range.h:441
Transform::result_type Result
Definition: range.h:433
TransformedRange(Range< Source > r, Transform t)
Definition: range.h:434
Transform m_transform
Definition: range.h:447
void setToEmpty()
Definition: range.h:443
Range< Source > m_range
Definition: range.h:446
Transform::argument_type Source
Definition: range.h:432
Definition: range.h:384
T head() const
Definition: range.h:403
Range< T > m_range
Definition: range.h:419
bool operator<=(const UniqueRange &r) const
Definition: range.h:412
void removeFirst()
Definition: range.h:397
UniqueRange(Range< T > r)
Definition: range.h:386
bool m_valid
Definition: range.h:420
UniqueRange()
Definition: range.h:385
void find() const
Definition: range.h:388
void setToEmpty()
Definition: range.h:408
Definition: mixin.h:13