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