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 */
13 #ifndef SEEN_INKSCAPE_UTIL_LIST_CONTAINER_H
14 #define SEEN_INKSCAPE_UTIL_LIST_CONTAINER_H
16 #include <limits>
17 #include "util/list.h"
19 namespace Inkscape {
21 namespace Util {
23 template <typename T>
24 class ListContainer {
25 public:
26 /* default constructible */
27 ListContainer() {}
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 }
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 }
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 }
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;
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; }
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 }
126 reference front() { return *_head; }
127 const_reference front() const { return *_head; }
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 }
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 }
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
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 }
280 private:
281 MutableList<T> _head;
282 MutableList<T> _tail;
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 };
338 }
340 }
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 :