|
1
30
31
32 package org.hsqldb.lib;
33
34
43 public class HsqlArrayHeap implements HsqlHeap {
44
45 protected ObjectComparator oc;
47 protected int count;
48 protected Object  [] heap;
49
50
52
59 public HsqlArrayHeap(int capacity,
60 ObjectComparator comparator)
61 throws IllegalArgumentException {
62
63 if (capacity <= 0) {
64 throw new IllegalArgumentException ("" + capacity);
65 }
66
67 if (comparator == null) {
68 throw new IllegalArgumentException ("null comparator");
69 }
70
71 heap = new Object [capacity];
72 oc = comparator;
73 }
74
75 public synchronized void clear() {
84
85 for (int i = 0; i < count; ++i) {
86 heap[i] = null;
87 }
88
89 count = 0;
90 }
91
92 public synchronized void add(Object o)
93 throws IllegalArgumentException , RuntimeException {
94
95 int ci; int pi;
98 if (o == null) {
99 throw new IllegalArgumentException ("null element");
100 }
101
102 if (isFull()) {
103 throw new RuntimeException ("full");
104 }
105
106 if (count >= heap.length) {
107 increaseCapacity();
108 }
109
110 ci = count;
111
112 count++;
113
114 do {
115 if (ci <= 0) {
116 break;
117 }
118
119 pi = (ci - 1) >> 1;
120
121 try {
122 if (oc.compare(o, heap[pi]) >= 0) {
123 break;
124 }
125 } catch (Exception e) {
126 throw new IllegalArgumentException (e.toString());
127 }
128
129 heap[ci] = heap[pi];
130 ci = pi;
131 } while (true);
132
133 heap[ci] = o;
134 }
135
136 public synchronized boolean isEmpty() {
137 return count == 0;
138 }
139
140 public synchronized boolean isFull() {
141
142 return count == Integer.MAX_VALUE;
144 }
145
146 public synchronized Object peek() {
147 return heap[0];
148 }
149
150 public synchronized Object remove() {
151
152 int ci; int li; int ri; int chi; Object co;
157 Object ro;
158
159 if (count == 0) {
160 return null;
161 }
162
163 ci = 0;
164 ro = heap[ci];
165
166 count--;
167
168 if (count == 0) {
169 heap[0] = null;
170
171 return ro;
172 }
173
174 co = heap[count];
175 heap[count] = null;
176
177 do {
178 li = (ci << 1) + 1;
179
180 if (li >= count) {
181 break;
182 }
183
184 ri = (ci << 1) + 2;
185 chi = (ri >= count || oc.compare(heap[li], heap[ri]) < 0) ? li
186 : ri;
187
188 if (oc.compare(co, heap[chi]) <= 0) {
189 break;
190 }
191
192 heap[ci] = heap[chi];
193 ci = chi;
194 } while (true);
195
196 heap[ci] = co;
197
198 return ro;
199 }
200
201 public synchronized int size() {
202 return count;
203 }
204
205 public synchronized String toString() {
279
280 StringBuffer sb = new StringBuffer ();
281
282 sb.append(super.toString());
283 sb.append(" : size=");
284 sb.append(count);
285 sb.append(' ');
286 sb.append('[');
287
288 for (int i = 0; i < count; i++) {
289 sb.append(heap[i]);
290
291 if (i + 1 < count) {
292 sb.append(',');
293 sb.append(' ');
294 }
295 }
296
297 sb.append(']');
298
299 return sb.toString();
300 }
301
302 private void increaseCapacity() {
315
316 Object [] oldheap;
317
318 oldheap = heap;
323
324 heap = new Object [3 * heap.length / 2 + 1];
326
327 System.arraycopy(oldheap, 0, heap, 0, count);
328 }
329
330 }
392 |
Popular Tags |
Java API By Example, From Geeks To Geeks.