1 /* =============================================================================
5 * =============================================================================
7 * Copyright (C) Stanford University, 2006. All Rights Reserved.
10 * =============================================================================
12 * For the license of bayes/sort.h and bayes/sort.c, please see the header
15 * ------------------------------------------------------------------------
17 * For the license of kmeans, please see kmeans/LICENSE.kmeans
19 * ------------------------------------------------------------------------
21 * For the license of ssca2, please see ssca2/COPYRIGHT
23 * ------------------------------------------------------------------------
25 * For the license of lib/mt19937ar.c and lib/mt19937ar.h, please see the
26 * header of the files.
28 * ------------------------------------------------------------------------
30 * For the license of lib/rbtree.h and lib/rbtree.c, please see
31 * lib/LEGALNOTICE.rbtree and lib/LICENSE.rbtree
33 * ------------------------------------------------------------------------
35 * Unless otherwise noted, the following license applies to STAMP files:
37 * Copyright (c) 2007, Stanford University
38 * All rights reserved.
40 * Redistribution and use in source and binary forms, with or without
41 * modification, are permitted provided that the following conditions are
44 * * Redistributions of source code must retain the above copyright
45 * notice, this list of conditions and the following disclaimer.
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
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.
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.
68 * =============================================================================
71 #define PARENT(i) ((i) / 2)
72 #define LEFT_CHILD(i) (2*i)
73 #define RIGHT_CHILD(i) (2*(i) + 1)
80 /* =============================================================================
82 * -- Returns NULL on failure
83 * =============================================================================
85 public heap(int initCapacity) {
86 int capacity = ((initCapacity > 0) ? (initCapacity) : (1));
87 elements = new Object[capacity];
89 this.capacity = capacity;
92 /* =============================================================================
94 * =============================================================================
96 public void siftUp(int startIndex) {
97 int index = startIndex;
99 int parentIndex = PARENT(index);
100 Object parentPtr = elements[parentIndex];
101 Object thisPtr = elements[index];
102 if (compare(parentPtr, thisPtr) >= 0) {
105 Object tmpPtr = parentPtr;
106 elements[parentIndex] = thisPtr;
107 elements[index] = tmpPtr;
112 /* =============================================================================
114 * -- Returns FALSE on failure
115 * =============================================================================
117 public boolean heap_insert(Object dataPtr) {
118 if ((size + 1) >= capacity) {
119 int 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];
125 this.elements = newElements;
129 elements[size] = dataPtr;
136 /* =============================================================================
138 * =============================================================================
140 public void heapify(int startIndex) {
141 int index = startIndex;
144 int leftIndex = LEFT_CHILD(index);
145 int rightIndex = RIGHT_CHILD(index);
148 if ((leftIndex <= size) &&
149 (compare(elements[leftIndex], elements[index]) > 0)) {
150 maxIndex = leftIndex;
155 if ((rightIndex <= size) &&
156 (compare(elements[rightIndex], elements[maxIndex]) > 0)) {
157 maxIndex = rightIndex;
160 if (maxIndex == index) {
163 Object tmpPtr = elements[index];
164 elements[index] = elements[maxIndex];
165 elements[maxIndex] = tmpPtr;
172 /* =============================================================================
174 * -- Returns NULL if empty
175 * =============================================================================
177 Object heap_remove() {
182 Object dataPtr = elements[1];
183 elements[1] = elements[size];
190 /* =============================================================================
192 * =============================================================================
194 boolean heap_isValid() {
195 for (int i = 1; i < size; i++) {
196 if (compare(elements[i+1], elements[PARENT(i+1)]) > 0) {
204 private static int compare(Object aPtr, Object bPtr) {
205 element aElementPtr = (element)aPtr;
206 element bElementPtr = (element)bPtr;
208 if (aElementPtr.encroachedEdgePtr!=null) {
209 if (bElementPtr.encroachedEdgePtr!=null) {
210 return 0; /* do not care */
216 if (bElementPtr.encroachedEdgePtr!=null) {
221 public void printHeap() {
222 System.out.println("[");
223 for (int i = 0; i < size; i++) {
224 System.out.print(elements[i+1]+" ");
226 System.out.println("]");