wibble  1.1
list.h
Go to the documentation of this file.
1 // -*- C++ -*-
2 #include <memory>
3 #include <vector>
4 #include <iterator>
5 #include <algorithm>
6 #include <cstddef>
7 
8 #ifndef WIBBLE_LIST_H
9 #define WIBBLE_LIST_H
10 
11 namespace wibble {
12 namespace list {
13 
14 template< typename List >
16 {
17  typedef std::forward_iterator_tag iterator_category;
18  typedef typename List::Type value_type;
19  typedef ptrdiff_t difference_type;
20  typedef value_type &pointer;
21  typedef value_type &reference;
22 
23  List l;
24 
26  l = l.tail();
27  return *this;
28  }
29 
31  ListIterator i = *this;
32  operator++();
33  return i;
34  }
35 
36  typename List::Type operator*() {
37  return l.head();
38  }
39 
40  bool operator==( const ListIterator &o ) const {
41  return l.empty() && o.l.empty();
42  }
43 
44  bool operator!=( const ListIterator &o ) const {
45  return !(l.empty() && o.l.empty());
46  }
47 
48  ListIterator( List _l = List() ) : l( _l )
49  {}
50 
51 };
52 
53 template< typename List >
54 struct Sorted
55 {
56  typedef std::vector< typename List::Type > Vec;
57  struct SharedVec {
58  int refs;
59  Vec vec;
60  SharedVec() : refs( 1 ) {}
61  void _ref() { ++refs; }
62  void _deref() { --refs; }
63  };
64 
65  struct SharedPtr {
67  SharedPtr( bool a = false ) { vec = a ? new SharedVec : 0; }
68 
69  SharedPtr( const SharedPtr &o ) {
70  vec = o.vec;
71  if ( vec )
72  vec->_ref();
73  }
74 
75  SharedPtr &operator=( const SharedPtr &o ) {
76  vec = o.vec;
77  if ( vec )
78  vec->_ref();
79  return *this;
80  }
81 
82  operator bool() { return vec; }
83  Vec &operator*() { return vec->vec; }
84  Vec *operator->() { return &(vec->vec); }
85 
87  if ( vec ) {
88  vec->_deref();
89  if ( !vec->refs )
90  delete vec;
91  }
92  }
93  };
94 
95  typedef typename List::Type Type;
96  List m_list;
98  size_t m_pos;
99 
100  void sort() const {
101  if ( m_sorted )
102  return;
103  m_sorted = SharedPtr( true );
104  std::copy( ListIterator< List >( m_list ), ListIterator< List >(),
105  std::back_inserter( *m_sorted ) );
106  std::sort( m_sorted->begin(), m_sorted->end() );
107  }
108 
109  Type head() const {
110  sort();
111  return (*m_sorted)[ m_pos ];
112  }
113 
114  Sorted tail() const {
115  sort();
116  Sorted s = *this;
117  s.m_pos ++;
118  return s;
119  }
120 
121  bool empty() const {
122  sort();
123  return m_pos == m_sorted->size();
124  }
125 
126  Sorted( const Sorted &o ) : m_list( o.m_list ), m_sorted( o.m_sorted ),
127  m_pos( o.m_pos ) {}
128 
129  Sorted &operator=( const Sorted &o ) {
130  m_sorted = o.m_sorted;
131  m_list = o.m_list;
132  m_pos = o.m_pos;
133  return *this;
134  }
135 
136  Sorted( List l = List() ) : m_list( l ), m_sorted( 0 ), m_pos( 0 ) {}
137 };
138 
139 template< typename List, typename Predicate >
140 struct Filtered
141 {
142  typedef typename List::Type Type;
143  mutable List m_list;
144  Predicate m_pred;
145 
146  bool empty() const {
147  seek();
148  return m_list.empty();
149  }
150 
151  Type head() const {
152  seek();
153  return m_list.head();
154  }
155 
156  void seek() const
157  {
158  while ( !m_list.empty() && !m_pred( m_list.head() ) )
159  m_list = m_list.tail();
160  }
161 
162  Filtered tail() const
163  {
164  Filtered r = *this;
165  r.seek();
166  r.m_list = r.m_list.tail();
167  return r;
168  }
169 
170  Filtered( List l, Predicate p )
171  : m_list( l ), m_pred( p )
172  {
173  }
174 
175  Filtered() {}
176 };
177 
178 template< typename List >
179 struct Unique
180 {
181  typedef typename List::Type Type;
182  mutable List m_list;
183 
184  bool empty() const {
185  seek();
186  return m_list.empty();
187  }
188 
189  Type head() const {
190  seek();
191  return m_list.head();
192  }
193 
194  void seek() const
195  {
196  if ( m_list.empty() )
197  return;
198  if ( m_list.tail().empty() )
199  return;
200  if ( m_list.head() == m_list.tail().head() ) {
201  m_list = m_list.tail();
202  return seek();
203  }
204  }
205 
206  Unique tail() const
207  {
208  Unique r = *this;
209  r.seek();
210  r.m_list = r.m_list.tail();
211  return r;
212  }
213 
214  Unique( List l = List() )
215  : m_list( l )
216  {
217  }
218 };
219 
220 template< typename List >
221 struct Take {
222  List l;
224 
225  typedef typename List::Type Type;
226 
227  Type head() const {
228  return l.head();
229  }
230 
231  bool empty() const {
232  return l.empty() || remaining == 0;
233  }
234 
235  Take tail() const {
236  Take t;
237  t.remaining = remaining - 1;
238  t.l = l.tail();
239  return t;
240  }
241 
242  Take( List _l, int m ) : l( _l ), remaining( m ) {}
243  Take() : remaining( 0 ) {}
244 };
245 
246 template< typename List, typename F >
247 struct Map {
248  List l;
249 
250  char f_space[ sizeof( F ) ];
251  F &f() {
252  return *static_cast<F *>(f_space);
253  }
254  const F &f() const {
255  return *static_cast<const F *>(f_space);
256  }
257 
258  typedef typename F::result_type Type;
259 
260  Type head() const {
261  return f()( l.head() );
262  }
263 
264  Map tail() const {
265  Map m;
266  m.l = l.tail();
267  m.f() = f();
268  return m;
269  }
270 
271  bool empty() const {
272  return l.empty();
273  }
274 
275  Map() {}
276  Map( const List &_l, const F &_f )
277  : l( _l )
278  {
279  f() = _f;
280  }
281 };
282 
283 template< typename T >
284 struct Empty {
285  typedef T Type;
286  T head() const { return T(); }
287  bool empty() const { return true; }
288  Empty tail() const { return Empty(); }
289 };
290 
291 template< typename T >
292 struct Singular {
293  typedef T Type;
295  bool m_empty;
296 
297  Singular() : m_empty( true ) {}
298  Singular( T i ) : m_value( i ), m_empty( false ) {}
299  T head() const { return m_value; }
300  bool empty() const { return m_empty; }
301  Singular tail() const { return Singular(); }
302 };
303 
304 template< typename T1, typename T2 >
305 struct Append {
306  typedef typename T1::Type Type;
307  T1 m_1;
308  T2 m_2;
309 
310  Append() {}
311  Append( T1 a, T2 b ) : m_1( a ), m_2( b ) {}
312  Type head() const {
313  if ( m_1.empty() )
314  return m_2.head();
315  return m_1.head();
316  }
317 
318  bool empty() const { return m_1.empty() && m_2.empty(); }
319  Append tail() const {
320  Append t = *this;
321  if ( !t.m_1.empty() )
322  t.m_1 = t.m_1.tail();
323  else
324  t.m_2 = t.m_2.tail();
325  return t;
326  }
327 
328 };
329 
330 template< typename X >
331 Singular< X > singular( const X &x ) {
332  return Singular< X >( x );
333 }
334 
335 template< typename X, typename Y >
336 Append< X, Y > append( const X &x, const Y &y ) {
337  return Append< X, Y >( x, y );
338 }
339 
340 template< typename List >
341 size_t count( List l ) {
342  size_t count = 0;
343  while ( !l.empty() ) {
344  l = l.tail();
345  ++ count;
346  }
347  return count;
348 }
349 
350 #undef foreach // Work around Qt braindamage.
351 
352 template< typename List, typename F >
353 void foreach( List l, F f ) {
354  while ( !l.empty() ) {
355  f( l.head() );
356  l = l.tail();
357  }
358 }
359 
360 template< typename List, template< typename > class F >
361 void foreach( List l, F< typename List::Type > f ) {
362  while ( !l.empty() ) {
363  f( l.head() );
364  l = l.tail();
365  }
366 }
367 
368 template< typename List, typename Pred >
370 {
371  return Filtered< List, Pred >( l, p );
372 }
373 
374 template< typename List, template< typename > class Pred >
375 Filtered< List, Pred< List > > filter( List l, Pred< List > p )
376 {
377  return Filtered< List, Pred< List > >( l, p );
378 }
379 
380 template< typename List, typename F >
381 Map< List, F > map( const List &l, const F &f )
382 {
383  return Map< List, F >( l, f );
384 }
385 
386 template< typename List >
388 {
389  return Sorted< List >( l );
390 }
391 
392 template< typename List >
394 {
395  return Unique< List >( l );
396 }
397 
398 template< typename List >
399 Take< List > take( int t, List l )
400 {
401  return Take< List >( l, t );
402 }
403 
404 template< typename List >
405 List drop( int t, List l )
406 {
407  while ( t > 0 ) {
408  l = l.tail();
409  -- t;
410  }
411  return l;
412 }
413 
414 template< typename List, typename Out >
415 void output( List l, Out it ) {
416  std::copy( ListIterator< List >( l ), ListIterator< List >(), it );
417 }
418 
419 template< typename List >
421  return ListIterator< List >( l );
422 }
423 
424 template< typename List >
426  return ListIterator< List >();
427 }
428 
429 }
430 }
431 
432 #endif
Definition: list.h:15
int refs
Definition: list.h:58
List l
Definition: list.h:248
List m_list
Definition: list.h:96
Unique(List l=List())
Definition: list.h:214
Type head() const
Definition: list.h:189
Singular(T i)
Definition: list.h:298
Filtered()
Definition: list.h:175
Sorted(List l=List())
Definition: list.h:136
SharedVec * vec
Definition: list.h:66
Definition: list.h:292
SharedVec()
Definition: list.h:60
Take tail() const
Definition: list.h:235
int remaining
Definition: list.h:223
List::Type Type
Definition: list.h:142
Take< List > take(int t, List l)
Definition: list.h:399
size_t m_pos
Definition: list.h:98
List l
Definition: list.h:222
Definition: list.h:54
ListIterator(List _l=List())
Definition: list.h:48
F::result_type Type
Definition: list.h:258
Filtered tail() const
Definition: list.h:162
bool m_empty
Definition: list.h:295
SharedPtr & operator=(const SharedPtr &o)
Definition: list.h:75
List::Type Type
Definition: list.h:181
List drop(int t, List l)
Definition: list.h:405
Definition: list.h:305
Take()
Definition: list.h:243
bool operator==(const ListIterator &o) const
Definition: list.h:40
Vec vec
Definition: list.h:59
Sorted tail() const
Definition: list.h:114
List m_list
Definition: list.h:182
T Type
Definition: list.h:293
bool empty() const
Definition: list.h:121
Definition: list.h:140
T1 m_1
Definition: list.h:307
Append tail() const
Definition: list.h:319
Take(List _l, int m)
Definition: list.h:242
ListIterator< List > begin(List l)
Definition: list.h:420
~SharedPtr()
Definition: list.h:86
Type head() const
Definition: list.h:312
T head() const
Definition: list.h:299
Append< X, Y > append(const X &x, const Y &y)
Definition: list.h:336
List::Type Type
Definition: list.h:95
Vec * operator->()
Definition: list.h:84
T1::Type Type
Definition: list.h:306
Type head() const
Definition: list.h:227
Filtered< List, Pred > filter(List l, Pred p)
Definition: list.h:369
size_t count(List l)
Definition: list.h:341
Unique< List > unique(List l)
Definition: list.h:393
Predicate m_pred
Definition: list.h:144
SharedPtr(bool a=false)
Definition: list.h:67
Map()
Definition: list.h:275
Unique tail() const
Definition: list.h:206
void sort() const
Definition: list.h:100
bool empty() const
Definition: list.h:184
T Type
Definition: list.h:285
F & f()
Definition: list.h:251
bool empty() const
Definition: list.h:287
Type head() const
Definition: list.h:151
bool empty() const
Definition: list.h:318
std::vector< typename List::Type > Vec
Definition: list.h:56
T head() const
Definition: list.h:286
Definition: list.h:221
Definition: list.h:247
SharedPtr(const SharedPtr &o)
Definition: list.h:69
void seek() const
Definition: list.h:156
Definition: list.h:179
void _ref()
Definition: list.h:61
Empty tail() const
Definition: list.h:288
ptrdiff_t difference_type
Definition: list.h:19
bool operator!=(const ListIterator &o) const
Definition: list.h:44
void _deref()
Definition: list.h:62
Map(const List &_l, const F &_f)
Definition: list.h:276
bool empty() const
Definition: list.h:300
T2 m_2
Definition: list.h:308
Singular()
Definition: list.h:297
bool empty() const
Definition: list.h:231
Singular< X > singular(const X &x)
Definition: list.h:331
Filtered(List l, Predicate p)
Definition: list.h:170
const F & f() const
Definition: list.h:254
Definition: list.h:284
Definition: amorph.h:17
Map tail() const
Definition: list.h:264
Append(T1 a, T2 b)
Definition: list.h:311
T m_value
Definition: list.h:294
Sorted(const Sorted &o)
Definition: list.h:126
Type head() const
Definition: list.h:260
List::Type value_type
Definition: list.h:18
Append()
Definition: list.h:310
bool empty() const
Definition: list.h:146
Singular tail() const
Definition: list.h:301
Type head() const
Definition: list.h:109
void output(List l, Out it)
Definition: list.h:415
Definition: list.h:65
void seek() const
Definition: list.h:194
bool empty() const
Definition: list.h:271
List l
Definition: list.h:23
ListIterator operator++(int)
Definition: list.h:30
Map< List, F > map(const List &l, const F &f)
Definition: list.h:381
value_type & reference
Definition: list.h:21
Definition: list.h:57
SharedPtr m_sorted
Definition: list.h:97
List::Type Type
Definition: list.h:225
value_type & pointer
Definition: list.h:20
List::Type operator*()
Definition: list.h:36
Sorted< List > sort(List l)
Definition: list.h:387
std::forward_iterator_tag iterator_category
Definition: list.h:17
Vec & operator*()
Definition: list.h:83
ListIterator & operator++()
Definition: list.h:25
ListIterator< List > end(List)
Definition: list.h:425
Sorted & operator=(const Sorted &o)
Definition: list.h:129
List m_list
Definition: list.h:143