diff options
Diffstat (limited to 'src/util/list-container.h')
| -rw-r--r-- | src/util/list-container.h | 353 |
1 files changed, 353 insertions, 0 deletions
diff --git a/src/util/list-container.h b/src/util/list-container.h new file mode 100644 index 0000000..7002387 --- /dev/null +++ b/src/util/list-container.h @@ -0,0 +1,353 @@ +// SPDX-License-Identifier: GPL-2.0-or-later +/* + * Inkscape::Util::ListContainer - encapsulates lists as STL containers, + * providing fast appending + * + * Authors: + * MenTaLguY <mental@rydia.net> + * + * Copyright (C) 2005 MenTaLguY + * + * Released under GNU GPL v2+, read the file 'COPYING' for more information. + */ + +#ifndef SEEN_INKSCAPE_UTIL_LIST_CONTAINER_H +#define SEEN_INKSCAPE_UTIL_LIST_CONTAINER_H + +#include <limits> +#include "util/list.h" + +namespace Inkscape { + +namespace Util { + +template <typename T> +class ListContainer { +public: + /* default constructible */ + ListContainer() = default; + + /* assignable */ + ListContainer(ListContainer const &other) { + *this = other; + } + ListContainer &operator=(ListContainer const &other) { + clear(); + for ( const_iterator iter = other.begin() ; iter ; ++iter ) { + push_back(*iter); + } + return *this; + } + void swap(ListContainer<T> &other) { + std::swap(other._head, _head); + std::swap(other._tail, _tail); + } + + /* equality comparable */ + bool operator==(ListContainer const &other) const { + const_iterator iter = _head; + const_iterator other_iter = other._head; + while ( iter && other_iter ) { + if (!( *iter == *other_iter )) { + return false; + } + ++iter; + ++other_iter; + } + return !iter && !other_iter; + } + bool operator!=(ListContainer const &other) const { + return !operator==(other); + } + + /* lessthan comparable */ + bool operator<(ListContainer const &other) const { + const_iterator iter = _head; + const_iterator other_iter = other._head; + while ( iter && other_iter ) { + if ( *iter < *other_iter ) { + return true; + } else if ( *other_iter < *iter ) { + return false; + } + ++iter; + ++other_iter; + } + return bool(other_iter); + } + bool operator>=(ListContainer const &other) const { + return !operator<(other); + } + + /* container */ + typedef typename List<T>::value_type value_type; + typedef List<T> iterator; + typedef List<T const> const_iterator; + typedef typename List<T>::reference reference; + typedef typename List<T>::const_reference const_reference; + typedef typename List<T>::pointer pointer; + typedef typename List<T>::difference_type difference_type; + typedef std::size_t size_type; + + iterator begin() { return _head; } + const_iterator begin() const { return _head; } + iterator end() { return iterator(); } + const_iterator end() const { return const_iterator(); } + size_type size() const { + size_type size=0; + for ( iterator iter = _head ; iter ; ++iter ) { + size++; + } + return size; + } + size_type max_size() const { + return std::numeric_limits<std::size_t>::max(); + } + bool empty() const { return !_head; } + + /* sequence */ + ListContainer(size_type count, const_reference value) { + for ( ; count ; --count ) { + push_back(value); + } + } + ListContainer(size_type count) { + value_type default_value; + for ( ; count ; --count ) { + push_back(default_value); + } + } + template <typename ForwardIterator> + ListContainer(ForwardIterator i, ForwardIterator j) { + for ( ; i != j ; ++i ) { + push_back(*i); + } + } + + reference front() { return *_head; } + const_reference front() const { return *_head; } + + iterator insert(const_iterator position, const_reference value) { + if (position) { + if ( position != _head ) { + MutableList<T> added(value); + MutableList<T> before=_before(position); + set_rest(added, rest(before)); + set_rest(before, added); + return added; + } else { + push_front(value); + return _head; + } + } else { + push_back(value); + return _tail; + } + } + void insert(const_iterator position, size_type count, const_reference value) + { + _insert_from_temp(position, ListContainer(count, value)); + } + template <typename ForwardIterator> + void insert(const_iterator position, ForwardIterator i, ForwardIterator j) { + _insert_from_temp(position, ListContainer(i, j)); + } + void erase(const_iterator position) { + erase(position, rest(position)); + } + void erase(const_iterator i, const_iterator j) { + if ( i == _head ) { + _head = static_cast<MutableList<T> &>(j); + if ( !j || !rest(j) ) { + _tail = _head; + } + } else { + MutableList<T> before=_before(i); + if (j) { + set_rest(before, static_cast<MutableList<T> &>(j)); + } else { + set_rest(before, MutableList<T>()); + _tail = before; + } + } + } + void clear() { + _head = _tail = MutableList<T>(); + } + void resize(size_type size, const_reference fill) { + MutableList<T> before; + MutableList<T> iter; + for ( iter = _head ; iter && size ; ++iter ) { + before = iter; + size--; + } + if (size) { + ListContainer temp(size, fill); + if (empty()) { + _head = temp._head; + _tail = temp._tail; + } else { + set_rest(_tail, temp._head); + _tail = temp._tail; + } + } else if (iter) { + if (before) { + set_rest(before, MutableList<T>()); + _tail = before; + } else { + _head = _tail = MutableList<T>(); + } + } + } + void resize(size_type size) { + resize(size, value_type()); + } + + /* front insertion sequence */ + void push_front(const_reference value) { + if (_head) { + _head = cons(value, _head); + } else { + _head = _tail = MutableList<T>(value); + } + } + void pop_front() { + if (_head) { + _head = rest(_head); + if (!_head) { + _tail = _head; + } + } + } + + /* back insertion sequence */ + reference back() { return *_tail; } + const_reference back() const { return *_tail; } + void push_back(const_reference value) { + if (_tail) { + MutableList<T> added(value); + set_rest(_tail, added); + _tail = added; + } else { + _head = _tail = MutableList<T>(value); + } + } + // we're not required to provide pop_back if we can't + // implement it efficiently + + /* additional */ + MutableList<T> detatchList() { + MutableList<T> list=_head; + _head = _tail = MutableList<T>(); + return list; + } + iterator insert_after(const_iterator pos, const_reference value) { + MutableList<T> added(value); + if (pos) { + MutableList<T> before=static_cast<MutableList<T> &>(pos); + set_rest(added, rest(before)); + set_rest(before, added); + if ( _tail == before ) { + _tail = added; + } + } else { + push_front(value); + } + } + void insert_after(const_iterator position, size_type count, + const_reference value) + { + _insert_after_from_temp(position, ListContainer(count, value)); + } + template <typename ForwardIterator> + void insert_after(const_iterator position, + ForwardIterator i, ForwardIterator j) + { + _insert_after_from_temp(position, ListContainer(i, j)); + } + void erase_after(const_iterator position) { + if (!position) { + pop_front(); + } else { + MutableList<T> before=static_cast<MutableList<T> &>(position); + MutableList<T> removed=rest(before); + set_rest(before, rest(removed)); + if ( removed == _tail ) { + _tail = before; + } + } + } + +private: + MutableList<T> _head; + MutableList<T> _tail; + + MutableList<T> _before(const_iterator position) { + for ( MutableList<T> iter = _head ; iter ; ++iter ) { + if ( rest(iter) == position ) { + return iter; + } + } + return MutableList<T>(); + } + void _insert_from_temp(const_iterator pos, ListContainer const &temp) { + if (temp.empty()) { + return; + } + if (empty()) { /* if empty, just take the whole thing */ + _head = temp._head; + _tail = temp._tail; + } else if (pos) { + if ( pos == _head ) { /* prepend */ + set_rest(temp._tail, _head); + _head = temp._head; + } else { /* insert somewhere in the middle */ + MutableList<T> before=_before(pos); + set_rest(temp._tail, static_cast<MutableList<T> &>(pos)); + set_rest(before, temp._head); + } + } else { /* append */ + set_rest(_tail, temp._head); + _tail = temp._tail; + } + } + void _insert_after_from_temp(const_iterator pos, + ListContainer const &temp) + { + if (temp.empty()) { + return; + } + if (empty()) { /* if empty, just take the whole thing */ + _head = temp._head; + _tail = temp._tail; + } else if (pos) { + if ( pos == _tail ) { /* append */ + set_rest(_tail, temp._head); + _tail = temp._tail; + } else { /* insert somewhere in the middle */ + MutableList<T> before=static_cast<MutableList<T> &>(pos); + set_rest(temp._tail, rest(before)); + set_rest(before, temp._head); + } + } else { /* prepend */ + set_rest(temp._tail, _head); + _head = temp._head; + } + } +}; + +} + +} + +#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 : |