ResidualVM logo ResidualVM website - Forums - Contact us BuildBot - Doxygen - Wiki curved edge

common/list.h

Go to the documentation of this file.
00001 /* ScummVM - Graphic Adventure Engine
00002  *
00003  * ScummVM is the legal property of its developers, whose names
00004  * are too numerous to list here. Please refer to the COPYRIGHT
00005  * file distributed with this source distribution.
00006  *
00007  * This program is free software; you can redistribute it and/or
00008  * modify it under the terms of the GNU General Public License
00009  * as published by the Free Software Foundation; either version 2
00010  * of the License, or (at your option) any later version.
00011  *
00012  * This program is distributed in the hope that it will be useful,
00013  * but WITHOUT ANY WARRANTY; without even the implied warranty of
00014  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00015  * GNU General Public License for more details.
00016  *
00017  * You should have received a copy of the GNU General Public License
00018  * along with this program; if not, write to the Free Software
00019  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
00020  *
00021  */
00022 
00023 #ifndef COMMON_LIST_H
00024 #define COMMON_LIST_H
00025 
00026 #include "common/list_intern.h"
00027 
00028 namespace Common {
00029 
00034 template<typename t_T>
00035 class List {
00036 protected:
00037     typedef ListInternal::NodeBase      NodeBase;
00038     typedef ListInternal::Node<t_T>     Node;
00039 
00040     NodeBase _anchor;
00041 
00042 public:
00043     typedef ListInternal::Iterator<t_T>     iterator;
00044     typedef ListInternal::ConstIterator<t_T>    const_iterator;
00045 
00046     typedef t_T value_type;
00047     typedef uint size_type;
00048 
00049 public:
00050     List() {
00051         _anchor._prev = &_anchor;
00052         _anchor._next = &_anchor;
00053     }
00054     List(const List<t_T> &list) {
00055         _anchor._prev = &_anchor;
00056         _anchor._next = &_anchor;
00057 
00058         insert(begin(), list.begin(), list.end());
00059     }
00060 
00061     ~List() {
00062         clear();
00063     }
00064 
00068     void insert(iterator pos, const t_T &element) {
00069         insert(pos._node, element);
00070     }
00071 
00075     template<typename iterator2>
00076     void insert(iterator pos, iterator2 first, iterator2 last) {
00077         for (; first != last; ++first)
00078             insert(pos, *first);
00079     }
00080 
00085     iterator erase(iterator pos) {
00086         assert(pos != end());
00087         return iterator(erase(pos._node)._next);
00088     }
00089 
00094     iterator reverse_erase(iterator pos) {
00095         assert(pos != end());
00096         return iterator(erase(pos._node)._prev);
00097     }
00098 
00104     iterator erase(iterator first, iterator last) {
00105         NodeBase *f = first._node;
00106         NodeBase *l = last._node;
00107         while (f != l)
00108             f = erase(f)._next;
00109         return last;
00110     }
00111 
00115     void remove(const t_T &val) {
00116         NodeBase *i = _anchor._next;
00117         while (i != &_anchor)
00118             if (val == static_cast<Node *>(i)->_data)
00119                 i = erase(i)._next;
00120             else
00121                 i = i->_next;
00122     }
00123 
00125     void push_front(const t_T &element) {
00126         insert(_anchor._next, element);
00127     }
00128 
00130     void push_back(const t_T &element) {
00131         insert(&_anchor, element);
00132     }
00133 
00135     void pop_front() {
00136         assert(!empty());
00137         erase(_anchor._next);
00138     }
00139 
00141     void pop_back() {
00142         assert(!empty());
00143         erase(_anchor._prev);
00144     }
00145 
00147     t_T &front() {
00148         return static_cast<Node *>(_anchor._next)->_data;
00149     }
00150 
00152     const t_T &front() const {
00153         return static_cast<Node *>(_anchor._next)->_data;
00154     }
00155 
00157     t_T &back() {
00158         return static_cast<Node *>(_anchor._prev)->_data;
00159     }
00160 
00162     const t_T &back() const {
00163         return static_cast<Node *>(_anchor._prev)->_data;
00164     }
00165 
00166     List<t_T> &operator=(const List<t_T> &list) {
00167         if (this != &list) {
00168             iterator i;
00169             const iterator e = end();
00170             const_iterator i2;
00171             const_iterator e2 = list.end();
00172 
00173             for (i = begin(), i2 = list.begin(); (i != e) && (i2 != e2); ++i, ++i2) {
00174                 static_cast<Node *>(i._node)->_data = static_cast<const Node *>(i2._node)->_data;
00175             }
00176 
00177             if (i == e)
00178                 insert(i, i2, e2);
00179             else
00180                 erase(i, e);
00181         }
00182 
00183         return *this;
00184     }
00185 
00186     size_type size() const {
00187         size_type n = 0;
00188         for (const NodeBase *cur = _anchor._next; cur != &_anchor; cur = cur->_next)
00189             ++n;
00190         return n;
00191     }
00192 
00193     void clear() {
00194         NodeBase *pos = _anchor._next;
00195         while (pos != &_anchor) {
00196             Node *node = static_cast<Node *>(pos);
00197             pos = pos->_next;
00198             delete node;
00199         }
00200 
00201         _anchor._prev = &_anchor;
00202         _anchor._next = &_anchor;
00203     }
00204 
00205     bool empty() const {
00206         return (&_anchor == _anchor._next);
00207     }
00208 
00209 
00210     iterator        begin() {
00211         return iterator(_anchor._next);
00212     }
00213 
00214     iterator        reverse_begin() {
00215         return iterator(_anchor._prev);
00216     }
00217 
00218     iterator        end() {
00219         return iterator(&_anchor);
00220     }
00221 
00222     const_iterator  begin() const {
00223         return const_iterator(_anchor._next);
00224     }
00225 
00226     const_iterator  reverse_begin() const {
00227         return const_iterator(_anchor._prev);
00228     }
00229 
00230     const_iterator  end() const {
00231         return const_iterator(const_cast<NodeBase *>(&_anchor));
00232     }
00233 
00234 protected:
00235     NodeBase erase(NodeBase *pos) {
00236         NodeBase n = *pos;
00237         Node *node = static_cast<Node *>(pos);
00238         n._prev->_next = n._next;
00239         n._next->_prev = n._prev;
00240         delete node;
00241         return n;
00242     }
00243 
00247     void insert(NodeBase *pos, const t_T &element) {
00248         ListInternal::NodeBase *newNode = new Node(element);
00249         assert(newNode);
00250 
00251         newNode->_next = pos;
00252         newNode->_prev = pos->_prev;
00253         newNode->_prev->_next = newNode;
00254         newNode->_next->_prev = newNode;
00255     }
00256 };
00257 
00258 } // End of namespace Common
00259 
00260 #endif


Generated on Sat Feb 9 2019 05:00:35 for ResidualVM by doxygen 1.7.1
curved edge   curved edge