wibble
1.1
Main Page
Namespaces
Classes
Files
File List
File Members
wibble
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 >
15
struct
ListIterator
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
25
ListIterator
&
operator++
() {
26
l
=
l
.tail();
27
return
*
this
;
28
}
29
30
ListIterator
operator++
(
int
) {
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
{
66
SharedVec
*
vec
;
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
86
~SharedPtr
() {
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
;
97
mutable
SharedPtr
m_sorted
;
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
;
223
int
remaining
;
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
;
294
T
m_value
;
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 >
369
Filtered< List, Pred >
filter
( List l, Pred p )
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 >
387
Sorted< List >
sort
( List l )
388
{
389
return
Sorted< List >
( l );
390
}
391
392
template
<
typename
List >
393
Unique< List >
unique
( List l )
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 >
420
ListIterator< List >
begin
( List l ) {
421
return
ListIterator< List >
( l );
422
}
423
424
template
<
typename
List >
425
ListIterator< List >
end
( List ) {
426
return
ListIterator< List >
();
427
}
428
429
}
430
}
431
432
#endif
Generated on Wed Oct 23 2013 17:14:25 for wibble by
1.8.4