0001: /*
0002: * Javolution - Java(TM) Solution for Real-Time and Embedded Systems
0003: * Copyright (C) 2005 - Javolution (http://javolution.org/)
0004: * All rights reserved.
0005: *
0006: * Permission to use, copy, modify, and distribute this software is
0007: * freely granted, provided that this notice is preserved.
0008: */
0009: package javolution.util;
0010:
0011: import java.io.IOException;
0012:
0013: import j2me.io.ObjectInputStream;
0014: import j2me.io.ObjectOutputStream;
0015: import j2me.io.Serializable;
0016: import j2me.lang.IllegalStateException;
0017: import j2me.util.Collection;
0018: import j2me.util.Iterator;
0019: import j2me.util.List;
0020: import j2me.util.ListIterator;
0021: import j2mex.realtime.MemoryArea;
0022: import java.util.NoSuchElementException;
0023:
0024: import javolution.context.ObjectFactory;
0025: import javolution.context.PersistentContext;
0026: import javolution.lang.Reusable;
0027:
0028: /**
0029: * <p> This class represents a linked list with real-time behavior;
0030: * smooth capacity increase and no memory allocation as long as the
0031: * list size does not exceed its initial capacity.</p>
0032: *
0033: * <p> All of the operations perform as could be expected for a doubly-linked
0034: * list ({@link #addLast insertion}/{@link #removeLast() deletion}
0035: * at the end of the list are nonetheless the fastest).
0036: * Operations that index into the list will traverse the list from
0037: * the begining or the end whichever is closer to the specified index.
0038: * Random access operations can be significantly accelerated by
0039: * {@link #subList splitting} the list into smaller ones.</p>
0040: *
0041: * <p> {@link FastList} (as for any {@link FastCollection} sub-class) supports
0042: * thread-safe, fast iterations without using iterators.[code]
0043: * FastList<String> list = new FastList<String>();
0044: * for (FastList.Node<String> n = list.head(), end = list.tail(); (n = n.getNext()) != end;) {
0045: * String value = n.getValue(); // No typecast necessary.
0046: * }[/code]</p>
0047: *
0048: * <p> {@link FastList} are fully {@link Reusable reusable}, they maintain
0049: * internal pools of {@link Node nodes} objects. When a node is removed
0050: * from its list, it is automatically restored to its pool.</p>
0051: *
0052: * <p> Custom list implementations may override the {@link #newNode} method
0053: * in order to return their own {@link Node} implementation (with
0054: * additional fields for example).</p>
0055: *
0056: * @author <a href="mailto:jean-marie@dautelle.com">Jean-Marie Dautelle</a>
0057: * @version 4.2, December 18, 2006
0058: */
0059: public class FastList/*<E>*/extends FastCollection/*<E>*/
0060: implements List/*<E>*/, Reusable {
0061:
0062: /**
0063: * Holds the main list factory.
0064: */
0065: private static final ObjectFactory FACTORY = new ObjectFactory() {
0066:
0067: public Object create() {
0068: return new FastList();
0069: }
0070:
0071: public void cleanup(Object obj) {
0072: ((FastList) obj).reset();
0073: }
0074: };
0075:
0076: /**
0077: * Holds the node marking the beginning of the list (not included).
0078: */
0079: private transient Node/*<E>*/_head = newNode();
0080:
0081: /**
0082: * Holds the node marking the end of the list (not included).
0083: */
0084: private transient Node/*<E>*/_tail = newNode();
0085:
0086: /**
0087: * Holds the value comparator.
0088: */
0089: private transient FastComparator/*<? super E>*/_valueComparator = FastComparator.DEFAULT;
0090:
0091: /**
0092: * Holds the current size.
0093: */
0094: private transient int _size;
0095:
0096: /**
0097: * Creates a list of small initial capacity.
0098: */
0099: public FastList() {
0100: this (4);
0101: }
0102:
0103: /**
0104: * Creates a persistent list associated to the specified unique identifier
0105: * (convenience method).
0106: *
0107: * @param id the unique identifier for this map.
0108: * @throws IllegalArgumentException if the identifier is not unique.
0109: * @see javolution.context.PersistentContext.Reference
0110: */
0111: public FastList(String id) {
0112: this ();
0113: new PersistentContext.Reference(id, this ) {
0114: protected void notifyChange() {
0115: FastList.this .clear();
0116: FastList.this .addAll((FastList) this .get());
0117: }
0118: };
0119: }
0120:
0121: /**
0122: * Creates a list of specified initial capacity; unless the list size
0123: * reaches the specified capacity, operations on this list will not allocate
0124: * memory (no lazy object creation).
0125: *
0126: * @param capacity the initial capacity.
0127: */
0128: public FastList(int capacity) {
0129: _head._next = _tail;
0130: _tail._previous = _head;
0131: Node/*<E>*/previous = _tail;
0132: for (int i = 0; i++ < capacity;) {
0133: Node/*<E>*/newNode = newNode();
0134: newNode._previous = previous;
0135: previous._next = newNode;
0136: previous = newNode;
0137: }
0138: }
0139:
0140: /**
0141: * Creates a list containing the specified values, in the order they
0142: * are returned by the collection's iterator.
0143: *
0144: * @param values the values to be placed into this list.
0145: */
0146: public FastList(Collection/*<? extends E>*/values) {
0147: this (values.size());
0148: addAll(values);
0149: }
0150:
0151: /**
0152: * Returns a new, preallocated or {@link #recycle recycled} list instance
0153: * (on the stack when executing in a {@link javolution.context.StackContext
0154: * StackContext}).
0155: *
0156: * @return a new, preallocated or recycled list instance.
0157: */
0158: public static/*<E>*/FastList/*<E>*/newInstance() {
0159: return (FastList/*<E>*/) FACTORY.object();
0160: }
0161:
0162: /**
0163: * Recycles a list {@link #newInstance() instance} immediately
0164: * (on the stack when executing in a {@link javolution.context.StackContext
0165: * StackContext}).
0166: */
0167: public static void recycle(FastList instance) {
0168: FACTORY.recycle(instance);
0169: }
0170:
0171: /**
0172: * Appends the specified value to the end of this list
0173: * (equivalent to {@link #addLast}).
0174: *
0175: * @param value the value to be appended to this list.
0176: * @return <code>true</code> (as per the general contract of the
0177: * <code>Collection.add</code> method).
0178: */
0179: public final boolean add(Object/*{E}*/value) {
0180: addLast(value);
0181: return true;
0182: }
0183:
0184: /**
0185: * Returns the hash code value for this list. The hash code of a list
0186: * is defined to be the result of the following calculation:[code]
0187: * h = 1;
0188: * Iterator i = list.iterator();
0189: * while (i.hasNext()) {
0190: * Object obj = i.next();
0191: * h = 31 * h + this.getValueComparator().hashCodeOf(obj);
0192: * }[/code]
0193: *
0194: * @return the hash code value for this list.
0195: */
0196: public int hashCode() {
0197: final FastComparator comp = this .getValueComparator();
0198: int h = 1;
0199: for (Node n = _head, end = _tail; (n = n._next) != end;) {
0200: h = 31 * h + comp.hashCodeOf(n._value);
0201: }
0202: return h;
0203: }
0204:
0205: /**
0206: * Returns the value at the specified position in this list.
0207: *
0208: * @param index the index of value to return.
0209: * @return the value at the specified position in this list.
0210: * @throws IndexOutOfBoundsException if <code>(index < 0) ||
0211: * (index >= size())</code>
0212: */
0213: public final Object/*{E}*/get(int index) {
0214: if ((index < 0) || (index >= _size))
0215: throw new IndexOutOfBoundsException("index: " + index);
0216: return nodeAt(index)._value;
0217: }
0218:
0219: /**
0220: * Replaces the value at the specified position in this list with the
0221: * specified value.
0222: *
0223: * @param index the index of value to replace.
0224: * @param value the value to be stored at the specified position.
0225: * @return the value previously at the specified position.
0226: * @throws IndexOutOfBoundsException if <code>(index < 0) ||
0227: * (index >= size())</code>
0228: */
0229: public final Object/*{E}*/set(int index, Object/*{E}*/value) {
0230: if ((index < 0) || (index >= _size))
0231: throw new IndexOutOfBoundsException("index: " + index);
0232: final Node/*<E>*/node = nodeAt(index);
0233: Object/*{E}*/previousValue = node._value;
0234: node._value = value;
0235: return previousValue;
0236: }
0237:
0238: /**
0239: * Inserts the specified value at the specified position in this list.
0240: * Shifts the value currently at that position
0241: * (if any) and any subsequent values to the right (adds one to their
0242: * indices).
0243: *
0244: * @param index the index at which the specified value is to be inserted.
0245: * @param value the value to be inserted.
0246: * @throws IndexOutOfBoundsException if <code>(index < 0) ||
0247: * (index > size())</code>
0248: */
0249: public final void add(int index, Object/*{E}*/value) {
0250: if ((index < 0) || (index > _size))
0251: throw new IndexOutOfBoundsException("index: " + index);
0252: addBefore(nodeAt(index), value);
0253: }
0254:
0255: /**
0256: * Inserts all of the values in the specified collection into this
0257: * list at the specified position. Shifts the value currently at that
0258: * position (if any) and any subsequent values to the right
0259: * (increases their indices).
0260: *
0261: * @param index the index at which to insert first value from the specified
0262: * collection.
0263: * @param values the values to be inserted into this list.
0264: * @return <code>true</code> if this list changed as a result of the call;
0265: * <code>false</code> otherwise.
0266: * @throws IndexOutOfBoundsException if <code>(index < 0) ||
0267: * (index > size())</code>
0268: */
0269: public final boolean addAll(int index,
0270: Collection/*<? extends E>*/values) {
0271: if ((index < 0) || (index > _size))
0272: throw new IndexOutOfBoundsException("index: " + index);
0273: final Node indexNode = nodeAt(index);
0274: Iterator/*<? extends E>*/i = values.iterator();
0275: while (i.hasNext()) {
0276: addBefore(indexNode, i.next());
0277: }
0278: return values.size() != 0;
0279: }
0280:
0281: /**
0282: * Removes the value at the specified position in this list.
0283: * Shifts any subsequent values to the left (subtracts one
0284: * from their indices). Returns the value that was removed from the
0285: * list.
0286: *
0287: * @param index the index of the value to removed.
0288: * @return the value previously at the specified position.
0289: * @throws IndexOutOfBoundsException if <code>(index < 0) ||
0290: * (index >= size())</code>
0291: */
0292: public final Object/*{E}*/remove(int index) {
0293: if ((index < 0) || (index >= _size))
0294: throw new IndexOutOfBoundsException("index: " + index);
0295: final Node/*<E>*/node = nodeAt(index);
0296: Object/*{E}*/previousValue = node._value;
0297: delete(node);
0298: return previousValue;
0299: }
0300:
0301: /**
0302: * Returns the index in this list of the first occurrence of the specified
0303: * value, or -1 if this list does not contain this value.
0304: *
0305: * @param value the value to search for.
0306: * @return the index in this list of the first occurrence of the specified
0307: * value, or -1 if this list does not contain this value.
0308: */
0309: public final int indexOf(Object value) {
0310: final FastComparator comp = this .getValueComparator();
0311: int index = 0;
0312: for (Node n = _head, end = _tail; (n = n._next) != end; index++) {
0313: if (comp == FastComparator.DEFAULT ? defaultEquals(value,
0314: n._value) : comp.areEqual(value, n._value))
0315: return index;
0316: }
0317: return -1;
0318: }
0319:
0320: /**
0321: * Returns the index in this list of the last occurrence of the specified
0322: * value, or -1 if this list does not contain this value.
0323: *
0324: * @param value the value to search for.
0325: * @return the index in this list of the last occurrence of the specified
0326: * value, or -1 if this list does not contain this value.
0327: */
0328: public final int lastIndexOf(Object value) {
0329: final FastComparator comp = this .getValueComparator();
0330: int index = size() - 1;
0331: for (Node n = _tail, end = _head; (n = n._previous) != end; index--) {
0332: if (comp == FastComparator.DEFAULT ? defaultEquals(value,
0333: n._value) : comp.areEqual(value, n._value))
0334: return index;
0335: }
0336: return -1;
0337: }
0338:
0339: /**
0340: * Returns a simple iterator over the elements in this list
0341: * (allocated on the stack when executed in a
0342: * {@link javolution.context.StackContext StackContext}).
0343: *
0344: * @return an iterator over this list values.
0345: */
0346: public Iterator/*<E>*/iterator() {
0347: return listIterator();
0348: }
0349:
0350: /**
0351: * Returns a list iterator over the elements in this list
0352: * (allocated on the stack when executed in a
0353: * {@link javolution.context.StackContext StackContext}).
0354: *
0355: * @return an iterator over this list values.
0356: */
0357: public ListIterator/*<E>*/listIterator() {
0358: return FastListIterator.valueOf(this , _head._next, 0, _size);
0359: }
0360:
0361: /**
0362: * Returns a list iterator from the specified position
0363: * (allocated on the stack when executed in a
0364: * {@link javolution.context.StackContext StackContext}).
0365: *
0366: * The specified index indicates the first value that would be returned by
0367: * an initial call to the <code>next</code> method. An initial call to
0368: * the <code>previous</code> method would return the value with the
0369: * specified index minus one.
0370: *
0371: * @param index index of first value to be returned from the
0372: * list iterator (by a call to the <code>next</code> method).
0373: * @return a list iterator over the values in this list
0374: * starting at the specified position in this list.
0375: * @throws IndexOutOfBoundsException if the index is out of range
0376: * [code](index < 0 || index > size())[/code].
0377: */
0378: public ListIterator/*<E>*/listIterator(int index) {
0379: if ((index < 0) || (index > _size))
0380: throw new IndexOutOfBoundsException("index: " + index);
0381: return FastListIterator.valueOf(this , nodeAt(index), index,
0382: _size);
0383: }
0384:
0385: /**
0386: * Returns a view of the portion of this list between the specified
0387: * indexes (allocated from the "stack" when executing in a
0388: * {@link javolution.context.StackContext StackContext}).
0389: * If the specified indexes are equal, the returned list is empty.
0390: * The returned list is backed by this list, so non-structural changes in
0391: * the returned list are reflected in this list, and vice-versa.
0392: *
0393: * This method eliminates the need for explicit range operations (of
0394: * the sort that commonly exist for arrays). Any operation that expects
0395: * a list can be used as a range operation by passing a subList view
0396: * instead of a whole list. For example, the following idiom
0397: * removes a range of values from a list:
0398: * <code>list.subList(from, to).clear();</code>
0399: * Similar idioms may be constructed for <code>indexOf</code> and
0400: * <code>lastIndexOf</code>, and all of the algorithms in the
0401: * <code>Collections</code> class can be applied to a subList.
0402: *
0403: * The semantics of the list returned by this method become undefined if
0404: * the backing list (i.e., this list) is <i>structurally modified</i> in
0405: * any way other than via the returned list (structural modifications are
0406: * those that change the size of this list, or otherwise perturb it in such
0407: * a fashion that iterations in progress may yield incorrect results).
0408: *
0409: * @param fromIndex low endpoint (inclusive) of the subList.
0410: * @param toIndex high endpoint (exclusive) of the subList.
0411: * @return a view of the specified range within this list.
0412: *
0413: * @throws IndexOutOfBoundsException if [code](fromIndex < 0 ||
0414: * toIndex > size || fromIndex < toIndex)[/code]
0415: */
0416: public final List/*<E>*/subList(int fromIndex, int toIndex) {
0417: if ((fromIndex < 0) || (toIndex > _size)
0418: || (fromIndex > toIndex))
0419: throw new IndexOutOfBoundsException("fromIndex: "
0420: + fromIndex + ", toIndex: " + toIndex
0421: + " for list of size: " + _size);
0422: return SubList.valueOf(this , nodeAt(fromIndex)._previous,
0423: nodeAt(toIndex), toIndex - fromIndex);
0424: }
0425:
0426: /**
0427: * Returns the first value of this list.
0428: *
0429: * @return this list's first value.
0430: * @throws NoSuchElementException if this list is empty.
0431: */
0432: public final Object/*{E}*/getFirst() {
0433: final Node/*<E>*/node = _head._next;
0434: if (node == _tail)
0435: throw new NoSuchElementException();
0436: return node._value;
0437: }
0438:
0439: /**
0440: * Returns the last value of this list.
0441: *
0442: * @return this list's last value.
0443: * @throws NoSuchElementException if this list is empty.
0444: */
0445: public final Object/*{E}*/getLast() {
0446: final Node/*<E>*/node = _tail._previous;
0447: if (node == _head)
0448: throw new NoSuchElementException();
0449: return node._value;
0450: }
0451:
0452: /**
0453: * Inserts the specified value at the beginning of this list.
0454: *
0455: * @param value the value to be inserted.
0456: */
0457: public final void addFirst(Object/*{E}*/value) {
0458: addBefore(_head._next, value);
0459: }
0460:
0461: /**
0462: * Appends the specified value to the end of this list <i>(fast)</i>.
0463: *
0464: * @param value the value to be inserted.
0465: */
0466: public void addLast(Object/*{E}*/value) { // Optimized.
0467: if (_tail._next == null) {
0468: increaseCapacity();
0469: }
0470: _tail._value = value;
0471: _tail = _tail._next;
0472: _size += ONE_VOLATILE; // Done last.
0473: }
0474:
0475: /**
0476: * Removes and returns the first value of this list.
0477: *
0478: * @return this list's first value before this call.
0479: * @throws NoSuchElementException if this list is empty.
0480: */
0481: public final Object/*{E}*/removeFirst() {
0482: final Node/*<E>*/first = _head._next;
0483: if (first == _tail)
0484: throw new NoSuchElementException();
0485: Object/*{E}*/previousValue = first._value;
0486: delete(first);
0487: return previousValue;
0488: }
0489:
0490: /**
0491: * Removes and returns the last value of this list <i>(fast)</i>.
0492: *
0493: * @return this list's last value before this call.
0494: * @throws NoSuchElementException if this list is empty.
0495: */
0496: public final Object/*{E}*/removeLast() {
0497: if (_size == 0)
0498: throw new NoSuchElementException();
0499: _size -= ONE_VOLATILE; // Done first.
0500: final Node/*<E>*/last = _tail._previous;
0501: final Object/*{E}*/previousValue = last._value;
0502: _tail = last;
0503: last._value = null;
0504: return previousValue;
0505: }
0506:
0507: ///////////////////////
0508: // Nodes operations. //
0509: ///////////////////////
0510:
0511: /**
0512: * Inserts the specified value before the specified Node.
0513: *
0514: * @param next the Node before which this value is inserted.
0515: * @param value the value to be inserted.
0516: */
0517: public final void addBefore(Node/*<E>*/next, Object/*{E}*/value) {
0518: if (_tail._next == null) {
0519: increaseCapacity();// Increases capacity.
0520: }
0521: final Node newNode = _tail._next;
0522: // Detaches newNode.
0523: final Node tailNext = _tail._next = newNode._next;
0524: if (tailNext != null) {
0525: tailNext._previous = _tail;
0526: }
0527: // Inserts before next.
0528: final Node previous = next._previous;
0529: previous._next = newNode;
0530: next._previous = newNode;
0531: newNode._next = next;
0532: newNode._previous = previous;
0533:
0534: newNode._value = value;
0535: _size += ONE_VOLATILE; // Done last.
0536: }
0537:
0538: /**
0539: * Returns the node at the specified index. This method returns
0540: * the {@link #headNode} node when [code]index < 0 [/code] or
0541: * the {@link #tailNode} node when [code]index >= size()[/code].
0542: *
0543: * @param index the index of the Node to return.
0544: */
0545: private final Node/*<E>*/nodeAt(int index) {
0546: // We cannot do backward search because of thread-safety.
0547: Node/*<E>*/node = _head;
0548: for (int i = index; i-- >= 0;) {
0549: node = node._next;
0550: }
0551: return node;
0552: }
0553:
0554: // Implements FastCollection abstract method.
0555: public final Record/*Node<E>*/head() {
0556: return _head;
0557: }
0558:
0559: // Implements FastCollection abstract method.
0560: public final Record/*Node<E>*/tail() {
0561: return _tail;
0562: }
0563:
0564: // Implements FastCollection abstract method.
0565: public final Object/*{E}*/valueOf(Record record) {
0566: return ((Node/*<E>*/) record)._value;
0567: }
0568:
0569: // Implements FastCollection abstract method.
0570: public final void delete(Record record) {
0571: Node/*<E>*/node = (Node/*<E>*/) record;
0572: _size -= ONE_VOLATILE; // Done first.
0573: node._value = null;
0574: // Detaches.
0575: node._previous._next = node._next;
0576: node._next._previous = node._previous;
0577: // Inserts after _tail.
0578: final Node/*<E>*/next = _tail._next;
0579: node._previous = _tail;
0580: node._next = next;
0581: _tail._next = node;
0582: if (next != null) {
0583: next._previous = node;
0584: }
0585: }
0586:
0587: // Overrides (optimization).
0588: public final boolean contains(Object value) {
0589: return indexOf(value) >= 0;
0590: }
0591:
0592: ///////////////////////
0593: // Contract Methods. //
0594: ///////////////////////
0595:
0596: // Implements abstract method.
0597: public final int size() {
0598: return _size;
0599: }
0600:
0601: // Overrides (optimization).
0602: public final void clear() {
0603: _size = ONE_VOLATILE - 1; // Done first.
0604: for (Node/*<E>*/n = _head, end = _tail; (n = n._next) != end;) {
0605: n._value = null;
0606: }
0607: _tail = _head._next;
0608: }
0609:
0610: // Implements Reusable interface.
0611: public void reset() {
0612: this .clear();
0613: _valueComparator = FastComparator.DEFAULT;
0614: }
0615:
0616: /**
0617: * Sets the comparator to use for value equality.
0618: *
0619: * @param comparator the value comparator.
0620: * @return <code>this</code>
0621: */
0622: public FastList/*<E>*/setValueComparator(
0623: FastComparator/*<? super E>*/comparator) {
0624: _valueComparator = comparator;
0625: return this ;
0626: }
0627:
0628: // Overrides.
0629: public FastComparator/*<? super E>*/getValueComparator() {
0630: return _valueComparator;
0631: }
0632:
0633: // Overrides to return a list (JDK1.5+).
0634: public Collection/*List<E>*/unmodifiable() {
0635: return (Collection/*List<E>*/) super .unmodifiable();
0636: }
0637:
0638: /**
0639: * Returns a new node for this list; this method can be overriden by
0640: * custom list implementation.
0641: *
0642: * @return a new node.
0643: */
0644: protected Node/*<E>*/newNode() {
0645: return new Node();
0646: }
0647:
0648: // Requires special handling during de-serialization process.
0649: private void readObject(ObjectInputStream stream)
0650: throws IOException, ClassNotFoundException {
0651:
0652: // Initial setup.
0653: _head = new Node();
0654: _tail = new Node();
0655: _head._next = _tail;
0656: _tail._previous = _head;
0657:
0658: setValueComparator((FastComparator) stream.readObject());
0659: final int size = stream.readInt();
0660: for (int i = size; i-- != 0;) {
0661: addLast((Object/*{E}*/) stream.readObject());
0662: }
0663: }
0664:
0665: // Requires special handling during serialization process.
0666: private void writeObject(ObjectOutputStream stream)
0667: throws IOException {
0668: stream.writeObject(getValueComparator());
0669: stream.writeInt(_size);
0670: Node node = _head;
0671: for (int i = _size; i-- != 0;) {
0672: node = node._next;
0673: stream.writeObject(node._value);
0674: }
0675: }
0676:
0677: // Increases capacity (_tail._next == null)
0678: private void increaseCapacity() {
0679: MemoryArea.getMemoryArea(this ).executeInArea(new Runnable() {
0680: public void run() {
0681: Node/*<E>*/newNode0 = newNode();
0682: _tail._next = newNode0;
0683: newNode0._previous = _tail;
0684:
0685: Node/*<E>*/newNode1 = newNode();
0686: newNode0._next = newNode1;
0687: newNode1._previous = newNode0;
0688:
0689: Node/*<E>*/newNode2 = newNode();
0690: newNode1._next = newNode2;
0691: newNode2._previous = newNode1;
0692:
0693: Node/*<E>*/newNode3 = newNode();
0694: newNode2._next = newNode3;
0695: newNode3._previous = newNode2;
0696: }
0697: });
0698: }
0699:
0700: /**
0701: * This class represents a {@link FastList} node; it allows for direct
0702: * iteration over the list {@link #getValue values}.
0703: * Custom {@link FastList} may use a derived implementation.
0704: * For example:[code]
0705: * static class MyList<E,X> extends FastList<E> {
0706: * protected MyNode newNode() {
0707: * return new MyNode();
0708: * }
0709: * class MyNode extends Node<E> {
0710: * X xxx; // Additional node field (e.g. cross references).
0711: * }
0712: * }[/code]
0713: */
0714: public static class Node/*<E>*/implements Record, Serializable {
0715:
0716: /**
0717: * Holds the next node.
0718: */
0719: private Node/*<E>*/_next;
0720:
0721: /**
0722: * Holds the previous node.
0723: */
0724: private Node/*<E>*/_previous;
0725:
0726: /**
0727: * Holds the node value.
0728: */
0729: private Object/*{E}*/_value;
0730:
0731: /**
0732: * Default constructor.
0733: */
0734: protected Node() {
0735: }
0736:
0737: /**
0738: * Returns the value for this node.
0739: *
0740: * @return the node value.
0741: */
0742: public final Object/*{E}*/getValue() {
0743: return _value;
0744: }
0745:
0746: // Implements Record interface.
0747: public final Record/*Node<E>*/getNext() {
0748: return _next;
0749: }
0750:
0751: // Implements Record interface.
0752: public final Record/*Node<E>*/getPrevious() {
0753: return _previous;
0754: }
0755:
0756: }
0757:
0758: /**
0759: * This inner class implements a sub-list.
0760: */
0761: private static final class SubList extends FastCollection implements
0762: List, Serializable {
0763:
0764: private static final ObjectFactory FACTORY = new ObjectFactory() {
0765: protected Object create() {
0766: return new SubList();
0767: }
0768:
0769: protected void cleanup(Object obj) {
0770: SubList sl = (SubList) obj;
0771: sl._list = null;
0772: sl._head = null;
0773: sl._tail = null;
0774: }
0775: };
0776:
0777: private FastList _list;
0778:
0779: private Node _head;
0780:
0781: private Node _tail;
0782:
0783: private int _size;
0784:
0785: public static SubList valueOf(FastList list, Node head,
0786: Node tail, int size) {
0787: SubList subList = (SubList) FACTORY.object();
0788: subList._list = list;
0789: subList._head = head;
0790: subList._tail = tail;
0791: subList._size = size;
0792: return subList;
0793: }
0794:
0795: public int size() {
0796: return _size;
0797: }
0798:
0799: public Record head() {
0800: return _head;
0801: }
0802:
0803: public Record tail() {
0804: return _tail;
0805: }
0806:
0807: public Object valueOf(Record record) {
0808: return _list.valueOf(record);
0809: }
0810:
0811: public void delete(Record record) {
0812: _list.delete(record);
0813: }
0814:
0815: public boolean addAll(int index, Collection values) {
0816: if ((index < 0) || (index > _size))
0817: throw new IndexOutOfBoundsException("index: " + index);
0818: final Node indexNode = nodeAt(index);
0819: Iterator i = values.iterator();
0820: while (i.hasNext()) {
0821: _list.addBefore(indexNode, i.next());
0822: }
0823: return values.size() != 0;
0824: }
0825:
0826: public Object get(int index) {
0827: if ((index < 0) || (index >= _size))
0828: throw new IndexOutOfBoundsException("index: " + index);
0829: return nodeAt(index)._value;
0830: }
0831:
0832: public Object set(int index, Object value) {
0833: if ((index < 0) || (index >= _size))
0834: throw new IndexOutOfBoundsException("index: " + index);
0835: final Node node = nodeAt(index);
0836: Object previousValue = node._value;
0837: node._value = value;
0838: return previousValue;
0839: }
0840:
0841: public void add(int index, Object element) {
0842: if ((index < 0) || (index > _size))
0843: throw new IndexOutOfBoundsException("index: " + index);
0844: _list.addBefore(nodeAt(index), element);
0845: }
0846:
0847: public Object remove(int index) {
0848: if ((index < 0) || (index >= _size))
0849: throw new IndexOutOfBoundsException("index: " + index);
0850: final Node node = nodeAt(index);
0851: Object previousValue = node._value;
0852: _list.delete(node);
0853: return previousValue;
0854: }
0855:
0856: public int indexOf(Object value) {
0857: final FastComparator comp = _list.getValueComparator();
0858: int index = 0;
0859: for (Node n = _head, end = _tail; (n = n._next) != end; index++) {
0860: if (comp.areEqual(value, n._value))
0861: return index;
0862: }
0863: return -1;
0864: }
0865:
0866: public int lastIndexOf(Object value) {
0867: final FastComparator comp = this .getValueComparator();
0868: int index = size() - 1;
0869: for (Node n = _tail, end = _head; (n = n._previous) != end; index--) {
0870: if (comp.areEqual(value, n._value)) {
0871: return index;
0872: }
0873: }
0874: return -1;
0875: }
0876:
0877: public ListIterator listIterator() {
0878: return listIterator(0);
0879: }
0880:
0881: public ListIterator listIterator(int index) {
0882: if ((index >= 0) && (index <= _size)) {
0883: return FastListIterator.valueOf(_list, nodeAt(index),
0884: index, _size);
0885: } else {
0886: throw new IndexOutOfBoundsException("index: " + index
0887: + " for list of size: " + _size);
0888: }
0889: }
0890:
0891: public List subList(int fromIndex, int toIndex) {
0892: if ((fromIndex < 0) || (toIndex > _size)
0893: || (fromIndex > toIndex))
0894: throw new IndexOutOfBoundsException("fromIndex: "
0895: + fromIndex + ", toIndex: " + toIndex
0896: + " for list of size: " + _size);
0897: SubList subList = SubList.valueOf(_list,
0898: nodeAt(fromIndex)._previous, nodeAt(toIndex),
0899: toIndex - fromIndex);
0900: return subList;
0901: }
0902:
0903: private final Node nodeAt(int index) {
0904: if (index <= (_size >> 1)) { // Forward search.
0905: Node node = _head;
0906: for (int i = index; i-- >= 0;) {
0907: node = node._next;
0908: }
0909: return node;
0910: } else { // Backward search.
0911: Node node = _tail;
0912: for (int i = _size - index; i-- > 0;) {
0913: node = node._previous;
0914: }
0915: return node;
0916: }
0917: }
0918: }
0919:
0920: /**
0921: * This inner class implements a fast list iterator.
0922: */
0923: private static final class FastListIterator implements ListIterator {
0924:
0925: private static final ObjectFactory FACTORY = new ObjectFactory() {
0926: protected Object create() {
0927: return new FastListIterator();
0928: }
0929:
0930: protected void cleanup(Object obj) {
0931: FastListIterator i = (FastListIterator) obj;
0932: i._list = null;
0933: i._currentNode = null;
0934: i._nextNode = null;
0935: }
0936: };
0937:
0938: private FastList _list;
0939:
0940: private Node _nextNode;
0941:
0942: private Node _currentNode;
0943:
0944: private int _length;
0945:
0946: private int _nextIndex;
0947:
0948: public static FastListIterator valueOf(FastList list,
0949: Node nextNode, int nextIndex, int size) {
0950: FastListIterator itr = (FastListIterator) FACTORY.object();
0951: itr._list = list;
0952: itr._nextNode = nextNode;
0953: itr._nextIndex = nextIndex;
0954: itr._length = size;
0955: return itr;
0956: }
0957:
0958: public boolean hasNext() {
0959: return (_nextIndex != _length);
0960: }
0961:
0962: public Object next() {
0963: if (_nextIndex == _length)
0964: throw new NoSuchElementException();
0965: _nextIndex++;
0966: _currentNode = _nextNode;
0967: _nextNode = _nextNode._next;
0968: return _currentNode._value;
0969: }
0970:
0971: public int nextIndex() {
0972: return _nextIndex;
0973: }
0974:
0975: public boolean hasPrevious() {
0976: return _nextIndex != 0;
0977: }
0978:
0979: public Object previous() {
0980: if (_nextIndex == 0)
0981: throw new NoSuchElementException();
0982: _nextIndex--;
0983: _currentNode = _nextNode = _nextNode._previous;
0984: return _currentNode._value;
0985: }
0986:
0987: public int previousIndex() {
0988: return _nextIndex - 1;
0989: }
0990:
0991: public void add(Object o) {
0992: _list.addBefore(_nextNode, o);
0993: _currentNode = null;
0994: _length++;
0995: _nextIndex++;
0996: }
0997:
0998: public void set(Object o) {
0999: if (_currentNode == null)
1000: throw new IllegalStateException();
1001: _currentNode._value = o;
1002: }
1003:
1004: public void remove() {
1005: if (_currentNode == null)
1006: throw new IllegalStateException();
1007: if (_nextNode == _currentNode) { // previous() has been called.
1008: _nextNode = _nextNode._next;
1009: } else {
1010: _nextIndex--;
1011: }
1012: _list.delete(_currentNode);
1013: _currentNode = null;
1014: _length--;
1015: }
1016: }
1017:
1018: // For inlining of default comparator.
1019: private static boolean defaultEquals(Object o1, Object o2) {
1020: return (o1 == null) ? (o2 == null) : (o1 == o2)
1021: || o1.equals(o2);
1022: }
1023:
1024: static volatile int ONE_VOLATILE = 1; // To prevent reordering.
1025:
1026: private static final long serialVersionUID = 1L;
1027:
1028: }
|