FastList


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