Robust/src/Benchmarks/SingleTM/Yada/avltree.java

   1 /* =============================================================================
   2  *
   3  * avltree.c
   4  * -- AVL balanced tree library
   5  *
   6  * =============================================================================
   7  *
   8  * AVL balanced tree library
   9  *
  10  *   > Created (Julienne Walker): June 17, 2003
  11  *   > Modified (Julienne Walker): September 24, 2005
  12  *
  13  * =============================================================================
  14  *
  15  * Modified May 5, 2006 by Chi Cao Minh
  16  *
  17  * - Changed to not need functions to duplicate and release the data pointer
  18  *
  19  * =============================================================================
  20  *
  21  * For the license of bayes/sort.h and bayes/sort.c, please see the header
  22  * of the files.
  23  *
  24  * ------------------------------------------------------------------------
  25  *
  26  * For the license of kmeans, please see kmeans/LICENSE.kmeans
  27  *
  28  * ------------------------------------------------------------------------
  29  *
  30  * For the license of ssca2, please see ssca2/COPYRIGHT
  31  *
  32  * ------------------------------------------------------------------------
  33  *
  34  * For the license of lib/mt19937ar.c and lib/mt19937ar.h, please see the
  35  * header of the files.
  36  *
  37  * ------------------------------------------------------------------------
  38  *
  39  * For the license of lib/rbtree.h and lib/rbtree.c, please see
  40  * lib/LEGALNOTICE.rbtree and lib/LICENSE.rbtree
  41  *
  42  * ------------------------------------------------------------------------
  43  *
  44  * Unless otherwise noted, the following license applies to STAMP files:
  45  *
  46  * Copyright (c) 2007, Stanford University
  47  * All rights reserved.
  48  *
  49  * Redistribution and use in source and binary forms, with or without
  50  * modification, are permitted provided that the following conditions are
  51  * met:
  52  *
  53  *     * Redistributions of source code must retain the above copyright
  54  *       notice, this list of conditions and the following disclaimer.
  55  *
  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
  59  *       distribution.
  60  *
  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.
  64  *
  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.
  76  *
  77  * =============================================================================
  78  */
  79
  80 #define HEIGHT_LIMIT 64
  81
  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;                 \
  87   root = save;                            \
  88 } while (false)
  89
  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;                            \
  99   root = save;                                       \
 100 } while (false)
 101
 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;                     \
 110     n.balance = 0;                           \
 111   }                                           \
 112   else { /* nn.balance == -bal */            \
 113     root.balance = 0;                        \
 114     n.balance = bal;                         \
 115   }                                           \
 116   nn.balance = 0;                            \
 117 } while (false)
 118
 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 );             \
 126   }                                        \
 127   else { /* n.balance == -bal */          \
 128     jsw_adjust_balance( root, dir, bal ); \
 129     jsw_double( root, 1-dir );             \
 130   }                                        \
 131 } while (false)
 132
 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 );                  \
 140   }                                            \
 141   else if ( nr.balance == bal ) {              \
 142     jsw_adjust_balance ( root, 1-dir, -bal );   \
 143     jsw_double ( root, dir );                  \
 144   }                                            \
 145   else { /* n.balance == 0 */                 \
 146     root.balance = -bal;                      \
 147     nr.balance = bal;                          \
 148     jsw_single ( root, dir );                  \
 149     done = 1;                                  \
 150   }                                            \
 151 } while (false)
 152
 153
 154 class avlnode {
 155   int balance; /* Balance factor */
 156   Object data;    /* User-defined content */
 157   avlnode link[]; /* Left (0) and right (1) links */
 158
 159   avlnode() {
 160     link=new avlnode[2];
 161   }
 162
 163   avlnode(avltree tree, Object data) {
 164     this.data = data;
 165     link=new avlnode[2];
 166   }
 167 }
 168
 169 class avltrav {
 170   avltree tree;               /* Paired tree */
 171   avlnode it;                 /* Current node */
 172   avlnode path[]; /* Traversal path */
 173   int  top;                /* Top of stack */
 174
 175   avltrav() {
 176     path=new avlnode[HEIGHT_LIMIT];
 177   }
 178
 179 /*
 180   First step in traversal,
 181   handles min and max
 182 */
 183   Object start(avltree tree, int dir) {
 184     this.tree = tree;
 185     it = tree.root;
 186     top = 0;
 187
 188     /* Build a path to work with */
 189     if ( it != null ) {
 190       while ( it.link[dir] != null ) {
 191         path[top++] = it;
 192         it = it.link[dir];
 193       }
 194     }
 195
 196     return it == null? null: it.data;
 197   }
 198
 199   /*
 200     Subsequent traversal steps,
 201     handles ascending and descending
 202   */
 203   Object move(int dir) {
 204     if (it.link[dir] != null) {
 205       /* Continue down this branch */
 206       path[top++] = it;
 207       it = it.link[dir];
 208
 209       while (it.link[1-dir] != null ) {
 210         path[top++] = it;
 211         it = it.link[1-dir];
 212       }
 213     } else {
 214       /* Move to the next branch */
 215       avlnode last;
 216
 217       do {
 218         if (top == 0 ) {
 219           it = null;
 220           break;
 221         }
 222
 223         last = it;
 224         it = path[--top];
 225       } while ( last == it.link[dir] );
 226     }
 227
 228     return it==null? null: it.data;
 229   }
 230
 231   Object avltfirst(avltree tree ) {
 232     return start(tree, 0 ); /* Min value */
 233   }
 234
 235   Object avltlast (avltree tree ) {
 236     return start(tree, 1 ); /* Max value */
 237   }
 238
 239   Object avltnext() {
 240     return move(1); /* Toward larger items */
 241   }
 242
 243   Object avltprev() {
 244     return move(0); /* Toward smaller items */
 245   }
 246 }
 247
 248 public class avltree {
 249   avlnode root; /* Top of the tree */
 250   int         size;   /* Number of items (user-defined) */
 251   int mode;
 252   //mode=0 element_mapCompareEdge
 253   //mode=1 element_mapCompare
 254
 255   public avltree(int mode) {
 256     size = 0;
 257     this.mode=mode;
 258   }
 259
 260   int cmp(Object a, Object b) {
 261     return 0;
 262   }
 263
 264
 265   boolean contains(Object key) {
 266     boolean success = false;
 267     edge searchPair=new edge();
 268     searchPair.firstPtr = key;
 269     if (avlfind(searchPair) != null) {
 270       success = true;
 271     }
 272     return success;
 273   }
 274
 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;
 282     }
 283     return dataPtr;
 284   }
 285
 286   boolean insert(Object key, Object data) {
 287     boolean success = false;
 288     edge insertPtr = new edge(key, data);
 289     if (avlinsert(insertPtr)) {
 290       success = true;
 291     }
 292     return success;
 293   }
 294
 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)) {
 301       success=true;
 302     }
 303     return success;
 304   }
 305
 306   Object avlfind(Object data ) {
 307     avlnode it = root;
 308
 309     while ( it != null ) {
 310       int cmp =cmp(it.data, data );
 311
 312       if ( cmp == 0 )
 313         break;
 314
 315       it = it.link[(cmp < 0)?1:0];
 316     }
 317
 318     return it == null ? null : it.data;
 319   }
 320
 321   boolean avlinsert(Object data ) {
 322     /* Empty tree case */
 323     if ( root == null ) {
 324       root = new avlnode(this,data);
 325     } else {
 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 */
 329       int dir;
 330
 331       /* Set up false root to ease maintenance */
 332       t = head;
 333       t.link[1] = root;
 334
 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;
 338         q = p.link[dir];
 339
 340         if ( q == null )
 341           break;
 342
 343         if ( q.balance != 0 ) {
 344           t = p;
 345           s = q;
 346         }
 347       }
 348
 349       p.link[dir] = q = new avlnode(this, data);
 350       if (q==null)
 351         return false;
 352
 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;
 357       }
 358
 359       q = s; /* Save rebalance point for parent fix */
 360
 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 );
 365       }
 366
 367       /* Fix parent */
 368       if ( q == head.link[1] )
 369         root = s;
 370       else
 371         t.link[(q == t.link[1])?1:0] = s;
 372     }
 373
 374     size++;
 375
 376     return true;
 377   }
 378
 379   boolean avlerase (Object data) {
 380     if (root != null) {
 381       avlnode it;
 382       avlnode up[]=new avlnode[HEIGHT_LIMIT];
 383       int upd[]=new int[HEIGHT_LIMIT];
 384       int top = 0;
 385       int done = 0;
 386
 387       it = root;
 388
 389       /* Search down tree and save path */
 390       for ( ; true ; ) {
 391         if ( it == null )
 392           return false;
 393         else if ( cmp ( it.data, data ) == 0 )
 394           break;
 395
 396         /* Push direction and node onto stack */
 397         upd[top] = (cmp ( it.data, data ) < 0)?1:0;
 398         up[top++] = it;
 399
 400         it = it.link[upd[top - 1]];
 401       }
 402
 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;
 407
 408         /* Fix parent */
 409         if (top != 0)
 410           up[top-1].link[upd[top - 1]] = it.link[dir];
 411         else
 412           root = it.link[dir];
 413       } else {
 414         /* Find the inorder successor */
 415         avlnode heir = it.link[1];
 416
 417         /* Save this path too */
 418         upd[top] = 1;
 419         up[top++] = it;
 420
 421         while ( heir.link[0] != null ) {
 422           upd[top] = 0;
 423           up[top++] = heir;
 424           heir = heir.link[0];
 425         }
 426
 427         /* Swap data */
 428         Object save = it.data;
 429         it.data = heir.data;
 430         heir.data = save;
 431
 432         /* Unlink successor and fix parent */
 433         up[top-1].link[(up[top - 1] == it)?1:0] = heir.link[1];
 434     }
 435
 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;
 440
 441         /* Terminate or rebalance as necessary */
 442         if (up[top].balance == 1 || up[top].balance==-1 )
 443           break;
 444         else if ( up[top].balance > 1 ||up[top].balance < -1) {
 445           jsw_remove_balance ( up[top], upd[top], done );
 446
 447           /* Fix parent */
 448           if ( top != 0 )
 449             up[top - 1].link[upd[top - 1]] = up[top];
 450           else
 451             root = up[0];
 452         }
 453       }
 454     }
 455     size--;
 456     return true;
 457   }
 458
 459   int avlsize() {
 460     return size;
 461   }
 462
 463 }
 464
 465
 466
 467 /* =============================================================================
 468  *
 469  * End of avltree.c
 470  *
 471  * =============================================================================
 472  */