(original) (raw)

ratlib/000775 007207 000054 00000000000 06334350132 013143 5ustar00jmccpcvision000000 000000 ratlib/man/000775 007207 000054 00000000000 05761144013 013720 5ustar00jmccpcvision000000 000000 ratlib/man/man3/000775 007207 000054 00000000000 05761362125 014564 5ustar00jmccpcvision000000 000000 ratlib/man/man3/RATintro.3000644 007207 000054 00000007351 05761170430 016352 0ustar00jmccpcvision000000 000000 .TH RATintro 3 "25 May 1995" .SH NAME intro \- introduction to RAT (Rectangle Access Tree) library functions .SH SYNOPSIS .B #include "ratlib.h" .SH DESCRIPTION .IX introduction "RAT library functions" .IX "RAT library functions, introduction to" The include file .B "ratlib.h" contains declarations for all the functions and structures implemented for use in the RAT library, .BR librat . C programs should be linked with the .B \-lrat option in order to use this library. .PP This library is for inserting, deleting, accessing and querying objects which can be described using two dimensional rectangular regions. Associated with each rectangular object is an arbitrary .B (void *) which can be used to hold either raw data or a pointer to object data. All rectangular objects are described with four parameters, .B x, .B y, .B w, .B h. .B (x,y) are the center point of the rectangle, and .B (w,h) are the width and height of the rectangle, measured as distances to the edges from the center. (Similar in nature to the center and radii of an ellipse.) The queries supported are rectangle intersection and containment using an arbitrary query rectangle, along with an exact/close match. .PP The time needed to insert, delete and access individual points is amortized .B O(log(n)) , and the time to perform either query is .ft B O(n^(3/4) * (log(n) ^ (1/4)) + k) .ft R where .B n is the number of rectangles currently being stored and .B k is the number of rectangles which match the query. .PP .SH DATA STRUCTURES The following structures (and typedef's) are defined in the .B "ratlib.h" file: .RS .LP .nf .ft B #define int32 int; /* Machine dependent */ typedef int32 RATVector[4] typedef struct _rat_obj_list_ { void *object; struct _rat_obj_list_ *next; } RATObjList_t, *RATObjList; typedef struct { RATVector location; RATObjList_t obj_list; } *RATRegion; typedef struct _rat_region_list_ { RATRegion region; struct _rat_region_list_ *next; } RATRegionList_t, *RATRegionList; typedef struct { int (*qualifier)(void *qualification, void *obj); void *qualification; int (*operation)(void *operand, void *obj); void *operand; } RATQualifiedOperation; .ft R .fi .RE .LP .SH LIBRARY FUNCTIONS The following are the functions that are defined in the .B ratlib.h header file. .B RATComputeTransform and .B RATRegionInvert are macros. If .B RAT_NO_INLINE is not defined, the following are also macros: .B RATNearestMatch, RATInsert, and .B RATDelete. .LP .nf .ft B RATComputeTransform(vec, x, y, w, h) RATVector vec; int32 x, y, w, h; RATRegionInvert(region, x, y, w, h) RATRegion region; int32 x, y, w, h; RATRegion RATCreateRegion(x, y, w, h, object) int32 x, y, w, h; void *object; RATTree RATCreateTree() RATRegion RATNearestMatch(tree, x, y, w, h) RATTree tree; int32 x, y, w, h; void RATInsert(tree, x, y, w, h, object) RATTree tree; int32 x, y, w, h; void *object; int RATDelete(tree, x, y, w, h, object_list) RATTree tree; int32 x, y, w, h; RATObjList object_list; RATRegionList RATContainedWithin(tree, x, y, w, h) RATTree tree; int32 x, y, w, h; RATRegionList RATIntersectsWith(tree, x, y, w, h) RATTree tree; int32 x, y, w, h; void RATBoundedWalk(tree, bounds, operation) RATTree tree; RATRegion bounds; RATQualifiedOperation *operation; void RATTotalWalk(tree, operation) RATTree tree; RATQualifiedOperation *operation; .ft R .fi ratlib/man/man3/RATCreateTree.3000644 007207 000054 00000001525 05761164567 017255 0ustar00jmccpcvision000000 000000 .TH RATCreateTree 3 "25 May 1995" .SH NAME RATCreateTree \- Create a Rectangle Access Tree structure .SH SYNOPSIS .LP .nf .ft B #include "ratlib.h" .fi .fi .LP .nf .ft B RATTree RATCreateTree(\|) .ft .fi .IX "RATCreateTree()" "create RAT tree" .SH DESCRIPTION .LP .B RATCreateTree(\|) creates a tree suitable for use in the RAT library and returns it. It can be used for dynamically inserting, deleting, accessing and querying on rectangular objects. The queries which can be done are rectangle intersection and containment for arbitrary query rectangles. Associated with each rectangle is an arbitrary object of type .B (void *), which can be used to store a pointer to an object or as the actual object itself. .LP .SH SEE ALSO .BR RATContainedWithin (3), .BR RATDelete (3), .BR RATInsert (3), .BR RATIntersectsWith (3) .BR RATNearestMatch (3) .fi e the center point of the rectangle, and .B (w,h) are the width and height of the rectangle, measured as distances to the edges from the center. (Similar in nature to theratlib/man/man3/RATContainedWithin.3000644 007207 000054 00000003333 05761356417 020315 0ustar00jmccpcvision000000 000000 .TH RATContainedWithin 3 "25 May 1995" .SH NAME RATContainedWithin \- Given an arbitrary rectangle and a Rectangle Access Tree, find all rectangles completely contained within the query rectangle. .LP RATIntersectsWith \- Given an arbitrary rectangle and a Rectangle Access Tree, find all rectangles that intersect the query rectangle. .SH SYNOPSIS .LP .nf .ft B #include "ratlib.h" .fi .LP .nf .ft B RATRegionList RATContainedWithin(tree, x, y, w, h) RATTree tree; int32 x, y, w, h; RATRegionList RATIntersectsWith(tree, x, y, w, h) RATTree tree; int32 x, y, w, h; .ft .fi .IX "RATContainedWithin()" "query RAT" .IX "RATIntersectsWith()" "query RAT" .SH DESCRIPTION .LP .B RATContainedWithin(\|) and .B RATIntersectsWith(\|) will search for all rectangles which are contained in or intersect the rectangle defined by .B (x,y,w,h), where .B (x,y) are the center of the rectangle and .B (w,h) are the distances from the center to an edge. (Similar in nature to the center and radii of an ellipse, except that it defines a rectangle.) All rectangle objects store in .B tree are returned in an .B RATRegionList. All unique rectangles are reported once. If more than one object occupy the exact same rectangle in the given Rectangle Access Tree, they are reported in linked list form as defined by the .B RATObjList type. (See .BR RATIntro (3).) The actual .B RATRegionList is malloc'd and for each one returned, it is the caller's responsibility to free them. The caller should not free the actual .B RATRegion's contained in the .B RATRegionList which are returned. Those are just pointers to actual elements of the tree. .LP .SH SEE ALSO .BR RATCreateTree (3), .BR RATDelete (3), .BR RATInsert (3), .BR RATIntro (3), .BR RATNearestMatch (3) .fi *object; struct _rat_obj_list_ *next; } RATObjList_t, *RATObjList; typedef struct { RATVector location; RATObjList_t obj_list; } *RATRegion; typedef struct _rat_region_list_ { RATRegion region; struct _rat_region_list_ *neratlib/man/man3/RATIntersectsWith.3000755 007207 000054 0000000000006334350066 023645 2RATContainedWithin.3ustar00jmccpcvision000000 000000 ratlib/man/man3/RATInsert.3000644 007207 000054 00000004746 05761362105 016472 0ustar00jmccpcvision000000 000000 .TH RATInsert 3 "25 May 1995" .SH NAME RATInsert \- Given a Rectangle Access Tree, insert an arbitrary object into it. .LP RATDelete \- Given a Rectangle Access Tree, delete the objects or a subset of the objects at a specified location. .SH SYNOPSIS .LP .nf .ft B #include "ratlib.h" .fi .LP .nf .ft B void RATInsert(tree, x, y, w, h, object) RATTree tree; int32 x, y, w, h; void *object; int RATDelete(tree, x, y, w, h, obj_list) RATTree tree; int32 x, y, w, h; RATObjList obj_list; .ft .fi .IX "RATInsert()" "insert object into RAT" .IX "RATDelete()" "delete objects from RAT" .SH DESCRIPTION .LP .B RATInsert(\) will insert a new object into the Rectangle Access Tree. The object is described and referenced by the rectangle it occupies in 2-D space. As described in .BR RATintro (3), rectangles are defined by .B (x,y,w,h), where .B (x,y) are the center of the rectangle and .B (w,h) are the distances from the center to an edge. (Similar in nature to the center and radii of an ellipse, except that it defines a rectangle.) The actual object, a .B (void *), can be anything you wish, including a non-pointer, as long as it occupies the same amount of space as a pointer on your machine. This function has no return value. .LP .B RATDelete(\) will delete all objects or a subset of objects which occupy a given rectangle. If you wish to delete all objects which occupy a single rectangle, you can simply pass .B NULL as your .B obj_list. If more than one object occupies a single rectangle and you wish to only delete a subset of them, you can pass the subset in an RATObjList, a linked list of type .B (void *). An equality check is performed on the objects to see if a particular item found at the given location matches one of the objects in the list. This means that if you are using the .B object field to point to a structure, the test performed is pointer equality, so a pointer to a separate copy of the same structure will not match. (If you find that you need an equality checker, I'm sure it wouldn't be hard to modify the code to do this.) This function returns non-zero if nothing was deleted and zero if something was deleted. .LP Both operations run in amortized .B O(log(n)) time. Any particular insert or delete can take up to .B O(n*log(n)) time, but this only happens after roughly half the rectangles have been deleted, or the number of rectangles has doubled. .SH SEE ALSO .BR RATContainedWithin (3), .BR RATCreateTree (3), .BR RATIntersectsWith (3), .BR RATIntro (3), .BR RATNearestMatch (3) , RATInsert, and .B RATDeratlib/man/man3/RATDelete.3000755 007207 000054 0000000000006334350066 020245 2RATInsert.3ustar00jmccpcvision000000 000000 ratlib/man/man3/RATNearestMatch.3000644 007207 000054 00000002525 05761362106 017576 0ustar00jmccpcvision000000 000000 .TH RATNearestMatch 3 "25 May 1995" .SH NAME RATNearestMatch \- Given a Rectangle Access Tree and a query rectangle, return either an exact match, or a "close" match .LP .SH SYNOPSIS .LP .nf .ft B #include "ratlib.h" .fi .LP .nf .ft B RATRegion RATNearestMatch(tree, x, y, w, h) RATTree tree; int32 x, y, w, h; .ft .fi .IX "RATNearestMatch()" "get object from RAT" .SH DESCRIPTION .LP .B RATNearestMatch(\) is used to query for particular rectangles in the Rectangle Access Tree. If an exact match exists, it is guaranteed to be returned in a .B RATRegion structure. This structure contains all the objects at the particular location. If there is no exact match, however, a "close" region is returned. In this sense, close is measured both in center point location and in rectangle width and height. As described in .BR RATintro (3), rectangles are defined by .B (x,y,w,h), where .B (x,y) are the center of the rectangle and .B (w,h) are the distances from the center to an edge. (Similar in nature to the center and radii of an ellipse, except that it defines a rectangle.) The .B RATRegion which is returned is .B not guaranteed to be the closest match. This operation runs in amortized .B O(log(n)) time. .LP .SH SEE ALSO .BR RATContainedWithin (3), .BR RATCreateTree (3), .BR RATDelete (3), .BR RATInsert (3), .BR RATIntersectsWith (3), .BR RATIntro (3) jects which occupy a single rectangle, you can simply pass .B NULL as your .B obj_list. If more than one object occupies a single rectangle and you wish to only delete a sratlib/src/000775 007207 000054 00000000000 06170311742 013734 5ustar00jmccpcvision000000 000000 ratlib/src/Makefile000644 007207 000054 00000001156 06170310245 015372 0ustar00jmccpcvision000000 000000 include ./make.conf CINCLUDES=-I. -I../include OBJS=dkdtree.o splaymin.o ratlib.o SRCS=dkdtree.c splaymin.c ratlib.c CFLAGS=$(COPTS) (CINCLUDES)ALL=(CINCLUDES) ALL=(CINCLUDES)ALL=(OBJS) LIBS=-lm all: (ALL)debug:(ALL) debug: (ALL)debug:(MAKE) "CFLAGS=-DDEBUG=1 -g (CFLAGS)"cleanalllibrat.a:(CFLAGS)" clean all librat.a: (CFLAGS)"cleanalllibrat.a:(OBJS) ar rv librat.a (OBJS)ranliblibrat.adepend:ALWAYSrm−f.dependfordin(OBJS) ranlib librat.a depend: ALWAYS rm -f .depend for d in (OBJS)ranliblibrat.adepend:ALWAYSrm−f.dependfordin(SRCS); do (CC)(CC) (CC)(CFLAGS) -M d; done >>.depend clean: rm -rf *.a *.o includes: cp icompat.h ratlib.h dkdtree.h splaylib.h ../../includes testtrees: testtrees.o librat.a (CC)−o(CC) -o (CC)−o@ @.olibrat.a@.o librat.a @.olibrat.a(LIBS) # purify (PUREOPTS)(PUREOPTS) (PUREOPTS)(CC) -o @@ @@.o librat.a $(LIBS) ALWAYS: icular location. If there is no exact match, however, a "close" region is returned. In this sense, close is measured both in center point location and in rectangle width and height. As described in .BR RATintro (3), rectangles are defined by .B (x,y,w,h), where .B (x,y) are the center of the rectangle and .B (w,h) are the distances from the center to an edge. (Similar in nature to the center and rratlib/src/dkdtree.c000644 007207 000054 00000103625 06170307167 015535 0ustar00jmccpcvision000000 000000 /* ** Copyright (C) 1995 Rick Romero and Carnegie Mellon University ** ** 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 1, 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., 675 Mass Ave, Cambridge, MA 02139, USA. */ #include #include #include #include #include "dkdtree.h" #define DKDLEAF_MALLOC_SIZE 100 static DKDLeaf_p DKDLeafFreeList = NULL; SplayNode_p DKDFindKthRecurse(SplayNode_p, int, int *); SplayNode_p DKDFindMedian(SplayTree_p, int); void DKDRebalanceLowerLevels(DKDNode_p, DKDNode_p, int32, int32); void DKDRebuildTree(DKDTree_p); int DKDRecurseRebuild(SplayTree_p, SplayTree_p, int, int32, int32, int32); void DKDRecurseCopyAndFreeElements(SplayNode_p, SplayTree_p); void DKDRecurseCreateAndFree(SplayNode_p, SplayTree_p, int); void DKDCreateSortTreeAndFree(DKDTree_p, SplayTree_p); void DKDCopyAndFreeTreeElements(SplayTree_p, SplayTree_p); SplayNode_p DKDFindLastOf(SplayTree_p, SplayNode_p, SplayNode_p, int, int *); SplayNode_p DKDSkipRepeats(SplayTree_p, SplayNode_p, int, int *); void DKDRecurseDestroy(SplayNode_p, int); int dkd_compare_nodes(void *obj1, void *obj2); int dkd_compare_leaves(void *obj1, void *obj2); int dkd_compare_leaves1(void *obj1, void *obj2); int dkd_compare_leaves2(void *obj1, void *obj2); int dkd_compare_leaves3(void *obj1, void *obj2); #ifdef DEBUG int rebalance_counts = 0; int rebuild_counts = 0; int inserts = 0; int deletes = 0; #endif int dkd_compare_nodes(void *obj1, void *obj2) { /* Check to see if either is a point, and not a range */ if (((DKDNode_p) obj1)->left == ((DKDNode_p) obj1)->right) { if (((DKDNode_p) obj2)->left <= ((DKDNode_p) obj1)->left) { if (((DKDNode_p) obj2)->right > ((DKDNode_p) obj1)->left) { return 0; } else { return 1; } } else { return -1; } } else if (((DKDNode_p) obj2)->left == ((DKDNode_p) obj2)->right) { if (((DKDNode_p) obj1)->left <= ((DKDNode_p) obj2)->left) { if (((DKDNode_p) obj1)->right > ((DKDNode_p) obj2)->left) { return 0; } else { return -1; } } else { return 1; } } else { /* We're comparing intervals, which should all be non-overlapping, so this * is a bit easier. */ return ((((DKDNode_p) obj1)->left == ((DKDNode_p) obj2)->left) ? 0 : (((DKDNode_p) obj1)->left > ((DKDNode_p) obj2)->left) ? 1 : -1); } /* if (((DKDNode_p) obj2)->left <= ((DKDNode_p) obj1)->left) { if (((DKDNode_p) obj2)->right > ((DKDNode_p) obj1)->left) { return 0; } else { return 1; } } else { return -1; } */ } int dkd_compare_leaves(void *obj1, void *obj2) { if (((DKDLeaf_p) obj1)->location[0] == ((DKDLeaf_p) obj2)->location[0]) { if (((DKDLeaf_p) obj1)->location[1] == ((DKDLeaf_p) obj2)->location[1]) { if (((DKDLeaf_p) obj1)->location[2] == ((DKDLeaf_p) obj2)->location[2]) { return ((((DKDLeaf_p) obj1)->location[3] == ((DKDLeaf_p) obj2)->location[3]) ? 0 : ((((DKDLeaf_p) obj1)->location[3] < ((DKDLeaf_p) obj2)->location[3]) ? -1 : 1)); } else return ((((DKDLeaf_p) obj1)->location[2] < ((DKDLeaf_p) obj2)->location[2]) ? -1 : 1); } else return ((((DKDLeaf_p) obj1)->location[1] < ((DKDLeaf_p) obj2)->location[1]) ? -1 : 1); } else return ((((DKDLeaf_p) obj1)->location[0] < ((DKDLeaf_p) obj2)->location[0]) ? -1 : 1); } int dkd_compare_leaves1(void *obj1, void *obj2) { if (((DKDLeaf_p) obj1)->location[1] == ((DKDLeaf_p) obj2)->location[1]) { if (((DKDLeaf_p) obj1)->location[2] == ((DKDLeaf_p) obj2)->location[2]) { return ((((DKDLeaf_p) obj1)->location[3] == ((DKDLeaf_p) obj2)->location[3]) ? 0 : ((((DKDLeaf_p) obj1)->location[3] < ((DKDLeaf_p) obj2)->location[3]) ? -1 : 1)); } else return ((((DKDLeaf_p) obj1)->location[2] < ((DKDLeaf_p) obj2)->location[2]) ? -1 : 1); } else return ((((DKDLeaf_p) obj1)->location[1] < ((DKDLeaf_p) obj2)->location[1]) ? -1 : 1); } int dkd_compare_leaves2(void *obj1, void *obj2) { if (((DKDLeaf_p) obj1)->location[2] == ((DKDLeaf_p) obj2)->location[2]) { return ((((DKDLeaf_p) obj1)->location[3] == ((DKDLeaf_p) obj2)->location[3]) ? 0 : ((((DKDLeaf_p) obj1)->location[3] < ((DKDLeaf_p) obj2)->location[3]) ? -1 : 1)); } else return ((((DKDLeaf_p) obj1)->location[2] < ((DKDLeaf_p) obj2)->location[2]) ? -1 : 1); } int dkd_compare_leaves3(void *obj1, void *obj2) { return ((((DKDLeaf_p) obj1)->location[3] == ((DKDLeaf_p) obj2)->location[3]) ? 0 : ((((DKDLeaf_p) obj1)->location[3] < ((DKDLeaf_p) obj2)->location[3]) ? -1 : 1)); } typedef int (*compare_function)(void *, void *); compare_function dkd_compare_leaves_array[DKD_DIMENSIONS] = \ { dkd_compare_leaves, dkd_compare_leaves1, dkd_compare_leaves2, dkd_compare_leaves3 }; #ifdef DEBUG int count_points(SplayNode_p node) { int c = 0; if (node->left) c = count_points(node->left); if (node->right) return (1 + c + count_points(node->right)); return (1+c); } #endif DKDLeaf_p DKDCreateLeaf() { DKDLeaf_p tmp; if (DKDLeafFreeList) { tmp = DKDLeafFreeList; DKDLeafFreeList = (DKDLeaf_p) tmp->obj_list.next; } else { int i; tmp = (DKDLeaf_p) malloc(sizeof(DKDLeaf_t) * DKDLEAF_MALLOC_SIZE); tmp += (DKDLEAF_MALLOC_SIZE-1); tmp->obj_list.next = (DKDObjList_p) DKDLeafFreeList; tmp--; for (i=DKDLEAF_MALLOC_SIZE-2; i; i--, tmp--) tmp->obj_list.next = (DKDObjList_p) (tmp+1); DKDLeafFreeList = tmp+1; } return tmp; } void DKDFreeLeaf(DKDLeaf_p leaf) { if (leaf) { leaf->obj_list.next = (DKDObjList_p) DKDLeafFreeList; DKDLeafFreeList = leaf; } } void DKDRecurseDestroy(SplayNode_p snode, int dimensions) { if (snode==NULL) return; if (dimensions>0) { if (snode->left) { DKDRecurseDestroy(snode->left, dimensions); } DKDRecurseDestroy(((DKDNode_p) snode->obj)->stree->root, dimensions - 1); free(((DKDNode_p) snode->obj)->stree); free(snode->obj); if (snode->right) { DKDRecurseDestroy(snode->right, dimensions); } SplayFreeNode(snode); } else { if (snode->left) DKDRecurseDestroy(snode->left, dimensions); if (snode->right) DKDRecurseDestroy(snode->right, dimensions); DKDFreeLeaf((DKDLeaf_p) snode->obj); SplayFreeNode(snode); } } void DKDDestroyTree(DKDTree_p dkdtree) { if (dkdtree) { if (dkdtree->stree) { if (dkdtree->stree->root) DKDRecurseDestroy(dkdtree->stree->root, dkdtree->dimensions-1); free(dkdtree->stree); } free(dkdtree); } } DKDTree_p CreateDKDTree(int d) { DKDTree_p dkdtree; DKDNode_p node; SplayTree_p stree; int i; dkdtree = (DKDTree_p) malloc(sizeof(DKDTree_t)); dkdtree->stree = stree = CreateSplay(dkd_compare_nodes); dkdtree->uppernodes = 1; dkdtree->lowernodes = LOWER_NODES_MIN; dkdtree->points = 0; dkdtree->dimensions = d; dkdtree->nodes = 1; dkdtree->inserts = dkdtree->deletes = 0; dkdtree->maxmods = LOWER_NODES_MIN * 8; for (i = d-1; i>0; i--) { node = (DKDNode_p) malloc(sizeof(DKDNode_t)); node->dimensions = i; if (i > 1) { node->nodes = 1; node->maxnodes = 2; } else { node->nodes = 0; node->maxnodes = LOWER_NODES_MIN; } node->points = 0; node->maxpoints = 1 << i; /* Max points allowed is 2 per low-level */ /* tree, or 2^d at the top level */ node->inserts = 0; node->deletes = 0; node->left = -MAXINT32; node->right = MAXINT32; if (i > 1) { node->stree = CreateSplay(dkd_compare_nodes); } else { node->stree = CreateSplay(dkd_compare_leaves); } SplayInsert(stree, (void *) node); stree = node->stree; } return dkdtree; } /* Find the median element in the splay tree. Just go until you reach the ** (count)'th element. */ SplayNode_p DKDFindKthRecurse(SplayNode_p node, int count, int *curnode) { SplayNode_p retval; if (node->left != NULL) { retval = DKDFindKthRecurse(node->left, count, curnode); if (*curnode >= count) return retval; } (*curnode)++; if (*curnode >= count) { return (SplayNode_p) node; } if (node->right != NULL) { return DKDFindKthRecurse(node->right, count, curnode); } return NULL; } /* ** Get the median element of the splay tree */ SplayNode_p DKDFindMedian(SplayTree_p tree, int points) { SplayNode_p node; int i; i = 0; if (tree->root) node = DKDFindKthRecurse(tree->root, (points + 1) / 2, &i); else return NULL; return node; } #define INLINE 0x1 void DKDRecurseCopyAndFreeElements(SplayNode_p oldnode, SplayTree_p newstree) { if (oldnode->left) { #if (INLINE&1) if (oldnode->left->left) { #if (INLINE&2) if (oldnode->left->left->left) { #if (INLINE&4) if (oldnode->left->left->left->left) { DKDRecurseCopyAndFreeElements(oldnode->left->left->left->left, newstree); } if (oldnode->left->left->left->right) { DKDRecurseCopyAndFreeElements(oldnode->left->left->left->right, newstree); } SplayInsert(newstree, oldnode->left->left->left->obj); SplayFreeNode(oldnode->left->left->left); #else /* INLINE&4 */ DKDRecurseCopyAndFreeElements(oldnode->left->left->left, newstree); #endif /* INLINE&4 */ } if (oldnode->left->left->right) { #if (INLINE&4) if (oldnode->left->left->right->left) { DKDRecurseCopyAndFreeElements(oldnode->left->left->right->left, newstree); } if (oldnode->left->left->right->right) { DKDRecurseCopyAndFreeElements(oldnode->left->left->right->right, newstree); } SplayInsert(newstree, oldnode->left->left->right->obj); SplayFreeNode(oldnode->left->left->right); #else /* INLINE&4 */ DKDRecurseCopyAndFreeElements(oldnode->left->left->right, newstree); #endif /* INLINE&4 */ } SplayInsert(newstree, oldnode->left->left->obj); SplayFreeNode(oldnode->left->left); #else /* INLINE & 2 */ DKDRecurseCopyAndFreeElements(oldnode->left->left, newstree); #endif /* INLINE & 2 */ } if (oldnode->left->right) { #if (INLINE&2) if (oldnode->left->right->left) { #if (INLINE&4) if (oldnode->left->right->left->left) { DKDRecurseCopyAndFreeElements(oldnode->left->right->left->left, newstree); } if (oldnode->left->right->left->right) { DKDRecurseCopyAndFreeElements(oldnode->left->right->left->right, newstree); } SplayInsert(newstree, oldnode->left->right->left->obj); SplayFreeNode(oldnode->left->right->left); #else /* INLINE & 4 */ DKDRecurseCopyAndFreeElements(oldnode->left->right->left, newstree); #endif /* INLINE & 4 */ } if (oldnode->left->right->right) { #if (INLINE&4) if (oldnode->left->right->right->left) { DKDRecurseCopyAndFreeElements(oldnode->left->right->right->left, newstree); } if (oldnode->left->right->right->right) { DKDRecurseCopyAndFreeElements(oldnode->left->right->right->right, newstree); } SplayInsert(newstree, oldnode->left->right->right->obj); SplayFreeNode(oldnode->left->right->right); #else /* INLINE & 4 */ DKDRecurseCopyAndFreeElements(oldnode->left->right->right, newstree); #endif /* INLINE & 4 */ } SplayInsert(newstree, oldnode->left->right->obj); SplayFreeNode(oldnode->left->right); #else /* INLINE & 2 */ DKDRecurseCopyAndFreeElements(oldnode->left->right, newstree); #endif /* INLINE & 2 */ } SplayInsert(newstree, oldnode->left->obj); SplayFreeNode(oldnode->left); #else /* INLINE & 1 */ DKDRecurseCopyAndFreeElements(oldnode->left, newstree); #endif /* INLINE & 1 */ } if (oldnode->right) { #if (INLINE&1) if (oldnode->right->left) { #if (INLINE&2) if (oldnode->right->left->left) { #if (INLINE&4) if (oldnode->right->left->left->left) { DKDRecurseCopyAndFreeElements(oldnode->right->left->left->left, newstree); } if (oldnode->right->left->left->right) { DKDRecurseCopyAndFreeElements(oldnode->right->left->left->right, newstree); } SplayInsert(newstree, oldnode->right->left->left->obj); SplayFreeNode(oldnode->right->left->left); #else /* INLINE & 4 */ DKDRecurseCopyAndFreeElements(oldnode->right->left->left, newstree); #endif /* INLINE & 4 */ } if (oldnode->right->left->right) { #if (INLINE&4) if (oldnode->right->left->right->left) { DKDRecurseCopyAndFreeElements(oldnode->right->left->right->left, newstree); } if (oldnode->right->left->right->right) { DKDRecurseCopyAndFreeElements(oldnode->right->left->right->right, newstree); } SplayInsert(newstree, oldnode->right->left->right->obj); SplayFreeNode(oldnode->right->left->right); #else /* INLINE & 4 */ DKDRecurseCopyAndFreeElements(oldnode->right->left->right, newstree); #endif /* INLINE & 4 */ } SplayInsert(newstree, oldnode->right->left->obj); SplayFreeNode(oldnode->right->left); #else /* INLINE & 2 */ DKDRecurseCopyAndFreeElements(oldnode->right->left, newstree); #endif /* INLINE & 2 */ } if (oldnode->right->right) { #if (INLINE&2) if (oldnode->right->right->left) { #if (INLINE&4) if (oldnode->right->right->left->left) { DKDRecurseCopyAndFreeElements(oldnode->right->right->left->left, newstree); } if (oldnode->right->right->left->right) { DKDRecurseCopyAndFreeElements(oldnode->right->right->left->right, newstree); } SplayInsert(newstree, oldnode->right->right->left->obj); SplayFreeNode(oldnode->right->right->left); #else /* INLINE & 4 */ DKDRecurseCopyAndFreeElements(oldnode->right->right->left, newstree); #endif /* INLINE & 4 */ } if (oldnode->right->right->right) { #if (INLINE&4) if (oldnode->right->right->right->left) { DKDRecurseCopyAndFreeElements(oldnode->right->right->right->left, newstree); } if (oldnode->right->right->right->right) { DKDRecurseCopyAndFreeElements(oldnode->right->right->right->right, newstree); } SplayInsert(newstree, oldnode->right->right->right->obj); SplayFreeNode(oldnode->right->right->right); #else /* INLINE & 4 */ DKDRecurseCopyAndFreeElements(oldnode->right->right->right, newstree); #endif /* INLINE & 4 */ } SplayInsert(newstree, oldnode->right->right->obj); SplayFreeNode(oldnode->right->right); #else /* INLINE & 2 */ DKDRecurseCopyAndFreeElements(oldnode->right->right, newstree); #endif /* INLINE & 2 */ } SplayInsert(newstree, oldnode->right->obj); SplayFreeNode(oldnode->right); #else /* INLINE & 1 */ DKDRecurseCopyAndFreeElements(oldnode->right, newstree); #endif /* INLINE & 1 */ } SplayInsert(newstree, oldnode->obj); SplayFreeNode(oldnode); } void DKDCopyAndFreeTreeElements(SplayTree_p oldstree, SplayTree_p newstree) { if (oldstree) { if (oldstree->root) { DKDRecurseCopyAndFreeElements(oldstree->root, newstree); } free(oldstree); } } SplayNode_p DKDFindLastOf(SplayTree_p stree, SplayNode_p orig, SplayNode_p curnode, int dim, int *count) { SplayNode_p lastnode; if (curnode->left) { lastnode = DKDFindLastOf(stree, orig, curnode->left, dim, count); } if (((DKDLeaf_p) curnode->obj)->location[dim] == ((DKDLeaf_p) orig->obj)->location[dim]) { (*count)++; if (curnode->right) { if (((DKDLeaf_p) curnode->right->leftmin->obj)->location[dim] == ((DKDLeaf_p) orig->obj)->location[dim]) { return DKDFindLastOf(stree, orig, curnode->right, dim, count); } else { return curnode; } } else { return curnode; } } else { return lastnode; } } SplayNode_p DKDSkipRepeats(SplayTree_p stree, SplayNode_p snode, int dim, int *count) { if (snode->right) { if (((DKDLeaf_p) snode->right->leftmin->obj)->location[dim] == ((DKDLeaf_p) snode->obj)->location[dim]) { return DKDFindLastOf(stree, snode, snode->right, dim, count); } else { return snode; } } return snode; } /* Recursively go down and rebuild all the different trees. * First split up the current tree, and for each split on the current tree, * go down and rebuild its children */ int DKDRecurseRebuild(SplayTree_p newtree, SplayTree_p sorttree, int dimensions, int32 uppernodes, int32 lowernodes, int32 totalpoints) { DKDNode_p newnode; SplayNode_p splitnode; SplayTree_p newstree, tmpstree; int i, count, done = 0; int32 oldright = -MAXINT32; if (dimensions > 0) { #ifdef DEBUG fflush(stdout); printf("Splitting trees at dimension %d, total points = %d\n", dimensions, totalpoints); fflush(stdout); #endif for (i = 0; (i < uppernodes) && (totalpoints - done > 0) && (sorttree->root); i++) { /* count = (totalpoints - done) / (uppernodes - i);*/ count = 0; #ifdef DEBUG fflush(stdout); if (count_points(sorttree->root) != totalpoints - done) { printf("oops, Points don't add up\n"); } printf("Current split: %d th node, %d nodes done, %d points remaining\n", (totalpoints - done) / (uppernodes - i), i, totalpoints - done); fflush(stdout); #endif newnode = (DKDNode_p) malloc(sizeof(DKDNode_t)); newnode->inserts = newnode->deletes = 0; if (dimensions > 1) { newnode->maxnodes = 2 * uppernodes; newnode->stree = CreateSplay(dkd_compare_nodes); } else { newnode->maxnodes = 2 * lowernodes; newnode->stree = CreateSplay(dkd_compare_leaves); } newnode->dimensions = dimensions; if (totalpoints - done > 1) { splitnode = DKDFindKthRecurse(sorttree->root, (totalpoints - done) / (uppernodes - i), &count); /* Could have been that there were duplicates of the same thing. * Need to move them over as well, so that intervals don't overlap * (pain in the ass :-( ) */ SplayNode(sorttree, splitnode); count = 0; splitnode = DKDSkipRepeats(sorttree, splitnode, dimensions, &count); newstree = CreateSplay(dkd_compare_leaves_array[dimensions]); /* Bring this guy to the top for splitting */ SplayNode(sorttree, splitnode); /* And split the trees */ newstree->root = sorttree->root->right; if (newstree->root != NULL) newstree->root->parent = NULL; sorttree->root->right = NULL; if ((totalpoints - done) / (uppernodes - i)) newnode->points = (totalpoints - done) / (uppernodes - i) + count; else newnode->points = 1 + count; #ifdef DEBUG if (newnode->points != (count_points(sorttree->root))) { printf("oops right here\n"); } #endif newnode->maxpoints = (2 * newnode->points < LOWER_NODES_MIN) ? LOWER_NODES_MIN : 2 * newnode->points; /* just set this to the old right */ newnode->left = oldright; if ((i + 1 < uppernodes) && (totalpoints - newnode->points - done > 0)) /* add the minimum of the greater tree to the maximum of the lower * tree and divide by two to split between them */ newnode->right = (((DKDLeaf_p) newstree->root->leftmin->obj)->location[dimensions] + ((DKDLeaf_p) sorttree->root->obj)->location[dimensions] + 1) / 2; else /* we're at the end of the tree, just set it to virtual infinity */ newnode->right = MAXINT32; oldright = newnode->right; tmpstree = sorttree; sorttree = newstree; newstree = CreateSplay(dkd_compare_leaves_array[dimensions - 1]); DKDCopyAndFreeTreeElements(tmpstree, newstree); } else { newnode->points = 1; newnode->maxpoints = LOWER_NODES_MIN; newnode->left = oldright; newnode->right = MAXINT32; /* ((DKDLeaf_p) sorttree->root->obj)->location[dimensions - 1];*/ newstree = CreateSplay(dkd_compare_leaves_array[dimensions - 1]); SplayInsert(newstree, sorttree->root->obj); SplayFreeNode(sorttree->root); sorttree->root = NULL; } newnode->nodes = DKDRecurseRebuild(newnode->stree, newstree, dimensions - 1, uppernodes, lowernodes, newnode->points); done = done + newnode->points; SplayInsert(newtree, (void *) newnode); #ifdef DEBUG fflush(stdout); printf("Done at dimension %d\n", dimensions); fflush(stdout); #endif } } else { /* we've already done this work, just copy over a pointer to the root * and be done with it. */ *newtree = *sorttree; i = totalpoints; } free(sorttree); /* Return the number of nodes or leaves that were completed */ return i; } void DKDRecurseCreateAndFree(SplayNode_p node, SplayTree_p newtree, int dimensions) { if (node == NULL) return; if (node->left) { DKDRecurseCreateAndFree(node->left, newtree, dimensions); } if (dimensions > 1) { DKDRecurseCreateAndFree(((DKDNode_p) node->obj)->stree->root, newtree, dimensions - 1); free(((DKDNode_p) node->obj)->stree); free(node->obj); } else { /* This is a DKDLeaf_p, we don't want to free it. */ SplayInsert(newtree, node->obj); } if (node->right) { DKDRecurseCreateAndFree(node->right, newtree, dimensions); } SplayFreeNode(node); } void DKDCreateSortTreeAndFree(DKDTree_p tree, SplayTree_p stree) { DKDRecurseCreateAndFree(tree->stree->root, stree, tree->dimensions); tree->stree->root = NULL; } /* Everything must be rebuilt cause we've done too many inserts & deletes */ /* Have to kill the entire tree and start over from scratch. */ void DKDRebuildTree(DKDTree_p tree) { int32 lowernodes, uppernodes; SplayTree_p sorttree; if (tree->points > 1) { lowernodes = pow((double) tree->points, (double) 1.0 / tree->dimensions) * pow((double) log((double) tree->points) * (1.0 / M_LN2), (double) 1.0 - 1.0 / tree->dimensions) + 0.5; if (lowernodes < LOWER_NODES_MIN) lowernodes = LOWER_NODES_MIN; uppernodes = pow((double) tree->points, 1.0 / tree->dimensions) * pow((double) log((double) tree->points) * (1.0 / M_LN2), -1.0 / tree->dimensions) + 0.5; } else { lowernodes = LOWER_NODES_MIN; uppernodes = 1; } #ifdef DEBUG fflush(stdout); printf("Rebuilding tree w/ %d upper nodes and %d leaves\n", uppernodes, lowernodes); fflush(stdout); #endif tree->uppernodes = uppernodes; tree->lowernodes = lowernodes; tree->nodes = uppernodes; tree->inserts = tree->deletes = 0; tree->maxmods = tree->points; if (tree->maxmods < LOWER_NODES_MIN / 2) tree->maxmods = LOWER_NODES_MIN / 2; sorttree = CreateSplay(dkd_compare_leaves_array[tree->dimensions-1]); DKDCreateSortTreeAndFree(tree, sorttree); DKDRecurseRebuild(tree->stree, sorttree, tree->dimensions - 1, uppernodes, lowernodes, tree->points); } void DKDRebalanceLowerLevels(DKDNode_p upper, DKDNode_p lower, int32 uppernodes, int32 lowernodes) { DKDNode_p newnode; DKDLeaf_p splitpoint; SplayTree_p sorttree; SplayNode_p splitnode; int count; sorttree = CreateSplay(dkd_compare_leaves_array[lower->dimensions]); DKDRecurseCreateAndFree(lower->stree->root, sorttree, lower->dimensions); splitnode = DKDFindMedian(sorttree, lower->points); count = 0; SplayNode(sorttree, splitnode); splitnode = DKDSkipRepeats(sorttree, splitnode, lower->dimensions, &count); splitpoint = (DKDLeaf_p) splitnode->obj; /* Set up a new node to hold the new tree */ newnode = (DKDNode_p) malloc(sizeof(DKDNode_t)); newnode->dimensions = lower->dimensions; newnode->maxnodes = lower->maxnodes; newnode->maxpoints = lower->maxpoints; newnode->inserts = lower->inserts = newnode->deletes = lower->deletes = 0; newnode->stree = CreateSplay(dkd_compare_leaves_array[lower->dimensions]); SplayNode(sorttree, splitnode); newnode->stree->root = sorttree->root->right; if (newnode->stree->root) { newnode->stree->root->parent = NULL; sorttree->root->right = NULL; } free(lower->stree); lower->stree = sorttree; if (newnode->stree->root) { newnode->left = ((((DKDLeaf_p) newnode->stree->root->leftmin->obj)->location[lower->dimensions]) + splitpoint->location[lower->dimensions] + 1) / 2; newnode->right = lower->right; lower->right = newnode->left; newnode->points = lower->points / 2 - count; lower->points = lower->points - newnode->points; sorttree = CreateSplay(dkd_compare_leaves_array[lower->dimensions - 1]); DKDRecurseCreateAndFree(newnode->stree->root, sorttree, 1); free(newnode->stree); if (lower->dimensions == 1) newnode->stree = CreateSplay(dkd_compare_leaves); else newnode->stree = CreateSplay(dkd_compare_nodes); newnode->nodes = DKDRecurseRebuild(newnode->stree, sorttree, lower->dimensions - 1, uppernodes, lowernodes, newnode->points); } sorttree = CreateSplay(dkd_compare_leaves_array[lower->dimensions - 1]); DKDRecurseCreateAndFree(lower->stree->root, sorttree, 1); free(lower->stree); if (lower->dimensions == 1) lower->stree = CreateSplay(dkd_compare_leaves); else lower->stree = CreateSplay(dkd_compare_nodes); lower->nodes = DKDRecurseRebuild(lower->stree, sorttree, lower->dimensions - 1, uppernodes, lowernodes, lower->points); if (newnode->stree->root) { #ifdef DEBUG if (newnode->nodes != count_points(newnode->stree->root)) { fflush(stdout); fprintf(stderr, "Error, wrong number of points in rebalanced tree.\n"); } if (lower->nodes != count_points(lower->stree->root)) { fflush(stdout); fprintf(stderr, "Error, wrong number of points in remainder of tree " "during rebalance.\n"); } if (newnode->left > newnode->right || lower->left > lower->right) { printf("oops again\n"); } #endif SplayInsert(upper->stree, newnode); upper->nodes++; } else { free(newnode->stree); free(newnode); } } void DKDInsert(DKDTree_p tree, dkd_vector location, void *obj) { int i; DKDNode_p curnode, newnode, oldnodes[DKD_DIMENSIONS]; DKDNode_t curnode_t; DKDLeaf_t tmpleaf_t; DKDLeaf_p tmpleaf, newleaf; SplayTree_p curstree; /* I didn't want to do a loop, but this will have to change if you * change the dimensionality of the structure */ tmpleaf_t.location[0] = location[0]; tmpleaf_t.location[1] = location[1]; tmpleaf_t.location[2] = location[2]; tmpleaf_t.location[3] = location[3]; tmpleaf = &tmpleaf_t; #ifdef DEBUG2 fflush(stdout); printf("Inserting element [%d %d %d %d]\n", location[0], location[1], location[2], location[3]); inserts++; #endif curnode = &curnode_t; curstree = tree->stree; /* tree->points++;*/ for (i = tree->dimensions-1; i; i--) { curnode_t.left = curnode_t.right = location[i]; oldnodes[i] = newnode = (DKDNode_p) SplayAccess(curstree, curnode); #ifdef DEBUG if (newnode->left > curnode_t.left || newnode->right < curnode_t.left) { fprintf(stderr, "Error inserting element\n"); } #endif /* newnode->points++;*/ curstree = newnode->stree; } SplayAccess(curstree, tmpleaf); if ((!curstree->root) || ((curstree->compare)(curstree->root->obj, tmpleaf))) { /* This is a new location, insert and update the path of nodes taken */ newleaf = DKDCreateLeaf(); newleaf->obj_list.next = NULL; newleaf->obj_list.object = obj; newleaf->location[0] = location[0]; newleaf->location[1] = location[1]; newleaf->location[2] = location[2]; newleaf->location[3] = location[3]; newnode->nodes++; newnode->points++; tree->points++; SplayInsert(curstree, newleaf); tree->inserts++; for (i=2; i<dkd_dimensions; i++)="" {="" (oldnodes[i]-="">inserts)++; (oldnodes[i]->points)++; } /* Check to see if I fell out of balance */ if (tree->inserts > tree->maxmods) { #ifdef DEBUG rebuild_counts++; printf("Rebuilding\n"); #endif DKDRebuildTree(tree); } else { if (oldnodes[1]->nodes >= oldnodes[1]->maxnodes) { if (oldnodes[2]->nodes >= oldnodes[2]->maxnodes) { if (oldnodes[3]->nodes >= oldnodes[3]->maxnodes) { #ifdef DEBUG rebuild_counts++; printf("Rebuilding\n"); #endif DKDRebuildTree(tree); } else { #ifdef DEBUG rebalance_counts+=2; printf("Rebalancing\n"); #endif DKDRebalanceLowerLevels(oldnodes[3], oldnodes[2], tree->uppernodes, tree->lowernodes); } } else { #ifdef DEBUG rebalance_counts+=1; printf("Rebalancing\n"); #endif DKDRebalanceLowerLevels(oldnodes[2], oldnodes[1], tree->uppernodes, tree->lowernodes); } } #ifdef DEBUG fflush(stdout); printf("Done Rebalance\n"); #endif } } else { /* This is not a new location, just tack it onto the end of the list */ /* and don't update the path w/ new inserts. */ DKDObjList_p newobj; tmpleaf = (DKDLeaf_p) curstree->root->obj; newobj = (DKDObjList_p) malloc(sizeof(DKDObjList_t)); newobj->object = obj; newobj->next = tmpleaf->obj_list.next; tmpleaf->obj_list.next = newobj; } } int DKDDeleteLeafSubset(DKDLeaf_p leaf, DKDObjList_p objs) { DKDObjList_p l1, l2, oldobj; int killit, killall = 1; if (objs) { /* Have to check to see if we want to delete first */ oldobj = &(leaf->obj_list); l1 = oldobj->next; while (l1) { l2 = objs; killit = 0; while (l2 && !(killit)) { if (l2->object == l1->object) killit = 1; else l2 = l2->next; } if (killit) { free(l1->object); oldobj->next = l1->next; free(l1); l1 = oldobj->next; } else { killall = 0; l1 = l1->next; } } l1 = &(leaf->obj_list); l2 = objs; killit = 0; while (l2 && !(killit)) { if (l2->object == l1->object) killit = 1; else l2 = l2->next; } if (killit) { if (l1->next) { leaf->obj_list = *(l1->next); free(l1->next); } } else { killall = 0; } } else { l1 = leaf->obj_list.next; while (l1) { l2 = l1; l1 = l1->next; free(l2); } } return killall; } int DKDDelete(DKDTree_p tree, dkd_vector location, DKDObjList_p objs) { int i; DKDNode_p curnode, newnode, oldnodes[DKD_DIMENSIONS]; DKDNode_t curnode_t; DKDLeaf_t tmpleaf_t; DKDLeaf_p tmpleaf; SplayTree_p curstree; SplayNode_p minright, maxleft; /* I didn't want to do a loop, but this will have to change if you * change the dimensionality of the structure */ tmpleaf_t.location[0] = location[0]; tmpleaf_t.location[1] = location[1]; tmpleaf_t.location[2] = location[2]; tmpleaf_t.location[3] = location[3]; tmpleaf = &tmpleaf_t; #ifdef DEBUG deletes++; #endif curnode = &curnode_t; curstree = tree->stree; for (i = tree->dimensions-1; i; i--) { curnode_t.left = curnode_t.right = location[i]; oldnodes[i] = newnode = (DKDNode_p) SplayAccess(curstree, curnode); curstree = newnode->stree; } SplayAccess(curstree, tmpleaf); if (curstree->root) { if ((curstree->compare)(curstree->root->obj, tmpleaf) == 0) { /* We have a match that we want to delete, check to see if it is * one of the ones we want to delete based on objs * (objs == NULL) deletes everything */ if (DKDDeleteLeafSubset((DKDLeaf_p) curstree->root->obj, objs)) { /* If this returns non-zero, then everything was deleted from this * leaf and everyone above needs to know */ tree->points--; tree->deletes++; for (i = 1; i < tree->dimensions; i++) { (oldnodes[i]->points)--; (oldnodes[i]->deletes)++; } (oldnodes[1]->nodes)--; DKDFreeLeaf((DKDLeaf_p) curstree->root->obj); SplayDelete(curstree, tmpleaf); if (oldnodes[1]->points == 0) { if (oldnodes[2]->points == 0) { oldnodes[2]->deletes++; oldnodes[2]->nodes--; SplayDelete(oldnodes[2]->stree, oldnodes[1]); free(oldnodes[1]->stree); free(oldnodes[1]); DKDRebuildTree(tree); } else { #ifdef DEBUG printf("Merging two lower nodes\n"); #endif /* have to fix this guy up... want to merge the left and right of * the two nodes to the left and right of this one so that we have * full coverage over the interval, check out oldnodes[2].stree * members to try to find the correct nodes to merge. */ minright = oldnodes[2]->stree->root->right; if (minright) minright = minright->leftmin; maxleft = oldnodes[2]->stree->root->left; if (maxleft) { while(maxleft->right) { maxleft = maxleft->right; } } if (minright && maxleft) { /* ((DKDNode_p) minright->obj)->left = (((DKDNode_p) minright->obj)->left + ((DKDNode_p) maxleft->obj)->right + 1) / 2; ((DKDNode_p) maxleft->obj)->right = ((DKDNode_p) minright->obj)->left; */ ((DKDNode_p) minright->obj)->left = ((DKDNode_p) maxleft->obj)->right = (oldnodes[1]->left + oldnodes[1]->right + 1) / 2; } else if (minright) { ((DKDNode_p) minright->obj)->left = -MAXINT32; } else if (maxleft) { ((DKDNode_p) maxleft->obj)->right = MAXINT32; } else { /* I shouldn't have hit this region... */ printf("Clean up needed...fucked up\n"); } SplayDelete(oldnodes[2]->stree, oldnodes[1]); oldnodes[2]->deletes++; oldnodes[2]->nodes--; free(oldnodes[1]->stree); free(oldnodes[1]); } } if (tree->deletes > tree->maxmods) { #ifdef DEBUG rebuild_counts++; printf("Rebuilding\n"); #endif DKDRebuildTree(tree); } return 0; } /* I deleted some of the objects, but not all of them */ return 0; } } return 1; } DKDLeaf_p DKDAccess(DKDTree_p tree, DKDLeaf_p node) { int i; DKDLeaf_p leaf; DKDNode_p curnode, newnode; DKDNode_t curnode_t; SplayTree_p curstree; curnode = &curnode_t; curstree = tree->stree; for (i = tree->dimensions-1; i; i--) { curnode_t.left = curnode_t.right = node->location[i]; newnode = (DKDNode_p) SplayAccess(curstree, curnode); curstree = (SplayTree_p) newnode->stree; } leaf = (DKDLeaf_p) SplayAccess(curstree, node); return leaf; } tree->root->right = NULL; } free(lower->stree); lower->stree = sorttree; if (newnode->stree->rootratlib/src/dkdtree.h000644 007207 000054 00000005122 06170307204 015523 0ustar00jmccpcvision000000 000000 /* ** Copyright (C) 1995 Rick Romero and Carnegie Mellon University ** ** 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 1, 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., 675 Mass Ave, Cambridge, MA 02139, USA. */ #ifndef _DKDTREE_H_ #define _DKDTREE_H_ #include #include #include "splaylib.h" #define DKD_DIMENSIONS 4 #define LOWER_NODES_MIN 20 #ifdef DEBUG extern int rebalance_counts; extern int rebuild_counts; extern int inserts; extern int deletes; #endif typedef int32 dkd_vector[DKD_DIMENSIONS]; typedef struct _dkd_tree_ { SplayTree_p stree; int32 dimensions; int32 points, nodes; int32 inserts, deletes, maxmods; int32 uppernodes, lowernodes; } DKDTree_t, *DKDTree_p; typedef struct _dkd_node_ { SplayTree_p stree; int32 dimensions; /* dimension of sub-tree rooted here */ int32 points; /* total points rooted at sub-tree */ int32 nodes; /* Number of actual Splay nodes */ int32 inserts; /* number of nodes inserted */ int32 deletes; /* number of nodes deleted */ int32 maxnodes; /* max number of splay nodes allowed */ int32 maxpoints; /* total allowed points in sub-tree */ int32 left, right; /* spatial extents of this tree */ } DKDNode_t, *DKDNode_p; typedef struct _dkd_obj_list_ { void *object; struct _dkd_obj_list_ *next; } DKDObjList_t, *DKDObjList_p; typedef struct _dkd_leaf_ { dkd_vector location; DKDObjList_t obj_list; /* List of objects at this location */ } DKDLeaf_t, *DKDLeaf_p; typedef struct _dkd_leaf_list_ DKDLeafList_t, *DKDLeafList_p; DKDTree_p CreateDKDTree(int dimensions); void DKDInsert(DKDTree_p, dkd_vector, void *); DKDLeaf_p DKDCreateLeaf(); void DKDFreeLeaf(DKDLeaf_p); int DKDDelete(DKDTree_p, dkd_vector, DKDObjList_p); DKDLeaf_p DKDAccess(DKDTree_p, DKDLeaf_p); void DKDDestroyTree(DKDTree_p); #endif location[lower->dimensions]) + splitpoint->location[lower->dimensions] + 1) / 2; newnode->right = lower->right; lower->right = newnode->left; newnode->points = lower->points / 2 - count; lower->points = lower->points - newnode->points; sorttree = CreateSplay(dkd_compare_leaves_array[lower->dimensions - 1]); DKDRecurseCreateAndFree(newnode->stree->root, sorttree, 1); free(newnode->stree); if (ratlib/src/ratlib.c000644 007207 000054 00000023522 06145676266 015400 0ustar00jmccpcvision000000 000000 /* ** Copyright (C) 1995 Rick Romero and Carnegie Mellon University ** ** 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 1, 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., 675 Mass Ave, Cambridge, MA 02139, USA. */ #include #include #ifdef DEBUG #define dfprintf(x) fprintf x #else #define dfprintf(x) #endif #define CastAsRegion(x) ((RATRegion)(x)) #define CastAsDKDNode(x) ((DKDNode_p)(x)) DKDLeaf_t RATGlobalTmpRegion_t; /************* Region *************/ RATRegion RATCreateRegion(int32 x,int32 y,int32 w,int32 h,void *object) { RATRegion region; if ((region=(DKDLeaf_p)malloc(sizeof(DKDLeaf_t)))==NULL) { fprintf(stderr,"_RATCreateRegion: Out of memory\n"); return NULL; } RATComputeTransform(region,x,y,w,h); region->obj_list.object = object; region->obj_list.next = NULL; return region; } /*void *RATFreeRegion(RATRegion region) { RATObjList objs; if (region==NULL) obj=NULL; else objs=region->obj_list; free(region); return obj; }*/ /***************** Region List *****************/ RATRegionList RATListDestructiveRest(RATRegionList list) { RATRegionList lp; lp=RATListRest(list); free(list); return lp; } /********************* Tree Destruction *********************/ void RATDestroyTree(RATTree tree) { DKDDestroyTree(tree); } typedef struct IVec { int32 left; int32 right; } IVec[DKD_DIMENSIONS]; static int RAT_CheckSplay(SplayNode_p node,int32 dim,IVec intvec) { int i; RATRegion region; DKDNode_p dkdnode; if (node==NULL) return 0; if (RAT_CheckSplay(node->left,dim,intvec)) { dfprintf((stderr,"left-")); return 1; } if (RAT_CheckSplay(node->right,dim,intvec)) { dfprintf((stderr,"right-")); return 1; } if (node->obj==NULL) return 0; if (dim==1) { region=CastAsRegion(node->obj); for (i=1;i<dkd_dimensions;i++) {="" if="" (region-="">location[i] < intvec[i].left || region->location[i] > intvec[i].right) { dfprintf((stderr,"Failure on dim [%d] for: [%d %d %d %d]\n", i,region->location[0],region->location[1], region->location[2],region->location[3])); return 1; } } } else { dkdnode=CastAsDKDNode(node->obj); if (dkdnode->stree!=NULL && dkdnode->stree->root!=NULL) { intvec[dim-1].left=dkdnode->left; intvec[dim-1].right=dkdnode->right; if (RAT_CheckSplay(dkdnode->stree->root,dim-1,intvec)) { dfprintf((stderr,"NODE Dim=[%D] L,R=[%D,%D]\n", dim-1,dkdnode->left,dkdnode->right)); return 1; } } } return 0; } int RATCheckIntegrity(RATTree tree) { IVec intvec; if (tree==NULL || tree->stree==NULL || tree->stree->root==NULL) return 0; if (RAT_CheckSplay(tree->stree->root,tree->dimensions,intvec)) { dfprintf((stderr,"Top Of Tree\N")); return 1; } return 0; } /********************* Access Functions *********************/ #if RAT_NO_INLINE RATRegion RATNearestMatch(RATTree t,int32 x, int32 y, int32 w, int32 h) { RATComputeTempTransform(x,y,w,h); return DKDAccess(t, &RATGlobalTmpRegion_t); } void RATInsert(RATTree t, int32 x, int32 y, int32 w, int32 h, void *obj) { RATVector vec; vec[0] = x+w; vec[1] = y+h; vec[2] = w-x; vec[3] = h-y; DKDInsert(t, vec, obj); } int RATDelete(RATTree t, int32 x, int32 y, int32 w, int32 h, RATObjList objs) { RATVector vec; vec[0] = x+w; vec[1] = y+h; vec[2] = w-x; vec[3] = h-y; return DKDDelete(t, vec, objs); } #endif /************************* Tree Walkers *************************/ #define GO_LEFT (1) #define GO_BOTH (0) #define GO_RIGHT (-1) #define LIST_INCR(lt) (lt= &((*lt)->next)) #define LIST_END(lt) {for (;(*lt)!=NULL;LIST_INCR(lt));} static int32 RAT_Acceptable(RATRegion node,RATRegion refer,int dir) { int32 i,accept; if (dir==GO_BOTH) return 1; if (node==NULL) return 0; if (refer==NULL) return 1; for (i=0,accept=1;i<dkd_dimensions;i++) accept="" &="((node-">location[i]-refer->location[i])*dir) <= 0; return accept; } static RATRegionList RAT_ListWalkDKDNode(DKDNode_p dkdnode,RATRegion region,int32 dir); static RATRegionList RAT_ListWalkSplayNode(SplayNode_p node,RATRegion region,int32 dir,int32 dim) { RATRegionList list,*lt; if (node==NULL) { dfprintf((stderr, "up.\n")); return NULL; } list=NULL; lt = &list; dfprintf((stderr, "LWSplay Left.")); (*lt) = RAT_ListWalkSplayNode(node->left,region,dir,dim); LIST_END(lt); if (dim==1) { if (RAT_Acceptable(node->obj,region,dir)) { (*lt)=(RATRegionList)malloc(sizeof(RATRegionList_t)); (*lt)->region=node->obj; dfprintf((stderr, "Adding: [%d %d %d %d]\n", (*lt)->region->location[0], (*lt)->region->location[1], (*lt)->region->location[2], (*lt)->region->location[3])); (*lt)->next=NULL; LIST_END(lt); } } else { dfprintf((stderr, "Going down to node dim %d, left=%d, right=%d\n", CastAsDKDNode(node->obj)->dimensions, CastAsDKDNode(node->obj)->left, CastAsDKDNode(node->obj)->right)); (*lt)=RAT_ListWalkDKDNode(node->obj,region,dir); LIST_END(lt); } dfprintf((stderr, "LWSplay Right.")); (*lt)=RAT_ListWalkSplayNode(node->right,region,dir,dim); dfprintf((stderr, "UP.\N")); return list; } static RATRegionList RAT_ListWalkDKDNode(DKDNode_p dkdnode,RATRegion region,int32 dir) { RATRegionList list,*lt; DKDNode_t sorter; list=NULL; lt = &list; if (dkdnode==NULL || dkdnode->stree==NULL || dkdnode->stree->root==NULL) return NULL; if (dir != GO_BOTH) { if (dkdnode->dimensions == 1) { SplayAccess(dkdnode->stree,region); } else { sorter.left=sorter.right=region->location[dkdnode->dimensions-1]; SplayAccess(dkdnode->stree,&sorter); } } if (dir==GO_RIGHT || dir==GO_BOTH) { (*lt) = RAT_ListWalkSplayNode(dkdnode->stree->root->right,region,dir,dkdnode->dimensions); LIST_END(lt); } if (dkdnode->dimensions==1) { if (RAT_Acceptable(dkdnode->stree->root->obj,region,dir)) { (*lt) = (RATRegionList)malloc(sizeof(RATRegionList_t)); (*lt)->region = dkdnode->stree->root->obj; (*lt)->next = NULL; LIST_END(lt); } } else { (*lt) = RAT_ListWalkDKDNode(dkdnode->stree->root->obj,region,dir); LIST_END(lt); } if (dir==GO_LEFT || dir==GO_BOTH) { (*lt) = RAT_ListWalkSplayNode(dkdnode->stree->root->left,region,dir,dkdnode->dimensions); } return list; } RATRegionList RATContainedWithin(RATTree tree, int32 x, int32 y, int32 w, int32 h) { if (tree==NULL || tree->stree==NULL) return NULL; RATComputeTempTransform(x,y,w,h); return RAT_ListWalkDKDNode(CastAsDKDNode(tree), &RATGlobalTmpRegion_t, GO_LEFT); } RATRegionList RATIntersectsWith(RATTree tree, int32 x, int32 y, int32 w, int32 h) { if (tree==NULL || tree->stree==NULL) return NULL; RATComputeTempTransform(x,y,-w,-h); return RAT_ListWalkDKDNode(CastAsDKDNode(tree), &RATGlobalTmpRegion_t, GO_RIGHT); } /************************ Functional Tree Walkers *************************/ int RATQualifiedTrue(void *obj1,void *obj2) { return 1; } static void RAT_FuncWalkDKDNode(DKDNode_p dkdnode,RATRegion region, int32 dir,RATQualifiedOperation *op); static void RAT_FuncWalkSplayNode(SplayNode_p node,RATRegion region,int32 dir, RATQualifiedOperation *op,int32 dim) { RATObjList list; if (node==NULL) return; RAT_FuncWalkSplayNode(node->left,region,dir,op,dim); if (dim==1) { if (RAT_Acceptable(node->obj,region,dir)) { list = &(CastAsRegion(node->obj)->obj_list); while(list) { if (op->qualifier(op->qualification,list->object)) op->operation(op->operand,list->object); list = list->next; } } } else { RAT_FuncWalkDKDNode(node->obj,region,dir,op); } RAT_FuncWalkSplayNode(node->right,region,dir,op,dim); } static void RAT_FuncWalkDKDNode(DKDNode_p dkdnode,RATRegion region, int32 dir,RATQualifiedOperation *op) { DKDNode_t sorter; RATObjList list; if (dkdnode==NULL || dkdnode->stree==NULL || dkdnode->stree->root==NULL) return; if (dir != GO_BOTH) { if (dkdnode->dimensions == 1) SplayAccess(dkdnode->stree,region); else { sorter.left=sorter.right=region->location[dkdnode->dimensions-1]; SplayAccess(dkdnode->stree,&sorter); } } if (dir==GO_RIGHT || dir==GO_BOTH) RAT_FuncWalkSplayNode(dkdnode->stree->root->right,region,dir,op,dkdnode->dimensions); if (dkdnode->dimensions==1) { if (RAT_Acceptable(dkdnode->stree->root->obj,region,dir)) { list = &(CastAsRegion(dkdnode->stree->root->obj)->obj_list); while(list) { if (op->qualifier(op->qualification,list->object)) op->operation(op->operand,list->object); list = list->next; } } } else RAT_FuncWalkDKDNode(dkdnode->stree->root->obj,region,dir,op); if (dir==GO_LEFT || dir==GO_BOTH) RAT_FuncWalkSplayNode(dkdnode->stree->root->left,region,dir,op,dkdnode->dimensions); } void RATBoundedWalk(RATTree tree,RATRegion bounds,RATQualifiedOperation *op) { RAT_FuncWalkDKDNode(CastAsDKDNode(tree),bounds,GO_LEFT,op); } void RATTotalWalk(RATTree tree,RATQualifiedOperation *op) { RAT_FuncWalkDKDNode(CastAsDKDNode(tree),NULL,GO_BOTH,op); } ratlib/src/ratlib.h000644 007207 000054 00000010742 06170307224 015364 0ustar00jmccpcvision000000 000000 /* ** Copyright (C) 1995 Rick Romero and Carnegie Mellon University ** ** 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 1, 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., 675 Mass Ave, Cambridge, MA 02139, USA. */ #ifndef _RATLIB_H_ #define _RATLIB_H_ #include "icompat.h" #include "dkdtree.h" typedef dkd_vector RATVector; typedef DKDTree_t RATTree_t; typedef DKDTree_p RATTree; typedef DKDLeaf_p RATRegion; typedef DKDObjList_p RATObjList; typedef DKDObjList_t RATObjList_t; typedef struct RATRegionList { RATRegion region; struct RATRegionList *next; } RATRegionList_t,*RATRegionList; typedef struct RATQualifiedOperation { int (*qualifier)(void *qualification,void *obj); void *qualification; int (*operation)(void *operand,void *obj); void *operand; } RATQualifiedOperation; extern DKDLeaf_t RATGlobalTmpRegion_t; #ifndef myABS #define myABS(x) (((x)<0) ? (-(x)) : (x)) #endif #define RATComputeTransform(vec,x,y,w,h) {\ (vec)->location[0] = (w)+(x); \ (vec)->location[1] = (h)+(y); \ (vec)->location[2] = (w)-(x); \ (vec)->location[3] = (h)-(y); } #define RATComputeTempTransform(x,y,w,h) \ {\ RATGlobalTmpRegion_t.location[0] = (w)+(x); \ RATGlobalTmpRegion_t.location[1] = (h)+(y); \ RATGlobalTmpRegion_t.location[2] = (w)-(x); \ RATGlobalTmpRegion_t.location[3] = (h)-(y); \ } /* ** Region ** */ RATRegion RATCreateRegion(int32, int32, int32, int32, void *); #define RATCreateBoundingRegion(x,y,w,h,obj) \ RATCreateRegion((x),(y),(w),(h),(obj)) #define RATCreateIntersectionRegion(x,y,w,h,obj) \ RATCreateRegion((x),(y),-(w),-(h),(obj)) #define RATCreatePointRegion(x,y,obj) \ RATCreateRegion((x),(y),0,0,(obj)) /*void *RATFreeRegion(RATRegion region);*/ #define RATGetRegionObjList(region) (&((region)->obj_list)) #define RATListRegion(list) ((list)->region) /* ** Region List ** */ RATRegionList RATListDestructiveRest(RATRegionList list); #define RATListRest(list) (list->next) #define RATListFirst(list) (list->region) #define RATListObject(list) (list->object) /**** Tree Contrustction/Destruction ****/ #define RATCreateTree() CreateDKDTree(DKD_DIMENSIONS) void RATDestroyTree(RATTree tree); /* ** Access functions ** */ #define RAT_NO_INLINE 1 #if RAT_NO_INLINE RATRegion RATNearestMatch(RATTree, int32, int32, int32, int32); void RATInsert(RATTree, int32, int32, int32, int32, void *); int RATDelete(RATTree t, int32, int32, int32, int32, RATObjList); #else /* Inlined Access Functions ** ** Define the inlined versions of these commands ** they use global temp variables & don't do any sanity checking */ #define RATNearestMatch(t,x,y,w,h) {\ RATComputeTempTransform((x),(y),(w),(h));\ DKDAccess(t,&RATGlobalTmpRegion_t);\ } #define RATInsert(t,x,y,w,h,o) {\ dkd_vector vec; \ vec[0] = (x)+(w); \ vec[1] = (y)+(h); \ vec[2] = (w)-(x); \ vec[3] = (h)-(y); \ DKDInsert(t,vec,o); \ } #define RATDelete(t,x,y,w,h,olist) {\ dkd_vector vec; \ vec[0] = (x)+(w); \ vec[1] = (y)+(h); \ vec[2] = (w)-(x); \ vec[3] = (h)-(y); \ DKDDelete(t,vec,(olist)); \ } #endif RATRegionList RATContainedWithin(RATTree, int32, int32, int32, int32); RATRegionList RATIntersectsWith(RATTree, int32, int32, int32, int32); /***** Tree Walkers *******/ int RATQualifiedTrue(void *,void *); void RATBoundedWalk(RATTree tree,RATRegion bounds,RATQualifiedOperation *op); void RATTotalWalk(RATTree tree,RATQualifiedOperation *op); /* ** Useful stuff */ #define RATRegionInvert(reg,x,y,w,h) \ { \ (x) = (((reg)->location[0] - (reg)->location[2]) >> 1); \ (y) = (((reg)->location[1] - (reg)->location[3]) >> 1); \ (w) = (((reg)->location[0] + (reg)->location[2]) >> 1); \ (h) = (((reg)->location[1] + (reg)->location[3]) >> 1); \ } #endif : (x)) #endif #define RATComratlib/src/splaylib.h000644 007207 000054 00000004110 06035365523 015724 0ustar00jmccpcvision000000 000000 /* ** Copyright (C) 1995 Rick Romero ** ** 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 1, 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., 675 Mass Ave, Cambridge, MA 02139, USA. */ #ifndef _SPLAYTREE_H_ #define _SPLAYTREE_H_ typedef struct SplayNode { struct SplayNode *left, *right, *parent, *leftmin; void *obj; } SplayNode_t, *SplayNode_p; typedef struct SplayTree { int (*compare)(); SplayNode_p root; } SplayTree_t, *SplayTree_p; SplayTree_p CreateSplay(int (*compare)()); SplayNode_p SplayCreateNode(); void SplayFreeNode(SplayNode_p); void SplayDelete(SplayTree_p, void *); void SplayInsert(SplayTree_p, void *); void SplayJoin(SplayTree_p, SplayTree_p); void SplaySplit(SplayTree_p, SplayTree_p, void *); void *SplayAccess(SplayTree_p, void *); void SplayNode(SplayTree_p, SplayNode_p); void S_splayr(SplayTree_p, SplayNode_p); void S_splayl(SplayTree_p, SplayNode_p); void S_splayrl(SplayTree_p, SplayNode_p); void S_splayrr(SplayTree_p, SplayNode_p); void S_splayll(SplayTree_p, SplayNode_p); void S_splaylr(SplayTree_p, SplayNode_p); SplayTree_p SplayCopyTree(SplayTree_p, void (*CopyNode)()); void SplayTraverse(SplayTree_p, void (*function)()); SplayNode_p SplayMinOfSubTree(SplayNode_p); void SplayCopySubTree(SplayNode_p, SplayNode_p, void (*CopyNode)()); void SplayInOrderTraverse(SplayNode_p, void (*function)()); void SplayDeleteTree(SplayTree_p); void SplayDeleteSubTree(SplayNode_p); void SplayDestroyTree(SplayTree_p); void SplayDestroySubTree(SplayNode_p); #endif ATCreateRegion((x),(y),(w),(h),(obj)) #define RATCreateIntersectionRegion(x,y,w,h,obj) \ RATCreateRegion((x),(y),-(w),-(h),(obj)) #define RATCreatePointRegion(x,y,obj) \ RATCreateRegion((x),(y),0,0,(obj)) /*void *RATFreeRegion(RATRegion region);*/ #define RATGetRegionObjList(region) (&((region)->obj_list)) #define RATListRegion(list) ((list)->region) /* ** Region List ** */ RATRegionList RATratlib/src/splaymin.c000644 007207 000054 00000030741 06146674713 015754 0ustar00jmccpcvision000000 000000 /* ** Copyright (C) 1995 Rick Romero ** ** 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 1, 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., 675 Mass Ave, Cambridge, MA 02139, USA. */ #include typedef struct SplayNode { struct SplayNode *left, *right, *parent, *leftmin; void *obj; } SNode; typedef struct SplayTree { int (*compare)(); SNode *root; } STree; STree *CreateSplay(int (*compare)()); SNode *SplayCreateNode(); void SplayDelete(STree *, void *); void SplayInsert(STree *, void *); void SplayJoin(STree *, STree *); void SplaySplit(STree *, STree *, void *); void *SplayAccess(STree *, void *); void SplayNode(STree *, SNode *); void S_splayr(STree *, SNode *); void S_splayl(STree *, SNode *); void S_splayrl(STree *, SNode *); void S_splayrr(STree *, SNode *); void S_splayll(STree *, SNode *); void S_splaylr(STree *, SNode *); STree *SplayCopyTree(STree *, void (*CopyNode)()); void SplayTraverse(STree *, void (*function)()); SNode *SplayMinOfSubTree(SNode *); void SplayCopySubTree(SNode *, SNode *, void (*CopyNode)()); void SplayInOrderTraverse(SNode *sn, void (*function)()); void SplayDeleteTree(STree *); void SplayDeleteSubTree(SNode *); void SplayDestroyTree(STree *); void SplayDestroySubTree(SNode *); void SplayFreeNode(SNode *); #define SNODE_MALLOC_SIZE 100 static SNode *SplayNodeFreeList = NULL; void SplayFreeNode(SNode *sn) { if (sn) { sn->right = SplayNodeFreeList; #ifdef DEBUG sn->left = NULL; sn->parent = NULL; sn->obj = NULL; sn->leftmin = NULL; #endif SplayNodeFreeList = sn; } } STree *CreateSplay(int (*compare)()) { STree *stree; stree = (STree *) malloc(sizeof(STree)); stree->compare = compare; stree->root = NULL; return stree; } SNode *SplayCreateNode() { SNode *tmp; if (SplayNodeFreeList) { tmp = SplayNodeFreeList; SplayNodeFreeList = tmp->right; } else { int i; tmp = (SNode *) malloc(sizeof(SNode) * SNODE_MALLOC_SIZE); tmp += (SNODE_MALLOC_SIZE-1); tmp->right = SplayNodeFreeList; tmp--; for (i=SNODE_MALLOC_SIZE-2; i; i--, tmp--) tmp->right = (tmp+1); SplayNodeFreeList = tmp+1; } tmp->leftmin = tmp; tmp->obj = tmp->left = tmp->right = tmp->parent = NULL; return tmp; } void *SplayAccess(STree *stree, void *obj) { SNode *snode; int res, done = 0; int (*compare)(); compare = stree->compare; snode = stree->root; if(snode == NULL) return NULL; if((compare)(obj, snode->obj) == 0) return snode->obj; /* if(snode->left == NULL && snode->right == NULL) return NULL;*/ if (snode->left == NULL && snode->right == NULL) return snode->obj; while(!done) { res = (compare)(obj, snode->obj); if (res == 0) done = 2; else if(res > 0) if(snode->right != NULL) { snode = snode->right; } else done = 1; else if(snode->left != NULL) { snode = snode->left; } else done = 1; } SplayNode(stree, snode); if (done == 2) return snode->obj; else /* return NULL; */ return snode->obj; } void SplayNode(STree *stree, SNode *snode) { SNode *par, *gpar, *ll, *lr, *l, *r, *rr, *rl; while((par = snode->parent) != NULL) { if(par->parent != NULL) { gpar = par->parent; ll = lr = rr = rl = NULL; l = gpar->left; r = gpar->right; if(l != NULL) { ll = l->left; lr = l->right; } if(r != NULL) { rl = r->left; rr = r->right; } if(snode == ll) S_splayll(stree, snode); else if(snode == lr) S_splaylr(stree, snode); else if(snode == rr) S_splayrr(stree, snode); else if(snode == rl) S_splayrl(stree, snode); } else { l = par->left; r = par->right; if(snode == l) S_splayl(stree, snode); else if(snode == r) S_splayr(stree, snode); else fprintf(stderr, "really fucked. go home and die.\n"); } } } void S_splayl(STree *stree, SNode *snode) { stree->root->left = snode->right; stree->root->parent = snode; if(snode->right != NULL) { stree->root->leftmin = snode->right->leftmin; snode->right->parent = stree->root; } else { stree->root->leftmin = stree->root; } snode->right = stree->root; stree->root = snode; snode->parent = NULL; } void S_splayr(STree *stree, SNode *snode) { stree->root->right = snode->left; stree->root->parent = snode; if(snode->left != NULL) snode->left->parent = stree->root; snode->left = stree->root; stree->root = snode; snode->parent = NULL; snode->leftmin = snode->left->leftmin; } void S_splayll(STree *stree, SNode *snode) { SNode *ggpar, *gpar, *par; par = snode->parent; gpar = par->parent; /* Do the min left operations */ if(par->right != NULL) gpar->leftmin = par->right->leftmin; else gpar->leftmin = gpar; if(snode->right != NULL) par->leftmin = snode->right->leftmin; else par->leftmin = par; /* Do the splay rotations */ ggpar = gpar->parent; gpar->left = par->right; if(gpar->left != NULL) gpar->left->parent = gpar; gpar->parent = par; par->right = gpar; par->left = snode->right; if(par->left != NULL) par->left->parent = par; par->parent = snode; snode->right = par; snode->parent = ggpar; if(ggpar != NULL) { if(ggpar->right == gpar) ggpar->right = snode; else ggpar->left = snode; } else { stree->root = snode; } } void S_splayrr(STree *stree, SNode *snode) { SNode *ggpar, *gpar, *par; par = snode->parent; gpar = par->parent; ggpar = gpar->parent; /* This min tracking is easy--gpar has min of all x, y, z */ par->leftmin = snode->leftmin = gpar->leftmin; /* Do rotations */ gpar->right = par->left; if(gpar->right != NULL) gpar->right->parent = gpar; gpar->parent = par; par->left = gpar; par->right = snode->left; if(par->right != NULL) par->right->parent = par; par->parent = snode; snode->left = par; snode->parent = ggpar; if(ggpar != NULL) { if(ggpar->right == gpar) ggpar->right = snode; else ggpar->left = snode; } else { stree->root = snode; } } void S_splaylr(STree *stree, SNode *snode) { SNode *ggpar, *gpar, *par; par = snode->parent; gpar = par->parent; /* Do the min calcs */ if(snode->right != NULL) gpar->leftmin = snode->right->leftmin; else gpar->leftmin = gpar; snode->leftmin = par->leftmin; /* Do the rotations */ ggpar = gpar->parent; par->right = snode->left; if(par->right != NULL) par->right->parent = par; par->parent = snode; gpar->left = snode->right; if(gpar->left != NULL) gpar->left->parent = gpar; gpar->parent = snode; snode->left = par; snode->right = gpar; snode->parent = ggpar; if(ggpar != NULL) { if(ggpar->right == gpar) ggpar->right = snode; else ggpar->left = snode; } else { stree->root = snode; } } void S_splayrl(STree *stree, SNode *snode) { SNode *ggpar, *gpar, *par; par = snode->parent; gpar = par->parent; /* Do the min swaps */ snode->leftmin = gpar->leftmin; if(snode->right != NULL) par->leftmin = snode->right->leftmin; else par->leftmin = par; /* do the rotations */ ggpar = gpar->parent; gpar->right = snode->left; if(gpar->right != NULL) gpar->right->parent = gpar; gpar->parent = snode; par->left = snode->right; if(par->left != NULL) par->left->parent = par; par->parent = snode; snode->left = gpar; snode->right = par; snode->parent = ggpar; if(ggpar != NULL) if(ggpar->right == gpar) ggpar->right = snode; else ggpar->left = snode; else stree->root = snode; } void SplaySplit(STree *stree, STree *stree2, void *obj) { SplayAccess(stree, obj); if ((stree->compare)(stree->root->obj, obj) > 0) { stree2->root = stree->root; stree->root = stree->root->left; if (stree->root) { stree->root->parent = NULL; } } else { stree2->root = stree->root->right; if(stree2->root != NULL) { stree2->root->parent = NULL; } stree->root->right = NULL; } } void SplayJoin(STree *stree1, STree *stree2) { SplayNode(stree2, stree2->root->leftmin); stree2->root->left = stree1->root; stree1->root->parent = stree2->root; stree1->root = stree2->root; stree1->root->leftmin = stree1->root->left->leftmin; free(stree2); } void SplayInsert(STree *stree, void *obj) { int (*compare)(); SNode *snode; snode = SplayCreateNode(); snode->obj = obj; compare = stree->compare; if(stree->root == NULL) { stree->root = snode; return; } SplayAccess(stree, obj); if((compare)(stree->root->obj, obj) < 0) { snode->left = stree->root; if(snode->left != NULL) { snode->leftmin = snode->left->leftmin; snode->left->parent = snode; } else { snode->leftmin = snode; } snode->right = stree->root->right; if(snode->right != NULL) snode->right->parent = snode; stree->root->right = NULL; stree->root = snode; snode->parent = NULL; } else { snode->right = stree->root; if(snode->right != NULL) { snode->right->parent = snode; snode->right->leftmin = snode->right; } snode->left = stree->root->left; if(snode->left != NULL) { snode->leftmin = snode->left->leftmin; snode->left->parent = snode; } else { snode->leftmin = snode; } stree->root->left = NULL; stree->root = snode; snode->parent = NULL; } } void SplayDelete(STree *stree, void *obj) { STree stree2; SNode *tmp; if (stree) { if (stree->root == NULL) return; } else { return; } if ((stree->compare)(SplayAccess(stree, obj),obj)) return; if (stree->root->right) { stree2.root = stree->root->right; stree2.root->parent = NULL; stree2.compare = stree->compare; SplayNode(&stree2, stree2.root->leftmin); stree2.root->left = stree->root->left; if (stree->root->left) { stree->root->left->parent = stree2.root; stree2.root->leftmin = stree->root->leftmin; } else { stree2.root->leftmin = stree2.root; } tmp = stree->root; stree->root = stree2.root; } else { tmp = stree->root; stree->root = stree->root->left; if (stree->root) stree->root->parent = NULL; } SplayFreeNode(tmp); } void CopySubTree(SNode *snode, SNode *snode2, void (*CopyNode)()) { SNode *new; CopyNode(snode, snode2); if(snode->left != NULL) { snode2->left = new = SplayCreateNode(); new->parent = snode2; CopySubTree(snode->left, new, CopyNode); snode2->leftmin = snode2->left->leftmin; } else { snode2->leftmin = snode; } if(snode->right != NULL) { snode2->right = new = SplayCreateNode(); new->parent = snode2; CopySubTree(snode->right, new, CopyNode); } } STree *SplayCopyTree(STree *st, void (*CopyNode)()) { STree *st2; st2 = CreateSplay(st->compare); if(st->root != NULL) { st2->root = SplayCreateNode(); CopySubTree(st->root, st2->root, CopyNode); } return st2; } void SplayTraverse(STree *st, void (*function)()) { if(st->root != NULL) SplayInOrderTraverse(st->root, function); } void SplayInOrderTraverse(SNode *sn, void (*function)()) { if(sn->left != NULL) SplayInOrderTraverse(sn->left, function); (function)(sn->obj); if(sn->right != NULL) SplayInOrderTraverse(sn->right, function); } SNode *MinOfSubTree(SNode *sn) { return sn->leftmin; } SNode *MinOfTree(STree *st) { return st->root->leftmin; } void SplayDeleteTree(STree *st) { SNode *sn; if((sn = st->root) != NULL) SplayDeleteSubTree(sn); free(st); } void SplayDeleteSubTree(SNode *sn) { if(sn->right != NULL) SplayDeleteSubTree(sn->right); if(sn->left != NULL) SplayDeleteSubTree(sn->left); SplayFreeNode(sn); } void SplayDestroyTree(STree *st) { SNode *sn; if((sn = st->root) != NULL) SplayDestroySubTree(sn); free(st); } void SplayDestroySubTree(SNode *sn) { if(sn->right != NULL) SplayDestroySubTree(sn->right); if(sn->left != NULL) SplayDestroySubTree(sn->left); free(sn->obj); SplayFreeNode(sn); } ratlib/src/make.conf000644 007207 000054 00000000144 06170310115 015506 0ustar00jmccpcvision000000 000000 #### #### Modify these to suit your environment! #### CC=gcc COPTS= -O CINCLUDES=-I. #### #### ar, *par; par = snode->parent; gpar = par->parent; /* Do the min left operations */ if(par->right != NULL) gpar->leftmin = par->right->leftmin; else gpar->leftmin = gpar; if(snode->right != NULL) par->leftmin = snode->right->leftmin; else par->leftmin = par; /* Do the splay rotations */ ggpar = gpar->parent; gpar->left = par->right; if(gpar->left != NULL) gpar->lefratlib/src/testtrees.c000644 007207 000054 00000004423 06145677777 016154 0ustar00jmccpcvision000000 000000 #include #include #include "ratlib.h" extern void DKDRebuildTree(DKDTree_p); char *pName = NULL; RATVector *vectors; #define myrand() ((lrand48() & 0xFFF) - 0x7FF) void usage() { fprintf(stderr, "Usage: %s vectors rebuilds [deletes]\n" "\tvectors\t\tNumber of vectors to insert into the tree\n" "\trebuilds\tNumber of times to rebuild the tree\n" "\tdeletes\t\tNumber of vectors to delete\n", pName); exit(1); } void GeneratePermute(int decksize, int handsize, int **hand) { int i, j, tmp; int *deck; *hand = (int *) malloc(sizeof(int) * handsize); deck = (int *) malloc(sizeof(int) * decksize); for (i = 0; i < decksize; i++) deck[i] = i; j = 0; while(handsize) { i = lrand48() % (decksize - j); tmp = deck[j]; deck[j] = deck[i+j]; deck[i+j] = tmp; handsize--; (*hand)[handsize] = deck[j]; j++; } free(deck); } void RandomDeletes(RATTree tree, int vecs, int deletes) { RATVector v1, v2; int *permute; GeneratePermute(vecs, deletes, &permute); while (deletes) { deletes--; if (RATDelete(tree, vectors[permute[deletes]][0], vectors[permute[deletes]][1], vectors[permute[deletes]][2], vectors[permute[deletes]][3], NULL)) { printf("Problem w/ Deleting a vector\n"); } } free(permute); } void RandomInserts(RATTree tree, int vecs) { srand48(time(NULL)); vectors = (RATVector *) malloc(sizeof(RATVector) * vecs); while(vecs) { vecs--; vectors[vecs][0] = myrand(); vectors[vecs][1] = myrand(); vectors[vecs][2] = myrand(); vectors[vecs][3] = myrand(); RATInsert(tree, vectors[vecs][0], vectors[vecs][1], vectors[vecs][2], vectors[vecs][3], NULL); } } int main(int argc, char *argv[]) { int rebuilds, vectors, deletes; RATTree tree; pName = argv[0]; if (argc < 3) { usage(); } if ((sscanf(argv[1], "%d", &vectors) != 1) || (sscanf(argv[2], "%d", &rebuilds) != 1)) { usage(); } if (argc == 4) { if (sscanf(argv[3], "%d", &deletes) != 1) { usage(); } } else { deletes = 0; } tree = RATCreateTree(); RandomInserts(tree, vectors); if (deletes) RandomDeletes(tree, vectors, deletes); while(rebuilds--) DKDRebuildTree(tree); RATDestroyTree(tree); exit(0); } t = snode->left; if(par->right != NULL) par->right->parent = par; par->parent = snode; snode->left = par; snode->parent = ggpar; if(ggpar != NULL) { if(ggpar->right == gpar) ggpar->right = snode; else ggratlib/src/.depend000644 007207 000054 00000003374 06170310256 015200 0ustar00jmccpcvision000000 000000 dkdtree.o: dkdtree.c \ /usr/local/lib/gcc-lib/sparc-sun-sunos4.1.3_U1/2.7.2/include/stdio.h \ /usr/local/lib/gcc-lib/sparc-sun-sunos4.1.3_U1/2.7.2/include/stdarg.h \ /usr/local/lib/gcc-lib/sparc-sun-sunos4.1.3_U1/2.7.2/include/va-sparc.h \ /usr/local/lib/gcc-lib/sparc-sun-sunos4.1.3_U1/2.7.2/include/stdlib.h \ /usr/local/lib/gcc-lib/sparc-sun-sunos4.1.3_U1/2.7.2/include/sys/stdtypes.h \ /usr/local/lib/gcc-lib/sparc-sun-sunos4.1.3_U1/2.7.2/include/math.h \ /usr/local/lib/gcc-lib/sparc-sun-sunos4.1.3_U1/2.7.2/include/floatingpoint.h \ /usr/local/lib/gcc-lib/sparc-sun-sunos4.1.3_U1/2.7.2/include/sys/ieeefp.h \ /usr/local/lib/gcc-lib/sparc-sun-sunos4.1.3_U1/2.7.2/include/values.h \ dkdtree.h icompat.h \ /usr/local/lib/gcc-lib/sparc-sun-sunos4.1.3_U1/2.7.2/include/malloc.h \ splaylib.h splaymin.o: splaymin.c \ /usr/local/lib/gcc-lib/sparc-sun-sunos4.1.3_U1/2.7.2/include/stdio.h \ /usr/local/lib/gcc-lib/sparc-sun-sunos4.1.3_U1/2.7.2/include/stdarg.h \ /usr/local/lib/gcc-lib/sparc-sun-sunos4.1.3_U1/2.7.2/include/va-sparc.h ratlib.o: ratlib.c \ /usr/local/lib/gcc-lib/sparc-sun-sunos4.1.3_U1/2.7.2/include/stdio.h \ /usr/local/lib/gcc-lib/sparc-sun-sunos4.1.3_U1/2.7.2/include/stdarg.h \ /usr/local/lib/gcc-lib/sparc-sun-sunos4.1.3_U1/2.7.2/include/va-sparc.h \ ratlib.h icompat.h \ /usr/local/lib/gcc-lib/sparc-sun-sunos4.1.3_U1/2.7.2/include/malloc.h \ /usr/local/lib/gcc-lib/sparc-sun-sunos4.1.3_U1/2.7.2/include/stdlib.h \ /usr/local/lib/gcc-lib/sparc-sun-sunos4.1.3_U1/2.7.2/include/sys/stdtypes.h \ dkdtree.h \ /usr/local/lib/gcc-lib/sparc-sun-sunos4.1.3_U1/2.7.2/include/math.h \ /usr/local/lib/gcc-lib/sparc-sun-sunos4.1.3_U1/2.7.2/include/floatingpoint.h \ /usr/local/lib/gcc-lib/sparc-sun-sunos4.1.3_U1/2.7.2/include/sys/ieeefp.h \ splaylib.h n = snode->right->leftmin; else gpar->leftmin = gpar; snode->leftmin = par->leftmin; /* Do the rotations */ ggpar = gpar->parent; par->right = snode->left; if(par->right != NULL) par->right->parent = par; par->parent = snode; gpar->lefratlib/src/icompat.h000644 007207 000054 00000011403 06170310151 015527 0ustar00jmccpcvision000000 000000 /* * icompat.h * Purpose: Handle integer type size compatibility. */ /* * Copyright (C) 1994 Visual Understanding Systems * All rights reserved world wide. */ /* * Revision history: * 94/05/11 Richard Nash nash@visus.com * Created */ #ifndef _ICOMPAT_H #define _ICOMPAT_H /* * This header file centralizes the integer size compatibility issues. A * program should almost never use char, short, int, long, or long long because * it can't be sure how many bits long each of these types are. There are some * cases when such use is unavoidable, system calls being one. Instead declare * the storage you need by using the below defined types. * * Edit this file by adding an #if block for your system type (which needs * to be defined somewhere, preferable with -DSYSTEM_FOOBAR on the compiler's * command line) so that the typedefs and constants meet this definition: * * Each of these types is assumed to be packed and addressable in * memory on any 8 bit boundary. * * Type Range * int8 [-128 to 127] * int16 [-32768 to 32767] * int32 [-2147483648 to 2147483647] * int64 [-9223372036854775808 to 9223372036854775807] * uint8 [0 to 255] * uint16 [0 to 65535] * uint32 [0 to 4294967295] * uint64 [0 to 18446744073709551615] * * Also define the CHARSIZE, SHORTSIZE, INTSIZE, LONGSIZE, and LONGLONGSIZE * macros to be the number of bits in a 'char', 'short', 'int', 'long', and * 'long long' respectively. This is needed since many system calls expect * these types and conversions may need to be done. * * If you are unable to do any of this on your system, all is not lost. For * example, if you can't get the 64 bit types to work, then just remove the * references to them. If the program that uses this header doesn't make * use of those types, then you are okay. Of course, if it does, it is probably * for a good reason. Then you should be aware that there may be problems in * the integer operations in this program is suspect to problems. You have * been warned. */ /*#ifdef SYSTEM_DECALPHA*/ #ifdef __alpha #include #include #ifndef _NO_COMPAT_TYPES_ typedef char int8; typedef short int16; typedef int int32; typedef long int64; typedef unsigned char uint8; typedef unsigned short uint16; typedef unsigned int uint32; typedef unsigned long uint64; #endif #define MININT8 (int8)-128 #define MAXINT8 (int8)127 #define MININT16 (int16)-32768 #define MAXINT16 (int16)32767 #define MININT32 (int32)-2147483648L #define MAXINT32 (int32)2147483647L #define MININT64 (int64)-9223372036854775808LL #define MAXINT64 (int64)9223372036854775807LL #define MAXUINT8 (uint8)255 #define MAXUINT16 (uint16)65535 #define MAXUINT32 (uint32)4294967295L #define MAXUINT64 (uint64)18446744073709551615LL #define CHARSIZE 8 #define SHORTSIZE 16 #define INTSIZE 32 #define LONGSIZE 64 #define LONGLONGSIZE 64 #else /* __alpha */ /* __MWERKS__ ==> MetroWerks for Mac compiler */ #ifdef __MWERKS__ #ifndef _NO_COMPAT_TYPES_ typedef char int8; typedef short int16; typedef long int32; typedef unsigned char uint8; typedef unsigned short uint16; typedef unsigned long uint32; #endif #define MININT8 (int8)-128 #define MAXINT8 (int8)127 #define MININT16 (int16)-32768 #define MAXINT16 (int16)32767 #define MININT32 (int32)-2147483648L #define MAXINT32 (int32)2147483647L #define MAXUINT8 (uint8)255 #define MAXUINT16 (uint16)65535 #define MAXUINT32 (uint32)4294967295L #define CHARSIZE 8 #define SHORTSIZE 16 #define INTSIZE 32 #define LONGSIZE 32 #else /* __MWERKS__ */ /* The default definitions. These work for the GNU compiler under * Nextstep 3.2 and probably on most machines with 32-bit data registers */ #include #include #ifndef _NO_COMPAT_TYPES_ typedef char int8; typedef short int16; typedef long int32; typedef long long int64; typedef unsigned char uint8; typedef unsigned short uint16; typedef unsigned long uint32; typedef unsigned long long uint64; #endif #define MININT8 (int8)-128 #define MAXINT8 (int8)127 #define MININT16 (int16)-32768 #define MAXINT16 (int16)32767 #define MININT32 (int32)-2147483648L #define MAXINT32 (int32)2147483647L #define MININT64 (int64)-9223372036854775808LL #define MAXINT64 (int64)9223372036854775807LL #define MAXUINT8 (uint8)255 #define MAXUINT16 (uint16)65535 #define MAXUINT32 (uint32)4294967295L #define MAXUINT64 (uint64)18446744073709551615LL #define CHARSIZE 8 #define SHORTSIZE 16 #define INTSIZE 32 #define LONGSIZE 32 #define LONGLONGSIZE 64 #endif /* __MWERKS__ */ #endif /* __alpha */ /* Define the Boolean type */ typedef unsigned char bool; #ifndef TRUE #define TRUE ((bool)1) #endif #ifndef FALSE #define FALSE ((bool)0) #endif #ifndef YES #define YES TRUE #endif #ifndef NO #define NO FALSE #endif #define BoolCast(i) (((i) == 0) ? FALSE : TRUE) #endif /*_ICOMPAT_H*/ } stree->root->left = NULL; stree->root = snode; snode->parent = NULL; } } void SplayDelete(STree *stree, void *obj) { STree stree2; SNode *tmp; if (stree) { if (stree->root == NULL) return; } else { return; }ratlib/src/README000644 007207 000054 00000036232 06170311062 014613 0ustar00jmccpcvision000000 000000 This set of software implements the rectangular object manipulation algorithm described in the paper "Object Manipulation for Document Conversion" (Romero and Thibadeau, Proceedings of ICIP-95, or see http://www.cs.cmu.edu/afs/cs.cmu.edu/project/pcvision/RATlib/www/ratlib.html) This software is being distributed under the GNU General Public License. Overview ======== The routines given here implement a general method of accessing objects based on 2-dimensional rectangles. Rectangles can be represented in two equivalent ways. For algorithmic purposes, it is useful to visualize the rectangle using the center point (x, y) and the half-width and half-height (w_2, h_2). This is what is used in the paper referenced above. However, because of integer round-off, it is easier from a programmers perspective to use instead the top-left and bottom-right corners of the rectangle, (x_1, y_1) and (x_2, y_2), where x_2 >= x_1 and y_2 >= y_1. Then, you can see that 2 * (x, y) = (x_1 + x_2, y_1 + y_2) 2 * (w_2, h_2) = (x_2 - x_1, y_2 - y_1) I suggest using the corners of the rectangle myself. Then, a rectangle is the 4-tuple (x_1 + x_2, y_1 + y_2, x_2 - x_1, y_2 - y_1). It's not too hard to go back and forth between the different representations, and this one won't have any aliasing or round-off problems. Given all that, this code will give you an interface to dynamically insert and delete rectangular objects into a tree structure. In addition, it will allow you to perform queries asking for rectangular regions that intersect or are contained within the query region. Objects are all represented as (void *)'s, so for portability sake, try not to shove anything other than a pointer into that (void *). (you're probably safe as long as the object is under 32 bits, but wierd things may happen if you try to later port to a 64 bit machine.) The protocol goes something like this: #include "ratlib.h" func() { RATTree rTree; RATRegion region; RATRegionList regionList; int32 x1, y1, x2, y2; void *object; rTree = RATCreateTree(); done = NewObject(&object, &x1, &y1, &x2, &y2); while (!done) { RATInsert(rTree, x1 + x2, y1 + y2, x2 - x1, y2 - y1, object); done = NewObject(&object, &x1, &y1, &x2, &y2); } done = NewQuery(&x1, &y1, &x2, &y2); while (!done) { regionList = RATContainedWithin(rTree, x1 + x2, y1 + y2, x2 - x1, y2 - y1); while(regionList) { DoSomething(RATListFirst(regionList)); regionList = RATListDestructiveRest(regionList); } done = NewQuery(&x1, &y1, &x2, &y2); } RATDestroyTree(rTree); } The Structures ============== RATTree A pointer to a tree object, internals aren't needed, but here are a couple of useful ones: tree->points The number of distinct rectangles currently in the tree tree->inserts Number of inserts since the last tree rebuild tree->deletes Number of deletes since the last tree rebuild typedef int32 RATVector[4]; An array of 4 32bit integers, used to represent the internal structure for the rectangles. Note that this vector is **not** the same vector as the 4-tuple that is passed in to these routines. typedef struct _rat_obj_list_ { void *object; struct _rat_obj_list_ *next; } RATObjList_t, *RATObjList; This structure is used to store lists of objects. I decided that the easiest way of dealing with duplicate rectangles in the same tree was to not deal with them at all. If you have objects that occupy the exact same rectangle, they are just bucketed together and stored in a linked-list of objects. This structure is the linked list used. typedef struct { RATVector location; RATObjList_t obj_list; } *RATRegion; This is the basic building block structure for regions. It contains one vector for the location (again, the actual numbers are not what was originally passed in,) and the first element of the linked list of objects. Note that the space for the first object is included in the RATRegion. (ie, it is not a pointer to a RATObjList_t, it is the actual first element.) This is done since no rectangle should ever really be in the tree without an object. RATRegion's are generally the structure which is used to return the results of point queries. typedef struct _rat_region_list_ { RATRegion region; struct _rat_region_list_ *next; } RATRegionList_t, *RATRegionList; This is simply a linked list of RATRegion's. These are returned from intersection and containment queries. typedef struct RATQualifiedOperation { int (*qualifier)(void *qualification, void *obj); void *qualification; int (*operation)(void *operand, void *obj); void *operand; } RATQualifiedOperation; This looks like one of the stranger ones here. It is a structure that is used by "Tree Walkers." For instance, suppose you needed to do a linear search on the entire tree that had nothing to do with their associated rectangles. You would build a RATQualifiedOperation structure to do this as follows: Create a function F1 that takes two (void *) arguments. F1's purpose is to tell the tree walker whether or not this object "qualifies" for the operation to be performed. Argument 1, the qualification, is an arbitrary (void *) that the programmer places into the structure. Use this for whatever you need, and if you don't need it, you can just put in a NULL. Argument 2, the object, is the (void *) that was originally passed in to RATInsert(t,x,y,w,h,object). If F1 returns non-zero, the function F2 is called. F2 also has two (void *) arguments, the first of which is the operand, which is arbitrarily set by the programmer. The second is again the (void *) object itself. If you don't think you need this structure to begin with, you are probably right. When rectangles somehow are no longer enough, you should probably take a look at this structure and the related functions. The Macros ========== RATComputeTransform(RATVector vec, int32 x, int32 y, int32 w, int32 h) This macro stores a transformed vector into vec, based on the given arguments. RATComputeTempTransform(int32 x, int32 y, int32 w, int32 h) This macro stores a transformed vector into a global temporary vector, based on the given arguments. The global temporary variable is RATGlobalTmpRegion_t. RATObjectList RATGetRegionObjList(RATRegion region) This returns the object list for a given region. RATRegionList RATListFirst(RATRegionList regionList) RATRegionList RATListRest(RATRegionList regionList) RATRegionList RATListObject(RATRegionList regionList) These are used to access the various parts of the RATRegionList structure. RATRegionInvert(RATRegion region, int32 x, int32 y, int32 w, int32 h) This macro will compute an inverse transformation on a region that was returned as part of a query. It fills in the values x, y, w, and h based on the values found in the RATRegion structure. The following functions can be specified as inline macros or as function calls at compile time. If you want to change them, change the line in ratlib.h that reads #define RAT_NO_INLINE 1 When it's defined to 1, then actual function calls are used. When defined as 0, inline code is generated via macros. The macros make use of the temporary global region RATGlobalTmpRegion_t. RATRegion RATNearestMatch(); void RATInsert(); int RATDelete(); The Routines ============ RATTree RATCreateTree(void) void RATDestroyTree(RATTree tree) These two functions are used to create and delete the trees. Note that RATDestroyTree does nothing to free the space pointed to by the (void *) object's which were passed in as arguments during tree insertions. void RATInsert(RATTree tree, int32 x, int32 y, int32 w, int32 h, void *object) Given the rectangle described by the 4-tuple (x, y, w, h), insert the (void *) object into the tree structure. As mentioned above, there are two useful rectangle representations. The "native" algorithm implementation is one where (x, y) is the center of the rectangle, and (w, h) are the width and height from the center of the rectangle out to an edge. (Or, the half-width and half-height.) Most applications probably don't represent rectangles in that fashion. The most common is probably either a two-corner representation, (x1, y1, x2, y2), where x1 <= x2 and y1 <= y2, or a top-left corner and full width/height (x, y, w, h). To use the first representation, call insert using RATInsert(tree, x1 + x2, y1 + y2, x2 - x1, y2 - y1, object); To use the second form, call insert using RATInsert(tree, x1 << 1, y1 << 1, w, h, object); int RATDelete(RATTree tree, int32 x, int32 y, int32 w, int32 h, RATObjList objs) This does just the opposite of insertion, deleting the entire region if necessary, and possibly rebalancing the tree. There's two ways to call this function. First, if (objs == NULL), then RATDelete will delete all of the objects that happen to be in that region. If the region you passed in does not match one of the stored regions exactly, then nothing is deleted. In the second form, if you have more than one object in a particular region, and would only like to delete some of them, you can instruct the deletion to only be applied to the objects in the passed in RATObjList objs. The test for equality to see whether two objects are the same is an equality check on the (void *), not the contents of whatever is being pointed to. I know this is a bit of a pain, but in practice, it's not that big of a deal. If the list of objects to delete you passed in consisted of the entire set of objects at that region, the actual region is deleted from the tree. Otherwise, it is left in to keep around the other objects. RATRegion RATNearestMatch(RATTree tree, int32 x, int32 y, int32 w, int32 h); This is a *dangerous* function to use unless you are using it to find exact matches. The "nearest" part of the name is very misleading. It does not really find the "nearest", as nearest in this context has multiple definitions. Suffice it to say, if an exact match exists, it will return that region. If an exact match doesn't exist, it will return one near where it would have been in the tree structure, but that in no way implies that they will be similar regions. RATRegionList RATContainedWithin(RATTree tree, int32 x, int32 y, int32 w, int32 h); Return a list of regions/rectangles which are completely contained within the query region/rectangle. RATRegionList RATIntersectsWith(RATTree tree, int32 x, int32 y, int32 w, int32 h); Return a list of regions/rectangles which intersect in any way the query region/rectangle. Note that this query returns a super-set of the regions returned for the equivalent containment query. RATRegionList RATListDestructiveRest(RATRegionList list); This is used to cycle through the various components returned by the intersection and containment query operators. The code generally looks something like this: regionList = RATIntersectsWith(tree, x, y, w, h); while(regionList) { OperateOnRegion(RATListFirst(regionList)); regionList = RATListDestructiveRest(regionList); } This code will pass to OperateOnRegion each of the regions returned by the query, (ie "void OperateOnRegion(RATRegion region);" should be the prototype for this.) In turn, RATListDestructiveRest frees up the space that was allocated for the list elements, one at a time. Efficiency and Errata ===================== The reason that these functions are also provided as inlines is simply to allow a re-munging of whatever form your rectangle may be. For each routine that takes in an (x, y, w, h), it computes a transform on that before shoving it into the data structure. By using the inline versions, you can allow the compiler to re-order both your transform and the data structure's transform. In other words, if you use the two-corners method of storing rectangles, then you will be passing all of these routines something like (x1 + x2, y1 + y2, x2 - x1, y2 - y1) The internal transform done is: (w + x, h + y, w - x, h - y) Which can be simplified into simply: (2 * x2, 2 * y2, -2 * x1, -2 * y1) It's a minor point, but something to be aware of. Also, I use Splay trees as my dynamic sorted tree structure. I'm not sure if they are in vogue now or not, but Danny Sleator is a smart guy and I doubt anybody has come up with anything significantly better in practice. (I've found it to be one of those severely flexible data structures that is almost impossible to go wrong with if you are in need of a dynamically modifiable sorted tree.) Anyways, that code should be pretty solid--I've banged on it for a couple of years now--and should probably be documented as well. It's not that it's complex, but it is useful. Finally, in a lot of my code, I don't actually free the data structures that I allocate. Instead, I stick them onto a local free list, and re-use them in later creations. I do this in both the splay tree code and in the divided kd-tree code. Also, when allocating these objects, I do it in hunks of like 100 at a time, throwing the unused 99 onto the free list. Hopefully, this is a good thing for you, as you don't have to worry so much about the efficiency of your particular malloc, how much memory is fragmenting, etc. However, I guess I could see the rare individual who needs to be able to give back to the OS that memory. If you are that individual, and you happen to modify my code to be both portable, non-malloc dependent, and still fast, I'd appreciate the patches. Compiling ========= I've managed to get this to compile on just about every Unix box I've tried, as long as a good ANSI compiler was available. That includes Ultrix, OSF 1.2 (from DEC), Digital Unix 3.2, SunOS 4.1.3, and Solaris 2.4 or 2.5, I don't remember. I have no reason to believe that it wouldn't compile on an HP or a RS/6000, but let me know if it complains. In general, look at make.conf, choose your compiler and compiler options, then type: make clean depend all To create and run a test program, type make testtrees ./testtrees 20000 2 1000 This will create 20000 random vectors, insert them into the tree, force the tree to rebuild itself twice, then delete 1000 of those vectors from the tree. (On a Sparc 5/85, this takes about 25 seconds.) As far as I know, I've gotten all of the memory leaks out of my code. I don't guarantee that I've fully tested all of these functions, and there may be some bugs lurking around. (Especially in the cases where you have more than one object occupying the exact same region.) Any questions can be mailed to: rickr+@cmu.edu Copyrights ========== dkdtree.c dkdtree.h ratlib.h ratlib.c testtrees.c All of these programs are Copyright (C) 1995-1996 Rick Romero and Carnegie Mellon University. splaymin.c splaylib.h These programs are Copyright (C) 1995-1996 Rick Romero. All of these programs are 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 1, 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. need, and if you don't need it, you can just put in a NULL. Argument 2, the object, is the (void *) that was originally passed in to RATInsert(t,x,y,w,h,object). If F1 returns non-zero, the function F2 is called. F2 also has two (void *) arguments, the first of which is the operand, which is arbitrarily set by the programmer. The second is agratlib/LICENSE000664 007207 000054 00000001306 06334350422 014152 0ustar00jmccpcvision000000 000000 Rectangle Access Tree Library (RATlib) -------------------------------------- Copyright 1996-1997 Richard Romero, Robert Thibadeau, Jason McMullan Copyright 1996-1997 Carnegie Mellon Univerity LICENSE ------- If you employ this source code in whole or in part in any code release whether for non-profit, governmental, or for-profit purposes, you agree to provide the attribution: "Includes the rectangle library by Rick Romero, Robert Thibadeau, and Jason McMullan of Carnegie Mellon University (rht@cs.cmu.edu)." You agree this attribution will appear on the viewable title page and/or title screen in a font no smaller than the font employed for the creator/owner of the package. nd containment query operators. The code generally looks something like this: regionList = RATIntersectsWith(tree, x, y, w, h); while(regionList) { OperateOnRegion(RATListFirst(regionList)); regionList = RATListDestructiveRest(regionList); } This code will pass to OperateOnRegion each of the reg</dkd_dimensions;i++)></dkd_dimensions;i++)></dkd_dimensions;>