rewrote config class; cleanup; code restructuring

svn-id: r4903

17 files changed, 828 insertions, 614 deletions

diff --git a/common/config-file.cpp b/common/config-file.cpp
index 17b9fb2b4f..18ac0009c9 100644
--- a/common/config-file.cpp
+++ b/common/config-file.cpp
@@ -20,30 +20,15 @@
  *
  */
 
+#include "stdafx.h"
 #include <stdio.h>
 #include <stdlib.h>
-#include "stdafx.h"
+#include <string.h>
 #include "config-file.h"
-#include "scumm.h"
+#include "engine.h" // for debug()
 
 #define MAXLINELEN 256
 
-#define xfree(p) {if (p) free(p);}
-
-#ifdef NEED_STRDUP
-char *strdup(const char *s) {
-	if (s) {
-		int len = strlen(s) + 1;
-		char *d = (char *)malloc(len);
-		if (d)
-			memcpy(d, s, len);
-		return d;
-	}
-	return NULL;
-}
-#endif /* NEED_STRDUP */
-
-
 static char *ltrim(char *t)
 {
 	for (; *t && (*t == ' '); t++);
@@ -64,115 +49,16 @@ static char *rtrim(char *t)
 	return t;
 }
 
-class hashconfig {
-public:
-	hashconfig (const char *);
-	 ~hashconfig ();
-	bool is_domain(const char *) const;
-	const char *get(const char *) const;
-	const char *set(const char *, const char *);
-	const char *getdomain() const;
-	void flush(FILE *) const;
-	void rename(const char *);
-	void merge(const hashconfig *);
-private:
-	char *domain;
-	char **keys, **values;
-	int nkeys;
-};
-
-hashconfig::hashconfig (const char *dom):domain(dom ? strdup(dom) : 0),
-keys(0), values(0), nkeys(0)
-{
-}
-
-hashconfig::~hashconfig () {
-	xfree(domain);
-}
-
-bool hashconfig::is_domain(const char *d) const
-{
-	return d && domain && !strcmp(d, domain);
-}
-
-const char *hashconfig::get(const char *key) const
-{
-	int i;
-
-	for (i = 0; i < nkeys; i++) {
-		if (!strcmp(key, keys[i])) {
-			return values[i];
-		}
-	}
-
-	return 0;
-}
-
-const char *hashconfig::set(const char *key, const char *value)
-{
-	int i;
-
-	for (i = 0; i < nkeys; i++) {
-		if (!strcmp(key, keys[i])) {
-			xfree(values[i]);
-			return values[i] = value ? strdup(value) : 0;
-		}
-	}
-
-	nkeys++;
-	keys = (char **)realloc(keys, nkeys * sizeof(char *));
-	values = (char **)realloc(values, nkeys * sizeof(char *));
-	keys[nkeys - 1] = strdup(key);
-	return values[nkeys - 1] = value ? strdup(value) : 0;
-}
-
-const char *hashconfig::getdomain() const
-{
-	return domain;
-}
-
-void hashconfig::flush(FILE *cfg_file) const
-{
-	int i;
-
-	if (!domain)
-		return;
-
-	fprintf(cfg_file, "[%s]\n", domain);
-
-	for (i = 0; i < nkeys; i++) {
-		if (values[i]) {
-			fprintf(cfg_file, "%s=%s\n", keys[i], values[i]);
-		}
-	}
-	fprintf(cfg_file, "\n");
-}
-
-void hashconfig::rename(const char *d)
-{
-	xfree(domain);
-	domain = d ? strdup(d) : 0;
-}
-
-void hashconfig::merge(const hashconfig *h)
-{
-	int i;
-
-	for (i = 0; i < h->nkeys; i++) {
-		set(h->keys[i], h->values[i]);
-	}
-}
-
-// The config-class itself.
+// The config-class itself.
 
