diff options
author | Daniel Baumann <daniel.baumann@progress-linux.org> | 2024-04-27 16:29:01 +0000 |
---|---|---|
committer | Daniel Baumann <daniel.baumann@progress-linux.org> | 2024-04-27 16:29:01 +0000 |
commit | 35a96bde514a8897f6f0fcc41c5833bf63df2e2a (patch) | |
tree | 657d15a03cc46bd099fc2c6546a7a4ad43815d9f /src/util/list.h | |
parent | Initial commit. (diff) | |
download | inkscape-35a96bde514a8897f6f0fcc41c5833bf63df2e2a.tar.xz inkscape-35a96bde514a8897f6f0fcc41c5833bf63df2e2a.zip |
Adding upstream version 1.0.2.upstream/1.0.2upstream
Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>
Diffstat (limited to 'src/util/list.h')
-rw-r--r-- | src/util/list.h | 413 |
1 files changed, 413 insertions, 0 deletions
diff --git a/src/util/list.h b/src/util/list.h new file mode 100644 index 0000000..68f410b --- /dev/null +++ b/src/util/list.h @@ -0,0 +1,413 @@ +// SPDX-License-Identifier: GPL-2.0-or-later +/* + * Authors: + * MenTaLguY <mental@rydia.net> + * + * Copyright (C) 2004 MenTaLguY + * + * Released under GNU GPL v2+, read the file 'COPYING' for more information. + */ + +#ifndef SEEN_INKSCAPE_UTIL_LIST_H +#define SEEN_INKSCAPE_UTIL_LIST_H + +#include <cstddef> +#include <iterator> +#include "inkgc/gc-managed.h" +#include "util/reference.h" + +namespace Inkscape { + +namespace Util { + +/// Generic ListCell for Inkscape::Util::List. +template <typename T> +struct ListCell : public GC::Managed<> { + ListCell() = default; + ListCell(typename Traits::Reference<T>::RValue v, ListCell *n) + : value(v), next(n) {} + + T value; + ListCell *next; +}; + +template <typename T> class List; +template <typename T> class MutableList; + +template <typename T> +bool is_empty(List<T> const &list); + +template <typename T> +typename List<T>::reference first(List<T> const &list); + +template <typename T> +List<T> const &rest(List<T> const &list); + +template <typename T> +MutableList<T> &rest(MutableList<T> const &list); + +template <typename T> +MutableList<T> const &set_rest(MutableList<T> const &list, + MutableList<T> const &rest); + +/// Helper template. +template <typename T> +class List<T const> { +public: + typedef std::forward_iterator_tag iterator_category; + typedef T const value_type; + typedef std::ptrdiff_t difference_type; + typedef typename Traits::Reference<value_type>::LValue reference; + typedef typename Traits::Reference<value_type>::RValue const_reference; + typedef typename Traits::Reference<value_type>::Pointer pointer; + + List() : _cell(nullptr) {} + explicit List(const_reference value, List const &next=List()) + : _cell(new ListCell<T>(value, next._cell)) {} + + operator bool() const { return this->_cell; } + + reference operator*() const { return this->_cell->value; } + pointer operator->() const { return &this->_cell->value; } + + bool operator==(List const &other) const { + return this->_cell == other._cell; + } + bool operator!=(List const &other) const { + return this->_cell != other._cell; + } + + List &operator++() { + this->_cell = this->_cell->next; + return *this; + } + List operator++(int) { + List old(*this); + this->_cell = this->_cell->next; + return old; + } + + friend reference first<>(List const &); + friend List const &rest<>(List const &); + friend bool is_empty<>(List const &); + +protected: + ListCell<T> *_cell; +}; + +/** + * Generic linked list. + * + * These lists are designed to store simple values like pointers, + * references, and scalar values. While they can be used to directly + * store more complex objects, destructors for those objects will not + * be called unless those objects derive from Inkscape::GC::Finalized. + * + * In general it's better to use lists to store pointers or references + * to objects requiring finalization and manage object lifetimes separately. + * + * @see Inkscape::GC::Finalized + * + * cons() is synonymous with List<T>(first, rest), except that the + * compiler will usually be able to infer T from the type of \a rest. + * + * If you need to create an empty list (which can, for example, be used + * as an 'end' value with STL algorithms), call the List<> constructor + * with no arguments, like so: + * + * <code> List<int>() </code> + */ +template <typename T> +class List : public List<T const> { +public: + typedef T value_type; + typedef typename Traits::Reference<value_type>::LValue reference; + typedef typename Traits::Reference<value_type>::RValue const_reference; + typedef typename Traits::Reference<value_type>::Pointer pointer; + + List() : List<T const>() {} + explicit List(const_reference value, List const &next=List()) + : List<T const>(value, next) {} + + reference operator*() const { return this->_cell->value; } + pointer operator->() const { return &this->_cell->value; } + + List &operator++() { + this->_cell = this->_cell->next; + return *this; + } + List operator++(int) { + List old(*this); + this->_cell = this->_cell->next; + return old; + } + + friend reference first<>(List const &); + friend List const &rest<>(List const &); + friend bool is_empty<>(List const &); +}; + +/// Helper template. +template <typename T> +class List<T &> { +public: + typedef std::forward_iterator_tag iterator_category; + typedef T &value_type; + typedef std::ptrdiff_t difference_type; + typedef typename Traits::Reference<value_type>::LValue reference; + typedef typename Traits::Reference<value_type>::RValue const_reference; + typedef typename Traits::Reference<value_type>::Pointer pointer; + + List() : _cell(nullptr) {} + List(const_reference value, List const &next=List()) + : _cell(new ListCell<T &>(value, next._cell)) {} + + operator bool() const { return this->_cell; } + + reference operator*() const { return this->_cell->value; } + pointer operator->() const { return &this->_cell->value; } + + bool operator==(List const &other) const { + return this->_cell == other._cell; + } + bool operator!=(List const &other) const { + return this->_cell != other._cell; + } + + List &operator++() { + this->_cell = this->_cell->next; + return *this; + } + List operator++(int) { + List old(*this); + this->_cell = this->_cell->next; + return old; + } + + friend reference first<>(List const &); + friend List const &rest<>(List const &); + friend bool is_empty<>(List const &); + +protected: + ListCell<T &> *_cell; +}; + +/** + * Generic MutableList. + * + * Like a linked list, but one whose tail can be exchanged for + * another later by using set_rest() or assignment through rest() + * as an lvalue. It's otherwise identical to the "non-mutable" form. + * + * As with List, you can create an empty list like so: + * + * <code> MutableList<int>() </code> + */ +template <typename T> +class MutableList : public List<T> { +public: + MutableList() = default; + explicit MutableList(typename List<T>::const_reference value, + MutableList const &next=MutableList()) + : List<T>(value, next) {} + + MutableList &operator++() { + this->_cell = this->_cell->next; + return *this; + } + MutableList operator++(int) { + MutableList old(*this); + this->_cell = this->_cell->next; + return old; + } + + friend MutableList &rest<>(MutableList const &); + friend MutableList const &set_rest<>(MutableList const &, + MutableList const &); +}; + +/** + * Creates a (non-empty) linked list. + * + * Creates a new linked list with a copy of the given value (\a first) + * in its first element; the remainder of the list will be the list + * provided as \a rest. + * + * The remainder of the list -- the "tail" -- is incorporated by + * reference rather than being copied. + * + * The returned value can also be treated as an STL forward iterator. + * + * @param first the value for the first element of the list + * @param rest the rest of the list; may be an empty list + * + * @return a new list + * + * @see List<> + * @see is_empty<> + * + */ +template <typename T> +inline List<T> cons(typename Traits::Reference<T>::RValue first, + List<T> const &rest) +{ + return List<T>(first, rest); +} + +/** + * Creates a (non-empty) linked list whose tail can be exchanged + * for another. + * + * Creates a new linked list, but one whose tail can be exchanged for + * another later by using set_rest() or assignment through rest() + * as an lvalue. It's otherwise identical to the "non-mutable" form. + * + * This form of cons() is synonymous with MutableList<T>(first, rest), + * except that the compiler can usually infer T from the type of \a rest. + * + * As with List<>, you can create an empty list like so: + * + * MutableList<int>() + * + * @see MutableList<> + * @see is_empty<> + * + * @param first the value for the first element of the list + * @param rest the rest of the list; may be an empty list + * + * @return a new list + */ +template <typename T> +inline MutableList<T> cons(typename Traits::Reference<T>::RValue first, + MutableList<T> const &rest) +{ + return MutableList<T>(first, rest); +} + +/** + * Returns true if the given list is empty. + * + * Returns true if the given list is empty. This is equivalent + * to !list. + * + * @param list the list + * + * @return true if the list is empty, false otherwise. + */ +template <typename T> +inline bool is_empty(List<T> const &list) { return !list._cell; } + +/** + * Returns the first value in a linked list. + * + * Returns a reference to the first value in the list. This + * corresponds to the value of the first argument passed to cons(). + * + * If the list holds mutable values (or references to them), first() + * can be used as an lvalue. + * + * For example: + * + * first(list) = value; + * + * The results of calling this on an empty list are undefined. + * + * @see cons<> + * @see is_empty<> + * + * @param list the list; cannot be empty + * + * @return a reference to the first value in the list + */ +template <typename T> +inline typename List<T>::reference first(List<T> const &list) { + return list._cell->value; +} + +/** + * Returns the remainder of a linked list after the first element. + * + * Returns the remainder of the list after the first element (its "tail"). + * + * This will be the same as the second argument passed to cons(). + * + * The results of calling this on an empty list are undefined. + * + * @see cons<> + * @see is_empty<> + * + * @param list the list; cannot be empty + * + * @return the remainder of the list + */ +template <typename T> +inline List<T> const &rest(List<T> const &list) { + return reinterpret_cast<List<T> const &>(list._cell->next); +} + +/** + * Returns a reference to the remainder of a linked list after + * the first element. + * + * Returns a reference to the remainder of the list after the first + * element (its "tail"). For MutableList<>, rest() can be used as + * an lvalue, to set a new tail. + * + * For example: + * + * rest(list) = other; + * + * Results of calling this on an empty list are undefined. + * + * @see cons<> + * @see is_empty<> + * + * @param list the list; cannot be empty + * + * @return a reference to the remainder of the list + */ +template <typename T> +inline MutableList<T> &rest(MutableList<T> const &list) { + return reinterpret_cast<MutableList<T> &>(list._cell->next); +} + +/** + * Sets a new tail for an existing linked list. + * + * Sets the tail of the given MutableList<>, corresponding to the + * second argument of cons(). + * + * Results of calling this on an empty list are undefined. + * + * @see rest<> + * @see cons<> + * @see is_empty<> + * + * @param list the list; cannot be empty + * @param rest the new tail; corresponds to the second argument of cons() + * + * @return the new tail + */ +template <typename T> +inline MutableList<T> const &set_rest(MutableList<T> const &list, + MutableList<T> const &rest) +{ + list._cell->next = rest._cell; + return reinterpret_cast<MutableList<T> &>(list._cell->next); +} + +} + +} + +#endif +/* + Local Variables: + mode:c++ + c-file-style:"stroustrup" + c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +)) + indent-tabs-mode:nil + fill-column:99 + End: +*/ +// vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:fileencoding=utf-8:textwidth=99 : |