00001 #ifndef UBI_SPLAYTREE_H 00002 #define UBI_SPLAYTREE_H 00003 /* $Id$ */ 00004 /* ========================================================================== ** 00005 * ubi_SplayTree.h 00006 * 00007 * Copyright (C) 1993-1998 by Christopher R. Hertel 00008 * 00009 * Email: crh@ubiqx.mn.org 00010 * -------------------------------------------------------------------------- ** 00011 * 00012 * This module implements "splay" trees. Splay trees are binary trees 00013 * that are rearranged (splayed) whenever a node is accessed. The 00014 * splaying process *tends* to make the tree bushier (improves balance), 00015 * and the nodes that are accessed most frequently *tend* to be closer to 00016 * the top. 00017 * 00018 * References: "Self-Adjusting Binary Search Trees", by Daniel Sleator and 00019 * Robert Tarjan. Journal of the Association for Computing 00020 * Machinery Vol 32, No. 3, July 1985 pp. 652-686 00021 * 00022 * See also: http://www.cs.cmu.edu/~sleator/ 00023 * 00024 * -------------------------------------------------------------------------- ** 00025 * 00026 * This library is free software; you can redistribute it and/or 00027 * modify it under the terms of the GNU Library General Public 00028 * License as published by the Free Software Foundation; either 00029 * version 2 of the License, or (at your option) any later version. 00030 * 00031 * This library is distributed in the hope that it will be useful, 00032 * but WITHOUT ANY WARRANTY; without even the implied warranty of 00033 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 00034 * Library General Public License for more details. 00035 * 00036 * You should have received a copy of the GNU Library General Public 00037 * License along with this library; if not, write to the Free 00038 * Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. 00039 * 00040 * ========================================================================== ** 00041 */ 00042 00043 #include "ubi_BinTree.h" /* Base binary tree functions, types, etc. */ 00044 00045 /* ========================================================================== ** 00046 * Function prototypes... 00047 */ 00048 00049 ubi_trBool ubi_sptInsert( ubi_btRootPtr RootPtr, 00050 ubi_btNodePtr NewNode, 00051 ubi_btItemPtr ItemPtr, 00052 ubi_btNodePtr *OldNode ); 00053 /* ------------------------------------------------------------------------ ** 00054 * This function uses a non-recursive algorithm to add a new element to the 00055 * splay tree. 00056 * 00057 * Input: RootPtr - a pointer to the ubi_btRoot structure that indicates 00058 * the root of the tree to which NewNode is to be added. 00059 * NewNode - a pointer to an ubi_btNode structure that is NOT 00060 * part of any tree. 00061 * ItemPtr - A pointer to the sort key that is stored within 00062 * *NewNode. ItemPtr MUST point to information stored 00063 * in *NewNode or an EXACT DUPLICATE. The key data 00064 * indicated by ItemPtr is used to place the new node 00065 * into the tree. 00066 * OldNode - a pointer to an ubi_btNodePtr. When searching 00067 * the tree, a duplicate node may be found. If 00068 * duplicates are allowed, then the new node will 00069 * be simply placed into the tree. If duplicates 00070 * are not allowed, however, then one of two things 00071 * may happen. 00072 * 1) if overwritting *is not* allowed, this 00073 * function will return FALSE (indicating that 00074 * the new node could not be inserted), and 00075 * *OldNode will point to the duplicate that is 00076 * still in the tree. 00077 * 2) if overwritting *is* allowed, then this 00078 * function will swap **OldNode for *NewNode. 00079 * In this case, *OldNode will point to the node 00080 * that was removed (thus allowing you to free 00081 * the node). 00082 * ** If you are using overwrite mode, ALWAYS ** 00083 * ** check the return value of this parameter! ** 00084 * Note: You may pass NULL in this parameter, the 00085 * function knows how to cope. If you do this, 00086 * however, there will be no way to return a 00087 * pointer to an old (ie. replaced) node (which is 00088 * a problem if you are using overwrite mode). 00089 * 00090 * Output: a boolean value indicating success or failure. The function 00091 * will return FALSE if the node could not be added to the tree. 00092 * Such failure will only occur if duplicates are not allowed, 00093 * nodes cannot be overwritten, AND a duplicate key was found 00094 * within the tree. 00095 * ------------------------------------------------------------------------ ** 00096 */ 00097 00098 void Rotate( ubi_btNodePtr p ); 00099 /* ------------------------------------------------------------------------ ** 00100 * This function performs a single rotation, moving node *p up one level 00101 * in the tree. 00102 * 00103 * Input: p - a pointer to an ubi_btNode in a tree. 00104 * 00105 * Output: None. 00106 * 00107 * Notes: This implements a single rotation in either direction (left 00108 * or right). This is the basic building block of all splay 00109 * tree rotations. 00110 * ------------------------------------------------------------------------ ** */ 00111 00112 ubi_btNodePtr ubi_sptRemove( ubi_btRootPtr RootPtr, ubi_btNodePtr DeadNode ); 00113 /* ------------------------------------------------------------------------ ** 00114 * This function removes the indicated node from the tree. 00115 * 00116 * Input: RootPtr - A pointer to the header of the tree that contains 00117 * the node to be removed. 00118 * DeadNode - A pointer to the node that will be removed. 00119 * 00120 * Output: This function returns a pointer to the node that was removed 00121 * from the tree (ie. the same as DeadNode). 00122 * 00123 * Note: The node MUST be in the tree indicated by RootPtr. If not, 00124 * strange and evil things will happen to your trees. 00125 * ------------------------------------------------------------------------ ** 00126 */ 00127 00128 ubi_btNodePtr ubi_sptLocate( ubi_btRootPtr RootPtr, 00129 ubi_btItemPtr FindMe, 00130 ubi_trCompOps CompOp ); 00131 /* ------------------------------------------------------------------------ ** 00132 * The purpose of ubi_btLocate() is to find a node or set of nodes given 00133 * a target value and a "comparison operator". The Locate() function is 00134 * more flexible and (in the case of trees that may contain dupicate keys) 00135 * more precise than the ubi_btFind() function. The latter is faster, 00136 * but it only searches for exact matches and, if the tree contains 00137 * duplicates, Find() may return a pointer to any one of the duplicate- 00138 * keyed records. 00139 * 00140 * Input: 00141 * RootPtr - A pointer to the header of the tree to be searched. 00142 * FindMe - An ubi_btItemPtr that indicates the key for which to 00143 * search. 00144 * CompOp - One of the following: 00145 * CompOp Return a pointer to the node with 00146 * ------ --------------------------------- 00147 * ubi_trLT - the last key value that is less 00148 * than FindMe. 00149 * ubi_trLE - the first key matching FindMe, or 00150 * the last key that is less than 00151 * FindMe. 00152 * ubi_trEQ - the first key matching FindMe. 00153 * ubi_trGE - the first key matching FindMe, or the 00154 * first key greater than FindMe. 00155 * ubi_trGT - the first key greater than FindMe. 00156 * Output: 00157 * A pointer to the node matching the criteria listed above under 00158 * CompOp, or NULL if no node matched the criteria. 00159 * 00160 * Notes: 00161 * In the case of trees with duplicate keys, Locate() will behave as 00162 * follows: 00163 * 00164 * Find: 3 Find: 3 00165 * Keys: 1 2 2 2 3 3 3 3 3 4 4 Keys: 1 1 2 2 2 4 4 5 5 5 6 00166 * ^ ^ ^ ^ ^ 00167 * LT EQ GT LE GE 00168 * 00169 * That is, when returning a pointer to a node with a key that is LESS 00170 * THAN the target key (FindMe), Locate() will return a pointer to the 00171 * LAST matching node. 00172 * When returning a pointer to a node with a key that is GREATER 00173 * THAN the target key (FindMe), Locate() will return a pointer to the 00174 * FIRST matching node. 00175 * 00176 * See Also: ubi_btFind(), ubi_btFirstOf(), ubi_btLastOf(). 00177 * ------------------------------------------------------------------------ ** 00178 */ 00179 00180 ubi_btNodePtr ubi_sptFind( ubi_btRootPtr RootPtr, 00181 ubi_btItemPtr FindMe ); 00182 /* ------------------------------------------------------------------------ ** 00183 * This function performs a non-recursive search of a tree for any node 00184 * matching a specific key. 00185 * 00186 * Input: 00187 * RootPtr - a pointer to the header of the tree to be searched. 00188 * FindMe - a pointer to the key value for which to search. 00189 * 00190 * Output: 00191 * A pointer to a node with a key that matches the key indicated by 00192 * FindMe, or NULL if no such node was found. 00193 * 00194 * Note: In a tree that allows duplicates, the pointer returned *might 00195 * not* point to the (sequentially) first occurance of the 00196 * desired key. In such a tree, it may be more useful to use 00197 * ubi_sptLocate(). 00198 * ------------------------------------------------------------------------ ** 00199 */ 00200 00201 void ubi_sptSplay( ubi_btRootPtr RootPtr, 00202 ubi_btNodePtr SplayMe ); 00203 /* ------------------------------------------------------------------------ ** 00204 * This function allows you to splay the tree at a given node, thus moving 00205 * the node to the top of the tree. 00206 * 00207 * Input: 00208 * RootPtr - a pointer to the header of the tree to be splayed. 00209 * SplayMe - a pointer to a node within the tree. This will become 00210 * the new root node. 00211 * Output: None. 00212 * 00213 * Notes: This is an uncharacteristic function for this group of modules 00214 * in that it provides access to the internal balancing routines, 00215 * which would normally be hidden. 00216 * Splaying the tree will not damage it (assuming that I've done 00217 * *my* job), but there is overhead involved. I don't recommend 00218 * that you use this function unless you understand the underlying 00219 * Splay Tree principles involved. 00220 * ------------------------------------------------------------------------ ** 00221 */ 00222 00223 int ubi_sptModuleID( int size, char *list[] ); 00224 /* ------------------------------------------------------------------------ ** 00225 * Returns a set of strings that identify the module. 00226 * 00227 * Input: size - The number of elements in the array <list>. 00228 * list - An array of pointers of type (char *). This array 00229 * should, initially, be empty. This function will fill 00230 * in the array with pointers to strings. 00231 * Output: The number of elements of <list> that were used. If this value 00232 * is less than <size>, the values of the remaining elements are 00233 * not guaranteed. 00234 * 00235 * Notes: Please keep in mind that the pointers returned indicate strings 00236 * stored in static memory. Don't free() them, don't write over 00237 * them, etc. Just read them. 00238 * ------------------------------------------------------------------------ ** 00239 */ 00240 00241 /* -------------------------------------------------------------------------- ** 00242 * Masquarade... 00243 * 00244 * This set of defines allows you to write programs that will use any of the 00245 * implemented binary tree modules (currently BinTree, AVLtree, and SplayTree). 00246 * Instead of using ubi_bt..., use ubi_tr..., and select the tree type by 00247 * including the appropriate module header. 00248 */ 00249 00250 #undef ubi_trInsert 00251 #undef ubi_trRemove 00252 #undef ubi_trLocate 00253 #undef ubi_trFind 00254 #undef ubi_trModuleID 00255 00256 #define ubi_trInsert( Rp, Nn, Ip, On ) \ 00257 ubi_sptInsert( (ubi_btRootPtr)(Rp), (ubi_btNodePtr)(Nn), \ 00258 (ubi_btItemPtr)(Ip), (ubi_btNodePtr *)(On) ) 00259 00260 #define ubi_trRemove( Rp, Dn ) \ 00261 ubi_sptRemove( (ubi_btRootPtr)(Rp), (ubi_btNodePtr)(Dn) ) 00262 00263 #define ubi_trLocate( Rp, Ip, Op ) \ 00264 ubi_sptLocate( (ubi_btRootPtr)(Rp), \ 00265 (ubi_btItemPtr)(Ip), \ 00266 (ubi_trCompOps)(Op) ) 00267 00268 #define ubi_trFind( Rp, Ip ) \ 00269 ubi_sptFind( (ubi_btRootPtr)(Rp), (ubi_btItemPtr)(Ip) ) 00270 00271 #define ubi_trSplay( Rp, Sm ) \ 00272 ubi_sptSplay( (ubi_btRootPtr)(Rp), (ubi_btNodePtr)(Sm) ) 00273 00274 #define ubi_trModuleID( s, l ) ubi_sptModuleID( s, l ) 00275 00276 /* ================================ The End ================================= */ 00277 #endif /* UBI_SPLAYTREE_H */
1.4.2