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

   1 /* =============================================================================
   2  *
   3  * heap.c
   4  *
   5  * =============================================================================
   6  *
   7  * Copyright (C) Stanford University, 2006.  All Rights Reserved.
   8  * Author: Chi Cao Minh
   9  *
  10  * =============================================================================
  11  *
  12  * For the license of bayes/sort.h and bayes/sort.c, please see the header
  13  * of the files.
  14  *
  15  * ------------------------------------------------------------------------
  16  *
  17  * For the license of kmeans, please see kmeans/LICENSE.kmeans
  18  *
  19  * ------------------------------------------------------------------------
  20  *
  21  * For the license of ssca2, please see ssca2/COPYRIGHT
  22  *
  23  * ------------------------------------------------------------------------
  24  *
  25  * For the license of lib/mt19937ar.c and lib/mt19937ar.h, please see the
  26  * header of the files.
  27  *
  28  * ------------------------------------------------------------------------
  29  *
  30  * For the license of lib/rbtree.h and lib/rbtree.c, please see
  31  * lib/LEGALNOTICE.rbtree and lib/LICENSE.rbtree
  32  *
  33  * ------------------------------------------------------------------------
  34  *
  35  * Unless otherwise noted, the following license applies to STAMP files:
  36  *
  37  * Copyright (c) 2007, Stanford University
  38  * All rights reserved.
  39  *
  40  * Redistribution and use in source and binary forms, with or without
  41  * modification, are permitted provided that the following conditions are
  42  * met:
  43  *
  44  *     * Redistributions of source code must retain the above copyright
  45  *       notice, this list of conditions and the following disclaimer.
  46  *
  47  *     * Redistributions in binary form must reproduce the above copyright
  48  *       notice, this list of conditions and the following disclaimer in
  49  *       the documentation and/or other materials provided with the
  50  *       distribution.
  51  *
  52  *     * Neither the name of Stanford University nor the names of its
  53  *       contributors may be used to endorse or promote products derived
  54  *       from this software without specific prior written permission.
  55  *
  56  * THIS SOFTWARE IS PROVIDED BY STANFORD UNIVERSITY ``AS IS'' AND ANY
  57  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  58  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  59  * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL STANFORD UNIVERSITY BE LIABLE
  60  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
  61  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
  62  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
  63  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
  64  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
  65  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
  66  * THE POSSIBILITY OF SUCH DAMAGE.
  67  *
  68  * =============================================================================
  69  */
  70
  71 #define PARENT(i)       ((i) / 2)
  72 #define LEFT_CHILD(i)   (2*i)
  73 #define RIGHT_CHILD(i)  (2*(i) + 1)
  74
  75 public class heap {
  76   Object [] elements;
  77   int size;
  78   int capacity;
  79
  80 /* =============================================================================
  81  * heap_alloc
  82  * -- Returns NULL on failure
  83  * =============================================================================
  84  */
  85   public heap(int initCapacity) {
  86     int capacity = ((initCapacity > 0) ? (initCapacity) : (1));
  87     elements = new Object[capacity];
  88     size=0;
  89     this.capacity = capacity;
  90   }
  91
  92 /* =============================================================================
  93  * siftUp
  94  * =============================================================================
  95  */
  96   public void siftUp(int startIndex) {
  97     int index = startIndex;
  98     while ((index > 1)) {
  99       long parentIndex = PARENT(index);
 100       Object parentPtr = elements[parentIndex];
 101       Object thisPtr   = elements[index];
 102       if (compare(parentPtr, thisPtr) >= 0) {
 103         break;
 104       }
 105       Object tmpPtr = parentPtr;
 106       elements[parentIndex] = thisPtr;
 107       elements[index] = tmpPtr;
 108       index = parentIndex;
 109     }
 110   }
 111
 112 /* =============================================================================
 113  * heap_insert
 114  * -- Returns FALSE on failure
 115  * =============================================================================
 116  */
 117   public boolean heap_insert(Object dataPtr) {
 118     if ((size + 1) >= capacity) {
 119       long newCapacity = capacity * 2;
 120       Object newElements[] = new Object[newCapacity];
 121       this.capacity = newCapacity;
 122       for (int i = 0; i <= size; i++) {
 123         newElements[i] = elements[i];
 124       }
 125       this.elements = newElements;
 126     }
 127
 128     size++;
 129     elements[size] = dataPtr;
 130     siftUp(heapPtr, size);
 131
 132     return true;
 133   }
 134
 135
 136 /* =============================================================================
 137  * heapify
 138  * =============================================================================
 139  */
 140   public void heapify(int startIndex) {
 141     int index = startIndex;
 142
 143     while (true) {
 144       int leftIndex = LEFT_CHILD(index);
 145       int rightIndex = RIGHT_CHILD(index);
 146       int maxIndex = -1;
 147
 148       if ((leftIndex <= size) &&
 149           (compare(elements[leftIndex], elements[index]) > 0)) {
 150         maxIndex = leftIndex;
 151       } else {
 152         maxIndex = index;
 153       }
 154
 155       if ((rightIndex <= size) &&
 156           (compare(elements[rightIndex], elements[maxIndex]) > 0)) {
 157         maxIndex = rightIndex;
 158       }
 159
 160       if (maxIndex == index) {
 161         break;
 162       } else {
 163         Object tmpPtr = elements[index];
 164         elements[index] = elements[maxIndex];
 165         elements[maxIndex] = tmpPtr;
 166         index = maxIndex;
 167       }
 168     }
 169   }
 170
 171
 172 /* =============================================================================
 173  * heap_remove
 174  * -- Returns NULL if empty
 175  * =============================================================================
 176  */
 177   Object heap_remove() {
 178     if (size < 1) {
 179       return null;
 180     }
 181
 182     Object dataPtr = elements[1];
 183     elements[1] = elements[size];
 184     size--;
 185     heapify(1);
 186
 187     return dataPtr;
 188   }
 189
 190 /* =============================================================================
 191  * heap_isValid
 192  * =============================================================================
 193  */
 194   boolean heap_isValid() {
 195     for (int i = 1; i < size; i++) {
 196       if (compare(elements[i+1], elements[PARENT(i+1)]) > 0) {
 197         return false;
 198       }
 199     }
 200     return true;
 201   }
 202
 203
 204   private static int compare(Object aPtr, Object bPtr) {
 205     element aElementPtr = (element)aPtr;
 206     element bElementPtr = (element)bPtr;
 207
 208     if (aElementPtr.encroachedEdgePtr) {
 209       if (bElementPtr.encroachedEdgePtr) {
 210         return 0; /* do not care */
 211       } else {
 212         return 1;
 213       }
 214     }
 215
 216     if (bElementPtr.encroachedEdgePtr) {
 217       return -1;
 218     }
 219   }
 220
 221   public void printHeap() {
 222     System.out.println("[");
 223     for (int i = 0; i < size; i++) {
 224       System.out.print(elements[i+1]+" ");
 225     }
 226     System.out.println("]");
 227   }
 228 }