From 7a12a67ce8ed7be60670338e68d2e211f1ec070f Mon Sep 17 00:00:00 2001 From: Max Horn Date: Sat, 21 Feb 2009 22:54:15 +0000 Subject: SCI: Moved aatree.* files together into engine/ svn-id: r38763 --- engines/sci/engine/aatree.cpp | 162 ++++++++++++++++++++++++++++++++++++++++ engines/sci/engine/aatree.h | 87 +++++++++++++++++++++ engines/sci/engine/kpathing.cpp | 2 +- engines/sci/include/aatree.h | 87 --------------------- engines/sci/module.mk | 2 +- engines/sci/scicore/aatree.cpp | 162 ---------------------------------------- 6 files changed, 251 insertions(+), 251 deletions(-) create mode 100644 engines/sci/engine/aatree.cpp create mode 100644 engines/sci/engine/aatree.h delete mode 100644 engines/sci/include/aatree.h delete mode 100644 engines/sci/scicore/aatree.cpp 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" diff --git a/engines/sci/include/aatree.h b/engines/sci/include/aatree.h deleted file mode 100644 index f40c9e0935..0000000000 --- a/engines/sci/include/aatree.h +++ /dev/null @@ -1,87 +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_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/module.mk b/engines/sci/module.mk index 00dfdbb0cf..c9bdd474a6 100644 --- a/engines/sci/module.mk +++ b/engines/sci/module.mk @@ -6,6 +6,7 @@ MODULE_OBJS = \ exereader.o \ sci.o \ tools.o \ + engine/aatree.o \ engine/game.o \ engine/gc.o \ engine/grammar.o \ @@ -52,7 +53,6 @@ MODULE_OBJS = \ gfx/resource/sci_resmgr.o \ gfx/resource/sci_view_0.o \ gfx/resource/sci_view_1.o \ - scicore/aatree.o \ scicore/sciconsole.o \ scicore/decompress0.o \ scicore/decompress01.o \ diff --git a/engines/sci/scicore/aatree.cpp b/engines/sci/scicore/aatree.cpp deleted file mode 100644 index 80552f6580..0000000000 --- a/engines/sci/scicore/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/include/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 -- cgit v1.2.3