Renamed template class 'List' to 'Array', since that is really what it is (a resizable array, not a linked list)

svn-id: r13520

4 files changed, 241 insertions, 90 deletions

diff --git a/common/array.h b/common/array.h
new file mode 100644
index 0000000000..9a40a392c4
--- /dev/null
+++ b/common/array.h
@@ -0,0 +1,170 @@
+/* ScummVM - Scumm Interpreter
+ * Copyright (C) 2002-2004 The ScummVM project
+ *
+ * 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., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
+ *
+ * $Header$
+ */
+
+#ifndef COMMON_ARRAY_H
+#define COMMON_ARRAY_H
+
+#include "common/scummsys.h"
+#include <assert.h>
+
+namespace Common {
+
+template <class T>
+class Array {
+protected:
+	int _capacity;
+	int _size;
+	T *_data;
+
+public:
+	typedef T *iterator;
+	typedef const T *const_iterator;
+
+public:
+	Array<T>() : _capacity(0), _size(0), _data(0) {}
+	Array<T>(const Array<T>& array) : _capacity(0), _size(0), _data(0) {
+		_size = array._size;
+		_capacity = _size + 32;
+		_data = new T[_capacity];
+		for (int i = 0; i < _size; i++)
+			_data[i] = array._data[i];
+	}
+
+	~Array<T>() {
+		if (_data)
+			delete [] _data;
+	}
+
+	void push_back(const T& element) {
+		ensureCapacity(_size + 1);
+		_data[_size++] = element;
+	}
+
+	void push_back(const Array<T>& array) {
+		ensureCapacity(_size + array._size);
+		for (int i = 0; i < array._size; i++)
+			_data[_size++] = array._data[i];
+	}
+
+	void insert_at(int idx, const T& element) {
+		assert(idx >= 0 && idx <= _size);
+		ensureCapacity(_size + 1);
+		// The following loop is not efficient if you can just memcpy things around.
+		// e.g. if you have a list of ints. But for real objects (String...), memcpy
+		// usually isn't correct (specifically, for any class which has a non-default
+		// copy behaviour. E.g. the String class uses a refCounter which has to be
+		// updated whenever a String is copied.
+		for (int i = _size; i > idx; i--) {
+			_data[i] = _data[i-1];
+		}
+		_data[idx] = element;
+		_size++;
+	}
+
+	T& remove_at(int idx) {
+		T& tmp;
+
+		assert(idx >= 0 && idx < _size);
+		tmp = _data[idx];
+		for (int i = idx; i < _size - 1; i++)
+			_data[i] = _data[i+1];
+		_size--;
+		return tmp;
+	}
+
+	// TODO: insert, remove, ...
+
+	T& operator [](int idx) {
+		assert(idx >= 0 && idx < _size);
+		return _data[idx];
+	}
+
+	const T& operator [](int idx) const {
+		assert(idx >= 0 && idx < _size);
+		return _data[idx];
+	}
+
+	Array<T>& operator  =(const Array<T>& array) {
+		if (_data)
+			delete [] _data;
+		_size = array._size;
+		_capacity = _size + 32;
+		_data = new T[_capacity];
+		for (int i = 0; i < _size; i++)
+			_data[i] = array._data[i];
+
+		return *this;
+	}
+
+	uint size() const {
+		return _size;
+	}
+
+	void clear() {
+		if (_data) {
+			delete [] _data;
+			_data = 0;
+		}
+		_size = 0;
+		_capacity = 0;
+	}
+	
+	bool isEmpty() const { 
+		return (_size == 0);
+	}
+
+
+	iterator		begin() {
+		return _data;
+	}
+
+	iterator		end() {
+		return _data + _size;
+	}
+
+	const_iterator	begin() const {
+		return _data;
+	}
+
+	const_iterator	end() const {
+		return _data + _size;
+	}
+
+protected:
+	void ensureCapacity(int new_len) {
+		if (new_len <= _capacity)
+			return;
+
+		T *old_data = _data;
+		_capacity = new_len + 32;
+		_data = new T[_capacity];
+
+		if (old_data) {
+			// Copy old data
+			for (int i = 0; i < _size; i++)
+				_data[i] = old_data[i];
+			delete [] old_data;
+		}
+	}
+};
+
+} // End of namespace Common
+
+#endif
diff --git a/common/config-manager.h b/common/config-manager.h
index 7f01ad01e9..2488e40696 100644
--- a/common/config-manager.h
+++ b/common/config-manager.h
@@ -23,7 +23,7 @@
 #ifndef COMMON_CONFIG_H
 #define COMMON_CONFIG_H
 
-#include "common/list.h"
+#include "common/array.h"
 #include "common/map.h"
 #include "common/singleton.h"
 #include "common/str.h"
@@ -127,7 +127,7 @@ private:
 	DomainMap		_globalDomains;
 	Domain			_defaultsDomain;
 	
-	List<Domain *>	_searchOrder;
+	Array<Domain *>	_searchOrder;
 
 	String			_activeDomain;
 	String			_filename;
