001: /* Copyright (c) 2001-2005, The HSQL Development Group
002: * All rights reserved.
003: *
004: * Redistribution and use in source and binary forms, with or without
005: * modification, are permitted provided that the following conditions are met:
006: *
007: * Redistributions of source code must retain the above copyright notice, this
008: * list of conditions and the following disclaimer.
009: *
010: * Redistributions in binary form must reproduce the above copyright notice,
011: * this list of conditions and the following disclaimer in the documentation
012: * and/or other materials provided with the distribution.
013: *
014: * Neither the name of the HSQL Development Group nor the names of its
015: * contributors may be used to endorse or promote products derived from this
016: * software without specific prior written permission.
017: *
018: * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
019: * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
020: * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
021: * ARE DISCLAIMED. IN NO EVENT SHALL HSQL DEVELOPMENT GROUP, HSQLDB.ORG,
022: * OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
023: * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
024: * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
025: * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
026: * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
027: * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
028: * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
029: */
030:
031: package org.hsqldb.lib;
032:
033: /**
034: * An HsqlHeap implementation backed by an array of objects and an
035: * {@link ObjectComparator ObjectComparator}. This implementation
036: * is non-blocking, dynamically resizing and thread-safe.
037: *
038: * @author boucherb@users
039: * @version 1.7.2
040: * @since 1.7.2
041: */
042: public class HsqlArrayHeap implements HsqlHeap {
043:
044: // --------------------------------- members -----------------------------------
045: protected ObjectComparator oc;
046: protected int count;
047: protected Object[] heap;
048:
049: // ------------------------------ constructors ---------------------------------
050:
051: /**
052: * Creates a new HsqlArrayHeap with the given initial capacity, using
053: * the specified ObjectComparator to maintain the heap invariant.
054: *
055: * @exception IllegalArgumentException if capacity less or equal to zero
056: * or comparator is null
057: */
058: public HsqlArrayHeap(int capacity, ObjectComparator comparator)
059: throws IllegalArgumentException {
060:
061: if (capacity <= 0) {
062: throw new IllegalArgumentException("" + capacity);
063: }
064:
065: if (comparator == null) {
066: throw new IllegalArgumentException("null comparator");
067: }
068:
069: heap = new Object[capacity];
070: oc = comparator;
071: }
072:
073: // /** Copy constructor (optional) */
074: // public HsqlArrayHeap(HsqlArrayHeap other) {
075: // count = other.count;
076: // oc = other.oc;
077: // heap = new Object[count];
078: // System.arraycopy(other.heap,0, heap, 0, count);
079: // }
080: // -------------------------- interface Implementation -------------------------
081: public synchronized void clear() {
082:
083: for (int i = 0; i < count; ++i) {
084: heap[i] = null;
085: }
086:
087: count = 0;
088: }
089:
090: public synchronized void add(Object o)
091: throws IllegalArgumentException, RuntimeException {
092:
093: int ci; // current index
094: int pi; // parent index
095:
096: if (o == null) {
097: throw new IllegalArgumentException("null element");
098: }
099:
100: if (isFull()) {
101: throw new RuntimeException("full");
102: }
103:
104: if (count >= heap.length) {
105: increaseCapacity();
106: }
107:
108: ci = count;
109:
110: count++;
111:
112: do {
113: if (ci <= 0) {
114: break;
115: }
116:
117: pi = (ci - 1) >> 1;
118:
119: try {
120: if (oc.compare(o, heap[pi]) >= 0) {
121: break;
122: }
123: } catch (Exception e) {
124: throw new IllegalArgumentException(e.toString());
125: }
126:
127: heap[ci] = heap[pi];
128: ci = pi;
129: } while (true);
130:
131: heap[ci] = o;
132: }
133:
134: public synchronized boolean isEmpty() {
135: return count == 0;
136: }
137:
138: public synchronized boolean isFull() {
139:
140: // almost impossible for this to happen
141: return count == Integer.MAX_VALUE;
142: }
143:
144: public synchronized Object peek() {
145: return heap[0];
146: }
147:
148: public synchronized Object remove() {
149:
150: int ci; // current index
151: int li; // left index
152: int ri; // right index
153: int chi; // child index
154: Object co;
155: Object ro;
156:
157: if (count == 0) {
158: return null;
159: }
160:
161: ci = 0;
162: ro = heap[ci];
163:
164: count--;
165:
166: if (count == 0) {
167: heap[0] = null;
168:
169: return ro;
170: }
171:
172: co = heap[count];
173: heap[count] = null;
174:
175: do {
176: li = (ci << 1) + 1;
177:
178: if (li >= count) {
179: break;
180: }
181:
182: ri = (ci << 1) + 2;
183: chi = (ri >= count || oc.compare(heap[li], heap[ri]) < 0) ? li
184: : ri;
185:
186: if (oc.compare(co, heap[chi]) <= 0) {
187: break;
188: }
189:
190: heap[ci] = heap[chi];
191: ci = chi;
192: } while (true);
193:
194: heap[ci] = co;
195:
196: return ro;
197: }
198:
199: public synchronized int size() {
200: return count;
201: }
202:
203: // ------------- standard object and collection methods (optional) -------------
204: // public synchronized Object clone() throws CloneNotSupportedException {
205: // return new HsqlArrayHeap(this);
206: // }
207: //
208: // public synchronized java.util.Enumeration elements() {
209: //
210: // Object[] elements;
211: //
212: // elements = new Object[count];
213: //
214: // System.arraycopy(heap, 0, elements, 0, count);
215: //
216: // return new HsqlEnumeration(elements);
217: // }
218: //
219: // public synchronized boolean equals(Object o) {
220: //
221: // HsqlArrayHeap other;
222: // HsqlArrayHeap thiscopy;
223: // HsqlArrayHeap othercopy;
224: //
225: // if (this == o) {
226: // return true;
227: // }
228: //
229: // if (!(o instanceof HsqlArrayHeap)) {
230: // return false;
231: // }
232: //
233: // other = (HsqlArrayHeap) o;
234: //
235: // if (count != other.size()) {
236: // return false;
237: // }
238: //
239: // // this is a bit "iffy"... non-equal comparators _might_ still
240: // // be _equivalent_ under current element content...
241: //
242: // if (!oc.equals(other.oc)) {
243: // return false;
244: // }
245: //
246: // thiscopy = new HsqlArrayHeap(this);
247: // othercopy = new HsqlArrayHeap(other);
248: //
249: // while(!thiscopy.isEmpty()) {
250: // if (!thiscopy.remove().equals(othercopy.remove())) {
251: // return false;
252: // }
253: // }
254: //
255: // return true;
256: // }
257: //
258: // public synchronized Object[] toArray(Object a[]) {
259: //
260: // if (a == null) {
261: // a = new Object[count];
262: // } else if ( a.length < count) {
263: // a = (Object[]) java.lang.reflect.Array.newInstance(
264: // a.getClass().getComponentType(), count);
265: // }
266: //
267: // System.arraycopy(heap, 0, a, 0, count);
268: //
269: // for (int i = count; i < a.length; i++) {
270: // a[i] = null;
271: // }
272: //
273: // return a;
274: // }
275: //
276: public synchronized String toString() {
277:
278: StringBuffer sb = new StringBuffer();
279:
280: sb.append(super .toString());
281: sb.append(" : size=");
282: sb.append(count);
283: sb.append(' ');
284: sb.append('[');
285:
286: for (int i = 0; i < count; i++) {
287: sb.append(heap[i]);
288:
289: if (i + 1 < count) {
290: sb.append(',');
291: sb.append(' ');
292: }
293: }
294:
295: sb.append(']');
296:
297: return sb.toString();
298: }
299:
300: //
301: // public void trim() {
302: //
303: // Object[] oldheap;
304: //
305: // oldheap = heap;
306: //
307: // heap = new Object[count == 0 ? 16 : count];
308: //
309: // System.arraycopy(oldheap, 0, heap, 0, count);
310: // }
311: // -------------------- internal implementation methods ------------------------
312: private void increaseCapacity() {
313:
314: Object[] oldheap;
315:
316: // no handling of boundary conditions.
317: // In the highly unlikely event of a rollover,
318: // in theory, an exception will be thrown (negative array index in
319: // array allocation?)
320: oldheap = heap;
321:
322: // as per java collections, v.s. JDK 1.1 java util.
323: heap = new Object[3 * heap.length / 2 + 1];
324:
325: System.arraycopy(oldheap, 0, heap, 0, count);
326: }
327:
328: // ------------------------------- tests ---------------------------------------
329: // public static void main(String[] args) {
330: //
331: // ObjectComparator oc = new ObjectComparator() {
332: //
333: // public int compare(Object a, Object b) {
334: //
335: // if (a == b) {
336: // return 0;
337: // }
338: //
339: // // null==null and smaller than any value
340: // if (a == null) {
341: // if (b == null) {
342: // return 0;
343: // }
344: //
345: // return -1;
346: // }
347: //
348: // if (b == null) {
349: // return 1;
350: // }
351: //
352: // return ((Integer) a).intValue() - ((Integer) b).intValue();
353: // }
354: // };
355: // HsqlHeap ah = new HsqlArrayHeap(6, oc);
356: //
357: // System.out.println("isEmpty() : " + ah.isEmpty());
358: //
359: // int[] ai = new int[] {
360: // 3, 99, 7, 9, -42, 2, 1, 23, -7
361: // };
362: // int least = Integer.MIN_VALUE;
363: //
364: // for (int i = 0; i < ai.length; i++) {
365: // System.out.println("add() : new Integer(" + ai[i] + ")");
366: // ah.add(new Integer(ai[i]));
367: // System.out.println("size() : " + ah.size());
368: // }
369: //
370: // while (ah.size() > 0) {
371: // int current = ((Integer) ah.remove()).intValue();
372: //
373: // if (current < least) {
374: // throw new RuntimeException("bad heap invariant");
375: // }
376: //
377: // least = current;
378: //
379: // System.out.println("remove() : " + current);
380: // System.out.println("size() : " + ah.size());
381: // }
382: //
383: // System.out.println("peak() : " + ah.peek());
384: // System.out.println("isEmpty() : " + ah.isEmpty());
385: // System.out.println("remove() : " + ah.remove());
386: // System.out.println("size() : " + ah.size());
387: // System.out.println("isEmpty() : " + ah.isEmpty());
388: // }
389: }
|