Rewrote Common::List iterator code to ensure const correctness is preserved.

We tried to implement the list iterators in a clever way, to reduce code
duplication. But this is essentially impossible to do properly, sadly --
this is one of the places where the ugly drawbacks of C++ really show.
As a consequence, our implementation had a bug which allowed one to
convert any const_iterator to an iterator, thus allowing modifying
elements of const lists.

This rewrite reintroduces code duplication but at least ensures that no
const list is written to accidentally.

Also fix some places which incorrectly used iterator instead of const_iterator
or (in the kyra code) accidentally wrote into a const list.

svn-id: r39279

1 files changed, 10 insertions, 93 deletions

diff --git a/common/list.h b/common/list.h
index 0372d217b7..325c8e8bd5 100644
--- a/common/list.h
+++ b/common/list.h
@@ -25,7 +25,7 @@
 #ifndef COMMON_LIST_H
 #define COMMON_LIST_H
 
-#include "common/scummsys.h"
+#include "common/list_intern.h"
 
 namespace Common {
 
@@ -33,100 +33,17 @@ namespace Common {
  * Simple double linked list, modeled after the list template of the standard
  * C++ library.
  */
-template<class t_T>
+template<typename t_T>
 class List {
 protected:
-#if defined (_WIN32_WCE) || defined (_MSC_VER)
-//FIXME evc4 and msvc7 doesn't like it as protected member
-public:
-#endif
-	struct NodeBase {
-		NodeBase *_prev;
-		NodeBase *_next;
-	};
-
-	template <class t_T2>
-	struct Node : public NodeBase {
-		t_T2 _data;
-
-		Node(const t_T2 &x) : _data(x) {}
-	};
-
-	template<class t_T2>
-	class Iterator {
-		template<class T> friend class Iterator;
-		friend class List<t_T>;
-		NodeBase *_node;
-
-#if !defined (__WINSCW__)
-		explicit Iterator(NodeBase *node) : _node(node) {}
-#else
-		Iterator(NodeBase *node) : _node(node) {}
-#endif
-
-	public:
-		Iterator() : _node(0) {}
-		template<class T>
-		Iterator(const Iterator<T> &c) : _node(c._node) {}
-
-		template<class T>
-		Iterator<t_T2> &operator=(const Iterator<T> &c) {
-			_node = c._node;
-			return *this;
-		}
-
-		// Prefix inc
-		Iterator<t_T2> &operator++() {
-			if (_node)
-				_node = _node->_next;
-			return *this;
-		}
-		// Postfix inc
-		Iterator<t_T2> operator++(int) {
-			Iterator tmp(_node);
-			++(*this);
-			return tmp;
-		}
-		// Prefix dec
-		Iterator<t_T2> &operator--() {
-			if (_node)
-				_node = _node->_prev;
-			return *this;
-		}
-		// Postfix dec
-		Iterator<t_T2> operator--(int) {
-			Iterator tmp(_node);
-			--(*this);
-			return tmp;
-		}
-		t_T2 &operator*() const {
-			assert(_node);
-#if (__GNUC__ == 2) && (__GNUC_MINOR__ >= 95)
-			return static_cast<List<t_T>::Node<t_T2> *>(_node)->_data;
-#else
-			return static_cast<Node<t_T2> *>(_node)->_data;
-#endif
-		}
-		t_T2 *operator->() const {
-			return &(operator*());
-		}
-
-		template<class T>
-		bool operator==(const Iterator<T> &x) const {
-			return _node == x._node;
-		}
-
-		template<class T>
-		bool operator!=(const Iterator<T> &x) const {
-			return _node != x._node;
-		}
-	};
+	typedef ListInternal::NodeBase		NodeBase;
+	typedef ListInternal::Node<t_T>		Node;
 
 	NodeBase _anchor;
 
 public:
-	typedef Iterator<t_T>			iterator;
-	typedef Iterator<const t_T>	const_iterator;
+	typedef ListInternal::Iterator<t_T>		iterator;
+	typedef ListInternal::ConstIterator<t_T>	const_iterator;
 
 	typedef t_T value_type;
 
@@ -155,7 +72,7 @@ public:
 	}
 
 	void insert(iterator pos, const t_T &element) {
-		NodeBase *newNode = new Node<t_T>(element);
+		ListInternal::NodeBase *newNode = new Node(element);
 
 		newNode->_next = pos._node;
 		newNode->_prev = pos._node->_prev;
@@ -174,7 +91,7 @@ public:
 
 		NodeBase *next = pos._node->_next;
 		NodeBase *prev = pos._node->_prev;
-		Node<t_T> *node = static_cast<Node<t_T> *>(pos._node);
+		Node *node = static_cast<Node *>(pos._node);
 		prev->_next = next;
 		next->_prev = prev;
 		delete node;
@@ -186,7 +103,7 @@ public:
 
 		NodeBase *next = pos._node->_next;
 		NodeBase *prev = pos._node->_prev;
-		Node<t_T> *node = static_cast<Node<t_T> *>(pos._node);
+		Node *node = static_cast<Node *>(pos._node);
 		prev->_next = next;
 		next->_prev = prev;
 		delete node;
@@ -221,7 +138,7 @@ public:
 			const_iterator j;
 
 			for (i = begin(), j = list.begin();  (i != end()) && (j != list.end()) ; ++i, ++j) {
-				static_cast<Node<t_T> *>(i._node)->_data = static_cast<Node<t_T> *>(j._node)->_data;
+				static_cast<Node *>(i._node)->_data = static_cast<const Node *>(j._node)->_data;
 			}
 
 			if (i == end())