001: /*
002: * $RCSfile: WakeupOnElapsedTimeHeap.java,v $
003: *
004: * Copyright 1999-2008 Sun Microsystems, Inc. All Rights Reserved.
005: * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
006: *
007: * This code is free software; you can redistribute it and/or modify it
008: * under the terms of the GNU General Public License version 2 only, as
009: * published by the Free Software Foundation. Sun designates this
010: * particular file as subject to the "Classpath" exception as provided
011: * by Sun in the LICENSE file that accompanied this code.
012: *
013: * This code is distributed in the hope that it will be useful, but WITHOUT
014: * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
015: * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
016: * version 2 for more details (a copy is included in the LICENSE file that
017: * accompanied this code).
018: *
019: * You should have received a copy of the GNU General Public License version
020: * 2 along with this work; if not, write to the Free Software Foundation,
021: * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
022: *
023: * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
024: * CA 95054 USA or visit www.sun.com if you need additional information or
025: * have any questions.
026: *
027: * $Revision: 1.5 $
028: * $Date: 2008/02/28 20:17:33 $
029: * $State: Exp $
030: */
031:
032: package javax.media.j3d;
033:
034: /**
035: * A Binary heap to store WakeupOnElapsedTime. It is arranged so that the
036: * smallest triggeredTime of the wakeup object is put at the top of the heap.
037: * Add/deletion takes O(log n) time.
038: * For better performance we can consider to use Fibonacci Heaps.
039: *
040: */
041: class WakeupOnElapsedTimeHeap implements Cloneable {
042:
043: // entry 0 is not used so index can be calculated more efficiently
044: WakeupOnElapsedTime data[];
045: int size = 0;
046:
047: /**
048: * Construct heap with user-defined capacity
049: */
050: WakeupOnElapsedTimeHeap(int initCapacity) {
051: data = new WakeupOnElapsedTime[initCapacity + 1];
052: }
053:
054: /**
055: * Construct heap of default capacity 10
056: */
057: WakeupOnElapsedTimeHeap() {
058: this (10);
059: }
060:
061: /**
062: * Return size of heap
063: */
064: final int size() {
065: return size;
066: }
067:
068: /**
069: * Return true if heap is empty
070: */
071: final boolean isEmpty() {
072: return (size == 0);
073: }
074:
075: /**
076: * Get the minimum element from the heap.
077: * User has to make sure that size > 0 before it is called.
078: */
079: final WakeupOnElapsedTime getMin() {
080: return data[1];
081: }
082:
083: /**
084: * Insert the key into the heap
085: */
086: final void insert(WakeupOnElapsedTime key) {
087: if (data.length == size + 1) {
088: WakeupOnElapsedTime oldData[] = data;
089: data = new WakeupOnElapsedTime[oldData.length << 1];
090: System.arraycopy(oldData, 0, data, 0, oldData.length);
091: }
092:
093: int i = ++size;
094:
095: int parentIdx = i >> 1;
096: WakeupOnElapsedTime parentKey = data[parentIdx];
097: long time = key.triggeredTime;
098:
099: while ((i > 1) && (parentKey.triggeredTime > time)) {
100: data[i] = parentKey;
101: i = parentIdx;
102: parentIdx >>= 1;
103: parentKey = data[parentIdx];
104: }
105: data[i] = key;
106: }
107:
108: /**
109: * Extract wakeup condition belongs to behav from the heap.
110: * Return true if wakeup is found.
111: */
112: final void extract(BehaviorRetained behav) {
113: for (int i = 1; i <= size; i++) {
114: if (data[i].behav == behav) {
115: extract(i);
116: }
117: }
118: }
119:
120: /**
121: * Extract wakeup from the heap.
122: * Return true if wakeup is found.
123: */
124: final boolean extract(WakeupOnElapsedTime wakeup) {
125: for (int i = 1; i <= size; i++) {
126: if (data[i] == wakeup) {
127: extract(i);
128: return true;
129: }
130: }
131: return false;
132: }
133:
134: /**
135: * Extract the minimum value from the heap.
136: * User has to make sure that size > 0 before it is called.
137: */
138: final WakeupOnElapsedTime extractMin() {
139: return extract(1);
140: }
141:
142: /**
143: * Extract the ith value from the heap.
144: * User has to make sure that i <= size before it is called.
145: */
146: final WakeupOnElapsedTime extract(int i) {
147: WakeupOnElapsedTime min = data[i];
148: WakeupOnElapsedTime temp;
149: int l, r;
150: int smallest;
151: data[i] = data[size];
152: data[size] = null; // for gc
153: size--;
154:
155: do {
156: l = i << 1;
157: r = l + 1;
158:
159: if ((l <= size)
160: && (data[l].triggeredTime < data[i].triggeredTime)) {
161: smallest = l;
162: } else {
163: smallest = i;
164: }
165: if ((r <= size)
166: && (data[r].triggeredTime < data[smallest].triggeredTime)) {
167: smallest = r;
168: }
169: if (smallest == i) {
170: break;
171: }
172: temp = data[smallest];
173: data[smallest] = data[i];
174: data[i] = temp;
175: i = smallest;
176: } while (true);
177:
178: return min;
179: }
180:
181: /***
182: * Trims the capacity of this instance to be the
183: * list's current size.
184: */
185: final void trimToSize() {
186: if (data.length > size + 1) {
187: WakeupOnElapsedTime oldData[] = data;
188: data = new WakeupOnElapsedTime[size + 1];
189: System.arraycopy(oldData, 0, data, 0, data.length);
190: }
191: }
192:
193: /**
194: * Clone this heap
195: */
196: protected final Object clone() {
197: try {
198: WakeupOnElapsedTimeHeap heap = (WakeupOnElapsedTimeHeap) super
199: .clone();
200: heap.data = new WakeupOnElapsedTime[size + 1];
201: System.arraycopy(data, 0, heap.data, 0, size + 1);
202: return heap;
203: } catch (CloneNotSupportedException e) {
204: // this shouldn't happen, since we are Cloneable
205: throw new InternalError();
206: }
207:
208: }
209:
210: public String toString() {
211: StringBuffer sb = new StringBuffer("[ ");
212:
213: if (size > 0) {
214: sb.append(data[1]);
215: }
216:
217: for (int i = 2; i <= size; i++) {
218: sb.append("," + data[i]);
219: }
220: sb.append(" ]");
221: return sb.toString();
222: }
223:
224: }
|