diff options
Diffstat (limited to 'common')
-rw-r--r-- | common/list.h | 169 |
1 files changed, 114 insertions, 55 deletions
diff --git a/common/list.h b/common/list.h index eabf8a4701..7afc97b014 100644 --- a/common/list.h +++ b/common/list.h @@ -26,95 +26,157 @@ namespace Common { -/* -TODO: Add a true list class, based on a linked list data structure - +/** + * Simple double linked list, modelled after the list template of the standard + * C++ library. + * Warning: as of now, this code is 100% untested. + */ template <class T> class List { protected: - template <class T> - class Node { - Node<T> *_prev; - Node<T> *_next; - T _data; - } - - template <class T> - class Iterator { - friend class List<T>; - private: - Node<T> *_node; + struct NodeBase { + NodeBase *_prev; + NodeBase *_next; + }; - public: - Node<T> &operator++() { + template <class T2> + struct Node : public NodeBase { + T2 _data; + + Node<T2>(const T2 &x) : _data(x) {} + }; + + template <class T2> + struct Iterator { + NodeBase *_node; + + Iterator<T2>(NodeBase *node) : _node(node) {} + + // Prefix inc + Iterator<T2> &operator++() { _node = _node->_next; + return *this; + } + // Postfix inc + Iterator<T2> operator++(int) { + Iterator<T2> tmp = *this; + _node = _node->_next; + return tmp; + } + // Prefix dec + Iterator<T2> &operator--() { + _node = _node->_prev; + return *this; + } + // Postfix dec + Iterator<T2> operator--(int) { + Iterator<T2> tmp = *this; + _node = _node->_prev; + return tmp; } - T& operator*() const { - return _node->_data; + return static_cast<Node<T2>*>(_node)->_data; } T* operator->() const { - return &(_node->_data); + return &(operator*()); + } + + bool operator==(const Iterator<T2>& x) const { + return _node == x._node; + } + + bool operator!=(const Iterator<T2>& x) const { + return _node != x._node; } }; - Iterator<T> *_anchor; + NodeBase *_anchor; public: - typedef Node<T> *iterator; - typedef const Node<T> *const_iterator; + typedef Iterator<T> iterator; + typedef const Iterator<T> const_iterator; public: - List<T>() : _anchor(...) {} - List<T>(const List<T>& list) : _anchor(...) { - ... copy list ... + List<T>() { + _anchor = new NodeBase; + _anchor->_prev = _anchor; + _anchor->_next = _anchor; + } + List<T>(const List<T>& list) { + _anchor = new NodeBase; + _anchor->_prev = _anchor; + _anchor->_next = _anchor; + + insert(begin(), list.begin(), list.end()); } ~List<T>() { - if (_data) - delete [] _data; + clear(); + delete _anchor; } - void push_back(const T& element) { - ... + void push_front(const T& element) { + insert(begin(), element); } - void push_back(const List<T>& list) { - ... + void push_back(const T& element) { + insert(end(), element); } void insert(iterator pos, const T& element) { - ... + NodeBase *newNode = new Node<T>(element); + + newNode->_next = pos._node; + newNode->_prev = pos._node->_prev; + newNode->_prev->_next = newNode; + newNode->_next->_prev = newNode; } - void insert(iterator pos, iterator beg, Iterator end) { - ... + template <typename iterator2> + void insert(iterator pos, iterator2 first, iterator2 last) { + for (; first != last; ++first) + insert(pos, *first); } - void erase(iterator beg, Iterator end) { - ... + iterator erase(iterator pos) { + assert(pos != end()); + + NodeBase *next = pos._node->_next; + NodeBase *prev = pos._node->_prev; + Node<T> *node = static_cast<Node<T> *>(pos._node); + prev->_next = next; + next->_prev = prev; + delete node; + return next; } - void remove(const T &val) { + iterator erase(iterator first, iterator last) { + while (first != last) + erase(first++); + return last; } +// void remove(const T &val) { +// ... +// } + List<T>& operator =(const List<T>& list) { - // Careful here: handle self-assignment properly! I.e. situations like - // List x; - // ... - // x = x; - // In particular, we can't just do this: - // clear(); - // insert(_first, list.begin(), list.end()); - ... + if (this != &list) { + // TODO: This could (and should) be optimized, by reusing + // the existing nodes... + clear(); + insert(begin(), list.begin(), list.end()); + } + + return *this; } uint size() const { - int size = 0; + int n = 0; for (const_iterator i = begin(); i != end(); ++i) - size++; - return size; + ++n; + return n; } void clear() { @@ -122,13 +184,12 @@ public: } bool isEmpty() const { - return (_anchor._node == _anchor._node._next); + return (_anchor == _anchor->_next); } iterator begin() { - Iterator iter = _anchor; - return ++iter; + return _anchor->_next; } iterator end() { @@ -136,15 +197,13 @@ public: } const_iterator begin() const { - Iterator iter = _anchor; - return ++iter; + return _anchor->_next; } const_iterator end() const { return _anchor; } }; -*/ } // End of namespace Common |