1 /* =============================================================================
4 * -- AVL balanced tree library
6 * =============================================================================
8 * AVL balanced tree library
10 * > Created (Julienne Walker): June 17, 2003
11 * > Modified (Julienne Walker): September 24, 2005
13 * =============================================================================
15 * Modified May 5, 2006 by Chi Cao Minh
17 * - Changed to not need functions to duplicate and release the data pointer
19 * =============================================================================
21 * For the license of bayes/sort.h and bayes/sort.c, please see the header
24 * ------------------------------------------------------------------------
26 * For the license of kmeans, please see kmeans/LICENSE.kmeans
28 * ------------------------------------------------------------------------
30 * For the license of ssca2, please see ssca2/COPYRIGHT
32 * ------------------------------------------------------------------------
34 * For the license of lib/mt19937ar.c and lib/mt19937ar.h, please see the
35 * header of the files.
37 * ------------------------------------------------------------------------
39 * For the license of lib/rbtree.h and lib/rbtree.c, please see
40 * lib/LEGALNOTICE.rbtree and lib/LICENSE.rbtree
42 * ------------------------------------------------------------------------
44 * Unless otherwise noted, the following license applies to STAMP files:
46 * Copyright (c) 2007, Stanford University
47 * All rights reserved.
49 * Redistribution and use in source and binary forms, with or without
50 * modification, are permitted provided that the following conditions are
53 * * Redistributions of source code must retain the above copyright
54 * notice, this list of conditions and the following disclaimer.
56 * * Redistributions in binary form must reproduce the above copyright
57 * notice, this list of conditions and the following disclaimer in
58 * the documentation and/or other materials provided with the
61 * * Neither the name of Stanford University nor the names of its
62 * contributors may be used to endorse or promote products derived
63 * from this software without specific prior written permission.
65 * THIS SOFTWARE IS PROVIDED BY STANFORD UNIVERSITY ``AS IS'' AND ANY
66 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
67 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
68 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL STANFORD UNIVERSITY BE LIABLE
69 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
70 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
71 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
72 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
73 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
74 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
75 * THE POSSIBILITY OF SUCH DAMAGE.
77 * =============================================================================
80 #define HEIGHT_LIMIT 64
82 /* Two way single rotation */
83 #define jsw_single(root,dir) do { \
84 avlnode save = root.link[1-dir]; \
85 root.link[1-dir] = save.link[dir]; \
86 save.link[dir] = root; \
90 /* Two way double rotation */
91 #define jsw_double(root,dir) do { \
92 avlnode save = root.link[1-dir].link[dir]; \
93 root.link[1-dir].link[dir] = save.link[1-dir]; \
94 save.link[1-dir] = root.link[1-dir]; \
95 root.link[1-dir] = save; \
96 save = root.link[1-dir]; \
97 root.link[1-dir] = save.link[dir]; \
98 save.link[dir] = root; \
102 /* Adjust balance before double rotation */
103 #define jsw_adjust_balance(root,dir,bal) do { \
104 avlnode n = root.link[dir]; \
105 avlnode nn = n.link[1-dir]; \
106 if ( nn.balance == 0 ) \
107 root.balance = n.balance = 0; \
108 else if ( nn.balance == bal ) { \
109 root.balance = -bal; \
112 else { /* nn.balance == -bal */ \
119 /* Rebalance after insertion */
120 #define jsw_insert_balance(root,dir) do { \
121 avlnode ni = root.link[dir]; \
122 int bal = dir == 0 ? -1 : +1; \
123 if ( ni.balance == bal ) { \
124 root.balance = ni.balance = 0; \
125 jsw_single ( root, 1-dir ); \
127 else { /* n.balance == -bal */ \
128 jsw_adjust_balance( root, dir, bal ); \
129 jsw_double( root, 1-dir ); \
133 /* Rebalance after deletion */
134 #define jsw_remove_balance(root,dir,done) do { \
135 avlnode nr = root.link[1-dir]; \
136 int bal = dir == 0 ? -1 : +1; \
137 if ( nr.balance == -bal ) { \
138 root.balance = nr.balance = 0; \
139 jsw_single ( root, dir ); \
141 else if ( nr.balance == bal ) { \
142 jsw_adjust_balance ( root, 1-dir, -bal ); \
143 jsw_double ( root, dir ); \
145 else { /* n.balance == 0 */ \
146 root.balance = -bal; \
148 jsw_single ( root, dir ); \
155 int balance; /* Balance factor */
156 Object data; /* User-defined content */
157 avlnode link[]; /* Left (0) and right (1) links */
163 avlnode(avltree tree, Object data) {
170 avltree tree; /* Paired tree */
171 avlnode it; /* Current node */
172 avlnode path[]; /* Traversal path */
173 int top; /* Top of stack */
176 path=new avlnode[HEIGHT_LIMIT];
180 First step in traversal,
183 Object start(avltree tree, int dir) {
188 /* Build a path to work with */
190 while ( it.link[dir] != null ) {
196 return it == null? null: it.data;
200 Subsequent traversal steps,
201 handles ascending and descending
203 Object move(int dir) {
204 if (it.link[dir] != null) {
205 /* Continue down this branch */
209 while (it.link[1-dir] != null ) {
214 /* Move to the next branch */
225 } while ( last == it.link[dir] );
228 return it==null? null: it.data;
231 Object avltfirst(avltree tree ) {
232 return start(tree, 0 ); /* Min value */
235 Object avltlast (avltree tree ) {
236 return start(tree, 1 ); /* Max value */
240 return move(1); /* Toward larger items */
244 return move(0); /* Toward smaller items */
248 public class avltree {
249 avlnode root; /* Top of the tree */
250 int size; /* Number of items (user-defined) */
252 //mode=0 element_mapCompareEdge
253 //mode=1 element_mapCompare
255 public avltree(int mode) {
260 int cmp(Object a, Object b) {
265 boolean contains(Object key) {
266 boolean success = false;
267 edge searchPair=new edge();
268 searchPair.firstPtr = key;
269 if (avlfind(searchPair) != null) {
275 Object find(Object key) {
276 Object dataPtr = null;
277 edge searchPair=new edge();
278 searchPair.firstPtr = key;
279 edge pairPtr = (edge)avlfind(searchPair);
280 if (pairPtr != null) {
281 dataPtr = pairPtr.secondPtr;
286 boolean insert(Object key, Object data) {
287 boolean success = false;
288 edge insertPtr = new edge(key, data);
289 if (avlinsert(insertPtr)) {
295 boolean remove(Object key) {
296 boolean success = false;
297 edge searchPair=new edge();
298 searchPair.firstPtr = key;
299 edge pairPtr = (edge) avlfind(searchPair);
300 if (avlerase(searchPair)) {
306 Object avlfind(Object data ) {
309 while ( it != null ) {
310 int cmp =cmp(it.data, data );
315 it = it.link[(cmp < 0)?1:0];
318 return it == null ? null : it.data;
321 boolean avlinsert(Object data ) {
322 /* Empty tree case */
323 if ( root == null ) {
324 root = new avlnode(this,data);
326 avlnode head =new avlnode(); /* Temporary tree root */
327 avlnode s, t; /* Place to rebalance and parent */
328 avlnode p, q; /* Iterator and save pointer */
331 /* Set up false root to ease maintenance */
335 /* Search down the tree, saving rebalance points */
336 for ( s = p = t.link[1]; true ; p=q ) {
337 dir = (cmp ( p.data, data ) < 0)?1:0;
343 if ( q.balance != 0 ) {
349 p.link[dir] = q = new avlnode(this, data);
353 /* Update balance factors */
354 for ( p = s; p != q; p = p.link[dir] ) {
355 dir = (cmp ( p.data, data ) < 0)?1:0;
356 p.balance += (dir == 0) ? -1 : +1;
359 q = s; /* Save rebalance point for parent fix */
361 /* Rebalance if necessary */
362 if ((s.balance<0?-s.balance:s.balance)>1) {
363 dir =(cmp(s.data,data) < 0)?1:0;
364 jsw_insert_balance ( s, dir );
368 if ( q == head.link[1] )
371 t.link[(q == t.link[1])?1:0] = s;
379 boolean avlerase (Object data) {
382 avlnode up[]=new avlnode[HEIGHT_LIMIT];
383 int upd[]=new int[HEIGHT_LIMIT];
389 /* Search down tree and save path */
393 else if ( cmp ( it.data, data ) == 0 )
396 /* Push direction and node onto stack */
397 upd[top] = (cmp ( it.data, data ) < 0)?1:0;
400 it = it.link[upd[top - 1]];
403 /* Remove the node */
404 if ( it.link[0] == null || it.link[1] == null ) {
405 /* Which child is not null? */
406 int dir = (it.link[0] == null)?1:0;
410 up[top-1].link[upd[top - 1]] = it.link[dir];
414 /* Find the inorder successor */
415 avlnode heir = it.link[1];
417 /* Save this path too */
421 while ( heir.link[0] != null ) {
428 Object save = it.data;
432 /* Unlink successor and fix parent */
433 up[top-1].link[(up[top - 1] == it)?1:0] = heir.link[1];
436 /* Walk back up the search path */
437 while ( --top >= 0 && (done==0) ) {
438 /* Update balance factors */
439 up[top].balance += upd[top] != 0 ? -1 : +1;
441 /* Terminate or rebalance as necessary */
442 if (up[top].balance == 1 || up[top].balance==-1 )
444 else if ( up[top].balance > 1 ||up[top].balance < -1) {
445 jsw_remove_balance ( up[top], upd[top], done );
449 up[top - 1].link[upd[top - 1]] = up[top];
467 /* =============================================================================
471 * =============================================================================