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
18namespace wibble {
19
20template< typename _ > struct Range;
21template< typename _ > struct Consumer;
22
23// FOO: there was no test catching that we don't implement ->
24// auxilliary class, used as Range< T >::iterator
25template< typename R >
26struct RangeIterator : mixin::Comparable< RangeIterator< R > > {
27 typedef typename R::ElementType T;
28
29 struct Proxy {
30 Proxy( T _x ) : x( _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 }
55protected:
57};
58
59// the common functionality of all ranges
60template< typename T, typename 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
92template< typename T >
94 virtual T head() const = 0;
95 virtual void removeFirst() = 0;
96 virtual void setToEmpty() = 0;
97 virtual ~RangeInterface() {}
98};
99
100template< typename T, typename W >
101struct 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 */
152template< typename T >
153struct 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(); }
165 void setToEmpty() { this->implementation()->setToEmpty(); }
166
167 template< typename C > operator Range< C >();
168};
169
170/* template< typename R >
171Range< 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
180namespace 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()
188template< typename It >
189struct 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() {
208 }
209
210protected:
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
221template< typename T, typename Casted >
222struct 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
239protected:
241};
242
243// explicit range-cast... probably not very useful explicitly, just
244// use the casting operator of Range
245template< typename T, typename C >
248}
249
250// old-code-compat for castedRange... slightly silly
251template< typename T, typename C >
254}
255
256// the range-cast operator, see castedRange and CastedRange
257template< typename T > template< typename C >
259 return castedRange< C >( *this );
260}
261
262// range( iterator1, iterator2 ) -- see IteratorRange
263template< typename In >
265 return IteratorRange< In >( b, e );
266}
267
268template< typename C >
270 return range( c.begin(), c.end() );
271}
272
273template< typename T >
274struct 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
321protected:
323 mutable bool m_valid:1;
324};
325
326template< typename R >
329}
330
331template< typename R, typename Pred >
332struct 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
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
368protected:
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
376template< typename R, typename Pred >
378 R r, Pred p ) {
379 return FilteredRange< R, Pred >( r, p );
380}
381
382template< typename T >
383struct 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
418protected:
420 mutable bool m_valid:1;
421};
422
423template< typename R >
426}
427
428template< typename Transform >
429struct 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
445protected:
447 Transform m_transform;
448};
449
450template< typename Trans >
453 return TransformedRange< Trans >( r, t );
454}
455
456template< typename T, typename _Advance, typename _End >
457struct 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() {
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
486protected:
490 bool m_end;
491};
492
493template< 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
bool m_valid
Definition: range.h:373
const Pred & pred() const
Definition: range.h:369
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
std::iterator_traits< It >::value_type Value
Definition: range.h:193
bool operator<=(const IteratorRange &r) const
Definition: range.h:202
Value head() const
Definition: range.h:199
It m_current
Definition: range.h:211
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
Proxy(T _x)
Definition: range.h:30
T x
Definition: range.h:31
const T * operator->() const
Definition: range.h:32
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
RangeIterator & operator++()
Definition: range.h:50
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
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
const Self & self() const
Definition: range.h:65
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