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
11namespace wibble {
12namespace list {
13
14template< typename List >
16{
17 typedef std::forward_iterator_tag iterator_category;
18 typedef typename List::Type value_type;
22
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
49 {}
50
51};
52
53template< typename List >
54struct Sorted
55{
56 typedef std::vector< typename List::Type > Vec;
57 struct SharedVec {
58 int refs;
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
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;
98 size_t m_pos;
99
100 void sort() const {
101 if ( m_sorted )
102 return;
103 m_sorted = SharedPtr( true );
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
127 m_pos( o.m_pos ) {}
128
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
139template< typename List, typename Predicate >
141{
142 typedef typename List::Type Type;
143 mutable List m_list;
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
163 {
164 Filtered r = *this;
165 r.seek();
166 r.m_list = r.m_list.tail();
167 return r;
168 }
169
171 : m_list( l ), m_pred( p )
172 {
173 }
174
176};
177
178template< typename List >
179struct 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
220template< typename List >
221struct Take {
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
246template< typename List, typename F >
247struct Map {
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
283template< typename T >
284struct 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
291template< typename T >
292struct Singular {
293 typedef T Type;
296
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
304template< typename T1, typename T2 >
305struct Append {
306 typedef typename T1::Type Type;
307 T1 m_1;
308 T2 m_2;
309
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
330template< typename X >
332 return Singular< X >( x );
333}
334
335template< typename X, typename Y >
336Append< X, Y > append( const X &x, const Y &y ) {
337 return Append< X, Y >( x, y );
338}
339
340template< typename List >
341size_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
352template< typename List, typename F >
353void foreach( List l, F f ) {
354 while ( !l.empty() ) {
355 f( l.head() );
356 l = l.tail();
357 }
358}
359
360template< typename List, template< typename > class F >
361void foreach( List l, F< typename List::Type > f ) {
362 while ( !l.empty() ) {
363 f( l.head() );
364 l = l.tail();
365 }
366}
367
368template< typename List, typename Pred >
373
374template< typename List, template< typename > class Pred >
379
380template< typename List, typename F >
381Map< List, F > map( const List &l, const F &f )
382{
383 return Map< List, F >( l, f );
384}
385
386template< typename List >
388{
389 return Sorted< List >( l );
390}
391
392template< typename List >
394{
395 return Unique< List >( l );
396}
397
398template< typename List >
400{
401 return Take< List >( l, t );
402}
403
404template< typename List >
405List drop( int t, List l )
406{
407 while ( t > 0 ) {
408 l = l.tail();
409 -- t;
410 }
411 return l;
412}
413
414template< typename List, typename Out >
415void output( List l, Out it ) {
416 std::copy( ListIterator< List >( l ), ListIterator< List >(), it );
417}
418
419template< typename List >
423
424template< typename List >
428
429}
430}
431
432#endif
ListIterator< List > end(List)
Definition list.h:425
ListIterator< List > begin(List l)
Definition list.h:420
Singular< X > singular(const X &x)
Definition list.h:331
Map< List, F > map(const List &l, const F &f)
Definition list.h:381
Append< X, Y > append(const X &x, const Y &y)
Definition list.h:336
Unique< List > unique(List l)
Definition list.h:393
size_t count(List l)
Definition list.h:341
Filtered< List, Pred > filter(List l, Pred p)
Definition list.h:369
Take< List > take(int t, List l)
Definition list.h:399
Sorted< List > sort(List l)
Definition list.h:387
void output(List l, Out it)
Definition list.h:415
List drop(int t, List l)
Definition list.h:405
Definition amorph.h:17
Definition amorph.h:30
Definition list.h:305
bool empty() const
Definition list.h:318
T1::Type Type
Definition list.h:306
T1 m_1
Definition list.h:307
Append(T1 a, T2 b)
Definition list.h:311
Type head() const
Definition list.h:312
T2 m_2
Definition list.h:308
Append()
Definition list.h:310
Append tail() const
Definition list.h:319
Definition list.h:284
T head() const
Definition list.h:286
T Type
Definition list.h:285
bool empty() const
Definition list.h:287
Empty tail() const
Definition list.h:288
Definition list.h:141
bool empty() const
Definition list.h:146
Filtered(List l, Predicate p)
Definition list.h:170
Type head() const
Definition list.h:151
Filtered()
Definition list.h:175
List::Type Type
Definition list.h:142
Predicate m_pred
Definition list.h:144
Filtered tail() const
Definition list.h:162
List m_list
Definition list.h:143
void seek() const
Definition list.h:156
Definition list.h:16
ListIterator(List _l=List())
Definition list.h:48
List::Type value_type
Definition list.h:18
ListIterator & operator++()
Definition list.h:25
value_type & reference
Definition list.h:21
List l
Definition list.h:23
value_type & pointer
Definition list.h:20
ptrdiff_t difference_type
Definition list.h:19
List::Type operator*()
Definition list.h:36
ListIterator operator++(int)
Definition list.h:30
bool operator==(const ListIterator &o) const
Definition list.h:40
bool operator!=(const ListIterator &o) const
Definition list.h:44
std::forward_iterator_tag iterator_category
Definition list.h:17
Definition list.h:247
Map(const List &_l, const F &_f)
Definition list.h:276
Map()
Definition list.h:275
F & f()
Definition list.h:251
Type head() const
Definition list.h:260
F::result_type Type
Definition list.h:258
List l
Definition list.h:248
char f_space[sizeof(F)]
Definition list.h:250
bool empty() const
Definition list.h:271
const F & f() const
Definition list.h:254
Map tail() const
Definition list.h:264
Definition list.h:292
T Type
Definition list.h:293
Singular(T i)
Definition list.h:298
bool empty() const
Definition list.h:300
Singular()
Definition list.h:297
T head() const
Definition list.h:299
T m_value
Definition list.h:294
Singular tail() const
Definition list.h:301
bool m_empty
Definition list.h:295
SharedPtr & operator=(const SharedPtr &o)
Definition list.h:75
SharedVec * vec
Definition list.h:66
SharedPtr(bool a=false)
Definition list.h:67
Vec * operator->()
Definition list.h:84
SharedPtr(const SharedPtr &o)
Definition list.h:69
Vec & operator*()
Definition list.h:83
~SharedPtr()
Definition list.h:86
void _ref()
Definition list.h:61
Vec vec
Definition list.h:59
int refs
Definition list.h:58
void _deref()
Definition list.h:62
SharedVec()
Definition list.h:60
Definition list.h:55
SharedPtr m_sorted
Definition list.h:97
Sorted tail() const
Definition list.h:114
Sorted(List l=List())
Definition list.h:136
bool empty() const
Definition list.h:121
void sort() const
Definition list.h:100
Sorted & operator=(const Sorted &o)
Definition list.h:129
List m_list
Definition list.h:96
List::Type Type
Definition list.h:95
size_t m_pos
Definition list.h:98
Sorted(const Sorted &o)
Definition list.h:126
std::vector< typename List::Type > Vec
Definition list.h:56
Type head() const
Definition list.h:109
Definition list.h:221
List::Type Type
Definition list.h:225
Take(List _l, int m)
Definition list.h:242
bool empty() const
Definition list.h:231
int remaining
Definition list.h:223
Type head() const
Definition list.h:227
Take()
Definition list.h:243
Take tail() const
Definition list.h:235
List l
Definition list.h:222
Definition list.h:180
List m_list
Definition list.h:182
List::Type Type
Definition list.h:181
bool empty() const
Definition list.h:184
Unique tail() const
Definition list.h:206
void seek() const
Definition list.h:194
Unique(List l=List())
Definition list.h:214
Type head() const
Definition list.h:189