[Scummvm-cvs-logs] CVS: scummvm/common map.h,1.16,1.17

[Max Horn]

Update of /cvsroot/scummvm/scummvm/common
In directory sc8-pr-cvs1:/tmp/cvs-serv10677

Modified Files:
	map.h 
Log Message:
renamed createNode() to findOrCreateNode(); added addKey() method; reimplemented merge()

Index: map.h
===================================================================
RCS file: /cvsroot/scummvm/scummvm/common/map.h,v
retrieving revision 1.16
retrieving revision 1.17
diff -u -d -r1.16 -r1.17
--- map.h	5 Oct 2003 14:15:31 -0000	1.16
+++ map.h	8 Oct 2003 18:05:20 -0000	1.17
@@ -113,7 +113,7 @@
 		if (!_root)
 			node = _root = new Node(key, _header);
 		else
-			node = createNode(_root, key);
+			node = findOrCreateNode(_root, key);
 		return node->_value;
 	}
 
@@ -136,6 +136,15 @@
 		return (_root == 0);
 	}
 
+	Value &addKey(const Key &key) {
+		Node *node;
+		if (!_root)
+			node = _root = new Node(key, _header);
+		else
+			node = findOrCreateNode(_root, key);
+		return node->_value;
+	}
+
 	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
@@ -179,17 +188,7 @@
 	}
 
 	void merge(const 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;
-		ConstIterator x(map.begin()), e(map.end());
-		for (; x != e; ++x) {
-			(*this)[x->_key] = x->_value;
-		}
+		merge(map._root);
 	}
 
 	ConstIterator	begin() const {
@@ -206,7 +205,16 @@
 	}
 
 protected:
-	// Find the node matching the given key, if any
+	/** Merge the content of the given tree into this tree. */
+	void merge(const Node *node) {
+		if (!node)
+			return;
+		(*this)[node->_key] = node->_value;
+		merge(node->_left);
+		merge(node->_right);
+	}
+
+	/** Find and return 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) {
@@ -218,7 +226,7 @@
 		return node;
 	}
 
-	Node *createNode(Node *node, const Key &key) {
+	Node *findOrCreateNode(Node *node, const Key &key) {
 		Node *prevNode = 0;
 		bool left = true;
 		while (node) {