← Back to branch summary

~vaifrax/inkscape/bugfix170049

« back to all changes in this revision

Viewing changes to src/util/list-container.h

  • Committer: mental
  • Date: 2006-01-16 02:36:01 UTC
  • Revision ID: mental@users.sourceforge.net-20060116023601-wkr0h7edl5veyudq
moving trunk for module inkscape

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/util/list-container.h
 
1
/*
 
2
 * Inkscape::Util::ListContainer - encapsulates lists as STL containers,
 
3
 *                                 providing fast appending
 
4
 *
 
5
 * Authors:
 
6
 *   MenTaLguY <mental@rydia.net>
 
7
 *
 
8
 * Copyright (C) 2005 MenTaLguY
 
9
 *
 
10
 * Released under GNU GPL, read the file 'COPYING' for more information
 
11
 */
 
12
 
 
13
#ifndef SEEN_INKSCAPE_UTIL_LIST_CONTAINER_H
 
14
#define SEEN_INKSCAPE_UTIL_LIST_CONTAINER_H
 
15
 
 
16
#include <limits>
 
17
#include "util/list.h"
 
18
 
 
19
namespace Inkscape {
 
20
 
 
21
namespace Util {
 
22
 
 
23
template <typename T>
 
24
class ListContainer {
 
25
public:
 
26
    /* default constructible */
 
27
    ListContainer() {}
 
28
 
 
29
    /* assignable */
 
30
    ListContainer(ListContainer const &other) {
 
31
        *this = other;
 
32
    }
 
33
    ListContainer &operator=(ListContainer const &other) {
 
34
        clear();
 
35
        for ( const_iterator iter = other.begin() ; iter ; ++iter ) {
 
36
            push_back(*iter);
 
37
        }
 
38
        return *this;
 
39
    }
 
40
    void swap(ListContainer<T> &other) {
 
41
        std::swap(other._head, _head);
 
42
        std::swap(other._tail, _tail);
 
43
    }
 
44
 
 
45
    /* equality comparable */
 
46
    bool operator==(ListContainer const &other) const {
 
47
        const_iterator iter = _head;
 
48
        const_iterator other_iter = other._head;
 
49
        while ( iter && other_iter ) {
 
50
            if (!( *iter == *other_iter )) {
 
51
                return false;
 
52
            }
 
53
            ++iter;
 
54
            ++other_iter;
 
55
        }
 
56
        return !iter && !other_iter;
 
57
    }
 
58
    bool operator!=(ListContainer const &other) const {
 
59
        return !operator==(other);
 
60
    }
 
61
 
 
62
    /* lessthan comparable */
 
63
    bool operator<(ListContainer const &other) const {
 
64
        const_iterator iter = _head;
 
65
        const_iterator other_iter = other._head;
 
66
        while ( iter && other_iter ) {
 
67
            if ( *iter < *other_iter ) {
 
68
                return true;
 
69
            } else if ( *other_iter < *iter ) {
 
70
                return false;
 
71
            }
 
72
            ++iter;
 
73
            ++other_iter;
 
74
        }
 
75
        return bool(other_iter);
 
76
    }
 
77
    bool operator>=(ListContainer const &other) const {
 
78
        return !operator<(other);
 
79
    }
 
80
 
 
81
    /* container */
 
82
    typedef typename List<T>::value_type value_type;
 
83
    typedef List<T> iterator;
 
84
    typedef List<T const> const_iterator;
 
85
    typedef typename List<T>::reference reference;
 
86
    typedef typename List<T>::const_reference const_reference;
 
87
    typedef typename List<T>::pointer pointer;
 
88
    typedef typename List<T>::difference_type difference_type;
 
89
    typedef std::size_t size_type;
 
90
 
 
91
    iterator begin() { return _head; }
 
92
    const_iterator begin() const { return _head; }
 
93
    iterator end() { return iterator(); }
 
94
    const_iterator end() const { return const_iterator(); }
 
95
    size_type size() const {
 
96
        size_type size=0;
 
97
        for ( iterator iter = _head ; iter ; ++iter ) {
 
98
            size++;
 
99
        }
 
100
        return size;
 
101
    }
 
102
    size_type max_size() const {
 
103
        return std::numeric_limits<std::size_t>::max();
 
104
    }
 
105
    bool empty() const { return !_head; }
 
106
 
 
107
    /* sequence */
 
108
    ListContainer(size_type count, const_reference value) {
 
109
        for ( ; count ; --count ) {
 
110
            push_back(value);
 
111
        }
 
112
    }
 
113
    ListContainer(size_type count) {
 
114
        value_type default_value;
 
115
        for ( ; count ; --count ) {
 
116
            push_back(default_value);
 
117
        }
 
118
    }
 
119
    template <typename ForwardIterator>
 
120
    ListContainer(ForwardIterator i, ForwardIterator j) {
 
121
        for ( ; i != j ; ++i ) {
 
122
            push_back(*i);
 
123
        }
 
124
    }
 
125
 
 
126
    reference front() { return *_head; }
 
127
    const_reference front() const { return *_head; }
 
128
 
 
129
    iterator insert(const_iterator position, const_reference value) {
 
130
        if (position) {
 
131
            if ( position != _head ) {
 
132
                MutableList<T> added(value);
 
133
                MutableList<T> before=_before(position);
 
134
                set_rest(added, rest(before));
 
135
                set_rest(before, added);
 
136
                return added;
 
137
            } else {
 
138
                push_front(value);
 
139
                return _head;
 
140
            }
 
141
        } else {
 
142
            push_back(value);
 
143
            return _tail;
 
144
        }
 
145
    }
 
146
    void insert(const_iterator position, size_type count, const_reference value)
 
147
    {
 
148
        _insert_from_temp(position, ListContainer(count, value));
 
149
    }
 
150
    template <typename ForwardIterator>
 
151
    void insert(const_iterator position, ForwardIterator i, ForwardIterator j) {
 
152
        _insert_from_temp(position, ListContainer(i, j));
 
153
    }
 
154
    void erase(const_iterator position) {
 
155
        erase(position, rest(position));
 
156
    }
 
157
    void erase(const_iterator i, const_iterator j) {
 
158
        if ( i == _head ) {
 
159
            _head = static_cast<MutableList<T> &>(j);
 
160
            if ( !j || !rest(j) ) {
 
161
                _tail = _head;
 
162
            }
 
163
        } else {
 
164
            MutableList<T> before=_before(i);
 
165
            if (j) {
 
166
                set_rest(before, static_cast<MutableList<T> &>(j));
 
167
            } else {
 
168
                set_rest(before, MutableList<T>());
 
169
                _tail = before;
 
170
            }
 
171
        }
 
172
    }
 
173
    void clear() {
 
174
        _head = _tail = MutableList<T>();
 
175
    }
 
176
    void resize(size_type size, const_reference fill) {
 
177
        MutableList<T> before;
 
178
        MutableList<T> iter;
 
179
        for ( iter = _head ; iter && size ; ++iter ) {
 
180
            before = iter;
 
181
            size--;
 
182
        }
 
183
        if (size) {
 
184
            ListContainer temp(size, fill);
 
185
            if (empty()) {
 
186
                _head = temp._head;
 
187
                _tail = temp._tail;
 
188
            } else {
 
189
                set_rest(_tail, temp._head);
 
190
                _tail = temp._tail;
 
191
            }
 
192
        } else if (iter) {
 
193
            if (before) {
 
194
                set_rest(before, MutableList<T>());
 
195
                _tail = before;
 
196
            } else {
 
197
                _head = _tail = MutableList<T>();
 
198
            }
 
199
        }
 
200
    }
 
201
    void resize(size_type size) {
 
202
        resize(size, value_type());
 
203
    }
 
204
 
 
205
    /* front insertion sequence */
 
206
    void push_front(const_reference value) {
 
207
        if (_head) {
 
208
            _head = cons(value, _head);
 
209
        } else {
 
210
            _head = _tail = MutableList<T>(value);
 
211
        }
 
212
    }
 
213
    void pop_front() {
 
214
        if (_head) {
 
215
            _head = rest(_head);
 
216
            if (!_head) {
 
217
                _tail = _head;
 
218
            }
 
219
        }
 
220
    }
 
221
 
 
222
    /* back insertion sequence */
 
223
    reference back() { return *_tail; }
 
224
    const_reference back() const { return *_tail; }
 
225
    void push_back(const_reference value) {
 
226
        if (_tail) {
 
227
            MutableList<T> added(value);
 
228
            set_rest(_tail, added);
 
229
            _tail = added;
 
230
        } else {
 
231
            _head = _tail = MutableList<T>(value);
 
232
        }
 
233
    }
 
234
    // we're not required to provide pop_back if we can't
 
235
    // implement it efficiently
 
236
 
 
237
    /* additional */
 
238
    MutableList<T> detatchList() {
 
239
        MutableList<T> list=_head;
 
240
        _head = _tail = MutableList<T>();
 
241
        return list;
 
242
    }
 
243
    iterator insert_after(const_iterator pos, const_reference value) {
 
244
        MutableList<T> added(value);
 
245
        if (pos) {
 
246
            MutableList<T> before=static_cast<MutableList<T> &>(pos);
 
247
            set_rest(added, rest(before));
 
248
            set_rest(before, added);
 
249
            if ( _tail == before ) {
 
250
                _tail = added;
 
251
            }
 
252
        } else {
 
253
            push_front(value);
 
254
        }
 
255
    }
 
256
    void insert_after(const_iterator position, size_type count,
 
257
                      const_reference value)
 
258
    {
 
259
        _insert_after_from_temp(position, ListContainer(count, value));
 
260
    }
 
261
    template <typename ForwardIterator>
 
262
    void insert_after(const_iterator position,
 
263
                      ForwardIterator i, ForwardIterator j)
 
264
    {
 
265
        _insert_after_from_temp(position, ListContainer(i, j));
 
266
    }
 
267
    void erase_after(const_iterator position) {
 
268
        if (!position) {
 
269
            pop_front();
 
270
        } else {
 
271
            MutableList<T> before=static_cast<MutableList<T> &>(position);
 
272
            MutableList<T> removed=rest(before);
 
273
            set_rest(before, rest(removed));
 
274
            if ( removed == _tail ) {
 
275
                _tail = before;
 
276
            }
 
277
        }
 
278
    }
 
279
 
 
280
private:
 
281
    MutableList<T> _head;
 
282
    MutableList<T> _tail;
 
283
 
 
284
    MutableList<T> _before(const_iterator position) {
 
285
        for ( MutableList<T> iter = _head ; iter ; ++iter ) {
 
286
            if ( rest(iter) == position ) {
 
287
                return iter;
 
288
            }
 
289
        }
 
290
        return MutableList<T>();
 
291
    }
 
292
    void _insert_from_temp(const_iterator pos, ListContainer const &temp) {
 
293
        if (temp.empty()) {
 
294
            return;
 
295
        }
 
296
        if (empty()) { /* if empty, just take the whole thing */
 
297
            _head = temp._head;
 
298
            _tail = temp._tail;
 
299
        } else if (pos) {
 
300
            if ( pos == _head ) { /* prepend */
 
301
                set_rest(temp._tail, _head);
 
302
                _head = temp._head;
 
303
            } else { /* insert somewhere in the middle */
 
304
                MutableList<T> before=_before(pos);
 
305
                set_rest(temp._tail, static_cast<MutableList<T> &>(pos));
 
306
                set_rest(before, temp._head);
 
307
            }
 
308
        } else { /* append */
 
309
            set_rest(_tail, temp._head);
 
310
            _tail = temp._tail;
 
311
        }
 
312
    }
 
313
    void _insert_after_from_temp(const_iterator pos,
 
314
                                 ListContainer const &temp)
 
315
    {
 
316
        if (temp.empty()) {
 
317
            return;
 
318
        }
 
319
        if (empty()) { /* if empty, just take the whole thing */
 
320
            _head = temp._head;
 
321
            _tail = temp._tail;
 
322
        } else if (pos) {
 
323
            if ( pos == _tail ) { /* append */
 
324
                set_rest(_tail, temp._head);
 
325
                _tail = temp._tail;
 
326
            } else { /* insert somewhere in the middle */
 
327
                MutableList<T> before=static_cast<MutableList<T> &>(pos);
 
328
                set_rest(temp._tail, rest(before));
 
329
                set_rest(before, temp._head);
 
330
            }
 
331
        } else { /* prepend */
 
332
            set_rest(temp._tail, _head);
 
333
            _head = temp._head;
 
334
        }
 
335
    }
 
336
};
 
337
 
 
338
}
 
339
 
 
340
}
 
341
 
 
342
#endif
 
343
/*
 
344
  Local Variables:
 
345
  mode:c++
 
346
  c-file-style:"stroustrup"
 
347
  c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +))
 
348
  indent-tabs-mode:nil
 
349
  fill-column:99
 
350
  End:
 
351
*/
 
352
// vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:encoding=utf-8:textwidth=99 :