SCI: converted aatree into a class

svn-id: r39544

3 files changed, 200 insertions, 269 deletions

diff --git a/engines/sci/engine/aatree.cpp b/engines/sci/engine/aatree.cpp
deleted file mode 100644
index 4cbe1b5c0a..0000000000
--- a/engines/sci/engine/aatree.cpp
+++ /dev/null
@@ -1,162 +0,0 @@
-/* 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$
- *
- */
-
-#include "sci/engine/aatree.h"
-
-#include "sci/sci_memory.h"
-
-namespace Sci {
-
-struct aatree {
-	struct aatree *left, *right;
-	int level;
-	void *key;
-};
-
-// Sentinel node
-static aatree_t bottom = {&bottom, &bottom, 0, NULL};
-
-static void skew(aatree_t **t) {
-	if ((*t)->left->level == (*t)->level) {
-		// Rotate right
-		aatree_t *temp = *t;
-		*t = (*t)->left;
-		temp->left = (*t)->right;
-		(*t)->right = temp;
-	}
-}
-
-static void split(aatree_t **t) {
-	if ((*t)->right->right->level == (*t)->level) {
-		// Rotate left
-		aatree_t *temp = *t;
-		*t = (*t)->right;
-		temp->right = (*t)->left;
-		(*t)->left = temp;
-		(*t)->level++;
-	}
-}
-
-static int delete_node(void *x, aatree_t **t, aatree_t *deleted, int (*compar)(const void *, const void *)) {
-	int retval = -1;
-
-	if (*t != &bottom) {
-		// Search down the tree
-		aatree_t **n;
-
-		if (compar(x, (*t)->key) < 0)
-			n = &(*t)->left;
-		else {
-			n = &(*t)->right;
-			deleted = *t;
-		}
-
-		retval = delete_node(x, n, deleted, compar);
-
-		// At the bottom of the tree we remove the element (if it is present)
-		if ((*n == &bottom) && (deleted != &bottom) && (compar(x, deleted->key) == 0)) {
-			aatree_t *temp;
-			deleted->key = (*t)->key;
-			temp = *t;
-			*t = (*t)->right;
-			free(temp);
-			retval = 0;
-		} else if (((*t)->left->level < (*t)->level - 1) || ((*t)->right->level < (*t)->level - 1)) {
-			(*t)->level--;
-			if ((*t)->right->level > (*t)->level)
-				(*t)->right->level = (*t)->level;
-			skew(t);
-			skew(&(*t)->right);
-			skew(&(*t)->right->right);
-			split(t);
-			split(&(*t)->right);
-		}
-	}
-
-	return retval;
-}
-
-aatree_t *aatree_new() {
-	return &bottom;
-}
-
-int aatree_insert(void *x, aatree_t **t, int (*compar)(const void *, const void *)) {
-	int retval = -1;
-	int c;
-
-	if (*t == &bottom) {
-		*t = (aatree_t *)sci_malloc(sizeof(aatree_t));
-
-		if (*t == NULL)
-			return 1;
-
-		(*t)->key = x;
-		(*t)->left = &bottom;
-		(*t)->right = &bottom;
-		(*t)->level = 1;
-		return 0;
-	}
-
-	c = compar(x, (*t)->key);
-
-	if (c < 0)
-		retval = aatree_insert(x, &(*t)->left, compar);
-	else if (c > 0)
-		retval = aatree_insert(x, &(*t)->right, compar);
-
-	skew(t);
-	split(t);
-	return retval;
-}
-
-int aatree_delete(void *x, aatree_t **t, int (*compar)(const void *, const void *)) {
-	return delete_node(x, t, &bottom, compar);
-}
-
-aatree_t *aatree_walk(aatree_t *t, int direction) {
-	if ((direction == AATREE_WALK_LEFT) && (t->left != &bottom))
-		return t->left;
-
-	if ((direction == AATREE_WALK_RIGHT) && (t->right != &bottom))
-		return t->right;
-
-	return NULL;
-}
-
-void *aatree_get_data(aatree_t *t) {
-	return t->key;
-}
-
-void aatree_free(aatree_t *t) {
-	if (t == &bottom)
-		return;
-
-	aatree_free(t->left);
-	aatree_free(t->right);
-
-	free(t);
-}
-
-} // End of namespace Sci
diff --git a/engines/sci/engine/aatree.h b/engines/sci/engine/aatree.h
index dea2ad1c66..74c97cf308 100644
--- a/engines/sci/engine/aatree.h
+++ b/engines/sci/engine/aatree.h
@@ -26,61 +26,172 @@
 #ifndef SCI_ENGINE_AATREE_H
 #define SCI_ENGINE_AATREE_H
 
