001: /*
002: * $RCSfile: WakeupIndexedList.java,v $
003: *
004: * Copyright 2001-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.7 $
028: * $Date: 2008/02/28 20:17:33 $
029: * $State: Exp $
030: */
031:
032: package javax.media.j3d;
033:
034: /**
035: * A strongly type unorder indexed array list.
036: * All operations remove(WakeupCondition), add(WakeupCondition),
037: * contains(WakeupCondition) etc. take O(1) time.
038: * The class is designed to optimize speed. So many reductance
039: * procedures call and range check as found in ArrayList are
040: * removed.
041: *
042: * <p>
043: * Use the following code to iterate through an array.
044: *
045: * <pre>
046: * WakeupIndexedList list = new WakeupIndexedList(YourClass.class);
047: * // add element here
048: *
049: * YourClass[] arr = (YourClass []) list.toArray();
050: * int size = list.arraySize();
051: * for (int i=0; i < size; i++) {
052: * YourClass obj = arr[i];
053: * ....
054: * }
055: * </pre>
056: *
057: * <p>
058: * Note:
059: * <ul>
060: * 1) The array return is a copied of internal array.<br>
061: * 2) Don't use arr.length , use list.arraySize();<br>
062: * 3) No need to do casting for individual element as in
063: * ArrayList.<br>
064: * 4) WakeupIndexedList is thread safe.<br>
065: * 5) Object implement this interface MUST initialize the index
066: * to -1.<br>
067: * </ul>
068: *
069: * <p>
070: * Limitation:
071: * <ul>
072: * - Same element can't add in two different WakeupIndexedList<br>
073: * - Order of WakeupCondition is not important<br>
074: * - Can't modify the clone() copy.<br>
075: * - Object can't be null<br>
076: * </ul>
077: */
078:
079: class WakeupIndexedList implements Cloneable, java.io.Serializable {
080:
081: // XXXX: set to false when release
082: final static boolean debug = false;
083:
084: /**
085: * The array buffer into which the elements of the ArrayList are stored.
086: * The capacity of the ArrayList is the length of this array buffer.
087: *
088: * It is non-private to enable compiler do inlining for get(),
089: * set(), remove() when -O flag turn on.
090: */
091: transient WakeupCondition elementData[];
092:
093: /**
094: * Clone copy of elementData return by toArray(true);
095: */
096: transient Object cloneData[];
097: // size of the above clone objec.
098: transient int cloneSize;
099:
100: transient boolean isDirty = true;
101:
102: /**
103: * Component Type of individual array element entry
104: */
105: Class componentType;
106:
107: /**
108: * The size of the ArrayList (the number of elements it contains).
109: *
110: * We make it non-private to enable compiler do inlining for
111: * getSize() when -O flag turn on.
112: */
113: int size;
114:
115: int listType;
116:
117: // Current VirtualUniverse using this structure
118: VirtualUniverse univ;
119:
120: /**
121: * Constructs an empty list with the specified initial capacity.
122: * and the class data Type
123: *
124: * @param initialCapacity the initial capacity of the list.
125: * @param componentType class type of element in the list.
126: */
127: WakeupIndexedList(int initialCapacity, Class componentType,
128: int listType, VirtualUniverse univ) {
129: this .componentType = componentType;
130: this .elementData = (WakeupCondition[]) java.lang.reflect.Array
131: .newInstance(componentType, initialCapacity);
132: this .listType = listType;
133: this .univ = univ;
134: }
135:
136: /**
137: * Constructs an empty list.
138: * @param componentType class type of element in the list.
139: */
140: WakeupIndexedList(Class componentType, int listType,
141: VirtualUniverse univ) {
142: this (10, componentType, listType, univ);
143: }
144:
145: /**
146: * Constructs an empty list with the specified initial capacity.
147: *
148: * @param initialCapacity the initial capacity of the list.
149: */
150: WakeupIndexedList(int initialCapacity, int listType,
151: VirtualUniverse univ) {
152: this (initialCapacity, WakeupCondition.class, listType, univ);
153: }
154:
155: /**
156: * Constructs an empty list.
157: * componentType default to Object.
158: */
159: WakeupIndexedList(int listType, VirtualUniverse univ) {
160: this (10, WakeupCondition.class, listType, univ);
161: }
162:
163: /**
164: * Initialize all indexes to -1
165: */
166: final static void init(WakeupCondition obj, int len) {
167: obj.listIdx = new int[2][len];
168:
169: for (int i = 0; i < len; i++) {
170: obj.listIdx[0][i] = -1;
171: obj.listIdx[1][i] = -1;
172: }
173: }
174:
175: /**
176: * Returns the number of elements in this list.
177: *
178: * @return the number of elements in this list.
179: */
180: final int size() {
181: return size;
182: }
183:
184: /**
185: * Returns the size of entry use in toArray() number of elements
186: * in this list.
187: *
188: * @return the number of elements in this list.
189: */
190: final int arraySize() {
191: return cloneSize;
192: }
193:
194: /**
195: * Tests if this list has no elements.
196: *
197: * @return <tt>true</tt> if this list has no elements;
198: * <tt>false</tt> otherwise.
199: */
200: final boolean isEmpty() {
201: return size == 0;
202: }
203:
204: /**
205: * Returns <tt>true</tt> if this list contains the specified element.
206: *
207: * @param o element whose presence in this List is to be tested.
208: */
209: synchronized final boolean contains(WakeupCondition o) {
210: return (o.listIdx[o.behav.getIdxUsed(univ)][listType] >= 0);
211: }
212:
213: /**
214: * Searches for the last occurence of the given argument, testing
215: * for equality using the <tt>equals</tt> method.
216: *
217: * @param o an object.
218: * @return the index of the first occurrence of the argument in this
219: * list; returns <tt>-1</tt> if the object is not found.
220: * @see Object#equals(Object)
221: */
222: synchronized final int indexOf(WakeupCondition o) {
223: return o.listIdx[o.behav.getIdxUsed(univ)][listType];
224: }
225:
226: /**
227: * Returns a shallow copy of this <tt>ArrayList</tt> instance. (The
228: * elements themselves are not copied.)
229: *
230: * @return a clone of this <tt>ArrayList</tt> instance.
231: */
232: synchronized protected final Object clone() {
233: try {
234: WakeupIndexedList v = (WakeupIndexedList) super .clone();
235: v.elementData = (WakeupCondition[]) java.lang.reflect.Array
236: .newInstance(componentType, size);
237: System.arraycopy(elementData, 0, v.elementData, 0, size);
238: isDirty = true; // can't use the old cloneData reference
239: return v;
240: } catch (CloneNotSupportedException e) {
241: // this shouldn't happen, since we are Cloneable
242: throw new InternalError();
243: }
244: }
245:
246: /**
247: * Returns an array containing all of the elements in this list.
248: * The size of the array may longer than the actual size. Use
249: * arraySize() to retrieve the size.
250: * The array return is a copied of internal array. if copy
251: * is true.
252: *
253: * @return an array containing all of the elements in this list
254: */
255: synchronized final Object[] toArray(boolean copy) {
256: if (copy) {
257: if (isDirty) {
258: if ((cloneData == null) || cloneData.length < size) {
259: cloneData = (Object[]) java.lang.reflect.Array
260: .newInstance(componentType, size);
261: }
262: System.arraycopy(elementData, 0, cloneData, 0, size);
263: cloneSize = size;
264: isDirty = false;
265: }
266: return cloneData;
267: } else {
268: cloneSize = size;
269: return elementData;
270: }
271:
272: }
273:
274: /**
275: * Returns an array containing all of the elements in this list.
276: * The size of the array may longer than the actual size. Use
277: * arraySize() to retrieve the size.
278: * The array return is a copied of internal array. So another
279: * thread can continue add/delete the current list. However,
280: * it should be noticed that two call to toArray() may return
281: * the same copy.
282: *
283: * @return an array containing all of the elements in this list
284: */
285: synchronized final Object[] toArray() {
286: return toArray(true);
287: }
288:
289: /**
290: * Returns an array containing elements starting from startElement
291: * all of the elements in this list. A new array of exact size
292: * is always allocated.
293: *
294: * @param startElement starting element to copy
295: *
296: * @return an array containing elements starting from
297: * startElement, null if element not found.
298: *
299: */
300: synchronized final Object[] toArray(WakeupCondition startElement) {
301: int idx = indexOf(startElement);
302: if (idx < 0) {
303: return (Object[]) java.lang.reflect.Array.newInstance(
304: componentType, 0);
305: }
306:
307: int s = size - idx;
308: Object data[] = (Object[]) java.lang.reflect.Array.newInstance(
309: componentType, s);
310: System.arraycopy(elementData, idx, data, 0, s);
311: return data;
312: }
313:
314: /**
315: * Trims the capacity of this <tt>ArrayList</tt> instance to be the
316: * list's current size. An application can use this operation to minimize
317: * the storage of an <tt>ArrayList</tt> instance.
318: */
319: synchronized final void trimToSize() {
320: if (elementData.length > size) {
321: Object oldData[] = elementData;
322: elementData = (WakeupCondition[]) java.lang.reflect.Array
323: .newInstance(componentType, size);
324: System.arraycopy(oldData, 0, elementData, 0, size);
325: }
326: }
327:
328: // Positional Access Operations
329:
330: /**
331: * Returns the element at the specified position in this list.
332: *
333: * @param index index of element to return.
334: * @return the element at the specified position in this list.
335: * @throws IndexOutOfBoundsException if index is out of range <tt>(index
336: * < 0 || index >= size())</tt>.
337: */
338: synchronized final Object get(int index) {
339: return elementData[index];
340: }
341:
342: /**
343: * Replaces the element at the specified position in this list with
344: * the specified element.
345: *
346: * @param index index of element to replace.
347: * @param o element to be stored at the specified position.
348: * @return the element previously at the specified position.
349: * @throws IndexOutOfBoundsException if index out of range
350: * <tt>(index < 0 || index >= size())</tt>.
351: */
352: synchronized final void set(int index, WakeupCondition o) {
353:
354: WakeupCondition oldElm = elementData[index];
355: if (oldElm != null) {
356: oldElm.listIdx[oldElm.behav.getIdxUsed(univ)][listType] = -1;
357: }
358: elementData[index] = o;
359:
360: int univIdx = o.behav.getIdxUsed(univ);
361:
362: if (debug) {
363: if (o.listIdx[univIdx][listType] != -1) {
364: System.err
365: .println("Illegal use of UnorderIndexedList idx in set "
366: + o.listIdx[univIdx][listType]);
367: Thread.dumpStack();
368: }
369: }
370:
371: o.listIdx[univIdx][listType] = index;
372: isDirty = true;
373: }
374:
375: /**
376: * Appends the specified element to the end of this list.
377: * It is the user responsible to ensure that the element add is of
378: * the same type as array componentType.
379: *
380: * @param o element to be appended to this list.
381: */
382: synchronized final void add(WakeupCondition o) {
383: if (elementData.length == size) {
384: WakeupCondition oldData[] = elementData;
385: elementData = (WakeupCondition[]) java.lang.reflect.Array
386: .newInstance(componentType, (size << 1));
387: System.arraycopy(oldData, 0, elementData, 0, size);
388:
389: }
390:
391: int univIdx = o.behav.getIdxUsed(univ);
392: // System.err.println(this + " add " + o + " univ " + univIdx);
393: if (debug) {
394: int idx = o.listIdx[univIdx][listType];
395: if (idx >= 0) {
396: if (elementData[idx] != o) {
397: System.err
398: .println("Illegal use of UnorderIndexedList idx in add "
399: + idx);
400: Thread.dumpStack();
401: }
402: }
403: }
404:
405: int idx = size++;
406: elementData[idx] = o;
407: o.listIdx[univIdx][listType] = idx;
408: isDirty = true;
409: }
410:
411: /**
412: * Removes the element at the specified position in this list.
413: * Replace the removed element by the last one.
414: *
415: * @param index the index of the element to removed.
416: * @throws IndexOutOfBoundsException if index out of range <tt>(index
417: * < 0 || index >= size())</tt>.
418: */
419: synchronized final void remove(int index) {
420: WakeupCondition elm = elementData[index];
421: int univIdx = elm.behav.getIdxUsed(univ);
422:
423: if (debug) {
424: if (elm.listIdx[univIdx][listType] != index) {
425: System.err
426: .println("Inconsistent idx in remove, expect "
427: + index + " actual "
428: + elm.listIdx[univIdx][listType]);
429: Thread.dumpStack();
430: }
431: }
432:
433: elm.listIdx[univIdx][listType] = -1;
434: size--;
435: if (index != size) {
436: elm = elementData[size];
437: elm.listIdx[univIdx][listType] = index;
438: elementData[index] = elm;
439: }
440: elementData[size] = null;
441: isDirty = true;
442: /*
443: if ((cloneData != null) && (index < cloneData.length)) {
444: cloneData[index] = null; // for gc
445: }
446: */
447: }
448:
449: /**
450: * Removes the element at the last position in this list.
451: * @return The element remove
452: * @throws IndexOutOfBoundsException if array is empty
453: */
454: synchronized final Object removeLastElement() {
455: WakeupCondition elm = elementData[--size];
456: elementData[size] = null;
457: elm.listIdx[elm.behav.getIdxUsed(univ)][listType] = -1;
458: isDirty = true;
459: /*
460: if ((cloneData != null) && (size < cloneData.length)) {
461: cloneData[size] = null; // for gc
462: }
463: */
464: return elm;
465: }
466:
467: /**
468: * Removes the specified element in this list.
469: * Replace the removed element by the last one.
470: *
471: * @param o the element to removed.
472: * @return true if object remove
473: * @throws IndexOutOfBoundsException if index out of range <tt>(index
474: * < 0 || index >= size())</tt>.
475: */
476: synchronized final boolean remove(WakeupCondition o) {
477: int univIdx = o.behav.getIdxUsed(univ);
478: int idx = o.listIdx[univIdx][listType];
479:
480: // System.err.println(this + " remove " + o + " univ " + univIdx);
481:
482: if (idx >= 0) {
483: // Object in the container
484: if (debug) {
485: if (o != elementData[idx]) {
486: System.err
487: .println(" Illegal use of UnorderIndexedList in remove expect "
488: + o
489: + " actual "
490: + elementData[idx]
491: + " idx = " + idx);
492: Thread.dumpStack();
493: }
494: }
495: size--;
496: if (idx != size) {
497: WakeupCondition elm = elementData[size];
498: elementData[idx] = elm;
499: elm.listIdx[elm.behav.getIdxUsed(univ)][listType] = idx;
500: }
501: elementData[size] = null;
502: o.listIdx[univIdx][listType] = -1;
503: isDirty = true;
504: return true;
505: }
506: return false;
507: }
508:
509: /**
510: * Removes all of the elements from this list. The list will
511: * be empty after this call returns.
512: */
513: synchronized final void clear() {
514: WakeupCondition o;
515:
516: for (int i = size - 1; i >= 0; i--) {
517: o = elementData[i];
518: o.listIdx[o.behav.getIdxUsed(univ)][listType] = -1;
519: elementData[i] = null; // Let gc do its work
520: }
521:
522: size = 0;
523: isDirty = true;
524: }
525:
526: synchronized final void clearMirror() {
527: if (cloneData != null) {
528: for (int i = cloneData.length - 1; i >= 0; i--) {
529: // don't set index to -1 since the original
530: // copy is using this.
531: cloneData[i] = null; // Let gc do its work
532: }
533: }
534: cloneSize = 0;
535: isDirty = true;
536: }
537:
538: final Class getComponentType() {
539: return componentType;
540: }
541:
542: synchronized public String toString() {
543: StringBuffer sb = new StringBuffer(hashCode() + " Size = "
544: + size + "[");
545: int len = size - 1;
546: Object obj;
547:
548: for (int i = 0; i < size; i++) {
549: obj = elementData[i];
550: if (obj != null) {
551: sb.append(elementData[i].toString());
552: } else {
553: sb.append("NULL");
554: }
555: if (i != len) {
556: sb.append(", ");
557: }
558: }
559: sb.append("]");
560: return sb.toString();
561: }
562:
563: /**
564: * Save the state of the <tt>ArrayList</tt> instance to a stream (that
565: * is, serialize it).
566: *
567: * @serialData The length of the array backing the <tt>ArrayList</tt>
568: * instance is emitted (int), followed by all of its elements
569: * (each an <tt>Object</tt>) in the proper order.
570: */
571: private synchronized void writeObject(java.io.ObjectOutputStream s)
572: throws java.io.IOException {
573: // Write out element count, and any hidden stuff
574: s.defaultWriteObject();
575:
576: // Write out array length
577: s.writeInt(elementData.length);
578:
579: // Write out all elements in the proper order.
580: for (int i = 0; i < size; i++)
581: s.writeObject(elementData[i]);
582:
583: }
584:
585: /**
586: * Reconstitute the <tt>ArrayList</tt> instance from a stream (that is,
587: * deserialize it).
588: */
589: private synchronized void readObject(java.io.ObjectInputStream s)
590: throws java.io.IOException, ClassNotFoundException {
591: // Read in size, and any hidden stuff
592: s.defaultReadObject();
593:
594: // Read in array length and allocate array
595: int arrayLength = s.readInt();
596: elementData = (WakeupCondition[]) java.lang.reflect.Array
597: .newInstance(componentType, arrayLength);
598:
599: // Read in all elements in the proper order.
600: for (int i = 0; i < size; i++)
601: elementData[i] = (WakeupCondition) s.readObject();
602: }
603: }
|