SCI: Replaced AATree by Common::List in AvoidPath. AATree does not help when

the input size is this small.

svn-id: r39855

2 files changed, 52 insertions, 246 deletions

diff --git a/engines/sci/engine/aatree.h b/engines/sci/engine/aatree.h
deleted file mode 100644
index e1d7c61b85..0000000000
--- a/engines/sci/engine/aatree.h
+++ /dev/null
@@ -1,198 +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$
- *
- */
-
-#ifndef SCI_ENGINE_AATREE_H
-#define SCI_ENGINE_AATREE_H
-
-#include "common/func.h"
-
-namespace Sci {
-
-// 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() const {
-		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
-
-#endif // SCI_ENIGNE_AATREE_H
diff --git a/engines/sci/engine/kpathing.cpp b/engines/sci/engine/kpathing.cpp
index cfb5fbad2b..759bc275ec 100644
--- a/engines/sci/engine/kpathing.cpp
+++ b/engines/sci/engine/kpathing.cpp
@@ -24,7 +24,6 @@
  */
 
 #include "sci/engine/state.h"
-#include "sci/engine/aatree.h"
 #include "sci/engine/kernel.h"
 #include "sci/gfx/gfx_widgets.h"
 #include "sci/gfx/gfx_state_internal.h"	// required for gfxw_port_t, gfxw_container_t
@@ -682,33 +681,33 @@ static void clockwise(const Vertex *v, const Common::Point *&p1, const Common::P
 	}
 }
 
