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