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

4 files changed, 195 insertions, 96 deletions

diff --git a/common/archive.cpp b/common/archive.cpp
index 7f81ecc7fb..a39d78dd9e 100644
--- a/common/archive.cpp
+++ b/common/archive.cpp
@@ -67,7 +67,7 @@ int Archive::listMatchingMembers(ArchiveMemberList &list, const String &pattern)
 
 
 
-SearchSet::ArchiveNodeList::iterator SearchSet::find(const String &name) const {
+SearchSet::ArchiveNodeList::iterator SearchSet::find(const String &name) {
 	ArchiveNodeList::iterator it = _list.begin();
 	for ( ; it != _list.end(); ++it) {
 		if (it->_name == name)
@@ -76,6 +76,15 @@ SearchSet::ArchiveNodeList::iterator SearchSet::find(const String &name) const {
 	return it;
 }
 
+SearchSet::ArchiveNodeList::const_iterator SearchSet::find(const String &name) const {
+	ArchiveNodeList::const_iterator it = _list.begin();
+	for ( ; it != _list.end(); ++it) {
+		if (it->_name == name)
+			break;
+	}
+	return it;
+}
+
 /*
 	Keep the nodes sorted according to descending priorities.
 	In case two or node nodes have the same priority, insertion
@@ -203,7 +212,7 @@ SeekableReadStream *SearchSet::createReadStreamForMember(const String &name) con
 	if (name.empty())
 		return 0;
 
-	ArchiveNodeList::iterator it = _list.begin();
+	ArchiveNodeList::const_iterator it = _list.begin();
 	for ( ; it != _list.end(); ++it) {
 		SeekableReadStream *stream = it->_arc->createReadStreamForMember(name);
 		if (stream)
diff --git a/common/archive.h b/common/archive.h
index ba3445cc16..69e29a73f2 100644
--- a/common/archive.h
+++ b/common/archive.h
@@ -144,7 +144,8 @@ class SearchSet : public Archive {
 	typedef List<Node> ArchiveNodeList;
 	ArchiveNodeList _list;
 
-	ArchiveNodeList::iterator find(const String &name) const;
+	ArchiveNodeList::iterator find(const String &name);
+	ArchiveNodeList::const_iterator find(const String &name) const;
 
 	// Add an archive keeping the list sorted by ascending priorities.
 	void insert(const Node& node);
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())
diff --git a/common/list_intern.h b/common/list_intern.h
new file mode 100644
index 0000000000..79e2deb939
--- /dev/null
+++ b/common/list_intern.h
@@ -0,0 +1,172 @@
+/* ScummVM - Graphic Adventure Engine
+ *
+ * ScummVM is the legal property of its developers, whose names
+ * are too numerous to list here. Please refer to the COPYRIGHT
+ * file distributed with this source distribution.
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+ *
+ * $URL$
+ * $Id$
+ */
+
+#ifndef COMMON_LIST_INTERN_H
+#define COMMON_LIST_INTERN_H
+
+#include "common/scummsys.h"
+
+namespace Common {
+
+template<typename T> class List;
+
+
+namespace ListInternal {
+	struct NodeBase {
+		NodeBase *_prev;
+		NodeBase *_next;
+	};
+
+	template <typename T>
+	struct Node : public NodeBase {
+		T _data;
+
+		Node(const T &x) : _data(x) {}
+	};
+
+	template<typename T> class ConstIterator;
+
+	template<typename T>
+	struct Iterator {
+		typedef Iterator<T>	Self;
+		typedef Node<T> *	NodePtr;
+		typedef T &			ValueRef;
+		typedef T *			ValuePtr;
+
+		NodeBase *_node;
+
+		Iterator() : _node(0) {}
+		Iterator(NodeBase *node) : _node(node) {}
+
+		// Prefix inc
+		Self &operator++() {
+			if (_node)
+				_node = _node->_next;
+			return *this;
+		}
+		// Postfix inc
+		Self operator++(int) {
+			Self tmp(_node);
+			++(*this);
+			return tmp;
+		}
+		// Prefix dec
+		Self &operator--() {
+			if (_node)
+				_node = _node->_prev;
+			return *this;
+		}
+		// Postfix dec
+		Self operator--(int) {
+			Self tmp(_node);
+			--(*this);
+			return tmp;
+		}
+		ValueRef operator*() const {
+			assert(_node);
+			return static_cast<NodePtr>(_node)->_data;
+		}
+		ValuePtr operator->() const {
+			return &(operator*());
+		}
+
+		bool operator==(const Self &x) const {
+			return _node == x._node;
+		}
+
+		bool operator!=(const Self &x) const {
+			return _node != x._node;
+		}
+	};
+
+	template<typename T>
+	struct ConstIterator {
+		typedef ConstIterator<T>	Self;
+		typedef const Node<T> *	NodePtr;
+		typedef const T &		ValueRef;
+		typedef const T *		ValuePtr;
+
+		const NodeBase *_node;
+
+		ConstIterator() : _node(0) {}
+		ConstIterator(const NodeBase *node) : _node(node) {}
+		ConstIterator(const Iterator<T> &x) : _node(x._node) {}
+
+		// Prefix inc
+		Self &operator++() {
+			if (_node)
+				_node = _node->_next;
+			return *this;
+		}
+		// Postfix inc
+		Self operator++(int) {
+			Self tmp(_node);
+			++(*this);
+			return tmp;
+		}
+		// Prefix dec
+		Self &operator--() {
+			if (_node)
+				_node = _node->_prev;
+			return *this;
+		}
+		// Postfix dec
+		Self operator--(int) {
+			Self tmp(_node);
+			--(*this);
+			return tmp;
+		}
+		ValueRef operator*() const {
+			assert(_node);
+			return static_cast<NodePtr>(_node)->_data;
+		}
+		ValuePtr operator->() const {
+			return &(operator*());
+		}
+
+		bool operator==(const Self &x) const {
+			return _node == x._node;
+		}
+
+		bool operator!=(const Self &x) const {
+			return _node != x._node;
+		}
+	};
+
+
+	template<typename T>
+	bool operator==(const Iterator<T>& a, const ConstIterator<T>& b) {
+		return a._node == b._node;
+	}
+	
+	template<typename T>
+	bool operator!=(const Iterator<T>& a, const ConstIterator<T>& b) {
+		return a._node != b._node;
+	}
+}
+
+
+} // End of namespace Common
+
+#endif