-Config::Config (const char *cfg, const char *d)
-: filename(strdup(cfg)), domain(d ? strdup(d) : 0), hash(0), ndomains(0), willwrite(false)
+Config::Config (const String &cfg, const String &d)
+ : filename(cfg), defaultDomain(d), willwrite(false)
 {
 	FILE *cfg_file;
 	char t[MAXLINELEN];
 
-	if (!(cfg_file = fopen(cfg, "r"))) {
-		debug(1, "Unable to open configuration file: %s.\n", filename);
+	if (!(cfg_file = fopen(filename.c_str(), "r"))) {
+		debug(1, "Unable to open configuration file: %s.\n", filename.c_str());
 	} else {
 		while (!feof(cfg_file)) {
 			if (!fgets(t, MAXLINELEN, cfg_file))
@@ -189,7 +75,7 @@ Config::Config (const char *cfg, const char *d)
 					}
 				} else {
 					// It's a new key in the domain.
-					if (!domain) {
+					if (defaultDomain.isEmpty()) {
 						debug(1, "Config file buggy: we have a key without a domain first.\n");
 					}
 					char *p = strchr(t, '\n');
@@ -217,35 +103,22 @@ Config::Config (const char *cfg, const char *d)
 	}
 }
 
-Config::~Config () {
-	int i;
-
-	xfree(filename);
-	xfree(domain);
-
-	for (i = 0; i < ndomains; i++) {
-		delete hash[i];
-	}
-	xfree(hash);
-}
-
-const char *Config::get(const char *key, const char *d) const
+const char *Config::get(const String &key, const String &d) const
 {
-	int i;
+	String domain;
 
-	if (!d)
-		d = domain;
+	if (d.isEmpty())
+		domain = defaultDomain;
+	else
+		domain = d;
 
-	for (i = 0; i < ndomains; i++) {
-		if (hash[i]->is_domain(d)) {
-			return hash[i]->get(key);
-		}
-	}
+	if (domains.contains(domain) && domains[domain].contains(key))
+		return domains[domain][key].c_str();
 
 	return 0;
 }
 
-const int Config::getInt(const char *key, int def, const char *d) const
+const int Config::getInt(const String &key, int def, const String &d) const
 {
 	const char *value = get(key, d);
 	
@@ -254,7 +127,7 @@ const int Config::getInt(const char *key, int def, const char *d) const
 	return def;
 }
 
-const bool Config::getBool(const char *key, bool def, const char *d) const
+const bool Config::getBool(const String &key, bool def, const String &d) const
 {
 	const char *value = get(key, d);
 	
@@ -263,133 +136,93 @@ const bool Config::getBool(const char *key, bool def, const char *d) const
 	return def;
 }
 
-const char *Config::set(const char *key, const char *value, const char *d)
+void Config::set(const String &key, const String &value, const String &d)
 {
-	int i;
+	String domain;
 
-	if (!d)
-		d = domain;
+	if (d.isEmpty())
+		domain = defaultDomain;
+	else
+		domain = d;
 
-	for (i = 0; i < ndomains; i++) {
-		if (hash[i]->is_domain(d)) {
-			return hash[i]->set(key, value);
-		}
-	}
-
-	ndomains++;
-	hash = (hashconfig **)realloc(hash, ndomains * sizeof(hashconfig *));
-	hash[ndomains - 1] = new hashconfig (d);
-
-	return hash[ndomains - 1]->set(key, value);
+	domains[domain][key] = value;
 }
 
-const char *Config::set(const char *key, int value_i, const char *d)
+void Config::setInt(const String &key, int value_i, const String &d)
 {
 	char value[MAXLINELEN];
 	sprintf(value, "%i", value_i);
-	return set(key, value, d);
+	set(key, String(value), d);
 }
 
-const char *Config::set(const char *key, bool value_b, const char *d)
+void Config::setBool(const String &key, bool value_b, const String &d)
 {
-	const char *value = value_b ? "true" : "false";
-	return set(key, value, d);
+	String value(value_b ? "true" : "false");
+	set(key, value, d);
 }
 
-void Config::set_domain(const char *d)
+void Config::set_domain(const String &d)
 {
-	int i;
-	xfree(domain);
-	domain = d ? strdup(d) : 0;
-
-	for (i = 0; i < ndomains; i++) {
-		if (hash[i]->is_domain(domain))
-			return;
-	}
-	ndomains++;
-	hash = (hashconfig **)realloc(hash, ndomains * sizeof(hashconfig *));
-	hash[ndomains - 1] = new hashconfig (domain);
+	defaultDomain = d;
 }
 
 void Config::flush() const
 {
 	FILE *cfg_file;
-	int i;
 
 	if (!willwrite)
 		return;
 
-	if (!(cfg_file = fopen(filename, "w"))) {
-		debug(1, "Unable to write configuration file: %s.\n", filename);
+	if (!(cfg_file = fopen(filename.c_str(), "w"))) {
+		debug(1, "Unable to write configuration file: %s.\n", filename.c_str());
 	} else {
-		for (i = 0; i < ndomains; i++) {
-			hash[i]->flush(cfg_file);
+		DomainMap::Iterator d;
+		for (d = domains.begin(); d != domains.end(); ++d) {
+			fprintf(cfg_file, "[%s]\n", d->_key.c_str());
+			
+			const StringMap &data = d->_value;
+			StringMap::Iterator x;
+			for (x = data.begin(); x != data.end(); ++x) {
+				const String &value = x->_value;
+				if (!value.isEmpty())
+					fprintf(cfg_file, "%s=%s\n", x->_key.c_str(), value.c_str());
+			}
+			fprintf(cfg_file, "\n");
 		}
 		fclose(cfg_file);
 	}
 }
 
-void Config::rename_domain(const char *d)
+void Config::rename_domain(const String &d)
 {
-	int i, index = -1;
+	if (d == defaultDomain)
+		return;
 
-	for (i = 0; i < ndomains; i++) {
-		if (hash[i]->is_domain(d)) {
-			index = i;
-		}
-	}
+	StringMap &oldHash = domains[defaultDomain];
+	StringMap &newHash = domains[d];
 
-	for (i = 0; i < ndomains; i++) {
-		if (hash[i]->is_domain(domain)) {
-			if (index >= 0) {
-				hash[i]->merge(hash[index]);
-				hash[index]->rename(0);
-				rename_domain(d);
-			} else {
-				hash[i]->rename(d);
-				set_domain(d);
-			}
-		}
-	}
+	newHash.merge(oldHash);
+	
+	domains.remove(defaultDomain);
+	
+	defaultDomain = d;
 }
 
-void Config::delete_domain(const char *d)
+void Config::delete_domain(const String &d)
 {
-	int i;
-
-	for (i = 0; i < ndomains; i++) {
-		if (hash[i]->is_domain(d)) {
-			hash[i]->rename(0);
-		}
-	}
+	domains.remove(d);
 }
 
-void Config::change_filename(const char *f)
+void Config::set_filename(const String &f)
 {
-	xfree(filename);
-	filename = f ? strdup(f) : 0;
+	filename = f;
 }
 
-void Config::merge_config(const Config *c)
+void Config::merge_config(const Config &c)
 {
-	int i, j;
-	bool found;
-
-	for (i = 0; i < c->ndomains; i++) {
-		found = false;
-		for (j = 0; j < ndomains; j++) {
-			if (hash[j]->is_domain(c->hash[i]->getdomain())) {
-				hash[j]->merge(c->hash[i]);
-				found = true;
-				break;
-			}
-		}
-		if (!found) {
-			ndomains++;
-			hash = (hashconfig **)realloc(hash, ndomains * sizeof(hashconfig *));
-			hash[ndomains - 1] = new hashconfig (domain);
-			hash[ndomains - 1]->merge(c->hash[i]);
-		}
+	DomainMap::Iterator d, end(c.domains.end());
+	for (d = c.domains.begin(); d != end; ++d) {
+		domains[d->_key].merge(d->_value);
 	}
 }
 
diff --git a/common/config-file.h b/common/config-file.h
index eee4cfde59..594b4814c0 100644
--- a/common/config-file.h
+++ b/common/config-file.h
@@ -23,31 +23,39 @@
 #ifndef CONFIG_FILE_H
 #define CONFIG_FILE_H
 
-class hashconfig;
+#include "common/util.h"
+#include "common/map.h"
+#include "common/str.h"
 
 class Config {
 public:
-	Config (const char * = "config.cfg", const char * = "default");
-	 ~Config ();
-	const char *get(const char *key, const char *dom = 0) const;
-	const int getInt(const char *key, int def = 0, const char *dom = 0) const;
-	const bool getBool(const char *key, bool def = false, const char *dom = 0) const;
+	typedef ScummVM::String String;
 
-	const char *set(const char *key, const char *value, const char *dom = 0);
-	const char *set(const char *key, int value, const char *dom = 0);
-	const char *set(const char *key, bool value, const char *dom = 0);
+	Config (const String & = String("config.cfg"), const String & = String("default"));
+	const char *get(const String &key, const String &dom = String()) const;
+	const int getInt(const String &key, int def = 0, const String &dom = String()) const;
+	const bool getBool(const String &key, bool def = false, const String &dom = String()) const;
 
-	void set_domain(const char *);
+	void set(const String &key, const String &value, const String &dom = String());
+	void setInt(const String &key, int value, const String &dom = String());
+	void setBool(const String &key, bool value, const String &dom = String());
+
+	void set_domain(const String &);
 	void flush() const;
-	void rename_domain(const char *);
-	void delete_domain(const char *);
-	void change_filename(const char *);
-	void merge_config(const Config *);
+	void rename_domain(const String &);
+	void delete_domain(const String &);
+	void set_filename(const String &);
+	void merge_config(const Config &);
 	void set_writing(bool);
-private:
-	char *filename, *domain;
-	hashconfig **hash;
-	int ndomains;
+
+protected:
+	typedef ScummVM::StringMap StringMap;
+	typedef ScummVM::Map<String, StringMap> DomainMap;
+
+	DomainMap domains;
+	String filename;
+	String defaultDomain;
+
 	bool willwrite;
 };
 
diff --git a/common/engine.cpp b/common/engine.cpp
index 9a53b69094..a31db7d641 100644
--- a/common/engine.cpp
+++ b/common/engine.cpp
@@ -22,7 +22,7 @@
 #include "engine.h"
 #include "gameDetector.h"
 #include "config-file.h"
-#include "scumm.h"
+#include "scumm/scumm.h"
 #include "simon/simon.h"
 #include "sound/mixer.h"
 
diff --git a/common/engine.h b/common/engine.h
index 8ca47dd17e..944acce1c0 100644
--- a/common/engine.h
+++ b/common/engine.h
@@ -24,6 +24,9 @@
 #include "scummsys.h"
 #include "system.h"
 
+#define SCUMMVM_VERSION "0.2.2 CVS"
+#define SCUMMVM_CVS "2002-09-06"
+
 class SoundMixer;
 class GameDetector;
 
diff --git a/common/file.cpp b/common/file.cpp
index abc71d1ff3..58bb8b559b 100644
--- a/common/file.cpp
+++ b/common/file.cpp
@@ -20,6 +20,7 @@
  */
 
 #include "file.h"
+#include "engine.h"	// For debug/warning/error
 
 File::File() {
 	_handle = NULL;
diff --git a/common/file.h b/common/file.h
index 807dcfab0a..691f06f57d 100644
--- a/common/file.h
+++ b/common/file.h
@@ -19,13 +19,12 @@
  *
  */
 
+#ifndef COMMON_FILE_H
+#define COMMON_FILE_H
+
 #include <stdio.h>
 #include "stdafx.h"
 #include "scummsys.h"
-#include "scumm.h"
-
-#ifndef FILE_H
-#define FILE_H
 
 class File {
 private:
diff --git a/common/gameDetector.cpp b/common/gameDetector.cpp
index 56c2eec937..2316331e73 100644
--- a/common/gameDetector.cpp
+++ b/common/gameDetector.cpp
@@ -139,7 +139,7 @@ void GameDetector::parseCommandLine(int argc, char **argv)
 			case 'a':
 				CHECK_OPTION();
 				_amiga = (c == 'a');
-				scummcfg->set("amiga", _amiga);
+				scummcfg->setBool("amiga", _amiga);
 				break;
 			case 'b':
 				HANDLE_OPTION();
@@ -148,7 +148,7 @@ void GameDetector::parseCommandLine(int argc, char **argv)
 			case 'c':
 				HANDLE_OPTION();
 				_cdrom = atoi(option);
-				scummcfg->set("cdrom", _cdrom);
+				scummcfg->setInt("cdrom", _cdrom);
 				break;
 			case 'd':
 				_debugMode = true;
@@ -166,7 +166,7 @@ void GameDetector::parseCommandLine(int argc, char **argv)
 			case 'f':
 				CHECK_OPTION();
 				_fullScreen = (c == 'f');
-				scummcfg->set("fullscreen", _fullScreen, "scummvm");
+				scummcfg->setBool("fullscreen", _fullScreen, "scummvm");
 				break;
 			case 'g':
 				HANDLE_OPTION();
@@ -179,7 +179,7 @@ void GameDetector::parseCommandLine(int argc, char **argv)
 				HANDLE_OPTION();
 				{
 					Config * newconfig = new Config(option, "scummvm");
-					scummcfg->merge_config(newconfig);
+					scummcfg->merge_config(*newconfig);
 					delete newconfig;
 					updateconfig();
 					break;
@@ -188,12 +188,12 @@ void GameDetector::parseCommandLine(int argc, char **argv)
 			case 'm':
 				HANDLE_OPTION();
 				_music_volume = atoi(option);
-				scummcfg->set("music_volume", _music_volume);
+				scummcfg->setInt("music_volume", _music_volume);
 				break;
 			case 'n':
 				CHECK_OPTION();
 				_noSubtitles = (c == 'n');
-				scummcfg->set("nosubtitles", _noSubtitles);
+				scummcfg->setBool("nosubtitles", _noSubtitles);
 				break;
 			case 'p':
 				HANDLE_OPTION();
@@ -207,7 +207,7 @@ void GameDetector::parseCommandLine(int argc, char **argv)
 			case 's':
 				HANDLE_OPTION();
 				_sfx_volume = atoi(option);
-				scummcfg->set("sfx_volume", _sfx_volume);
+				scummcfg->setInt("sfx_volume", _sfx_volume);
 				break;
 			case 't':
 				HANDLE_OPTION();
@@ -227,20 +227,20 @@ void GameDetector::parseCommandLine(int argc, char **argv)
 				scummcfg->set_writing(true);
 				HANDLE_OPT_OPTION();
 				if (option != NULL)
-					scummcfg->change_filename(option);
+					scummcfg->set_filename(option);
 				break;
 			case 'x':
 				_save_slot = 0;
 				HANDLE_OPT_OPTION();
 				if (option != NULL) {
 					_save_slot = atoi(option);
-					scummcfg->set("save_slot", _save_slot);
+					scummcfg->setInt("save_slot", _save_slot);
 				}
 				break;
 			case 'y':
 				HANDLE_OPTION();
 				_talkSpeed = atoi(option);				
-				scummcfg->set("talkspeed", _talkSpeed);
+				scummcfg->setInt("talkspeed", _talkSpeed);
 				break;
 			default:
 				goto ShowHelpAndExit;
diff --git a/common/list.h b/common/list.h
new file mode 100644
index 0000000000..87e8b5ab34
--- /dev/null
+++ b/common/list.h
@@ -0,0 +1,121 @@
+/* ScummVM - Scumm Interpreter
+ * Copyright (C) 2002 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_LIST_H
+#define COMMON_LIST_H
+
+#include "scummsys.h"
+
+namespace ScummVM {
+
+template <class T>
+class List {
+protected:
+	int		_capacity;
+	int		_size;
+	T		*_data;
+
+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>()
+	{
+		if (_data)
+			delete [] _data;
+	}
+	
+	void push_back(const T& str)
+	{
+		ensureCapacity(_size + 1);
+		_data[_size++] = str;
+	}
+	
+	// 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];
+	}
+
+	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;
+	}
+
+	int size() const	{ return _size; }
+
+	void clear()
+	{
+		if (_data) {
+			delete [] _data;
+			_data = 0;
+		}
+		_size = 0;
+		_capacity = 0;
+	}
+	
+	bool isEmpty() const	{ return (_size == 0); }
+
+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 ScummVM
+
+#endif
diff --git a/common/main.cpp b/common/main.cpp
index 1d1adf9dfb..8ce167f382 100644
--- a/common/main.cpp
+++ b/common/main.cpp
@@ -22,10 +22,8 @@
 
 #include "stdafx.h"
 #include "engine.h"
-#include "scumm.h"
 #include "sound/mididrv.h"
 #include "gameDetector.h"
-#include "simon/simon.h"
 #include "config-file.h"
 
 GameDetector detector;
diff --git a/common/map.h b/common/map.h
new file mode 100644
index 0000000000..4d3b3f26ac
--- /dev/null
+++ b/common/map.h
@@ -0,0 +1,249 @@
+/* ScummVM - Scumm Interpreter
+ * Copyright (C) 2002 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_MAP_H
+#define COMMON_MAP_H
+
+#include "scummsys.h"
+
+namespace ScummVM {
+
+template <class Key, class Value>
+class Map {
+protected:
+	struct Node {
+		Node *_parent;
+		Node *_left, *_right;
+		Key _key;
+		Value _value;
+		Node() {}
+		Node(const Key &key, Node *parent) : _parent(parent), _key(key) {}
+	};
+	
+	Node *_root;
+	Node *_header;
+
+	class Iterator {
+		Node *_node;
+		
+	public:
+		Iterator(Node *node = 0) : _node(node) {}
+		Node &operator *() { assert(_node != 0); return *_node; }
+		const Node &operator *() const { assert(_node != 0); return *_node; }
+        const Node *operator->() const { assert(_node != 0); return _node; }
+        bool operator !=(const Iterator &iter) const { return _node != iter._node; }
+		void operator ++()
+		{
+			if (!_node)
+				return;
+			if (_node->_right) {
+				_node = _node->_right;
+				while (_node->_left)
+					_node = _node->_left;
+			} else {
+				Node *parent = _node->_parent;
+				while (_node == parent->_right) {
+					_node = parent;
+					parent = _node->_parent;
+				}
+				
+				if (_node->_right != parent)
+					_node = parent;
+			}
+			
+			if (_node->_parent == 0)
+				_node = 0;
+		}
+	};
+
+public:
+	Map<Key, Value>() : _root(0)
+	{
+		_header = new Node();
+		_header->_right = _header->_left = _header;
+	}
+
+	/*
+	 * Return the object for the given key. If no match is found, a new entry
+	 * with the given key and the default data value is inserted.
+	 */
+	Value &operator [](const Key &key)
+	{
+		Node *node;
+		if (!_root)
+			node = _root = new Node(key, _header);
+		else
+			node = createNode(_root, key);
+		return node->_value;
+	}
+
+	const Value &operator [](const Key &key) const
+	{
+		Node *node = findNode(_root, key);
+		assert(node != 0);
+		return node->_value;
+	}
+	
+	bool contains(const Key &key) const
+	{
+		return (findNode(_root, key) != 0);
+	}
+
+	void clear()
+	{
+		clearNodes(_root);
+		_root = 0;
+	}
+
+	bool isEmpty() const
+	{
+		return (_root == 0);
+	}
+
+	void remove(const Key &key)
+	{
+		// TODO - implement efficiently. Indeed, maybe switch to using red-black trees?
+		// For now, just a lame, bad remove algorithm. Rule: don't remove elements
+		// from one of our maps if you need to be efficient :-)
+		Node *node = findNode(_root, key);
+		if (!node)
+			return;
+		
+		// Now we have to remove 'node'. There are two simple cases and one hard.
+		Node *parent = node->_parent;
+		Node *rep;
+		if (!node->_left) {
+			rep = node->_right;
+		} else if (!node->_right) {
+			rep = node->_left;
+		} else {
+			// We have to do it the hard way since both children are present.
+			Node *n2;
+			
+			n2 = rep = node->_right;
+			
+			// Now insert the left child leftmost into our right child
+			while (n2->_left)
+				n2 = n2->_left;
+			n2->_left = node->_left;
+			n2->_left->_parent = n2;
+		}
+
+		// Replace this node with node 'rep'
+		if (rep)
+			rep->_parent = parent;
+		if (!parent) // Root node?
+			_root = rep;
+		else if (parent->_left == node)
+			parent->_left = rep;
+		else
+			parent->_right = rep;
+		
+		// Finally free the allocated memory
+		delete node;
+	}
+	
+	void merge(Map<Key, Value> map)
+	{
+		// FIXME - this is a very bad algorithm.
+		// Right now we insert the items from 'map' using the default iterator,
+		// which gives us the objects ordered, leading to an unbalanced tree.
+		// This could be fixed by switching to a red black tree, or by using a 
+		// different walk order (infix comes to mind).
+		if (map.isEmpty())
+			return;
+		Iterator x(map.begin()), end(map.end());
+		for (; x != end; ++x) {
+			(*this)[x->_key] = x->_value;
+		}
+	}
+	
+	Iterator	begin() const
+	{
+		Node *node = _root;
+		if (node) {
+			while (node->_left)
+				node = node->_left;
+		}
+		return Iterator(node);
+	}
+	
+	Iterator	end() const
+	{
+		return Iterator();
+	}
+
+protected:
+	// Find the node matching the given key, if any
+	Node *findNode(Node *node, const Key &key) const
+	{
+		while (node && (key != node->_key)) {
+			if (key < node->_key) {
+				node = node->_left;
+			} else {
+				node = node->_right;
+			}
+		}
+		return node;
+	}
+
+	Node *createNode(Node *node, const Key &key)
+	{
+		Node *prevNode = 0;
+		bool left = true;
+		while (node) {
+			prevNode = node;
+			if (key == node->_key) {
+				return node;
+			} else if (key < node->_key) {
+				left = true;
+				node = node->_left;
+			} else {
+				left = false;
+				node = node->_right;
+			}
+		}
+		node = new Node(key, prevNode);
+		if (left) {
+			prevNode->_left = node;
+		} else {
+			prevNode->_right = node;
+		}
+		return node;
+	}
+	
+	void clearNodes(Node *node)
+	{
+		if (!node)
+			return;
+
+		clearNodes(left);
+		clearNodes(right);
+		delete node;
+	}
+};
+
+class String;
+
+typedef Map<String, String> StringMap;
+
+};	// End of namespace ScummVM
+
+#endif
diff --git a/common/scaler.cpp b/common/scaler.cpp
index 3f6b3b9f09..9a98d1e8ef 100644
--- a/common/scaler.cpp
+++ b/common/scaler.cpp
@@ -618,7 +618,7 @@ void Scale_2xSaI(uint8 *srcPtr, uint32 srcPitch, uint8 * /* deltaPtr */ ,
 			uint32 E, F, G, H;
 			uint32 I, J, K, L;
 			uint32 x1, x2, a1, f1, f2;
-			uint32 position, product1;
+			uint32 position, product1 = 0;
 
 			position = w >> 16;
 			A = bP[position];					// current pixel
diff --git a/common/str.cpp b/common/str.cpp
new file mode 100644
index 0000000000..2594489371
--- /dev/null
+++ b/common/str.cpp
@@ -0,0 +1,235 @@
+/* ScummVM - Scumm Interpreter
+ * Copyright (C) 2002 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$
+ */
+
+#include "stdafx.h"
+#include "str.h"
+
+
+namespace ScummVM {
+
+String::String(const char *str)
+{
+	_refCount = new int(1);
+	if (str) {
+		_capacity = _len = strlen(str);
+		_str = (char *)calloc(1, _capacity+1);
+		memcpy(_str, str, _len+1);
+	} else {
+		_capacity = _len = 0;
+		_str = 0;
+	}
+}
+
+String::String(const String &str)
+{
+	++(*str._refCount);
+
+	_refCount = str._refCount;
+	_capacity = str._capacity;
+	_len = str._capacity;
+	_str = str._str;
+}
+
+String::~String()
+{
+	decRefCount();
+}
+
+void String::decRefCount()
+{
+	--(*_refCount);
+	if (*_refCount <= 0) {
+		delete _refCount;
+		if (_str)
+			free(_str);
+	}
+}
+
+String& String::operator  =(const char* str)
+{
+	int len = strlen(str);
+	if (len > 0) {
+		ensureCapacity(len, false);
+		
+		_len = len;
+		memcpy(_str, str, _len + 1);
+	} else if (_len > 0) {
+		decRefCount();
+		
+		_refCount = new int(1);
+		_capacity = 0;
+		_len = 0;
+		_str = 0;
+	}
+	return *this;
+}
+
+String& String::operator  =(const String& str)
+{
+	++(*str._refCount);
+
+	decRefCount();
+	
+	_refCount = str._refCount;
+	_capacity = str._capacity;
+	_len = str._len;
+	_str = str._str;
+
+	return *this;
+}
+
+String& String::operator +=(const char* str)
+{
+	int len = strlen(str);
+	if (len > 0) {
+		ensureCapacity(_len + len, true);
+
+		memcpy(_str + _len, str, len + 1);
+		_len += len;
+	}
+	return *this;
+}
+
+String& String::operator +=(const String& str)
+{
+	int len = str._len;
+	if (len > 0) {
+		ensureCapacity(_len + len, true);
+
+		memcpy(_str + _len, str._str, len + 1);
+		_len += len;
+	}
+	return *this;
+}
+
+String& String::operator +=(char c)
+{
+	ensureCapacity(_len + 1, true);
+	
+	_str[_len++] = c;
+	_str[_len] = 0;
+
+	return *this;
+}
+
+bool String::operator ==(const String& x) const
+{
+	return (_len == x._len) && ((_len == 0) || (0 == strcmp(_str, x._str)));
+}
+
+bool String::operator ==(const char* x) const
+{
+	if (_str == 0)
+		return (x == 0) || (*x == 0);
+	if (x == 0)
+		return (_len == 0);
+	return (0 != strcmp(_str, x));
+}
+
+bool String::operator !=(const String& x) const
+{
+	return (_len != x._len) || ((_len != 0) && (0 != strcmp(_str, x._str)));
+}
+
+bool String::operator !=(const char* x) const
+{
+	if (_str == 0)
+		return (x != 0) && (*x != 0);
+	if (x == 0)
+		return (_len != 0);
+	return (0 == strcmp(_str, x));
+}
+
+bool String::operator < (const String& x) const
+{
+	if (!_len || !x._len)	// Any or both particpants are empty?
+		return !_len && x._len;	// Less only if this string is empty and the other isn't
+	return strcmp(_str, x._str) < 0;
+}
+
+bool String::operator <= (const String& x) const
+{
+	if (!_len || !x._len)	// Any or both particpants are empty?
+		return !_len;	// Less or equal unless the other string is empty and this one isn't
+	return strcmp(_str, x._str) <= 0;
+}
+
+bool String::operator > (const String& x) const
+{
+	return (x < *this);
+}
+
+bool String::operator >= (const String& x) const
+{
+	return (x <= *this);
+}
+
+void String::deleteLastChar() {
+	if (_len > 0) {
+		ensureCapacity(_len - 1, true);
+		_str[--_len] = 0;
+	}
+}
+
+void String::clear()
+{
+	if (_capacity) {
+		decRefCount();
+		
+		_refCount = new int(1);
+		_capacity = 0;
+		_len = 0;
+		_str = 0;
+	}
+}
+
+void String::ensureCapacity(int new_len, bool keep_old)
+{
+	// If there is not enough space, or if we are not the only owner 
+	// of the current data, then we have to reallocate it.
+	if (new_len <= _capacity && *_refCount == 1)
+		return;
+
+	int		newCapacity = (new_len <= _capacity) ? _capacity : new_len + 32;
+	char	*newStr = (char *)calloc(1, newCapacity+1);
+
+	if (keep_old && _str)
+		memcpy(newStr, _str, _len + 1);
+	else
+		_len = 0;
+
+	decRefCount();
+	
+	_refCount = new int(1);
+	_capacity = newCapacity;
+	_str = newStr;
+}
+
+bool operator == (const char* y, const String& x)
+{
+	return (x == y);
+}
+
+bool operator != (const char* y, const String& x)
+{
+	return x != y;
+}
+
+};	// End of namespace ScummVM
diff --git a/common/str.h b/common/str.h
new file mode 100644
index 0000000000..0446782aa7
--- /dev/null
+++ b/common/str.h
@@ -0,0 +1,96 @@
+/* ScummVM - Scumm Interpreter
+ * Copyright (C) 2002 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_STRING_H
+#define COMMON_STRING_H
+
+#include "scummsys.h"
+#include "common/list.h"
+
+namespace ScummVM {
+
+/*
+ TODO
+ Add a class ConstString which is a light weight base class of String.
+ It will be immutable, and *not* copy the char pointer it gets when created.
+ Only constructor: ConstString(const char *ptr)
+ Then whenever you now use "const String &" in a parameter, use "const ConstString &"
+ instead (mayhaps make a typedef even). Thus, parameters are passed w/o 
+ causing a free/malloc. Then only for permenant storage, when we assign it to a
+ real String object, will a malloc be issued (to this end, make String aware of
+ ConstString ?!?
+*/
+class String {
+protected:
+	int		*_refCount;
+	int		_capacity;
+	int		_len;
+	char	*_str;
+public:
+	String() : _capacity(0), _len(0), _str(0) { _refCount = new int(1); }
+	String(const char *str);
+	String(const String &str);
+	~String();
+	
+	String& operator  =(const char* str);
+	String& operator  =(const String& str);
+	String& operator +=(const char* str);
+	String& operator +=(const String& str);
+	String& operator +=(char c);
+
+	bool operator ==(const String& x) const;
+	bool operator ==(const char* x) const;
+	bool operator !=(const String& x) const;
+	bool operator !=(const char* x) const;
+	bool operator <(const String& x) const;
+	bool operator <=(const String& x) const;
+	bool operator >(const String& x) const;
+	bool operator >=(const String& x) const;
+
+	const char *c_str() const		{ return _str; }
+	int size() const				{ return _len; }
+	
+	void deleteLastChar();
+	void clear();
+
+	bool isEmpty() const	{ return (_len == 0); }
+
+protected:
+	void ensureCapacity(int new_len, bool keep_old);
+	void decRefCount();
+};
+
+// Some useful additional comparision operators for Strings
+bool operator == (const char* x, const String& y);
+bool operator != (const char* x, const String& y);
+
+class StringList : public List<String> {
+public:
+	void push_back(const char* str)
+	{
+		ensureCapacity(_size + 1);
+		_data[_size] = str;
+		_size++;
+	}
+};
+
+};	// End of namespace ScummVM
+
+#endif
diff --git a/common/system.h b/common/system.h
index b8255eff48..4bac597eb1 100644
--- a/common/system.h
+++ b/common/system.h
@@ -20,10 +20,12 @@
  *
  */
 
-#ifndef _SYSTEM_H
-#define _SYSTEM_H
+#ifndef COMMON_SYSTEM_H
+#define COMMON_SYSTEM_H
 
-/* Interface to what's below ScummVM */
+#include "scummsys.h"
+
+// Interface to the ScummVM backend
 
 class OSystem {
 public:
diff --git a/common/timer.cpp b/common/timer.cpp
index 7ca8f4c1a2..1c184a4d4e 100644
--- a/common/timer.cpp
+++ b/common/timer.cpp
@@ -18,12 +18,16 @@
  * $Header$
  */
 
+#ifndef __MORPHOS__
+
 #include "stdafx.h"
-#include "scumm.h"
 #include "scummsys.h"
 #include "timer.h"
+#include "scumm/scumm.h"
+
+// FIXME - this shouldn't use Scumm, but rather Engine (so that e.g. we can
+// reuse the code for Simon).
 
-#ifndef __MORPHOS__
 static Scumm * scumm;
 
 Timer::Timer(Scumm * parent) {
@@ -154,5 +158,5 @@ void Timer::releaseProcedure (TimerProc procedure) {
 	}
 	_timerRunning = true;
 }
-#endif
 
+#endif
diff --git a/common/util.cpp b/common/util.cpp
index 6f55014ef9..7ff4a9e032 100644
--- a/common/util.cpp
+++ b/common/util.cpp
@@ -80,8 +80,6 @@ void ClearBlendCache(byte *palette, int weight)
 }
 
 
-#pragma mark -
-
 /*
  * Print hexdump of the data passed in, 8 bytes a row
  */
@@ -122,191 +120,3 @@ void hexdump(const byte * data, int len)
 		printf(" ");
 	printf("|\n");
 }
-
-
-#pragma mark -
-
-
-namespace ScummVM {
-
-String::String(const char *str)
-{
-	_refCount = new int(1);
-	_capacity = _len = strlen(str);
-	_str = (char *)calloc(1, _capacity+1);
-	memcpy(_str, str, _len+1);
-}
-
-String::String(const String &str)
-{
-	++(*str._refCount);
-
-	_refCount = str._refCount;
-	_capacity = str._capacity;
-	_len = str._capacity;
-	_str = str._str;
-}
-
-String::~String()
-{
-	decRefCount();
-}
-
-void String::decRefCount()
-{
-	--(*_refCount);
-	if (*_refCount <= 0) {
-		delete _refCount;
-		if (_str)
-			free(_str);
-	}
-}
-
-String& String::operator  =(const char* str)
-{
-	int len = strlen(str);
-	if (len > 0) {
-		ensureCapacity(len, false);
-		
-		_len = len;
-		memcpy(_str, str, _len + 1);
-	} else if (_len > 0) {
-		decRefCount();
-		
-		_refCount = new int(1);
-		_capacity = 0;
-		_len = 0;
-		_str = 0;
-	}
-	return *this;
-}
-
-String& String::operator  =(const String& str)
-{
-	++(*str._refCount);
-
-	decRefCount();
-	
-	_refCount = str._refCount;
-	_capacity = str._capacity;
-	_len = str._len;
-	_str = str._str;
-
-	return *this;
-}
-
-String& String::operator +=(const char* str)
-{
-	int len = strlen(str);
-	if (len > 0) {
-		ensureCapacity(_len + len, true);
-
-		memcpy(_str + _len, str, len + 1);
-		_len += len;
-	}
-	return *this;
-}
-
-String& String::operator +=(const String& str)
-{
-	int len = str._len;
-	if (len > 0) {
-		ensureCapacity(_len + len, true);
-
-		memcpy(_str + _len, str._str, len + 1);
-		_len += len;
-	}
-	return *this;
-}
-
-String& String::operator +=(char c)
-{
-	ensureCapacity(_len + 1, true);
-	
-	_str[_len++] = c;
-	_str[_len] = 0;
-
-	return *this;
-}
-
-bool String::operator ==(const String& x)
-{
-	return (_len == x._len) && ((_len == 0) || (0 == strcmp(_str, x._str)));
-}
-
-bool String::operator ==(const char* x)
-{
-	if (_str == 0)
-		return (x == 0) || (*x == 0);
-	if (x == 0)
-		return (_len == 0);
-	return (0 != strcmp(_str, x));
-}
-
-bool String::operator !=(const String& x)
-{
-	return (_len != x._len) || ((_len != 0) && (0 != strcmp(_str, x._str)));
-}
-
-bool String::operator !=(const char* x)
-{
-	if (_str == 0)
-		return (x != 0) && (*x != 0);
-	if (x == 0)
-		return (_len != 0);
-	return (0 == strcmp(_str, x));
-}
-
-
-void String::deleteLastChar() {
-	if (_len > 0) {
-		ensureCapacity(_len - 1, true);
-		_str[--_len] = 0;
-	}
-}
-
-void String::clear()
-{
-	if (_capacity) {
-		decRefCount();
-		
-		_refCount = new int(1);
-		_capacity = 0;
-		_len = 0;
-		_str = 0;
-	}
-}
-
-void String::ensureCapacity(int new_len, bool keep_old)
-{
-	// If there is not enough space, or if we are not the only owner 
-	// of the current data, then we have to reallocate it.
-	if (new_len <= _capacity && *_refCount == 1)
-		return;
-
-	int		newCapacity = (new_len <= _capacity) ? _capacity : new_len + 32;
-	char	*newStr = (char *)calloc(1, newCapacity+1);
-
-	if (keep_old && _str)
-		memcpy(newStr, _str, _len + 1);
-	else
-		_len = 0;
-
-	decRefCount();
-	
-	_refCount = new int(1);
-	_capacity = newCapacity;
-	_str = newStr;
-}
-
-bool operator == (const char* y, const String& x)
-{
-	return x == y;
-}
-
-bool operator != (const char* y, const String& x)
-{
-	return x != y;
-}
-
-};	// End of namespace ScummVM
diff --git a/common/util.h b/common/util.h
index 7c8a2dd048..afaf2acaf4 100644
--- a/common/util.h
+++ b/common/util.h
@@ -18,8 +18,8 @@
  * $Header$
  */
 
-#ifndef UTIL_H
-#define UTIL_H
+#ifndef COMMON_UTIL_H
+#define COMMON_UTIL_H
 
 #include "scummsys.h"
 
@@ -35,6 +35,9 @@
 #define	MAX(a,b) (((a)>(b))?(a):(b))
 #endif
 
+#define SWAP(a,b) do{int tmp=a; a=b; b=tmp; } while(0)
+#define ARRAYSIZE(x) (sizeof(x)/sizeof(x[0]))
+
 
 int RGBMatch(byte *palette, int r, int g, int b);
 int Blend(int src, int dst, byte *palette);
@@ -45,152 +48,4 @@ void ClearBlendCache(byte *palette, int weight);
  */
 void hexdump(const byte * data, int len);
 
-
-namespace ScummVM {
-
-template <class T>
-class List {
-protected:
-	int		_capacity;
-	int		_size;
-	T		*_data;
-
-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>()
-	{
-		if (_data)
-			delete [] _data;
-	}
-	
-	void push_back(const T& str)
-	{
-		ensureCapacity(_size + 1);
-		_data[_size++] = str;
-	}
-	
-	// 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];
-	}
-
-	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;
-	}
-
-	int size() const	{ return _size; }
-
-	void clear()
-	{
-		if (_data) {
-			delete [] _data;
-			_data = 0;
-		}
-		_size = 0;
-		_capacity = 0;
-	}
-	
-	bool isEmpty() const	{ return (_size == 0); }
-
-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;
-		}
-	}
-};
-
-
-class String {
-protected:
-	int		*_refCount;
-	int		_capacity;
-	int		_len;
-	char	*_str;
-public:
-	String() : _capacity(0), _len(0), _str(0) { _refCount = new int(1); }
-	String(const char *str);
-	String(const String &str);
-	~String();
-	
-	String& operator  =(const char* str);
-	String& operator  =(const String& str);
-	String& operator +=(const char* str);
-	String& operator +=(const String& str);
-	String& operator +=(char c);
-
-	bool operator ==(const String& x);
-	bool operator ==(const char* x);
-	bool operator !=(const String& x);
-	bool operator !=(const char* x);
-
-//	operator char *()				{ return _str; }
-	operator const char *()	const	{ return _str; }
-	const char *c_str() const		{ return _str; }
-	int size() const				{ return _len; }
-	
-	void deleteLastChar();
-	void clear();
-
-	bool isEmpty() const	{ return (_len == 0); }
-
-protected:
-	void ensureCapacity(int new_len, bool keep_old);
-	void decRefCount();
-};
-
-// Some useful additional comparision operators for Strings
-bool operator == (const char* x, const String& y);
-bool operator != (const char* x, const String& y);
-
-class StringList : public List<String> {
-public:
-	void push_back(const char* str)
-	{
-		ensureCapacity(_size + 1);
-		_data[_size] = str;
-		_size++;
-	}
-};
-
-};	// End of namespace ScummVM
-
 #endif