1 /** \file
2 * Inkscape::Util::List - managed linked list
3 *
4 * Authors:
5 * MenTaLguY <mental@rydia.net>
6 *
7 * Copyright (C) 2004 MenTaLguY
8 *
9 * Released under GNU GPL, read the file 'COPYING' for more information
10 */
12 #ifndef SEEN_INKSCAPE_UTIL_LIST_H
13 #define SEEN_INKSCAPE_UTIL_LIST_H
15 #include <cstddef>
16 #include <iterator>
17 #include "gc-managed.h"
18 #include "traits/reference.h"
20 namespace Inkscape {
22 namespace Util {
24 /// Generic ListCell for Inkscape::Util::List.
25 template <typename T>
26 struct ListCell : public GC::Managed<> {
27 ListCell() {}
28 ListCell(typename Traits::Reference<T>::RValue v, ListCell *n)
29 : value(v), next(n) {}
31 T value;
32 ListCell *next;
33 };
35 template <typename T> class List;
36 template <typename T> class MutableList;
38 template <typename T>
39 bool is_empty(List<T> const &list);
41 template <typename T>
42 typename List<T>::reference first(List<T> const &list);
44 template <typename T>
45 List<T> const &rest(List<T> const &list);
47 template <typename T>
48 MutableList<T> &rest(MutableList<T> const &list);
50 template <typename T>
51 MutableList<T> const &set_rest(MutableList<T> const &list,
52 MutableList<T> const &rest);
54 /// Helper template.
55 template <typename T>
56 class List<T const> {
57 public:
58 typedef std::forward_iterator_tag iterator_category;
59 typedef T const value_type;
60 typedef std::ptrdiff_t difference_type;
61 typedef typename Traits::Reference<value_type>::LValue reference;
62 typedef typename Traits::Reference<value_type>::RValue const_reference;
63 typedef typename Traits::Reference<value_type>::Pointer pointer;
65 List() : _cell(NULL) {}
66 explicit List(const_reference value, List const &next=List())
67 : _cell(new ListCell<T>(value, next._cell)) {}
69 operator bool() const { return this->_cell; }
71 reference operator*() const { return this->_cell->value; }
72 pointer operator->() const { return &this->_cell->value; }
74 bool operator==(List const &other) const {
75 return this->_cell == other._cell;
76 }
77 bool operator!=(List const &other) const {
78 return this->_cell != other._cell;
79 }
81 List &operator++() {
82 this->_cell = this->_cell->next;
83 return *this;
84 }
85 List operator++(int) {
86 List old(*this);
87 this->_cell = this->_cell->next;
88 return old;
89 }
91 friend reference first<>(List const &);
92 friend List const &rest<>(List const &);
93 friend bool is_empty<>(List const &);
95 protected:
96 ListCell<T> *_cell;
97 };
99 /**
100 * Generic linked list.
101 *
102 * These lists are designed to store simple values like pointers,
103 * references, and scalar values. While they can be used to directly
104 * store more complex objects, destructors for those objects will not
105 * be called unless those objects derive from Inkscape::GC::Finalized.
106 *
107 * In general it's better to use lists to store pointers or references
108 * to objects requiring finalization and manage object lifetimes separately.
109 *
110 * @see Inkscape::GC::Finalized
111 *
112 * cons() is synonymous with List<T>(first, rest), except that the
113 * compiler will usually be able to infer T from the type of \a rest.
114 *
115 * If you need to create an empty list (which can, for example, be used
116 * as an 'end' value with STL algorithms), call the List<> constructor
117 * with no arguments, like so:
118 *
119 * <code> List<int>() </code>
120 */
121 template <typename T>
122 class List : public List<T const> {
123 public:
124 typedef T value_type;
125 typedef typename Traits::Reference<value_type>::LValue reference;
126 typedef typename Traits::Reference<value_type>::RValue const_reference;
127 typedef typename Traits::Reference<value_type>::Pointer pointer;
129 List() : List<T const>() {}
130 explicit List(const_reference value, List const &next=List())
131 : List<T const>(value, next) {}
133 reference operator*() const { return this->_cell->value; }
134 pointer operator->() const { return &this->_cell->value; }
136 List &operator++() {
137 this->_cell = this->_cell->next;
138 return *this;
139 }
140 List operator++(int) {
141 List old(*this);
142 this->_cell = this->_cell->next;
143 return old;
144 }
146 friend reference first<>(List const &);
147 friend List const &rest<>(List const &);
148 friend bool is_empty<>(List const &);
149 };
151 /// Helper template.
152 template <typename T>
153 class List<T &> {
154 public:
155 typedef std::forward_iterator_tag iterator_category;
156 typedef T &value_type;
157 typedef std::ptrdiff_t difference_type;
158 typedef typename Traits::Reference<value_type>::LValue reference;
159 typedef typename Traits::Reference<value_type>::RValue const_reference;
160 typedef typename Traits::Reference<value_type>::Pointer pointer;
162 List() : _cell(NULL) {}
163 List(const_reference value, List const &next=List())
164 : _cell(new ListCell<T &>(value, next._cell)) {}
166 operator bool() const { return this->_cell; }
168 reference operator*() const { return this->_cell->value; }
169 pointer operator->() const { return &this->_cell->value; }
171 bool operator==(List const &other) const {
172 return this->_cell == other._cell;
173 }
174 bool operator!=(List const &other) const {
175 return this->_cell != other._cell;
176 }
178 List &operator++() {
179 this->_cell = this->_cell->next;
180 return *this;
181 }
182 List operator++(int) {
183 List old(*this);
184 this->_cell = this->_cell->next;
185 return old;
186 }
188 friend reference first<>(List const &);
189 friend List const &rest<>(List const &);
190 friend bool is_empty<>(List const &);
192 protected:
193 ListCell<T &> *_cell;
194 };
196 /**
197 * Generic MutableList.
198 *
199 * Like a linked list, but one whose tail can be exchanged for
200 * another later by using set_rest() or assignment through rest()
201 * as an lvalue. It's otherwise identical to the "non-mutable" form.
202 *
203 * As with List, you can create an empty list like so:
204 *
205 * <code> MutableList<int>() </code>
206 */
207 template <typename T>
208 class MutableList : public List<T> {
209 public:
210 MutableList() {}
211 explicit MutableList(typename List<T>::const_reference value,
212 MutableList const &next=MutableList())
213 : List<T>(value, next) {}
215 MutableList &operator++() {
216 this->_cell = this->_cell->next;
217 return *this;
218 }
219 MutableList operator++(int) {
220 MutableList old(*this);
221 this->_cell = this->_cell->next;
222 return old;
223 }
225 friend MutableList &rest<>(MutableList const &);
226 friend MutableList const &set_rest<>(MutableList const &,
227 MutableList const &);
228 };
230 /** @brief Creates a (non-empty) linked list.
231 *
232 * Creates a new linked list with a copy of the given value (\a first)
233 * in its first element; the remainder of the list will be the list
234 * provided as \a rest.
235 *
236 * The remainder of the list -- the "tail" -- is incorporated by
237 * reference rather than being copied.
238 *
239 * The returned value can also be treated as an STL forward iterator.
240 *
241 * @param first the value for the first element of the list
242 * @param rest the rest of the list; may be an empty list
243 *
244 * @returns a new list
245 *
246 * @see List<>
247 * @see is_empty<>
248 *
249 */
250 template <typename T>
251 inline List<T> cons(typename Traits::Reference<T>::RValue first,
252 List<T> const &rest)
253 {
254 return List<T>(first, rest);
255 }
257 /** @brief Creates a (non-empty) linked list whose tail can be exchanged
258 * for another.
259 *
260 * Creates a new linked list, but one whose tail can be exchanged for
261 * another later by using set_rest() or assignment through rest()
262 * as an lvalue. It's otherwise identical to the "non-mutable" form.
263 *
264 * This form of cons() is synonymous with MutableList<T>(first, rest),
265 * except that the compiler can usually infer T from the type of \a rest.
266 *
267 * As with List<>, you can create an empty list like so:
268 *
269 * MutableList<int>()
270 *
271 * @see MutableList<>
272 * @see is_empty<>
273 *
274 * @param first the value for the first element of the list
275 * @param rest the rest of the list; may be an empty list
276 *
277 * @returns a new list
278 */
279 template <typename T>
280 inline MutableList<T> cons(typename Traits::Reference<T>::RValue first,
281 MutableList<T> const &rest)
282 {
283 return MutableList<T>(first, rest);
284 }
286 /** @brief Returns true if the given list is empty.
287 *
288 * Returns true if the given list is empty. This is equivalent
289 * to !list.
290 *
291 * @param list the list
292 *
293 * @returns true if the list is empty, false otherwise.
294 */
295 template <typename T>
296 inline bool is_empty(List<T> const &list) { return !list._cell; }
298 /** @brief Returns the first value in a linked list.
299 *
300 * Returns a reference to the first value in the list. This
301 * corresponds to the value of the first argument passed to cons().
302 *
303 * If the list holds mutable values (or references to them), first()
304 * can be used as an lvalue.
305 *
306 * For example:
307 *
308 * first(list) = value;
309 *
310 * The results of calling this on an empty list are undefined.
311 *
312 * @see cons<>
313 * @see is_empty<>
314 *
315 * @param list the list; cannot be empty
316 *
317 * @returns a reference to the first value in the list
318 */
319 template <typename T>
320 inline typename List<T>::reference first(List<T> const &list) {
321 return list._cell->value;
322 }
324 /** @brief Returns the remainder of a linked list after the first element.
325 *
326 * Returns the remainder of the list after the first element (its "tail").
327 *
328 * This will be the same as the second argument passed to cons().
329 *
330 * The results of calling this on an empty list are undefined.
331 *
332 * @see cons<>
333 * @see is_empty<>
334 *
335 * @param list the list; cannot be empty
336 *
337 * @returns the remainder of the list
338 */
339 template <typename T>
340 inline List<T> const &rest(List<T> const &list) {
341 return reinterpret_cast<List<T> const &>(list._cell->next);
342 }
344 /** @brief Returns a reference to the remainder of a linked list after
345 * the first element.
346 *
347 * Returns a reference to the remainder of the list after the first
348 * element (its "tail"). For MutableList<>, rest() can be used as
349 * an lvalue, to set a new tail.
350 *
351 * For example:
352 *
353 * rest(list) = other;
354 *
355 * Results of calling this on an empty list are undefined.
356 *
357 * @see cons<>
358 * @see is_empty<>
359 *
360 * @param list the list; cannot be empty
361 *
362 * @returns a reference to the remainder of the list
363 */
364 template <typename T>
365 inline MutableList<T> &rest(MutableList<T> const &list) {
366 return reinterpret_cast<MutableList<T> &>(list._cell->next);
367 }
369 /** @brief Sets a new tail for an existing linked list.
370 *
371 * Sets the tail of the given MutableList<>, corresponding to the
372 * second argument of cons().
373 *
374 * Results of calling this on an empty list are undefined.
375 *
376 * @see rest<>
377 * @see cons<>
378 * @see is_empty<>
379 *
380 * @param list the list; cannot be empty
381 * @param rest the new tail; corresponds to the second argument of cons()
382 *
383 * @returns the new tail
384 */
385 template <typename T>
386 inline MutableList<T> const &set_rest(MutableList<T> const &list,
387 MutableList<T> const &rest)
388 {
389 list._cell->next = rest._cell;
390 return reinterpret_cast<MutableList<T> &>(list._cell->next);
391 }
393 }
395 }
397 #endif
398 /*
399 Local Variables:
400 mode:c++
401 c-file-style:"stroustrup"
402 c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +))
403 indent-tabs-mode:nil
404 fill-column:99
405 End:
406 */
407 // vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:encoding=utf-8:textwidth=99 :