+#include "common/func.h"
+
 namespace Sci {
 
-/* Andersson tree implementation. Stores data pointers in a balanced binary
-** tree. A user-supplied comparison function defines the ordering. For the
-** semantics of this function see qsort(3)
-*/
-
-typedef struct aatree aatree_t;
-
-// Left child
-#define AATREE_WALK_LEFT 0
-// Right child
-#define AATREE_WALK_RIGHT 1
-
-aatree_t *aatree_new();
-/* Allocates a new aatree
-** Parameters: (void)
-** Returns   : (aatree_t *) A newly allocated aatree
-*/
-
-void aatree_free(aatree_t *t);
-/* Deallocates an aatree
-** Parameters: (aatree_t *) t: The aatree
-** Returns   : (void)
-*/
-
-int aatree_delete(void *x, aatree_t **t, int (*compar)(const void *, const void *));
-/* Deletes a data element from an aatree
-** Parameters: (void *) x: The data element to delete
-**             (aatree_t **) t: The aatree
-**             compar: The comparison function
-** Returns   : (int) 0 on success, -1 if x wasn't found in t
-*/
-
-int aatree_insert(void *x, aatree_t **t, int (*compar)(const void *, const void *));
-/* Inserts a data element into an aatree
-** Parameters: (void *) x: The data element to insert
-**             (aatree_t **) t: The aatree
-**             compar: The comparison function
-** Returns   : (int) 0 on success, -1 if x already exists in t
-*/
-
-aatree_t *aatree_walk(aatree_t *t, int direction);
-/* Walks to either the left or right child of a node
-** Parameters: (aatree_t *) t: The node
-**             (int) direction: AATREE_WALK_LEFT or AATREE_WALK_RIGHT
-** Returns   : (aatree_t *) The requested child of t or NULL if it doesn't
-**                          exist
-*/
-
-void *aatree_get_data(aatree_t *t);
-/* Returns the data element of a node
-** Parameters: (aatree_t *) t: The node
-** Returns   : (void *) The data element
-*/
+// Andersson tree implementation.
+
+template<typename Key>
+struct AATreeNode {
+	AATreeNode() : _left(this), _right(this), _level(0) { }
+	AATreeNode(const Key &key, AATreeNode *left, AATreeNode *right, int level) : _key(key), _left(left), _right(right), _level(level) { }
+
+	Key _key;
+	AATreeNode *_left, *_right;
+	int _level;
+};
+
+template<typename Key, class LessFunc = Common::Less<Key> >
+class AATree {
+public:
+	AATree() {
+		_bottom = new AATreeNode<Key>;
+		_root = _bottom;
+	}
+
+	AATree(const AATree<Key, LessFunc> &tree) {
+		_bottom = new AATreeNode<Key>;
+		_root = copyTree(tree._root, tree._bottom);
+	}
+
+	const AATree<Key, LessFunc> &operator=(const AATree<Key, LessFunc> &tree) {
+		if (this != &tree) {
+			freeNode(_root);
+			_root = copyTree(tree._root, tree._bottom);
+		}
+
+		return *this;
+	}
+
+	~AATree() {
+		freeNode(_root);
+		delete _bottom;
+	}
+
+	void insert(const Key &key) {
+		insertNode(key, _root);
+	}
+
+	bool remove(const Key &key) {
+		return removeNode(key, _root);
+	}
+
+	// Returns a pointer to the smallest Key or NULL if the tree is empty.
+	const Key *findSmallest() {
+		AATreeNode<Key> *node = _root;
+
+		if (node == _bottom)
+			return NULL;
+
+		while (node->_left != _bottom)
+			node = node->_left;
+
+		return &node->_key;
+	}
+
+private:
+	AATreeNode<Key> *_root;
+	AATreeNode<Key> *_bottom;
+	LessFunc _less;
+
+private:
+	void freeNode(AATreeNode<Key> *node) {
+		if (node == _bottom)
+			return;
+
+		freeNode(node->_left);
+		freeNode(node->_right);
+
+		delete node;
+	}
+
+	void skew(AATreeNode<Key> *&node) {
+		if (node->_left->_level == node->_level) {
+			// Rotate right
+			AATreeNode<Key> *temp = node;
+			node = node->_left;
+			temp->_left = node->_right;
+			node->_right = temp;
+		}
+	}
+
+	void split(AATreeNode<Key> *&node) {
+		if (node->_right->_right->_level == node->_level) {
+			// Rotate left
+			AATreeNode<Key> *temp = node;
+			node = node->_right;
+			temp->_right = node->_left;
+			node->_left = temp;
+			node->_level++;
+		}
+	}
+
+	bool removeNode(const Key &key, AATreeNode<Key> *&node) {
+		bool ok = false;
+		static AATreeNode<Key> *last, *deleted = _bottom;
+
+		if (node != _bottom) {
+			// Search down the tree and set pointers last and deleted
+			last = node;
+
+			if (_less(key, node->_key))
+				ok = removeNode(key, node->_left);
+			else {
+				deleted = node;
+				ok = removeNode(key, node->_right);
+			}
+
+			if ((node == last) && (deleted != _bottom) && !_less(key, deleted->_key) && !_less(deleted->_key, key)) {
+				// At the bottom of the tree we remove the element (if it is present)
+				deleted->_key = node->_key;
+				deleted = _bottom;
+				node = node->_right;
+				delete last;
+				return true;
+			}
+
+			if ((node->_left->_level < node->_level - 1) || (node->_right->_level < node->_level - 1)) {
+				// On the way back, we rebalance
+				node->_level--;
+				if (node->_right->_level > node->_level)
+					node->_right->_level = node->_level;
+
+				skew(node);
+				skew(node->_right);
+				skew(node->_right->_right);
+				split(node);
+				split(node->_right);
+			}
+		}
+
+		return ok;
+	}
+
+	void insertNode(const Key &key, AATreeNode<Key> *&node) {
+		if (node == _bottom) {
+			node = new AATreeNode<Key>(key, _bottom, _bottom, 1);
+
+			assert(node);
+			return;
+		}
+
+		if (_less(key, node->_key))
+			insertNode(key, node->_left);
+		else if (_less(node->_key, key))
+			insertNode(key, node->_right);
+
+		skew(node);
+		split(node);
+	}
+
+	AATreeNode<Key> *copyTree(AATreeNode<Key> *node, const AATreeNode<Key> *bottom) {
+		if (node == bottom)
+			return _bottom;
+
+		return new AATreeNode<Key>(node->_key, copyTree(node->_left, bottom), copyTree(node->_right, bottom), node->_level);
+	}
+};
 
 } // End of namespace Sci
 
