From a45ed16fc402266dc9ba3f61292920b88713221e Mon Sep 17 00:00:00 2001 From: Walter van Niftrik Date: Thu, 19 Mar 2009 22:47:30 +0000 Subject: SCI: converted aatree into a class svn-id: r39544 --- engines/sci/engine/aatree.cpp | 162 ------------------------------ engines/sci/engine/aatree.h | 217 ++++++++++++++++++++++++++++++---------- engines/sci/engine/kpathing.cpp | 90 +++++++---------- 3 files changed, 200 insertions(+), 269 deletions(-) delete mode 100644 engines/sci/engine/aatree.cpp (limited to 'engines/sci/engine') 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 ⊥ -} - -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 = ⊥ - (*t)->right = ⊥ - (*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 +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 > +class AATree { +public: + AATree() { + _bottom = new AATreeNode; + _root = _bottom; + } + + AATree(const AATree &tree) { + _bottom = new AATreeNode; + _root = copyTree(tree._root, tree._bottom); + } + + const AATree &operator=(const AATree &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 *node = _root; + + if (node == _bottom) + return NULL; + + while (node->_left != _bottom) + node = node->_left; + + return &node->_key; + } + +private: + AATreeNode *_root; + AATreeNode *_bottom; + LessFunc _less; + +private: + void freeNode(AATreeNode *node) { + if (node == _bottom) + return; + + freeNode(node->_left); + freeNode(node->_right); + + delete node; + } + + void skew(AATreeNode *&node) { + if (node->_left->_level == node->_level) { + // Rotate right + AATreeNode *temp = node; + node = node->_left; + temp->_left = node->_right; + node->_right = temp; + } + } + + void split(AATreeNode *&node) { + if (node->_right->_right->_level == node->_level) { + // Rotate left + AATreeNode *temp = node; + node = node->_right; + temp->_right = node->_left; + node->_left = temp; + node->_level++; + } + } + + bool removeNode(const Key &key, AATreeNode *&node) { + bool ok = false; + static AATreeNode *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 *&node) { + if (node == _bottom) { + node = new AATreeNode(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 *copyTree(AATreeNode *node, const AATreeNode *bottom) { + if (node == bottom) + return _bottom; + + return new AATreeNode(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 { // 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 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) { -- cgit v1.2.3