src/util/list.h

   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  */
  11
  12 #ifndef SEEN_INKSCAPE_UTIL_LIST_H
  13 #define SEEN_INKSCAPE_UTIL_LIST_H
  14
  15 #include <cstddef>
  16 #include <iterator>
  17 #include "gc-managed.h"
  18 #include "util/reference.h"
  19
  20 namespace Inkscape {
  21
  22 namespace Util {
  23
  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) {}
  30
  31     T value;
  32     ListCell *next;
  33 };
  34
  35 template <typename T> class List;
  36 template <typename T> class MutableList;
  37
  38 template <typename T>
  39 bool is_empty(List<T> const &list);
  40
  41 template <typename T>
  42 typename List<T>::reference first(List<T> const &list);
  43
  44 template <typename T>
  45 List<T> const &rest(List<T> const &list);
  46
  47 template <typename T>
  48 MutableList<T> &rest(MutableList<T> const &list);
  49
  50 template <typename T>
  51 MutableList<T> const &set_rest(MutableList<T> const &list,
  52                                MutableList<T> const &rest);
  53
  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;
  64
  65     List() : _cell(NULL) {}
  66     explicit List(const_reference value, List const &next=List())
  67     : _cell(new ListCell<T>(value, next._cell)) {}
  68
  69     operator bool() const { return this->_cell; }
  70
  71     reference operator*() const { return this->_cell->value; }
  72     pointer operator->() const { return &this->_cell->value; }
  73
  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     }
  80
  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     }
  90
  91     friend reference first<>(List const &);
  92     friend List const &rest<>(List const &);
  93     friend bool is_empty<>(List const &);
  94
  95 protected:
  96     ListCell<T> *_cell;
  97 };
  98
  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;
 128
 129     List() : List<T const>() {}
 130     explicit List(const_reference value, List const &next=List())
 131     : List<T const>(value, next) {}
 132
 133     reference operator*() const { return this->_cell->value; }
 134     pointer operator->() const { return &this->_cell->value; }
 135
 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     }
 145
 146     friend reference first<>(List const &);
 147     friend List const &rest<>(List const &);
 148     friend bool is_empty<>(List const &);
 149 };
 150
 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;
 161
 162     List() : _cell(NULL) {}
 163     List(const_reference value, List const &next=List())
 164     : _cell(new ListCell<T &>(value, next._cell)) {}
 165
 166     operator bool() const { return this->_cell; }
 167
 168     reference operator*() const { return this->_cell->value; }
 169     pointer operator->() const { return &this->_cell->value; }
 170
 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     }
 177
 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     }
 187
 188     friend reference first<>(List const &);
 189     friend List const &rest<>(List const &);
 190     friend bool is_empty<>(List const &);
 191
 192 protected:
 193     ListCell<T &> *_cell;
 194 };
 195
 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) {}
 214
 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     }
 224
 225     friend MutableList &rest<>(MutableList const &);
 226     friend MutableList const &set_rest<>(MutableList const &,
 227                                          MutableList const &);
 228 };
 229
 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 }
 256
 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 }
 285
 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; }
 297
 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 }
 323
 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 }
 343
 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 }
 368
 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 }
 392
 393 }
 394
 395 }
 396
 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:fileencoding=utf-8:textwidth=99 :