-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 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 {
-		const Common::Point *v1, *v2, *w1, *w2;
+/**
+ * Compares two edges that are intersected by the sweeping line by distance from vertex_cur
+ * @param a				the first edge
+ * @param b				the second edge
+ * @return true if a is closer to vertex_cur than b, false otherwise
+ */
+static bool edgeIsCloser(const Vertex *a, const Vertex *b) {
+	const Common::Point *v1, *v2, *w1, *w2;
 
-		// Check for comparison of the same edge
-		if (a == b)
-			return false;
+	// Check for comparison of the same edge
+	if (a == b)
+		return false;
 
-		// We can assume that the sweeping line intersects both edges and
-		// that the edges do not properly intersect
+	// We can assume that the sweeping line intersects both edges and
+	// that the edges do not properly intersect
 
-		// 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);
+	// 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);
 
-		// 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.
+	// 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.
 
-		return ((left_on(*v1, *v2, *w1) && left_on(*v1, *v2, *w2)) || (left_on(*w2, *w1, *v1) && left_on(*w2, *w1, *v2)));
-	}
-};
+	return ((left_on(*v1, *v2, *w1) && left_on(*v1, *v2, *w2)) || (left_on(*w2, *w1, *v1) && left_on(*w2, *w1, *v2)));
+}
 
 static int inside(const Common::Point &p, Vertex *vertex) {
 	// Determines whether or not a line from a point to a vertex intersects the
@@ -739,17 +738,15 @@ static int inside(const Common::Point &p, Vertex *vertex) {
 	return 0;
 }
 
-typedef AATree<const Vertex *, EdgeIsCloser> EdgeAATree;
-
 /**
  * Determines whether or not a vertex is visible from vertex_cur.
  * @param vertex		the vertex
  * @param vertex_prev	the previous vertex in the sort order, or NULL
  * @param visible		true if vertex_prev is visible, false otherwise
- * @param tree			the tree of edges intersected by the sweeping line
+ * @param intersected	the list of edges intersected by the sweeping line
  * @return true if vertex is visible from vertex_cur, false otherwise
  */
-static bool visible(Vertex *vertex, Vertex *vertex_prev, bool visible, const EdgeAATree &tree) {
+static bool visible(Vertex *vertex, Vertex *vertex_prev, bool visible, const VertexList &intersected) {
 	const Common::Point &p = vertex_cur->v;
 	const Common::Point &w = vertex->v;
 
@@ -763,17 +760,27 @@ static bool visible(Vertex *vertex, Vertex *vertex_prev, bool visible, const Edg
 	if (vertex_prev && !visible && between(p, w, vertex_prev->v))
 		return false;
 
-	const Vertex *const *edge = tree.findSmallest();
+	if (intersected.empty()) {
+		// No intersected edges
+		return true;
+	}
 
-	if (edge) {
-		const Common::Point *p1, *p2;
+	// Look for the intersected edge that is closest to vertex_cur
+	VertexList::const_iterator it = intersected.begin();
+	const Vertex *edge = *it++;
 
-		// Check for intersection with sweeping line before vertex
-		clockwise(*edge, p1, p2);
-		if (left(*p2, *p1, p) && left(*p1, *p2, w))
-			return false;
+	for (; it != intersected.end(); ++it) {
+		if (edgeIsCloser(*it, edge))
+			edge = *it;
 	}
 
+	const Common::Point *p1, *p2;
+
+	// Check for intersection with sweeping line before vertex
+	clockwise(edge, p1, p2);
+	if (left(*p2, *p1, p) && left(*p1, *p2, w))
+		return false;
+
 	return true;
 }
 
@@ -784,7 +791,8 @@ static bool visible(Vertex *vertex, Vertex *vertex_prev, bool visible, const Edg
  * @return list of vertices that are visible from vert
  */
 static VertexList *visible_vertices(PathfindingState *s, Vertex *vert) {
-	EdgeAATree tree;
+	// List of edges intersected by the sweeping line
+	VertexList intersected;
 	VertexList *visVerts = new VertexList();
 	const Common::Point &p = vert->v;
 
@@ -806,7 +814,7 @@ static VertexList *visible_vertices(PathfindingState *s, Vertex *vert) {
 				clockwise(vertex, high, low);
 	
 				if ((high->y < p.y) && (low->y >= p.y) && (*low != p))
-					tree.insert(vertex);
+					intersected.push_front(vertex);
 			}
 		}
 	}
@@ -818,24 +826,20 @@ static VertexList *visible_vertices(PathfindingState *s, Vertex *vert) {
 		Vertex *v1;
 
 		// Compute visibility of vertex_index[i]
-		is_visible = visible(s->vertex_index[i], s->vertex_index[i - 1], is_visible, tree);
+		is_visible = visible(s->vertex_index[i], s->vertex_index[i - 1], is_visible, intersected);
 
 		// Update visibility matrix
 		if (is_visible)
 			visVerts->push_front(s->vertex_index[i]);
 
-		// Delete anti-clockwise edges from tree
+		// Delete anti-clockwise edges from list
 		v1 = CLIST_PREV(s->vertex_index[i]);
-		if (left(p, s->vertex_index[i]->v, v1->v)) {
-			if (!tree.remove(v1))
-				sciprintf("[avoidpath] Error: failed to remove edge from tree\n");
-		}
+		if (left(p, s->vertex_index[i]->v, v1->v))
+			intersected.remove(v1);
 
 		v1 = CLIST_NEXT(s->vertex_index[i]);
-		if (left(p, s->vertex_index[i]->v, v1->v)) {
-			if (!tree.remove(s->vertex_index[i]))
-				sciprintf("[avoidpath] Error: failed to remove edge from tree\n");
-		}
+		if (left(p, s->vertex_index[i]->v, v1->v))
+			intersected.remove(s->vertex_index[i]);
 
 		// Add clockwise edges of collinear vertices when sweeping line moves
 		if ((i < s->vertices - 1) && !collinear(p, s->vertex_index[i]->v, s->vertex_index[i + 1]->v)) {
@@ -843,11 +847,11 @@ static VertexList *visible_vertices(PathfindingState *s, Vertex *vert) {
 			for (j = i; (j >= 1) && collinear(p, s->vertex_index[i]->v, s->vertex_index[j]->v); j--) {
 				v1 = CLIST_PREV(s->vertex_index[j]);
 				if (left(s->vertex_index[j]->v, p, v1->v))
-					tree.insert(v1);
+					intersected.push_front(v1);
 
 				v1 = CLIST_NEXT(s->vertex_index[j]);
 				if (left(s->vertex_index[j]->v, p, v1->v))
-					tree.insert(s->vertex_index[j]);
+					intersected.push_front(s->vertex_index[j]);
 			}
 		}
 	}