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() )
288  else if ( m_second.head() < m_first.head() )
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();
302  m_valid = false;
303  }
304 
305  T head() const {
306  find();
307  return m_first.head();
308  }
309 
310  void 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();
400  m_valid = false;
401  }
402 
403  T head() const {
404  find();
405  return m_range.head();
406  }
407 
408  void 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