diff options
Diffstat (limited to 'engines/sci/engine')
| -rw-r--r-- | engines/sci/engine/aatree.cpp | 162 | ||||
| -rw-r--r-- | engines/sci/engine/aatree.h | 87 | ||||
| -rw-r--r-- | engines/sci/engine/kpathing.cpp | 2 |
3 files changed, 250 insertions, 1 deletions
diff --git a/engines/sci/engine/aatree.cpp b/engines/sci/engine/aatree.cpp new file mode 100644 index 0000000000..3cd3a01691 --- /dev/null +++ b/engines/sci/engine/aatree.cpp @@ -0,0 +1,162 @@ +/* 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/include/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 new file mode 100644 index 0000000000..f40c9e0935 --- /dev/null +++ b/engines/sci/engine/aatree.h @@ -0,0 +1,87 @@ +/* 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_AATREE_H +#define _SCI_AATREE_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 +*/ + +} // End of namespace Sci + +#endif // !_SCI_AATREE_H diff --git a/engines/sci/engine/kpathing.cpp b/engines/sci/engine/kpathing.cpp index e61bee0391..b84ea704f0 100644 --- a/engines/sci/engine/kpathing.cpp +++ b/engines/sci/engine/kpathing.cpp @@ -28,7 +28,7 @@ */ #include "sci/include/engine.h" -#include "sci/include/aatree.h" +#include "sci/engine/aatree.h" #include "sci/include/list.h" #include "sci/gfx/gfx_widgets.h" |