1 files changed, 226 insertions, 0 deletions
diff --git a/src/javax/media/j3d/WakeupOnElapsedTimeHeap.java b/src/javax/media/j3d/WakeupOnElapsedTimeHeap.java
new file mode 100644
index 0000000..d14a148
--- /dev/null
+++ b/src/javax/media/j3d/WakeupOnElapsedTimeHeap.java
@@ -0,0 +1,226 @@
+/*
+ * Copyright 1999-2008 Sun Microsystems, Inc.  All Rights Reserved.
+ * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
+ *
+ * This code is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License version 2 only, as
+ * published by the Free Software Foundation.  Sun designates this
+ * particular file as subject to the "Classpath" exception as provided
+ * by Sun in the LICENSE file that accompanied this code.
+ *
+ * This code is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+ * version 2 for more details (a copy is included in the LICENSE file that
+ * accompanied this code).
+ *
+ * You should have received a copy of the GNU General Public License version
+ * 2 along with this work; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
+ *
+ * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
+ * CA 95054 USA or visit www.sun.com if you need additional information or
+ * have any questions.
+ *
+ */
+
+package javax.media.j3d;
+
+/**
+ * A Binary heap to store WakeupOnElapsedTime. It is arranged so that the
+ * smallest triggeredTime of the wakeup object is put at the top of the heap.
+ * Add/deletion takes O(log n) time.
+ * For better performance we can consider to use Fibonacci Heaps.
+ *
+ */
+class WakeupOnElapsedTimeHeap implements Cloneable {
+
+    // entry 0 is not used so index can be calculated more efficiently
+    WakeupOnElapsedTime data[];
+    int size = 0;
+
+    /**
+     * Construct heap with user-defined capacity
+     */
+    WakeupOnElapsedTimeHeap(int initCapacity) {
+	data = new WakeupOnElapsedTime[initCapacity+1];
+    }
+
+    /**
+     * Construct heap of default capacity 10
+     */
+    WakeupOnElapsedTimeHeap() {
+	this(10);
+    }
+
+    /**
+     * Return size of heap
+     */
+    final int size() {
+	return size;
+    }
+
+    /**
+     * Return true if heap is empty
+     */
+    final boolean isEmpty() {
+	return (size == 0);
+    }
+
+    /**
+     * Get the minimum element from the heap.
+     * User has to make sure that size > 0 before it is called.
+     */
+    final WakeupOnElapsedTime getMin() {
+	return data[1];
+    }
+
+
+    /**
+     * Insert the key into the heap
+     */
+    final void insert(WakeupOnElapsedTime key) {
+	if (data.length == size + 1) {
+	    WakeupOnElapsedTime oldData[] = data;
+	    data = new WakeupOnElapsedTime[oldData.length << 1];
+	    System.arraycopy(oldData, 0, data, 0, oldData.length);
+	}
+
+	int i = ++size;
+
+	int parentIdx = i >> 1;
+	WakeupOnElapsedTime parentKey = data[parentIdx];
+	long time = key.triggeredTime;
+
+	while ((i > 1) && (parentKey.triggeredTime > time)) {
+	    data[i] = parentKey;
+	    i = parentIdx;
+	    parentIdx >>= 1;
+	    parentKey = data[parentIdx];
+	}
+	data[i] = key;
+    }
+
+    /**
+     * Extract wakeup condition belongs to behav from the heap.
+     * Return true if wakeup is found.
+     */
+    final void extract(BehaviorRetained behav) {
+	for (int i=1; i <= size; i++) {
+	    if (data[i].behav == behav) {
+		extract(i);
+	    }
+	}
+    }
+
+    /**
+     * Extract wakeup from the heap.
+     * Return true if wakeup is found.
+     */
+    final boolean extract(WakeupOnElapsedTime wakeup) {
+	for (int i=1; i <= size; i++) {
+	    if (data[i] == wakeup) {
+		extract(i);
+		return true;
+	    }
+	}
+	return false;
+    }
+
+    /**
+     * Extract the minimum value from the heap.
+     * User has to make sure that size > 0 before it is called.
+     */
+    final WakeupOnElapsedTime extractMin() {
+	return extract(1);
+    }
+
+    /**
+     * Extract the ith value from the heap.
+     * User has to make sure that i <= size before it is called.
+     */
+    final WakeupOnElapsedTime extract(int i) {
+	WakeupOnElapsedTime min = data[i];
+	WakeupOnElapsedTime temp;
+	int l, r;
+	int smallest;
+	data[i] = data[size];
+	data[size] = null; // for gc
+	size--;
+
+
+	do {
+	    l = i << 1;
+	    r = l+1;
+
+	    if ((l <= size) &&
+		(data[l].triggeredTime < data[i].triggeredTime)) {
+		smallest = l;
+	    } else {
+		smallest = i;
+	    }
+	    if ((r <= size) &&
+		(data[r].triggeredTime < data[smallest].triggeredTime)) {
+		smallest = r;
+	    }
+	    if (smallest == i) {
+		break;
+	    }
+	    temp = data[smallest];
+	    data[smallest] = data[i];
+	    data[i] = temp;
+	    i = smallest;
+	} while (true);
+
+	return min;
+    }
+
+
+    /***
+     * Trims the capacity of this instance to be the
+     * list's current size.
+     */
+    final void trimToSize() {
+	if (data.length > size+1) {
+	    WakeupOnElapsedTime oldData[] = data;
+	    data = new WakeupOnElapsedTime[size+1];
+	    System.arraycopy(oldData, 0, data, 0, data.length);
+	}
+    }
+
+    /**
+     * Clone this heap
+     */
+    @Override
+    protected final Object clone() {
+	try {
+	    WakeupOnElapsedTimeHeap heap = (WakeupOnElapsedTimeHeap)super.clone();
+	    heap.data =  new WakeupOnElapsedTime[size+1];
+	    System.arraycopy(data, 0, heap.data, 0, size+1);
+	    return heap;
+	} catch (CloneNotSupportedException e) {
+	    // this shouldn't happen, since we are Cloneable
+	    throw new InternalError();
+	}
+
+    }
+
+
+    @Override
+    public String toString() {
+	StringBuffer sb = new StringBuffer("[ ");
+
+	if (size > 0) {
+	    sb.append(data[1]);
+	}
+
+	for (int i=2; i <= size; i++) {
+	    sb.append("," + data[i]);
+	}
+	sb.append(" ]");
+	return sb.toString();
+    }
+
+
+
+}