diff --git a/common/list.h b/common/list.h
index fd09ea0d9f..eabf8a4701 100644
--- a/common/list.h
+++ b/common/list.h
@@ -26,25 +26,48 @@
 
 namespace Common {
 
+/*
+TODO: Add a true list class, based on a linked list data structure
+
 template <class T>
 class List {
 protected:
-	int _capacity;
-	int _size;
-	T *_data;
+	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;
+	
+	public:
+		Node<T> &operator++() {
+			_node = _node->_next;
+		}
+		
+		T& operator*() const {
+			return _node->_data;
+		}
+		T* operator->() const {
+			return &(_node->_data);
+		}
+	};
+
+	Iterator<T> *_anchor;
 
 public:
-	typedef T *iterator;
-	typedef const T *const_iterator;
+	typedef Node<T> *iterator;
+	typedef const Node<T> *const_iterator;
 
 public:
-	List<T>() : _capacity(0), _size(0), _data(0) {}
-	List<T>(const List<T>& list) : _capacity(0), _size(0), _data(0) {
-		_size = list._size;
-		_capacity = _size + 32;
-		_data = new T[_capacity];
-		for (int i = 0; i < _size; i++)
-			_data[i] = list._data[i];
+	List<T>() : _anchor(...) {}
+	List<T>(const List<T>& list) : _anchor(...) {
+		... copy list ...
 	}
 
 	~List<T>() {
@@ -53,117 +76,75 @@ public:
 	}
 
 	void push_back(const T& element) {
-		ensureCapacity(_size + 1);
-		_data[_size++] = element;
+		...
 	}
 
 	void push_back(const List<T>& list) {
-		ensureCapacity(_size + list._size);
-		for (int i = 0; i < list._size; i++)
-			_data[_size++] = list._data[i];
-	}
-
-	void insert_at(int idx, const T& element) {
-		assert(idx >= 0 && idx <= _size);
-		ensureCapacity(_size + 1);
-		// The following loop is not efficient if you can just memcpy things around.
-		// e.g. if you have a list of ints. But for real objects (String...), memcpy
-		// usually isn't correct (specifically, for any class which has a non-default
-		// copy behaviour. E.g. the String class uses a refCounter which has to be
-		// updated whenever a String is copied.
-		for (int i = _size; i > idx; i--) {
-			_data[i] = _data[i-1];
-		}
-		_data[idx] = element;
-		_size++;
+		...
 	}
 
-	T& remove_at(int idx) {
-		T& tmp;
-
-		assert(idx >= 0 && idx < _size);
-		tmp = _data[idx];
-		for (int i = idx; i < _size - 1; i++)
-			_data[i] = _data[i+1];
-		_size--;
-		return tmp;
+	void insert(iterator pos, const T& element) {
+		...
 	}
 
-	// TODO: insert, remove, ...
+	void insert(iterator pos, iterator beg, Iterator end) {
+		...
+	}
 
-	T& operator [](int idx) {
-		assert(idx >= 0 && idx < _size);
-		return _data[idx];
+	void erase(iterator beg, Iterator end) {
+		...
 	}
 
-	const T& operator [](int idx) const {
-		assert(idx >= 0 && idx < _size);
-		return _data[idx];
+	void remove(const T &val) {
 	}
 
-	List<T>& operator  =(const List<T>& list) {
-		if (_data)
-			delete [] _data;
-		_size = list._size;
-		_capacity = _size + 32;
-		_data = new T[_capacity];
-		for (int i = 0; i < _size; i++)
-			_data[i] = list._data[i];
 
-		return *this;
+	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());
+		...
 	}
 
 	uint size() const {
-		return _size;
+		int size = 0;
+		for (const_iterator i = begin(); i != end(); ++i)
+			size++;
+		return size;
 	}
 
 	void clear() {
-		if (_data) {
-			delete [] _data;
-			_data = 0;
-		}
-		_size = 0;
-		_capacity = 0;
+		erase(begin(), end());
 	}
 	
 	bool isEmpty() const { 
-		return (_size == 0);
+		return (_anchor._node == _anchor._node._next);
 	}
 
 
 	iterator		begin() {
-		return _data;
+		Iterator iter = _anchor;
+		return ++iter;
 	}
 
 	iterator		end() {
-		return _data + _size;
+		return _anchor;
 	}
 
 	const_iterator	begin() const {
-		return _data;
+		Iterator iter = _anchor;
+		return ++iter;
 	}
 
 	const_iterator	end() const {
-		return _data + _size;
-	}
-
-protected:
-	void ensureCapacity(int new_len) {
-		if (new_len <= _capacity)
-			return;
-
-		T *old_data = _data;
-		_capacity = new_len + 32;
-		_data = new T[_capacity];
-
-		if (old_data) {
-			// Copy old data
-			for (int i = 0; i < _size; i++)
-				_data[i] = old_data[i];
-			delete [] old_data;
-		}
+		return _anchor;
 	}
 };
+*/
 
 } // End of namespace Common
 
diff --git a/common/str.h b/common/str.h
index 2534dabd90..8697ca2871 100644
--- a/common/str.h
+++ b/common/str.h
@@ -22,7 +22,7 @@
 #define COMMON_STRING_H
 
 #include "common/scummsys.h"
-#include "common/list.h"
+#include "common/array.h"
 
 #include <assert.h>
 #include <string.h>
@@ -126,7 +126,7 @@ protected:
 bool operator == (const char *x, const ConstString &y);
 bool operator != (const char *x, const ConstString &y);
 
-class StringList : public List<String> {
+class StringList : public Array<String> {
 public:
 	void push_back(const char *str) {
 		ensureCapacity(_size + 1);