simple double linked list template class (completely untested)

svn-id: r13555

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