diff options
Diffstat (limited to 'engines/sci/engine/aatree.cpp')
| -rw-r--r-- | engines/sci/engine/aatree.cpp | 162 |
1 files changed, 162 insertions, 0 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 |