diff --git a/engines/sci/engine/kpathing.cpp b/engines/sci/engine/kpathing.cpp
index b5f34d3f07..2dcf17c793 100644
--- a/engines/sci/engine/kpathing.cpp
+++ b/engines/sci/engine/kpathing.cpp
@@ -644,10 +644,10 @@ static int vertex_compare(const void *a, const void *b) {
 	return -1;
 }
 
-static void clockwise(Vertex *v, Common::Point *p1, Common::Point *p2) {
+static void clockwise(const Vertex *v, Common::Point *p1, Common::Point *p2) {
 	// Orders the points of an edge clockwise around vertex_cur. If all three
 	// points are collinear the original order is used
-	// Parameters: (Vertex *) v: The first vertex of the edge
+	// Parameters: (const Vertex *) v: The first vertex of the edge
 	// Returns   : (void)
 	//             (Common::Point) *p1: The first point in clockwise order
 	//             (Common::Point) *p2: The second point in clockwise order
@@ -662,45 +662,33 @@ static void clockwise(Vertex *v, Common::Point *p1, Common::Point *p2) {
 	}
 }
 
-static int edge_compare(const void *a, const void *b) {
+struct EdgeIsCloser: public Common::BinaryFunction<const Vertex *, const Vertex *, bool> {
 	// Compares two edges that are intersected by the sweeping line by distance
 	// from vertex_cur
-	// Parameters: (const void *) a, b: The first vertices of the edges
-	// Returns   : (int) -1 if a is closer than b, 1 if b is closer than a, and
-	//                   0 if a and b are equal
-	Common::Point v1, v2, w1, w2;
-
-	// We can assume that the sweeping line intersects both edges and
-	// that the edges do not properly intersect
-
-	if (a == b)
-		return 0;
+	// Parameters: (const Vertex *const &) a, b: The first vertices of the edges
+	// Returns   : (bool) true if a is closer to vertex_cur than b, false otherwise
+	bool operator()(const Vertex *const &a, const Vertex *const &b) const {
+		Common::Point v1, v2, w1, w2;
 
-	// Order vertices clockwise so we know vertex_cur is to the right of
-	// directed edges (v1, v2) and (w1, w2)
-	clockwise((Vertex *)a, &v1, &v2);
-	clockwise((Vertex *)b, &w1, &w2);
+		// Check for comparison of the same edge
+		if (a == b)
+			return false;
 
-	// As the edges do not properly intersect one edge must lie entirely
-	// to one side of another. Note that the special case where edges are
-	// collinear does not need to be handled as those edges will never be
-	// in the tree simultaneously
+		// We can assume that the sweeping line intersects both edges and
+		// that the edges do not properly intersect
 
-	// b is left of a
-	if (left_on(v1, v2, w1) && left_on(v1, v2, w2))
-		return -1;
-
-	// b is right of a
-	if (left_on(v2, v1, w1) && left_on(v2, v1, w2))
-		return 1;
+		// Order vertices clockwise so we know vertex_cur is to the right of
+		// directed edges (v1, v2) and (w1, w2)
+		clockwise(a, &v1, &v2);
+		clockwise(b, &w1, &w2);
 
-	// a is left of b
-	if (left_on(w1, w2, v1) && left_on(w1, w2, v2))
-		return 1;
+		// At this point we know that one edge must lie entirely to one side
+		// of the other, as the edges are not collinear and cannot intersect
+		// other than possibly sharing a vertex.
 
-	// a is right of b
-	return -1;
-}
+		return ((left_on(v1, v2, w1) && left_on(v1, v2, w2)) || (left_on(w2, w1, v1) && left_on(w2, w1, v2)));
+	}
+};
 
 static int inside(Common::Point p, Vertex *vertex) {
 	// Determines whether or not a line from a point to a vertex intersects the
@@ -731,19 +719,20 @@ static int inside(Common::Point p, Vertex *vertex) {
 	return 0;
 }
 
-static int visible(Vertex *vertex, Vertex *vertex_prev, int visible, aatree_t *tree) {
+typedef AATree<const Vertex *, EdgeIsCloser> EdgeAATree;
+
+static int visible(Vertex *vertex, Vertex *vertex_prev, int visible, EdgeAATree &tree) {
 	// Determines whether or not a vertex is visible from vertex_cur
 	// Parameters: (Vertex *) vertex: The vertex
 	//             (Vertex *) vertex_prev: The previous vertex in the sort
 	//                                       order, or NULL
 	//             (int) visible: 1 if vertex_prev is visible, 0 otherwise
-	//             (aatree_t *) tree: The tree of edges intersected by the
-	//                                sweeping line
+	//             (EdgeAATree &) tree: The tree of edges intersected by the
+	//                                  sweeping line
 	// Returns   : (int) 1 if vertex is visible from vertex_cur, 0 otherwise
-	Vertex *edge;
+	const Vertex *const *edge;
 	Common::Point p = vertex_cur->v;
 	Common::Point w = vertex->v;
-	aatree_t *tree_n = tree;
 
 	// Check if sweeping line intersects the interior of the polygon
 	// locally at vertex
@@ -755,17 +744,13 @@ static int visible(Vertex *vertex, Vertex *vertex_prev, int visible, aatree_t *t
 	if (vertex_prev && !visible && between(p, w, vertex_prev->v))
 		return 0;
 
-	// Find leftmost node of tree */
-	while ((tree_n = aatree_walk(tree_n, AATREE_WALK_LEFT)))
-		tree = tree_n;
-
-	edge = (Vertex*)aatree_get_data(tree);
+	edge = tree.findSmallest();
 
 	if (edge) {
 		Common::Point p1, p2;
 
 		// Check for intersection with sweeping line before vertex
-		clockwise(edge, &p1, &p2);
+		clockwise(*edge, &p1, &p2);
 		if (left(p2, p1, p) && left(p1, p2, w))
 			return 0;
 	}
@@ -778,7 +763,7 @@ static void visible_vertices(PathfindingState *s, Vertex *vert) {
 	// updates the visibility matrix
 	// Parameters: (PathfindingState *) s: The pathfinding state
 	//             (Vertex *) vert: The vertex
-	aatree_t *tree = aatree_new();
+	EdgeAATree tree;
 	Common::Point p = vert->v;
 	Polygon *polygon;
 	int i;
@@ -804,7 +789,7 @@ static void visible_vertices(PathfindingState *s, Vertex *vert) {
 			clockwise(vertex, &high, &low);
 
 			if ((high.y < p.y) && (low.y >= p.y) && (low != p))
-				aatree_insert(vertex, &tree, edge_compare);
+				tree.insert(vertex);
 		}
 	}
 
@@ -824,13 +809,13 @@ static void visible_vertices(PathfindingState *s, Vertex *vert) {
 		// Delete anti-clockwise edges from tree
 		v1 = CLIST_PREV(vert_sorted[i]);
 		if (left(p, vert_sorted[i]->v, v1->v)) {
-			if (aatree_delete(v1, &tree, edge_compare))
+			if (!tree.remove(v1))
 				sciprintf("[avoidpath] Error: failed to remove edge from tree\n");
 		}
 
 		v1 = CLIST_NEXT(vert_sorted[i]);
 		if (left(p, vert_sorted[i]->v, v1->v)) {
-			if (aatree_delete(vert_sorted[i], &tree, edge_compare))
+			if (!tree.remove(vert_sorted[i]))
 				sciprintf("[avoidpath] Error: failed to remove edge from tree\n");
 		}
 
@@ -840,19 +825,16 @@ static void visible_vertices(PathfindingState *s, Vertex *vert) {
 			for (j = i; (j >= 1) && collinear(p, vert_sorted[i]->v, vert_sorted[j]->v); j--) {
 				v1 = CLIST_PREV(vert_sorted[j]);
 				if (left(vert_sorted[j]->v, p, v1->v))
-					aatree_insert(v1, &tree, edge_compare);
+					tree.insert(v1);
 
 				v1 = CLIST_NEXT(vert_sorted[j]);
 				if (left(vert_sorted[j]->v, p, v1->v))
-					aatree_insert(vert_sorted[j], &tree, edge_compare);
+					tree.insert(vert_sorted[j]);
 			}
 		}
 	}
 
 	free(vert_sorted);
-
-	// Free tree
-	aatree_free(tree);
 }
 
 static float distance(FloatPoint a, FloatPoint b) {