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