001: /*
002: * Javolution - Java(TM) Solution for Real-Time and Embedded Systems
003: * Copyright (C) 2005 - Javolution (http://javolution.org/)
004: * All rights reserved.
005: *
006: * Permission to use, copy, modify, and distribute this software is
007: * freely granted, provided that this notice is preserved.
008: */
009: package javolution.util;
010:
011: import java.io.IOException;
012: import java.util.NoSuchElementException;
013:
014: import j2me.io.ObjectInputStream;
015: import j2me.io.ObjectOutputStream;
016: import j2me.lang.IllegalStateException;
017: import j2me.lang.UnsupportedOperationException;
018: import j2me.util.Collection;
019: import j2me.util.Iterator;
020: import j2me.util.List;
021: import j2me.util.ListIterator;
022: import j2me.util.RandomAccess;
023: import j2mex.realtime.MemoryArea;
024: import javolution.context.ObjectFactory;
025: import javolution.context.PersistentContext;
026: import javolution.lang.MathLib;
027: import javolution.lang.Reusable;
028:
029: /**
030: * <p> This class represents a random access collection with real-time behavior
031: * (smooth capacity increase).</p>
032: * <img src="doc-files/list-add.png"/>
033: *
034: * <p> This class has the following advantages over the widely used
035: * <code>java.util.ArrayList</code>:<ul>
036: * <li> No large array allocation (for large collections multi-dimensional
037: * arrays are employed). The garbage collector is not stressed with
038: * large chunk of memory to allocate (likely to trigger a
039: * full garbage collection due to memory fragmentation).</li>
040: * <li> Support concurrent access/iteration without synchronization if the
041: * collection values are not removed/inserted (Ref.
042: * {@link javolution.util} discussion).</li>
043: * </ul></p>
044: *
045: * <p> Iterations over the {@link FastTable} values are faster when
046: * performed using the {@link #get} method rather than using collection
047: * records or iterators:[code]
048: * for (int i = 0, n = table.size(); i < n; i++) {
049: * table.get(i);
050: * }[/code]</p>
051: *
052: * <p> {@link FastTable} supports {@link #sort sorting} in place (quick sort)
053: * using the {@link FastCollection#getValueComparator() value comparator}
054: * for the table (no object or array allocation when sorting).</p>
055: *
056: * <p> The size of a {@link FastTable} can be {@link #setSize set} directly
057: * and populated concurrently through the {@link #set(int, Object)}
058: * method (e.g. table shared by multiple threads each working on
059: * different index ranges).</p>
060: *
061: * @author <a href="mailto:jean-marie@dautelle.com">Jean-Marie Dautelle</a>
062: * @version 5.2, August 20, 2007
063: */
064: public class FastTable/*<E>*/extends FastCollection/*<E>*/implements
065: List/*<E>*/, Reusable, RandomAccess {
066:
067: /**
068: * Holds the factory for this fast table.
069: */
070: private static final ObjectFactory FACTORY = new ObjectFactory() {
071: public Object create() {
072: return new FastTable();
073: }
074:
075: public void cleanup(Object obj) {
076: ((FastTable) obj).reset();
077: }
078: };
079:
080: // We do a full resize (and copy) only when the capacity is less than C1.
081: // For large collections, multi-dimensional arrays are employed.
082:
083: private static final int B0 = 4; // Initial capacity in bits.
084:
085: private static final int C0 = 1 << B0; // Initial capacity (16)
086:
087: private static final int B1 = 10; // Low array maximum capacity in bits.
088:
089: private static final int C1 = 1 << B1; // Low array maximum capacity (1024).
090:
091: private static final int M1 = C1 - 1; // Mask.
092:
093: // Resizes up to 1024 maximum (16, 32, 64, 128, 256, 512, 1024).
094: private transient Object/*{E}*/[] _low;
095:
096: // For larger capacity use multi-dimensional array.
097: private transient Object/*{E}*/[][] _high;
098:
099: /**
100: * Holds the current capacity.
101: */
102: private transient int _capacity;
103:
104: /**
105: * Holds the current size.
106: */
107: private transient int _size;
108:
109: /**
110: * Holds the value comparator.
111: */
112: private transient FastComparator/*<? super E>*/_valueComparator = FastComparator.DEFAULT;
113:
114: /**
115: * Creates a table of small initial capacity.
116: */
117: public FastTable() {
118: _capacity = C0;
119: _low = (Object/*{E}*/[]) new Object[C0];
120: _high = (Object/*{E}*/[][]) new Object[1][];
121: _high[0] = _low;
122: }
123:
124: /**
125: * Creates a persistent table associated to the specified unique identifier
126: * (convenience method).
127: *
128: * @param id the unique identifier for this map.
129: * @throws IllegalArgumentException if the identifier is not unique.
130: * @see javolution.context.PersistentContext.Reference
131: */
132: public FastTable(String id) {
133: this ();
134: new PersistentContext.Reference(id, this ) {
135: protected void notifyChange() {
136: FastTable.this .clear();
137: FastTable.this .addAll((FastList) this .get());
138: }
139: };
140: }
141:
142: /**
143: * Creates a table of specified initial capacity; unless the table size
144: * reaches the specified capacity, operations on this table will not
145: * allocate memory (no lazy object creation).
146: *
147: * @param capacity the initial capacity.
148: */
149: public FastTable(int capacity) {
150: this ();
151: while (capacity > _capacity) {
152: increaseCapacity();
153: }
154: }
155:
156: /**
157: * Creates a table containing the specified values, in the order they
158: * are returned by the collection's iterator.
159: *
160: * @param values the values to be placed into this table.
161: */
162: public FastTable(Collection/*<? extends E>*/values) {
163: this (values.size());
164: addAll(values);
165: }
166:
167: /**
168: * Returns a new, preallocated or {@link #recycle recycled} table instance
169: * (on the stack when executing in a {@link javolution.context.StackContext
170: * StackContext}).
171: *
172: * @return a new, preallocated or recycled table instance.
173: */
174: public static/*<E>*/FastTable/*<E>*/newInstance() {
175: return (FastTable/*<E>*/) FACTORY.object();
176: }
177:
178: /**
179: * Recycles a table {@link #newInstance() instance} immediately
180: * (on the stack when executing in a {@link javolution.context.StackContext
181: * StackContext}).
182: */
183: public static void recycle(FastTable instance) {
184: FACTORY.recycle(instance);
185: }
186:
187: /**
188: * Sets the size of this table. If the specified size is greater than
189: * the current size then <code>null</code> elements are added; otherwise
190: * the last elements are removed until the desired size is reached.
191: *
192: * @param size the new size.
193: */
194: public void setSize(int size) {
195: while (_size < size) { // Adds null elements.
196: addLast(null);
197: }
198: while (_size > size) { // Removes last elements.
199: removeLast();
200: }
201: }
202:
203: /**
204: * Returns the element at the specified index.
205: *
206: * @param index index of value to return.
207: * @return the value at the specified position in this list.
208: * @throws IndexOutOfBoundsException if <code>(index < 0) ||
209: * (index >= size())</code>
210: */
211: public final Object/*{E}*/get(int index) { // Short to be inlined.
212: if (index >= _size)
213: throw new IndexOutOfBoundsException();
214: return index < C1 ? _low[index]
215: : _high[index >> B1][index & M1];
216: }
217:
218: /**
219: * Replaces the value at the specified position in this table with the
220: * specified value.
221: *
222: * @param index index of value to replace.
223: * @param value value to be stored at the specified position.
224: * @return previous value.
225: * @throws IndexOutOfBoundsException if <code>(index < 0) ||
226: * (index >= size())</code>
227: */
228: public final Object/*{E}*/set(int index, Object/*{E}*/value) {
229: if (index >= _size)
230: throw new IndexOutOfBoundsException();
231: final Object/*{E}*/[] low = _high[index >> B1];
232: final Object/*{E}*/previous = low[index & M1];
233: low[index & M1] = value;
234: return previous;
235: }
236:
237: /**
238: * Appends the specified value to the end of this table.
239: *
240: * @param value the value to be appended to this table.
241: * @return <code>true</code> (as per the general contract of the
242: * <code>Collection.add</code> method).
243: */
244: public final boolean add(Object/*{E}*/value) {
245: if (_size >= _capacity)
246: increaseCapacity();
247: _high[_size >> B1][_size & M1] = value;
248: _size += ONE_VOLATILE; // Prevents compiler reordering.
249: return true;
250: }
251:
252: /**
253: * Returns the first value of this table.
254: *
255: * @return this table first value.
256: * @throws NoSuchElementException if this table is empty.
257: */
258: public final Object/*{E}*/getFirst() {
259: if (_size == 0)
260: throw new NoSuchElementException();
261: return _low[0];
262: }
263:
264: /**
265: * Returns the last value of this table.
266: *
267: * @return this table last value.
268: * @throws NoSuchElementException if this table is empty.
269: */
270: public final Object/*{E}*/getLast() {
271: if (_size == 0)
272: throw new NoSuchElementException();
273: return get(_size - 1);
274: }
275:
276: /**
277: * Appends the specified value to the end of this table <i>(fast)</i>.
278: *
279: * @param value the value to be added.
280: */
281: public final void addLast(Object/*{E}*/value) {
282: add(value);
283: }
284:
285: /**
286: * Removes and returns the last value of this table <i>(fast)</i>.
287: *
288: * @return this table's last value before this call.
289: * @throws NoSuchElementException if this table is empty.
290: */
291: public final Object/*{E}*/removeLast() {
292: if (_size == 0)
293: throw new NoSuchElementException();
294: _size--; // No need for volatile, removal are not thread-safe.
295: final Object/*{E}*/[] low = _high[_size >> B1];
296: final Object/*{E}*/previous = low[_size & M1];
297: low[_size & M1] = null;
298: return previous;
299: }
300:
301: // Overrides.
302: public final void clear() {
303: for (int i = 0; i < _size; i += C1) {
304: final int count = MathLib.min(_size - i, C1);
305: final Object/*{E}*/[] low = _high[i >> B1];
306: System.arraycopy(NULL_BLOCK, 0, low, 0, count);
307: }
308: _size = 0; // No need for volatile, removal are not thread-safe.
309: }
310:
311: private static final Object[] NULL_BLOCK = (Object[]) new Object[C1];
312:
313: // Implements Reusable interface.
314: public void reset() {
315: clear();
316: this .setValueComparator(FastComparator.DEFAULT);
317: }
318:
319: /**
320: * Inserts all of the values in the specified collection into this
321: * table at the specified position. Shifts the value currently at that
322: * position (if any) and any subsequent values to the right
323: * (increases their indices).
324: *
325: * <p>Note: If this method is used concurrent access must be synchronized
326: * (the table is no more thread-safe).</p>
327: *
328: * @param index the index at which to insert first value from the specified
329: * collection.
330: * @param values the values to be inserted into this list.
331: * @return <code>true</code> if this list changed as a result of the call;
332: * <code>false</code> otherwise.
333: * @throws IndexOutOfBoundsException if <code>(index < 0) ||
334: * (index > size())</code>
335: */
336: public final boolean addAll(int index,
337: Collection/*<? extends E>*/values) {
338: if ((index < 0) || (index > _size))
339: throw new IndexOutOfBoundsException("index: " + index);
340: final int shift = values.size();
341: shiftRight(index, shift);
342: Iterator/*<? extends E>*/valuesIterator = values.iterator();
343: for (int i = index, n = index + shift; i < n; i++) {
344: _high[i >> B1][i & M1] = valuesIterator.next();
345: }
346: _size += shift * ONE_VOLATILE; // Increases size last (thread-safe)
347: return shift != 0;
348: }
349:
350: /**
351: * Inserts the specified value at the specified position in this table.
352: * Shifts the value currently at that position
353: * (if any) and any subsequent values to the right (adds one to their
354: * indices).
355: *
356: * <p>Note: If this method is used concurrent access must be synchronized
357: * (the table is no more thread-safe).</p>
358: *
359: * @param index the index at which the specified value is to be inserted.
360: * @param value the value to be inserted.
361: * @throws IndexOutOfBoundsException if <code>(index < 0) ||
362: * (index > size())</code>
363: */
364: public final void add(int index, Object/*{E}*/value) {
365: if ((index < 0) || (index > _size))
366: throw new IndexOutOfBoundsException("index: " + index);
367: shiftRight(index, 1);
368: _high[index >> B1][index & M1] = value;
369: _size += ONE_VOLATILE; // Increases size last (thread-safe).
370: }
371:
372: /**
373: * Removes the value at the specified position from this table.
374: * Shifts any subsequent values to the left (subtracts one
375: * from their indices). Returns the value that was removed from the
376: * table.
377: *
378: * <p>Note: If this method is used concurrent access must be synchronized
379: * (the table is no more thread-safe).</p>
380: *
381: * @param index the index of the value to removed.
382: * @return the value previously at the specified position.
383: * @throws IndexOutOfBoundsException if <code>(index < 0) ||
384: * (index >= size())</code>
385: */
386: public final Object/*{E}*/remove(int index) {
387: final Object/*{E}*/previous = get(index);
388: shiftLeft(index + 1, 1);
389: _size--; // No need for volatile, removal are not thread-safe.
390: _high[_size >> B1][_size & M1] = null; // Deallocates for GC.
391: return previous;
392: }
393:
394: /**
395: * Removes the values between <code>[fromIndex..toIndex[<code> from
396: * this table.
397: *
398: * <p>Note: If this method is used concurrent access must be synchronized
399: * (the table is no more thread-safe).</p>
400: *
401: * @param fromIndex the beginning index, inclusive.
402: * @param toIndex the ending index, exclusive.
403: * @throws IndexOutOfBoundsException if <code>(fromIndex < 0) || (toIndex < 0)
404: * || (fromIndex > toIndex) || (toIndex > this.size())</code>
405: */
406: public final void removeRange(int fromIndex, int toIndex) {
407: if ((fromIndex < 0) || (toIndex < 0) || (fromIndex > toIndex)
408: || (toIndex > _size))
409: throw new IndexOutOfBoundsException();
410: final int shift = toIndex - fromIndex;
411: shiftLeft(fromIndex, shift);
412: _size -= shift; // No need for volatile, removal are not thread-safe.
413: for (int i = _size, n = _size + shift; i < n; i++) {
414: _high[i >> B1][i & M1] = null; // Deallocates for GC.
415: }
416: }
417:
418: /**
419: * Returns the index in this table of the first occurrence of the specified
420: * value, or -1 if this table does not contain this value.
421: *
422: * @param value the value to search for.
423: * @return the index in this table of the first occurrence of the specified
424: * value, or -1 if this table does not contain this value.
425: */
426: public final int indexOf(Object value) {
427: final FastComparator comp = this .getValueComparator();
428: for (int i = 0; i < _size;) {
429: final Object/*{E}*/[] low = _high[i >> B1];
430: final int count = MathLib.min(low.length, _size - i);
431: for (int j = 0; j < count; j++) {
432: if (comp == FastComparator.DEFAULT ? defaultEquals(
433: value, low[j]) : comp.areEqual(value, low[j]))
434: return i + j;
435: }
436: i += count;
437: }
438: return -1;
439: }
440:
441: /**
442: * Returns the index in this table of the last occurrence of the specified
443: * value, or -1 if this table does not contain this value.
444: *
445: * @param value the value to search for.
446: * @return the index in this table of the last occurrence of the specified
447: * value, or -1 if this table does not contain this value.
448: */
449: public final int lastIndexOf(Object value) {
450: final FastComparator comp = this .getValueComparator();
451: for (int i = _size - 1; i >= 0;) {
452: final Object/*{E}*/[] low = _high[i >> B1];
453: final int count = (i & M1) + 1;
454: for (int j = count; --j >= 0;) {
455: if (comp == FastComparator.DEFAULT ? defaultEquals(
456: value, low[j]) : comp.areEqual(value, low[j]))
457: return i + j - count + 1;
458: }
459: i -= count;
460: }
461: return -1;
462: }
463:
464: /**
465: * Returns an iterator over the elements in this list
466: * (allocated on the stack when executed in a
467: * {@link javolution.context.StackContext StackContext}).
468: *
469: * @return an iterator over this list values.
470: */
471: public Iterator/*<E>*/iterator() {
472: return FastTableIterator.valueOf(this , 0, 0, _size);
473: }
474:
475: /**
476: * Returns a list iterator over the elements in this list
477: * (allocated on the stack when executed in a
478: * {@link javolution.context.StackContext StackContext}).
479: *
480: * @return an iterator over this list values.
481: */
482: public ListIterator/*<E>*/listIterator() {
483: return FastTableIterator.valueOf(this , 0, 0, _size);
484: }
485:
486: /**
487: * Returns a list iterator from the specified position
488: * (allocated on the stack when executed in a
489: * {@link javolution.context.StackContext StackContext}).
490: * The list iterator being returned does not support insertion/deletion.
491: *
492: * @param index the index of first value to be returned from the
493: * list iterator (by a call to the <code>next</code> method).
494: * @return a list iterator of the values in this table
495: * starting at the specified position in this list.
496: * @throws IndexOutOfBoundsException if the index is out of range
497: * [code](index < 0 || index > size())[/code]
498: */
499: public ListIterator/*<E>*/listIterator(int index) {
500: if ((index < 0) || (index > _size))
501: throw new IndexOutOfBoundsException();
502: return FastTableIterator.valueOf(this , index, 0, _size);
503: }
504:
505: /**
506: * Returns a view of the portion of this list between the specified
507: * indexes (instance of {@link FastList} allocated from the "stack" when
508: * executing in a {@link javolution.context.StackContext StackContext}).
509: * If the specified indexes are equal, the returned list is empty.
510: * The returned list is backed by this list, so non-structural changes in
511: * the returned list are reflected in this list, and vice-versa.
512: *
513: * This method eliminates the need for explicit range operations (of
514: * the sort that commonly exist for arrays). Any operation that expects
515: * a list can be used as a range operation by passing a subList view
516: * instead of a whole list. For example, the following idiom
517: * removes a range of values from a list: [code]
518: * list.subList(from, to).clear();[/code]
519: * Similar idioms may be constructed for <code>indexOf</code> and
520: * <code>lastIndexOf</code>, and all of the algorithms in the
521: * <code>Collections</code> class can be applied to a subList.
522: *
523: * The semantics of the list returned by this method become undefined if
524: * the backing list (i.e., this list) is <i>structurally modified</i> in
525: * any way other than via the returned list (structural modifications are
526: * those that change the size of this list, or otherwise perturb it in such
527: * a fashion that iterations in progress may yield incorrect results).
528: *
529: * @param fromIndex low endpoint (inclusive) of the subList.
530: * @param toIndex high endpoint (exclusive) of the subList.
531: * @return a view of the specified range within this list.
532: *
533: * @throws IndexOutOfBoundsException if [code](fromIndex < 0 ||
534: * toIndex > size || fromIndex > toIndex)[/code]
535: */
536: public final List/*<E>*/subList(int fromIndex, int toIndex) {
537: if ((fromIndex < 0) || (toIndex > _size)
538: || (fromIndex > toIndex))
539: throw new IndexOutOfBoundsException("fromIndex: "
540: + fromIndex + ", toIndex: " + toIndex
541: + " for list of size: " + _size);
542: return SubTable.valueOf(this , fromIndex, toIndex - fromIndex);
543: }
544:
545: /**
546: * Reduces the capacity of this table to the current size (minimize
547: * storage space).
548: */
549: public final void trimToSize() {
550: while (_capacity - _size > C1) {
551: _capacity -= C1;
552: _high[_capacity >> B1] = null;
553: }
554: }
555:
556: /**
557: * Sorts this table in place (quick sort) using this table
558: * {@link FastCollection#getValueComparator() value comparator}
559: * (smallest first).
560: *
561: * @return <code>this</code>
562: */
563: public final FastTable/*<E>*/sort() {
564: if (_size > 1) {
565: quicksort(0, _size - 1, this .getValueComparator());
566: }
567: return this ;
568: }
569:
570: // From Wikipedia Quick Sort - http://en.wikipedia.org/wiki/Quicksort
571: //
572: private void quicksort(int first, int last, FastComparator cmp) {
573: int pivIndex = 0;
574: if (first < last) {
575: pivIndex = partition(first, last, cmp);
576: quicksort(first, (pivIndex - 1), cmp);
577: quicksort((pivIndex + 1), last, cmp);
578: }
579: }
580:
581: private int partition(int f, int l, FastComparator cmp) {
582: int up, down;
583: Object/*{E}*/piv = get(f);
584: up = f;
585: down = l;
586: do {
587: while (cmp.compare(get(up), piv) <= 0 && up < l) {
588: up++;
589: }
590: while (cmp.compare(get(down), piv) > 0 && down > f) {
591: down--;
592: }
593: if (up < down) { // Swaps.
594: Object/*{E}*/temp = get(up);
595: set(up, get(down));
596: set(down, temp);
597: }
598: } while (down > up);
599: set(f, get(down));
600: set(down, piv);
601: return down;
602: }
603:
604: /**
605: * Sets the comparator to use for value equality or comparison if the
606: * collection is ordered (see {@link #sort()}).
607: *
608: * @param comparator the value comparator.
609: * @return <code>this</code>
610: */
611: public FastTable/*<E>*/setValueComparator(
612: FastComparator/*<? super E>*/comparator) {
613: _valueComparator = comparator;
614: return this ;
615: }
616:
617: // Overrides.
618: public FastComparator/*<? super E>*/getValueComparator() {
619: return _valueComparator;
620: }
621:
622: // Implements FastCollection abstract method.
623: public final int size() {
624: return _size;
625: }
626:
627: // Implements FastCollection abstract method.
628: public final Record head() {
629: return Index.valueOf(-1);
630: }
631:
632: // Implements FastCollection abstract method.
633: public final Record tail() {
634: return Index.valueOf(_size);
635: }
636:
637: // Implements FastCollection abstract method.
638: public final Object/*{E}*/valueOf(Record record) {
639: return get(((Index) record).intValue());
640: }
641:
642: // Implements FastCollection abstract method.
643: public final void delete(Record record) {
644: remove(((Index) record).intValue());
645: }
646:
647: // Overrides to return a list (JDK1.5+).
648: public Collection/*List<E>*/unmodifiable() {
649: return (Collection/*List<E>*/) super .unmodifiable();
650: }
651:
652: // Overrides (optimization).
653: public final boolean contains(Object value) {
654: return indexOf(value) >= 0;
655: }
656:
657: // Requires special handling during de-serialization process.
658: private void readObject(ObjectInputStream stream)
659: throws IOException, ClassNotFoundException {
660: setValueComparator((FastComparator) stream.readObject());
661: final int size = stream.readInt();
662: _capacity = C0;
663: while ((_capacity < _size) && (_capacity < C1)) {
664: _capacity <<= 1; // Increases capacity up to C1 to avoid resizes.
665: }
666: _low = (Object/*{E}*/[]) new Object[_capacity];
667: _high = (Object/*{E}*/[][]) new Object[1][];
668: _high[0] = _low;
669: for (int i = 0; i < size; i++) {
670: addLast((Object/*{E}*/) stream.readObject());
671: }
672: }
673:
674: // Requires special handling during serialization process.
675: private void writeObject(ObjectOutputStream stream)
676: throws IOException {
677: stream.writeObject(getValueComparator());
678: final int size = _size;
679: stream.writeInt(size);
680: for (int i = 0; i < size; i++) {
681: stream.writeObject(get(i));
682: }
683: }
684:
685: /**
686: * Returns the current capacity of this table.
687: *
688: * @return this table's capacity.
689: */
690: protected final int getCapacity() {
691: return _capacity;
692: }
693:
694: /**
695: * Increases this table capacity.
696: */
697: private void increaseCapacity() {
698: MemoryArea.getMemoryArea(this ).executeInArea(new Runnable() {
699: public void run() {
700: if (_capacity < C1) { // For small capacity, resize.
701: _capacity <<= 1;
702: Object/*{E}*/[] tmp = (Object/*{E}*/[]) new Object[_capacity];
703: System.arraycopy(_low, 0, tmp, 0, _low.length);
704: _low = tmp;
705: _high[0] = tmp;
706: } else { // Add a new low block of 1024 elements.
707: int j = _capacity >> B1;
708: if (j >= _high.length) { // Resizes _high.
709: Object/*{E}*/[][] tmp = (Object/*{E}*/[][]) new Object[_high.length * 2][];
710: System
711: .arraycopy(_high, 0, tmp, 0,
712: _high.length);
713: _high = tmp;
714: }
715: _high[j] = (Object/*{E}*/[]) new Object[C1];
716: _capacity += C1;
717: }
718: }
719: });
720: }
721:
722: /**
723: * This inner class implements a sub-table.
724: */
725: private static final class SubTable extends FastCollection
726: implements List, RandomAccess {
727:
728: private static final ObjectFactory FACTORY = new ObjectFactory() {
729: protected Object create() {
730: return new SubTable();
731: }
732:
733: protected void cleanup(Object obj) {
734: SubTable st = (SubTable) obj;
735: st._table = null;
736: }
737: };
738:
739: private FastTable _table;
740:
741: private int _offset;
742:
743: private int _size;
744:
745: public static SubTable valueOf(FastTable table, int offset,
746: int size) {
747: SubTable subTable = (SubTable) FACTORY.object();
748: subTable._table = table;
749: subTable._offset = offset;
750: subTable._size = size;
751: return subTable;
752: }
753:
754: public int size() {
755: return _size;
756: }
757:
758: public Record head() {
759: return Index.valueOf(-1);
760: }
761:
762: public Record tail() {
763: return Index.valueOf(_size);
764: }
765:
766: public Object valueOf(Record record) {
767: return _table.get(((Index) record).intValue() + _offset);
768: }
769:
770: public void delete(Record record) {
771: throw new UnsupportedOperationException(
772: "Deletion not supported, thread-safe collections.");
773: }
774:
775: public boolean addAll(int index, Collection values) {
776: throw new UnsupportedOperationException(
777: "Insertion not supported, thread-safe collections.");
778: }
779:
780: public Object get(int index) {
781: if ((index < 0) || (index >= _size))
782: throw new IndexOutOfBoundsException("index: " + index);
783: return _table.get(index + _offset);
784: }
785:
786: public Object set(int index, Object value) {
787: if ((index < 0) || (index >= _size))
788: throw new IndexOutOfBoundsException("index: " + index);
789: return _table.set(index + _offset, value);
790: }
791:
792: public void add(int index, Object element) {
793: throw new UnsupportedOperationException(
794: "Insertion not supported, thread-safe collections.");
795: }
796:
797: public Object remove(int index) {
798: throw new UnsupportedOperationException(
799: "Deletion not supported, thread-safe collections.");
800: }
801:
802: public int indexOf(Object value) {
803: final FastComparator comp = _table.getValueComparator();
804: for (int i = -1; ++i < _size;) {
805: if (comp.areEqual(value, _table.get(i + _offset)))
806: return i;
807: }
808: return -1;
809: }
810:
811: public int lastIndexOf(Object value) {
812: final FastComparator comp = _table.getValueComparator();
813: for (int i = _size; --i >= 0;) {
814: if (comp.areEqual(value, _table.get(i + _offset)))
815: return i;
816: }
817: return -1;
818: }
819:
820: public ListIterator listIterator() {
821: return listIterator(0);
822: }
823:
824: public ListIterator listIterator(int index) {
825: if ((index >= 0) && (index <= _size)) {
826: return FastTableIterator.valueOf(_table, index
827: + _offset, _offset, _offset + _size);
828: } else {
829: throw new IndexOutOfBoundsException("index: " + index
830: + " for table of size: " + _size);
831: }
832: }
833:
834: public List subList(int fromIndex, int toIndex) {
835: if ((fromIndex < 0) || (toIndex > _size)
836: || (fromIndex > toIndex))
837: throw new IndexOutOfBoundsException("fromIndex: "
838: + fromIndex + ", toIndex: " + toIndex
839: + " for list of size: " + _size);
840: return SubTable.valueOf(_table, _offset + fromIndex,
841: toIndex - fromIndex);
842: }
843: }
844:
845: /**
846: * This inner class implements a fast table iterator.
847: */
848: private static final class FastTableIterator implements
849: ListIterator {
850:
851: private static final ObjectFactory FACTORY = new ObjectFactory() {
852: protected Object create() {
853: return new FastTableIterator();
854: }
855:
856: protected void cleanup(Object obj) {
857: FastTableIterator i = (FastTableIterator) obj;
858: i._table = null;
859: i._low = null;
860: i._high = null;
861: }
862: };
863:
864: private FastTable _table;
865:
866: private int _currentIndex;
867:
868: private int _start; // Inclusive.
869:
870: private int _end; // Exclusive.
871:
872: private int _nextIndex;
873:
874: private Object[] _low;
875:
876: private Object[][] _high;
877:
878: public static FastTableIterator valueOf(FastTable table,
879: int nextIndex, int start, int end) {
880: FastTableIterator iterator = (FastTableIterator) FACTORY
881: .object();
882: iterator._table = table;
883: iterator._start = start;
884: iterator._end = end;
885: iterator._nextIndex = nextIndex;
886: iterator._low = table._low;
887: iterator._high = table._high;
888: iterator._currentIndex = -1;
889: return iterator;
890: }
891:
892: public boolean hasNext() {
893: return (_nextIndex != _end);
894: }
895:
896: public Object next() {
897: if (_nextIndex == _end)
898: throw new NoSuchElementException();
899: final int i = _currentIndex = _nextIndex++;
900: return i < C1 ? _low[i] : _high[i >> B1][i & M1];
901: }
902:
903: public int nextIndex() {
904: return _nextIndex;
905: }
906:
907: public boolean hasPrevious() {
908: return _nextIndex != _start;
909: }
910:
911: public Object previous() {
912: if (_nextIndex == _start)
913: throw new NoSuchElementException();
914: final int i = _currentIndex = --_nextIndex;
915: return i < C1 ? _low[i] : _high[i >> B1][i & M1];
916: }
917:
918: public int previousIndex() {
919: return _nextIndex - 1;
920: }
921:
922: public void add(Object o) {
923: _table.add(_nextIndex++, o);
924: _end++;
925: _currentIndex = -1;
926: }
927:
928: public void set(Object o) {
929: if (_currentIndex >= 0) {
930: _table.set(_currentIndex, o);
931: } else {
932: throw new IllegalStateException();
933: }
934: }
935:
936: public void remove() {
937: if (_currentIndex >= 0) {
938: _table.remove(_currentIndex);
939: _end--;
940: if (_currentIndex < _nextIndex) {
941: _nextIndex--;
942: }
943: _currentIndex = -1;
944: } else {
945: throw new IllegalStateException();
946: }
947: }
948: }
949:
950: // Shifts element from the specified index to the right (higher indexes).
951: private void shiftRight(int index, int shift) {
952: while (_size + shift >= _capacity) {
953: increaseCapacity();
954: }
955: for (int i = _size; --i >= index;) {
956: final int dest = i + shift;
957: _high[dest >> B1][dest & M1] = _high[i >> B1][i & M1];
958: }
959: }
960:
961: // Shifts element from the specified index to the left (lower indexes).
962: private void shiftLeft(int index, int shift) {
963: for (int i = index; i < _size; i++) {
964: final int dest = i - shift;
965: _high[dest >> B1][dest & M1] = _high[i >> B1][i & M1];
966: }
967: }
968:
969: // For inlining of default comparator.
970: private static boolean defaultEquals(Object o1, Object o2) {
971: return (o1 == null) ? (o2 == null) : (o1 == o2)
972: || o1.equals(o2);
973: }
974:
975: private static final long serialVersionUID = 1L;
976:
977: static volatile int ONE_VOLATILE = 1; // To prevent reordering.
978: }
|