FastTable


1   /*
2    * Javolution - Java(TM) Solution for Real-Time and Embedded Systems
3    * Copyright (C) 2005 - Javolution (http://javolution.org/)
4    * All rights reserved.
5    * 
6    * Permission to use, copy, modify, and distribute this software is
7    * freely granted, provided that this notice is preserved.
8    */
9   package javolution.util;
10  
11  import java.io.IOException  ;
12  import java.util.NoSuchElementException  ;
13  
14  import j2me.io.ObjectInputStream;
15  import j2me.io.ObjectOutputStream;
16  import j2me.lang.IllegalStateException;
17  import j2me.lang.UnsupportedOperationException;
18  import j2me.util.Collection;
19  import j2me.util.Iterator;
20  import j2me.util.List;
21  import j2me.util.ListIterator;
22  import j2me.util.RandomAccess;
23  import j2mex.realtime.MemoryArea;
24  import javolution.context.PersistentContext;
25  import javolution.context.RealtimeObject;
26  import javolution.lang.Reusable;
27  
28  /**
29   * <p> This class represents a random access collection with real-time behavior; 
30   *     smooth capacity increase (no array resize/copy ever) and no memory 
31   *     allocation as long as the collection size does not exceed its initial
32   *     capacity.</p>
33   *     <img SRC="doc-files/list-add.png"/>
34   *     
35   * <p> This class has the following advantages over the widely used 
36   *     <code>java.util.ArrayList</code>:<ul>
37   *     <li> Faster when the capacity is unknown (default constructor) as no 
38   *          array resize/copy is ever performed.</li>
39   *     <li> No large array allocation (for large collections multi-dimensional
40   *          arrays are employed). Does not stress the garbage collector with
41   *          large chunk of memory to allocate (likely to trigger a
42   *          full garbage collection due to memory fragmentation).</li>
43   *     <li> Support concurrent access/iteration without synchronization if the 
44   *          collection values are not removed/inserted (Ref. 
45   *          {@link javolution.util} discussion).</li>
46   *     </ul></p>
47   *     
48   *  <p> Iterations over the {@link FastTable} values are faster when
49   *      performed using the {@link #get} method rather than using collection
50   *      records or iterators:[code]
51   *     for (int i = 0, n = table.size(); i < n; i++) {
52   *          table.get(i);
53   *     }[/code]</p>
54   *     
55   *  <p> {@link FastTable} supports {@link #sort sorting} in place (quick sort) 
56   *      using the {@link FastCollection#getValueComparator() value comparator}
57   *      for the table (no object or array allocation when sorting).</p> 
58   * 
59   * @author <a HREF="mailto:jean-marie@dautelle.com">Jean-Marie Dautelle</a>
60   * @version 4.2, December 18, 2006
61   */
62  public class FastTable/*<E>*/extends FastCollection/*<E>*/implements
63          List/*<E>*/, Reusable, RandomAccess {
64  
65      /**
66       * Holds the factory for this fast table.
67       */
68      private static final Factory FACTORY = new Factory() {
69          public Object   create() {
70              return new FastTable();
71          }
72  
73          public void cleanup(Object   obj) {
74              ((FastTable) obj).reset();
75          }
76      };
77  
78      //
79      // Holds the arrays. The array sizes are adjusted to ensures that
80      // no more than 4 time the required space is ever allocated.
81      //
82      // elems[1<<D3][1<<D2][1<<D1][1<<D0]
83      // with get(i) = elems[(i>>R3)&M3][(i>>R2)&M2][(i>>R1)&M1][(i>>R0)&M0]
84      // 
85  
86      private static final int D0 = 5;
87  
88      private static final int M0 = (1 << D0) - 1;
89  
90      private static final int C0 = 1 << D0; // capacity chars0
91  
92      private static final int D1 = D0 + 2;
93  
94      private static final int R1 = D0;
95  
96      private static final int M1 = (1 << D1) - 1;
97  
98      private static final int C1 = 1 << (D0 + D1); // capacity elems1
99  
100     private static final int D2 = D1 + 2;
101 
102     private static final int R2 = D0 + D1;
103 
104     private static final int M2 = (1 << D2) - 1;
105 
106     private static final int C2 = 1 << (D0 + D1 + D2); // capacity elems2
107 
108     private static final int D3 = D2 + 2;
109 
110     private static final int R3 = D0 + D1 + D2;
111 
112     // new Object[1<<7][1<<5], 12 bits (4096)
113     private transient Object  /*{E}*/[][] _elems1;
114 
115     // new Object[1<<9][1<<7][1<<5], 21 bits (2097152)
116     private transient Object  /*{E}*/[][][] _elems2;
117 
118     // new Object[1<<11][1<<9][1<<7][1<<5], 32 bits
119     private transient Object  /*{E}*/[][][][] _elems3;
120 
121     /**
122      * Holds the current capacity. 
123      */
124     private transient int _capacity = C0;
125 
126     /**
127      * Holds the current size.
128      */
129     private transient int _size;
130 
131     /**
132      * Holds the value comparator.
133      */
134     private transient FastComparator/*<? super E>*/ _valueComparator = FastComparator.DEFAULT;
135 
136     /**
137      * Creates a table of small initial capacity.
138      */
139     public FastTable() {
140         _elems1 = (Object  /*{E}*/[][]) new Object  [1][];
141         _elems1[0] = (Object  /*{E}*/[]) new Object  [C0];
142     }
143 
144     /**
145      * Creates a persistent table associated to the specified unique identifier
146      * (convenience method).
147      * 
148      * @param id the unique identifier for this map.
149      * @throws IllegalArgumentException if the identifier is not unique.
150      * @see javolution.context.PersistentContext.Reference
151      */
152     public FastTable(String   id) {
153         this();
154         new PersistentContext.Reference(id, this) {
155             protected void notifyChange() {
156                 FastTable.this.clear();
157                 FastTable.this.addAll((FastList) this.get());
158             }
159         };
160     }
161 
162     /**
163      * Creates a table of specified initial capacity; unless the table size 
164      * reaches the specified capacity, operations on this table will not 
165      * allocate memory (no lazy object creation).
166      * 
167      * @param capacity the initial capacity.
168      */
169     public FastTable(int capacity) {
170         this();
171         while (capacity > _capacity) {
172             increaseCapacity();
173         }
174     }
175 
176     /**
177      * Creates a table containing the specified values, in the order they
178      * are returned by the collection's iterator.
179      *
180      * @param values the values to be placed into this table.
181      */
182     public FastTable(Collection/*<? extends E>*/values) {
183         this(values.size());
184         addAll(values);
185     }
186 
187     /**
188      * Returns a new, preallocated or {@link #recycle recycled} table instance
189      * (on the stack when executing in a {@link javolution.context.PoolContext
190      * PoolContext}).
191      *
192      * @return a new, preallocated or recycled table instance.
193      */
194     public static/*<E>*/FastTable/*<E>*/newInstance() {
195         return (FastTable/*<E>*/) FACTORY.object();
196     }
197 
198     /**
199      * Recycles a table {@link #newInstance() instance} immediately
200      * (on the stack when executing in a {@link javolution.context.PoolContext
201      * PoolContext}). 
202      */
203     public static void recycle(FastTable instance) {
204         FACTORY.recycle(instance);
205     }
206 
207     /**
208      * Returns the current capacity of this table.
209      *
210      * @return this table's capacity.
211      */
212     protected final int getCapacity() {
213         return _capacity;
214     }
215 
216     /**
217      * Returns the element at the specified index.
218      *
219      * @param index index of value to return.
220      * @return the value at the specified position in this list.
221      * @throws IndexOutOfBoundsException if <code>(index < 0) || 
222      *         (index >= size())</code>
223      */
224     public final Object  /*{E}*/get(int index) { // Short to be inlined.
225         if (((index >> R2) == 0) && (index < _size))
226             return _elems1[(index >> R1)][index & M0];
227         return get2(index);
228     }
229 
230     private final Object  /*{E}*/get2(int index) {
231         if ((index < 0) || (index >= _size))
232             throw new IndexOutOfBoundsException  ("index: " + index);
233         return (index < C2) ? _elems2[(index >> R2)][(index >> R1) & M1][index
234                 & M0]
235                 : _elems3[(index >> R3)][(index >> R2) & M2][(index >> R1) & M1][index
236                         & M0];
237     }
238 
239     /**
240      * Replaces the value at the specified position in this table with the
241      * specified value.
242      *
243      * @param index index of value to replace.
244      * @param value value to be stored at the specified position.
245      * @throws IndexOutOfBoundsException if <code>(index < 0) || 
246      *         (index >= size())</code>
247      */
248     public final Object  /*{E}*/set(int index, Object  /*{E}*/value) {
249         if ((index < 0) || (index >= _size))
250             throw new IndexOutOfBoundsException  ("index: " + index);
251         final Object  /*{E}*/[] elems = (index < C1) ? _elems1[(index >> R1)]
252                 : (index < C2) ? _elems2[(index >> R2)][(index >> R1) & M1]
253                         : _elems3[(index >> R3)][(index >> R2) & M2][(index >> R1)
254                                 & M1];
255         final Object  /*{E}*/oldValue = elems[index & M0];
256         elems[index & M0] = value;
257         return oldValue;
258     }
259 
260     /**
261      * Appends the specified value to the end of this table.
262      *
263      * @param value the value to be appended to this table.
264      * @return <code>true</code> (as per the general contract of the
265      *         <code>Collection.add</code> method).
266      */
267     public final boolean add(Object  /*{E}*/value) {
268         final int i = _size;
269         if (i >= _capacity) {
270             increaseCapacity();
271         }
272         final Object  /*{E}*/[] elems = (i < C1) ? _elems1[(i >> R1)]
273                 : (i < C2) ? _elems2[(i >> R2)][(i >> R1) & M1]
274                         : _elems3[(i >> R3)][(i >> R2) & M2][(i >> R1) & M1];
275         elems[i & M0] = value;
276         // The size increment is always performed last (the compiler will not 
277         // reorder due to possible IndexOutOfBoundsException above).
278         _size++;
279         return true;
280     }
281 
282     /**
283      * Returns the first value of this table.
284      *
285      * @return this table first value.
286      * @throws NoSuchElementException if this table is empty.
287      */
288     public final Object  /*{E}*/getFirst() {
289         if (_size == 0)
290             throw new NoSuchElementException  ();
291         return _elems1[0][0];
292     }
293     
294     /**
295      * Returns the last value of this table.
296      *
297      * @return this table last value.
298      * @throws NoSuchElementException if this table is empty.
299      */
300     public final Object  /*{E}*/getLast() {
301         if (_size == 0)
302             throw new NoSuchElementException  ();
303         final int i = _size - 1;
304         final Object  /*{E}*/[] elems = (i < C1) ? _elems1[(i >> R1)]
305                 : (i < C2) ? _elems2[(i >> R2)][(i >> R1) & M1]
306                         : _elems3[(i >> R3)][(i >> R2) & M2][(i >> R1) & M1];
307         return elems[i & M0];
308     }
309 
310     /**
311      * Appends the specified value to the end of this table <i>(fast)</i>.
312      * 
313      * @param value the value to be added.
314      */
315     public final void addLast(Object  /*{E}*/value) {
316         add(value);
317     }
318 
319     /**
320      * Removes and returns the last value of this table <i>(fast)</i>.
321      *
322      * @return this table's last value before this call.
323      * @throws NoSuchElementException if this table is empty.
324      */
325     public final Object  /*{E}*/removeLast() {
326         if (_size == 0)
327             throw new NoSuchElementException  ();
328         final int i = --_size;
329         final Object  /*{E}*/[] elems = (i < C1) ? _elems1[(i >> R1)]
330                 : (i < C2) ? _elems2[(i >> R2)][(i >> R1) & M1]
331                         : _elems3[(i >> R3)][(i >> R2) & M2][(i >> R1) & M1];
332         final Object  /*{E}*/oldValue = elems[i & M0];
333         elems[i & M0] = null;
334         return oldValue;
335     }
336 
337     // Overrides.
338     public final void clear() {
339         final int size = _size;
340         _size = 0;
341         final int blockSize = Math.min(size, C0);
342         for (int i = 0; i < size; i += C0) {
343             final Object  /*{E}*/[] elems = (i < C1) ? _elems1[(i >> R1)]
344                     : (i < C2) ? _elems2[(i >> R2)][(i >> R1) & M1]
345                             : _elems3[(i >> R3)][(i >> R2) & M2][(i >> R1) & M1];
346             System.arraycopy(NULL_BLOCK, 0, elems, 0, blockSize);
347         }
348     }
349 
350     private static final Object  [] NULL_BLOCK = (Object  []) new Object  [C0];    
351 
352     /**
353      * Inserts all of the values in the specified collection into this
354      * table at the specified position. Shifts the value currently at that
355      * position (if any) and any subsequent values to the right 
356      * (increases their indices). 
357      *
358      * @param index the index at which to insert first value from the specified
359      *        collection.
360      * @param values the values to be inserted into this list.
361      * @return <code>true</code> if this list changed as a result of the call;
362      *         <code>false</code> otherwise.
363      * @throws IndexOutOfBoundsException if <code>(index < 0) || 
364      *         (index > size())</code>
365      */
366     public final boolean addAll(int index, Collection/*<? extends E>*/values) {
367         if ((index < 0) || (index > _size))
368             throw new IndexOutOfBoundsException  ("index: " + index);
369         final int shift = values.size();
370         final int prevSize = _size;
371         final int newSize = prevSize + shift;
372         while (newSize >= _capacity) {
373             increaseCapacity();
374         }
375         _size = newSize; // Set here to avoid index error.
376         // Shift values after index (TBD: Optimize).
377         for (int i = prevSize; --i >= index;) {
378             this.set(i + shift, this.get(i));
379         }
380         Iterator/*<? extends E>*/valuesIterator = values.iterator();
381         for (int i = index, n = index + shift; i < n; i++) {
382             this.set(i, valuesIterator.next());
383         }
384         return shift != 0;
385     }
386 
387     /**
388      * Inserts the specified value at the specified position in this table.
389      * Shifts the value currently at that position
390      * (if any) and any subsequent values to the right (adds one to their
391      * indices).
392      *
393      * @param index the index at which the specified value is to be inserted.
394      * @param value the value to be inserted.
395      * @throws IndexOutOfBoundsException if <code>(index < 0) || 
396      *         (index > size())</code>
397      */
398     public final void add(int index, Object  /*{E}*/value) {
399         if ((index < 0) || (index > _size))
400             throw new IndexOutOfBoundsException  ("index: " + index);
401         final int prevSize = _size;
402         final int newSize = prevSize + 1;
403         if (newSize >= _capacity) {
404             increaseCapacity();
405         }
406         _size = newSize;
407         for (int i = index, n = newSize; i < n;) {
408             value = this.set(i++, value);
409         }
410     }
411 
412     /**
413      * Removes the value at the specified position from this table.
414      * Shifts any subsequent values to the left (subtracts one
415      * from their indices). Returns the value that was removed from the
416      * table.
417      *
418      * @param index the index of the value to removed.
419      * @return the value previously at the specified position.
420      * @throws IndexOutOfBoundsException if <code>(index < 0) || 
421      *         (index >= size())</code>
422      */
423     public final Object  /*{E}*/remove(int index) {
424         if ((index < 0) || (index >= _size))
425             throw new IndexOutOfBoundsException  ("index: " + index);
426         final int lastIndex = _size - 1;
427         Object  /*{E}*/obj = this.get(lastIndex);
428         for (int i = lastIndex; --i >= index;) {
429             obj = this.set(i, obj);
430         }
431         this.set(lastIndex, null); // For GC to do its work.
432         _size = lastIndex;
433         return obj;
434     }
435 
436     /**
437      * Removes the values between <code>[fromIndex..toIndex[<code> from
438      * this table.
439      * 
440      * @param fromIndex the beginning index, inclusive.
441      * @param toIndex the ending index, exclusive.
442      * @throws IndexOutOfBoundsException if <code>(fromIndex < 0) || (toIndex < 0) 
443      *         || (fromIndex > toIndex) || (toIndex > this.size())</code>
444      */
445     public final void removeRange(int fromIndex, int toIndex) {
446         final int prevSize = _size;
447         if ((fromIndex < 0) || (toIndex < 0) || (fromIndex > toIndex)
448                 || (toIndex > prevSize))
449             throw new IndexOutOfBoundsException  ();
450         for (int i = toIndex, j = fromIndex; i < prevSize;) {
451             this.set(j++, this.get(i++));
452         }
453         final int newSize = prevSize - toIndex + fromIndex;
454         for (int i = newSize; i < prevSize;) {
455             this.set(i++, null); // For GC to do its work.
456         }
457         _size = newSize;
458     }
459 
460     /**
461      * Returns the index in this table of the first occurrence of the specified
462      * value, or -1 if this table does not contain this value.
463      *
464      * @param value the value to search for.
465      * @return the index in this table of the first occurrence of the specified
466      *         value, or -1 if this table does not contain this value.
467      */
468     public final int indexOf(Object   value) {
469         final FastComparator comp = this.getValueComparator();
470         for (int i = -1; ++i < _size;) {
471             if (comp.areEqual(value, get(i)))
472                 return i;
473         }
474         return -1;
475     }
476 
477     /**
478      * Returns the index in this table of the last occurrence of the specified
479      * value, or -1 if this table does not contain this value.
480      *
481      * @param value the value to search for.
482      * @return the index in this table of the last occurrence of the specified
483      *         value, or -1 if this table does not contain this value.
484      */
485     public final int lastIndexOf(Object   value) {
486         final FastComparator comp = this.getValueComparator();
487         for (int i = _size; --i >= 0;) {
488             if (comp.areEqual(value, get(i)))
489                 return i;
490         }
491         return -1;
492     }
493 
494     /**
495      * Returns an iterator over the elements in this list 
496      * (allocated on the stack when executed in a 
497      * {@link javolution.context.PoolContext PoolContext}).
498      *
499      * @return an iterator over this list values.
500      */
501     public Iterator/*<E>*/iterator() {
502         FastTableIterator i = (FastTableIterator) FastTableIterator.FACTORY
503                 .object();
504         i._table = this;
505         i._start = 0;
506         i._end = this._size;
507         i._nextIndex = 0;
508         i._currentIndex = -1;
509         return i;
510     }
511 
512     /**
513      * Returns a list iterator over the elements in this list 
514      * (allocated on the stack when executed in a 
515      * {@link javolution.context.PoolContext PoolContext}).
516      *
517      * @return an iterator over this list values.
518      */
519     public ListIterator/*<E>*/listIterator() {
520         FastTableIterator i = (FastTableIterator) FastTableIterator.FACTORY
521                 .object();
522         i._table = this;
523         i._start = 0;
524         i._end = this._size;
525         i._nextIndex = 0;
526         i._currentIndex = -1;
527         return i;
528     }
529 
530     /**
531      * Returns a list iterator from the specified position
532      * (allocated on the stack when executed in a 
533      * {@link javolution.context.PoolContext PoolContext}).
534      * The list iterator being returned does not support insertion/deletion.
535      * 
536      * @param index the index of first value to be returned from the
537      *        list iterator (by a call to the <code>next</code> method).
538      * @return a list iterator of the values in this table
539      *         starting at the specified position in this list.
540      * @throws IndexOutOfBoundsException if the index is out of range 
541      *         [code](index < 0 || index > size())[/code]
542      */
543     public ListIterator/*<E>*/listIterator(int index) {
544         if ((index >= 0) && (index <= _size)) {
545             FastTableIterator i = (FastTableIterator) FastTableIterator.FACTORY
546                     .object();
547             i._table = this;
548             i._start = 0;
549             i._end = this._size;
550             i._nextIndex = index;
551             i._currentIndex = -1;
552             return i;
553         } else {
554             throw new IndexOutOfBoundsException  ("index: " + index
555                     + " for table of size: " + _size);
556         }
557     }
558 
559     /**
560      * Returns a view of the portion of this list between the specified
561      * indexes (instance of {@link FastList} allocated from the "stack" when
562      * executing in a {@link javolution.context.PoolContext PoolContext}).
563      * If the specified indexes are equal, the returned list is empty. 
564      * The returned list is backed by this list, so non-structural changes in
565      * the returned list are reflected in this list, and vice-versa. 
566      *
567      * This method eliminates the need for explicit range operations (of
568      * the sort that commonly exist for arrays). Any operation that expects
569      * a list can be used as a range operation by passing a subList view
570      * instead of a whole list.  For example, the following idiom
571      * removes a range of values from a list: [code]
572      * list.subList(from, to).clear();[/code]
573      * Similar idioms may be constructed for <code>indexOf</code> and
574      * <code>lastIndexOf</code>, and all of the algorithms in the
575      * <code>Collections</code> class can be applied to a subList.
576      *
577      * The semantics of the list returned by this method become undefined if
578      * the backing list (i.e., this list) is <i>structurally modified</i> in
579      * any way other than via the returned list (structural modifications are
580      * those that change the size of this list, or otherwise perturb it in such
581      * a fashion that iterations in progress may yield incorrect results).
582      *
583      * @param fromIndex low endpoint (inclusive) of the subList.
584      * @param toIndex high endpoint (exclusive) of the subList.
585      * @return a view of the specified range within this list.
586      * 
587      * @throws IndexOutOfBoundsException if [code](fromIndex < 0 ||
588      *          toIndex > size || fromIndex > toIndex)[/code]
589      */
590     public final List/*<E>*/subList(int fromIndex, int toIndex) {
591         if ((fromIndex < 0) || (toIndex > _size) || (fromIndex > toIndex))
592             throw new IndexOutOfBoundsException  ("fromIndex: " + fromIndex
593                     + ", toIndex: " + toIndex + " for list of size: " + _size);
594         SubTable st = (SubTable) SubTable.FACTORY.object();
595         st._table = this;
596         st._offset = fromIndex;
597         st._size = toIndex - fromIndex;
598         return st;
599     }
600 
601     /**
602      * Reduces the capacity of this table to the current size (minimize 
603      * storage space).
604      */
605     public final void trimToSize() {
606         while (_capacity > _size + C0) {
607             decreaseCapacity();
608         }
609     }
610 
611     /**
612      * Sorts this table in place (quick sort) using this table 
613      * {@link FastCollection#getValueComparator() value comparator}.
614      */
615     public final void sort() {
616         if (_size > 1) {
617             quicksort(0, _size - 1, this.getValueComparator());
618         }
619     }
620 
621     // From Wikipedia Quick Sort - http://en.wikipedia.org/wiki/Quicksort
622     //
623     private void quicksort(int first, int last, FastComparator cmp) {
624         int pivIndex = 0;
625         if (first < last) {
626             pivIndex = partition(first, last, cmp);
627             quicksort(first, (pivIndex - 1), cmp);
628             quicksort((pivIndex + 1), last, cmp);
629         }
630     }
631 
632     private int partition(int f, int l, FastComparator cmp) {
633         int up, down;
634         Object  /*{E}*/ piv = this.get(f);
635         up = f;
636         down = l;
637         do {
638             while (cmp.compare(get(up), piv) <= 0 && up < l) {
639                 up++;
640             }
641             while (cmp.compare(get(down), piv) > 0 && down > f) {
642                 down--;
643             }
644             if (up < down) { // Swaps.
645                 Object  /*{E}*/ temp = get(up);
646                 set(up, get(down));
647                 set(down, temp);
648             }
649         } while (down > up);
650         set(f, get(down));
651         set(down, piv);
652         return down;
653     }
654 
655 
656     /**
657      * Sets the comparator to use for value equality.
658      *
659      * @param comparator the value comparator.
660      * @return <code>this</code>
661      */
662     public FastTable/*<E>*/ setValueComparator(FastComparator/*<? super E>*/ comparator) {
663         _valueComparator = comparator;
664         return this;
665     }
666     
667     // Overrides.
668     public FastComparator/*<? super E>*/ getValueComparator() {
669         return _valueComparator;
670     }
671     
672     // Implements FastCollection abstract method.
673     public final int size() {
674         return _size;
675     }
676 
677     // Implements FastCollection abstract method.
678     public final Record head() {
679         return Index.valueOf(-1);
680     }
681 
682     // Implements FastCollection abstract method.
683     public final Record tail() {
684         return Index.valueOf(_size);
685     }
686 
687     // Implements FastCollection abstract method.
688     public final Object  /*{E}*/valueOf(Record record) {
689         return get(((Index) record).intValue());
690     }
691 
692     // Implements FastCollection abstract method.
693     public final void delete(Record record) {
694         remove(((Index) record).intValue());
695     }
696 
697     // Overrides  to return a list (JDK1.5+).
698     public Collection/*List<E>*/unmodifiable() {
699         return (Collection/*List<E>*/) super.unmodifiable();
700     }
701 
702     // Requires special handling during de-serialization process.
703     private void readObject(ObjectInputStream stream) throws IOException  ,
704             ClassNotFoundException   {
705         // Default setup.
706         _capacity = C0;
707         _elems1 = (Object  /*{E}*/[][]) new Object  [1][];
708         _elems1[0] = (Object  /*{E}*/[]) new Object  [C0];
709         
710         setValueComparator((FastComparator) stream.readObject());
711         final int size = stream.readInt();
712         for (int i = 0; i < size; i++) {
713             addLast((Object  /*{E}*/) stream.readObject());
714         }
715     }
716 
717     // Requires special handling during serialization process.
718     private void writeObject(ObjectOutputStream stream) throws IOException   {
719         stream.writeObject(getValueComparator());
720         final int size = _size;
721         stream.writeInt(size);
722         for (int i = 0; i < size; i++) {
723             stream.writeObject(get(i));
724         }
725     }
726 
727     /**
728      * Increases this table capacity.
729      */
730     protected void increaseCapacity() {
731         MemoryArea.getMemoryArea(this).executeInArea(new Runnable  () {
732             public void run() {
733                 final int c = _capacity;
734                 _capacity += C0;
735                 if (c < C1) {
736                     if (_elems1.length == 1) { // Replaces the original table.
737                         Object  /*{E}*/[][] tmp = (Object  /*{E}*/[][]) new Object  [1 << D1][];
738                         tmp[0] = _elems1[0];
739                         _elems1 = tmp;
740                     }
741                     _elems1[(c >> R1)] = (Object  /*{E}*/[]) new Object  [1 << D0];
742 
743                 } else if (c < C2) {
744                     if (_elems2 == null) {
745                         _elems2 = (Object  /*{E}*/[][][]) new Object  [1 << D2][][];
746                     }
747                     if (_elems2[(c >> R2)] == null) {
748                         _elems2[(c >> R2)] = (Object  /*{E}*/[][]) new Object  [1 << D1][];
749                     }
750                     _elems2[(c >> R2)][(c >> R1) & M1] = (Object  /*{E}*/[]) new Object  [1 << D0];
751 
752                 } else {
753                     if (_elems3 == null) {
754                         _elems3 = (Object  /*{E}*/[][][][]) new Object  [D3][][][];
755                     }
756                     if (_elems3[(c >> R3)] == null) {
757                         _elems3[(c >> R3)] = (Object  /*{E}*/[][][]) new Object  [D2][][];
758                     }
759                     if (_elems3[(c >> R3)][(c >> R2) & M2] == null) {
760                         _elems3[(c >> R3)][(c >> R2) & M2] = (Object  /*{E}*/[][]) new Object  [D1][];
761                     }
762                     _elems3[(c >> R3)][(c >> R2) & M2][(c >> R1) & M1] = (Object  /*{E}*/[]) new Object  [D0];
763                 }
764             }
765         });
766     }
767 
768     /**
769      * Decreases this table capacity.
770      */
771     protected void decreaseCapacity() {
772         if (_size >= _capacity - C0) return;
773         final int c = _capacity;
774         _capacity -= C0;
775         if (c < C1) {
776             _elems1[(c >> R1)] = null;
777             _elems2 = null;
778             _elems3 = null;
779         } else if (c < C2) {
780             _elems2[(c >> R2)][(c >> R1) & M1] = null;
781             _elems3 = null;
782         } else {
783             _elems3[(c >> R3)][(c >> R2) & M2][(c >> R1) & M1] = null;
784         }
785     }
786 
787     /**
788      * This inner class implements a fast table iterator.
789      */
790     private static final class FastTableIterator extends RealtimeObject
791             implements ListIterator {
792 
793         private static final Factory FACTORY = new Factory() {
794             protected Object   create() {
795                 return new FastTableIterator();
796             }
797 
798             protected void cleanup(Object   obj) {
799                 FastTableIterator i = (FastTableIterator) obj;
800                 i._table = null;
801             }
802         };
803 
804         private FastTable _table;
805 
806         private int _currentIndex;
807 
808         private int _start; // Inclusive.
809 
810         private int _end; // Exclusive.
811 
812         private int _nextIndex;
813 
814         public boolean hasNext() {
815             return (_nextIndex != _end);
816         }
817 
818         public Object   next() {
819             if (_nextIndex == _end)
820                 throw new NoSuchElementException  ();
821             return _table.get(_currentIndex = _nextIndex++);
822         }
823 
824         public int nextIndex() {
825             return _nextIndex;
826         }
827 
828         public boolean hasPrevious() {
829             return _nextIndex != _start;
830         }
831 
832         public Object   previous() {
833             if (_nextIndex == _start)
834                 throw new NoSuchElementException  ();
835             return _table.get(_currentIndex = --_nextIndex);
836         }
837 
838         public int previousIndex() {
839             return _nextIndex - 1;
840         }
841 
842         public void add(Object   o) {
843             _table.add(_nextIndex++, o);
844             _end++;
845             _currentIndex = -1;
846         }
847 
848         public void set(Object   o) {
849             if (_currentIndex >= 0) {
850                 _table.set(_currentIndex, o);
851             } else {
852                 throw new IllegalStateException  ();
853             }
854         }
855 
856         public void remove() {
857             if (_currentIndex >= 0) {
858                 _table.remove(_currentIndex);
859                 _end--;
860                 if (_currentIndex < _nextIndex) {
861                     _nextIndex--;
862                 }
863                 _currentIndex = -1;
864             } else {
865                 throw new IllegalStateException  ();
866             }
867         }
868     }
869 
870     /**
871      * This inner class implements a sub-table.
872      */
873     private static final class SubTable extends FastCollection implements List,
874             RandomAccess {
875 
876         private static final Factory FACTORY = new Factory() {
877             protected Object   create() {
878                 return new SubTable();
879             }
880 
881             protected void cleanup(Object   obj) {
882                 SubTable st = (SubTable) obj;
883                 st._table = null;
884             }
885         };
886 
887         private FastTable _table;
888 
889         private int _offset;
890 
891         private int _size;
892 
893         public int size() {
894             return _size;
895         }
896 
897         public Record head() {
898             return Index.valueOf(-1);
899         }
900 
901         public Record tail() {
902             return Index.valueOf(_size);
903         }
904 
905         public Object   valueOf(Record record) {
906             return _table.get(((Index) record).intValue() + _offset);
907         }
908 
909         public void delete(Record record) {
910             throw new UnsupportedOperationException  (
911                     "Deletion not supported, thread-safe collections.");
912         }
913 
914         public boolean addAll(int index, Collection values) {
915             throw new UnsupportedOperationException  (
916                     "Insertion not supported, thread-safe collections.");
917         }
918 
919         public Object   get(int index) {
920             if ((index < 0) || (index >= _size))
921                 throw new IndexOutOfBoundsException  ("index: " + index);
922             return _table.get(index + _offset);
923         }
924 
925         public Object   set(int index, Object   value) {
926             if ((index < 0) || (index >= _size))
927                 throw new IndexOutOfBoundsException  ("index: " + index);
928             return _table.set(index + _offset, value);
929         }
930 
931         public void add(int index, Object   element) {
932             throw new UnsupportedOperationException  (
933                     "Insertion not supported, thread-safe collections.");
934         }
935 
936         public Object   remove(int index) {
937             throw new UnsupportedOperationException  (
938                     "Deletion not supported, thread-safe collections.");
939         }
940 
941         public int indexOf(Object   value) {
942             final FastComparator comp = _table.getValueComparator();
943             for (int i = -1; ++i < _size;) {
944                 if (comp.areEqual(value, _table.get(i + _offset)))
945                     return i;
946             }
947             return -1;
948         }
949 
950         public int lastIndexOf(Object   value) {
951             final FastComparator comp = _table.getValueComparator();
952             for (int i = _size; --i >= 0;) {
953                 if (comp.areEqual(value, _table.get(i + _offset)))
954                     return i;
955             }
956             return -1;
957         }
958 
959         public ListIterator listIterator() {
960             return listIterator(0);
961         }
962 
963         public ListIterator listIterator(int index) {
964             if ((index >= 0) && (index <= _size)) {
965                 FastTableIterator i = (FastTableIterator) FastTableIterator.FACTORY
966                         .object();
967                 i._table = _table;
968                 i._start = _offset;
969                 i._end = _offset + _size;
970                 i._nextIndex = index + _offset;
971                 return i;
972             } else {
973                 throw new IndexOutOfBoundsException  ("index: " + index
974                         + " for table of size: " + _size);
975             }
976         }
977 
978         public List subList(int fromIndex, int toIndex) {
979             if ((fromIndex < 0) || (toIndex > _size) || (fromIndex > toIndex))
980                 throw new IndexOutOfBoundsException  ("fromIndex: " + fromIndex
981                         + ", toIndex: " + toIndex + " for list of size: "
982                         + _size);
983             SubTable st = (SubTable) SubTable.FACTORY.object();
984             st._table = _table;
985             st._offset = _offset + fromIndex;
986             st._size = toIndex - fromIndex;
987             return st;
988         }
989     }
990 
991     private static final long serialVersionUID = 1L;
992 }
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags