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;
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{
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;
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(); }
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 >
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
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 >
249
250// old-code-compat for castedRange... slightly silly
251template< typename T, typename C >
255
256// the range-cast operator, see castedRange and CastedRange
257template< typename T > template< typename C >
261
262// range( iterator1, iterator2 ) -- see IteratorRange
263template< typename In >
267
268template< typename C >
270 return range( c.begin(), c.end() );
271}
272
273template< typename T >
274struct IntersectionRange : RangeMixin< T, IntersectionRange< T > >
275{
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 >
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;
373 mutable bool m_valid:1;
374};
375
376template< typename R, typename Pred >
381
382template< typename T >
383struct UniqueRange : RangeMixin< T, UniqueRange< T > >
384{
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 >
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;
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:
448};
449
450template< typename Trans >
455
456template< typename T, typename _Advance, typename _End >
457struct GeneratedRange : RangeMixin< T, GeneratedRange< T, _Advance, _End > >
458{
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 >
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
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 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
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 amorph.h:30
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