0001: /*
0002: * Copyright 2001-2005 The Apache Software Foundation
0003: *
0004: * Licensed under the Apache License, Version 2.0 (the "License");
0005: * you may not use this file except in compliance with the License.
0006: * You may obtain a copy of the License at
0007: *
0008: * http://www.apache.org/licenses/LICENSE-2.0
0009: *
0010: * Unless required by applicable law or agreed to in writing, software
0011: * distributed under the License is distributed on an "AS IS" BASIS,
0012: * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
0013: * See the License for the specific language governing permissions and
0014: * limitations under the License.
0015: */
0016: package org.apache.commons.collections.list;
0017:
0018: import java.io.IOException;
0019: import java.io.ObjectInputStream;
0020: import java.io.ObjectOutputStream;
0021: import java.lang.reflect.Array;
0022: import java.util.AbstractList;
0023: import java.util.Collection;
0024: import java.util.ConcurrentModificationException;
0025: import java.util.Iterator;
0026: import java.util.List;
0027: import java.util.ListIterator;
0028: import java.util.NoSuchElementException;
0029:
0030: import org.apache.commons.collections.OrderedIterator;
0031:
0032: /**
0033: * An abstract implementation of a linked list which provides numerous points for
0034: * subclasses to override.
0035: * <p>
0036: * Overridable methods are provided to change the storage node and to change how
0037: * nodes are added to and removed. Hopefully, all you need for unusual subclasses
0038: * is here.
0039: *
0040: * @since Commons Collections 3.0
0041: * @version $Revision: 219343 $ $Date: 2005-07-16 18:08:16 +0100 (Sat, 16 Jul 2005) $
0042: *
0043: * @author Rich Dougherty
0044: * @author Phil Steitz
0045: * @author Stephen Colebourne
0046: */
0047: public abstract class AbstractLinkedList implements List {
0048:
0049: /*
0050: * Implementation notes:
0051: * - a standard circular doubly-linked list
0052: * - a marker node is stored to mark the start and the end of the list
0053: * - node creation and removal always occurs through createNode() and
0054: * removeNode().
0055: * - a modification count is kept, with the same semantics as
0056: * {@link java.util.LinkedList}.
0057: * - respects {@link AbstractList#modCount}
0058: */
0059:
0060: /**
0061: * A {@link Node} which indicates the start and end of the list and does not
0062: * hold a value. The value of <code>next</code> is the first item in the
0063: * list. The value of of <code>previous</code> is the last item in the list.
0064: */
0065: protected transient Node header;
0066: /** The size of the list */
0067: protected transient int size;
0068: /** Modification count for iterators */
0069: protected transient int modCount;
0070:
0071: /**
0072: * Constructor that does nothing intended for deserialization.
0073: * <p>
0074: * If this constructor is used by a serializable subclass then the init()
0075: * method must be called.
0076: */
0077: protected AbstractLinkedList() {
0078: super ();
0079: }
0080:
0081: /**
0082: * Constructs a list copying data from the specified collection.
0083: *
0084: * @param coll the collection to copy
0085: */
0086: protected AbstractLinkedList(Collection coll) {
0087: super ();
0088: init();
0089: addAll(coll);
0090: }
0091:
0092: /**
0093: * The equivalent of a default constructor, broken out so it can be called
0094: * by any constructor and by <code>readObject</code>.
0095: * Subclasses which override this method should make sure they call super,
0096: * so the list is initialised properly.
0097: */
0098: protected void init() {
0099: header = createHeaderNode();
0100: }
0101:
0102: //-----------------------------------------------------------------------
0103: public int size() {
0104: return size;
0105: }
0106:
0107: public boolean isEmpty() {
0108: return (size() == 0);
0109: }
0110:
0111: public Object get(int index) {
0112: Node node = getNode(index, false);
0113: return node.getValue();
0114: }
0115:
0116: //-----------------------------------------------------------------------
0117: public Iterator iterator() {
0118: return listIterator();
0119: }
0120:
0121: public ListIterator listIterator() {
0122: return new LinkedListIterator(this , 0);
0123: }
0124:
0125: public ListIterator listIterator(int fromIndex) {
0126: return new LinkedListIterator(this , fromIndex);
0127: }
0128:
0129: //-----------------------------------------------------------------------
0130: public int indexOf(Object value) {
0131: int i = 0;
0132: for (Node node = header.next; node != header; node = node.next) {
0133: if (isEqualValue(node.getValue(), value)) {
0134: return i;
0135: }
0136: i++;
0137: }
0138: return -1;
0139: }
0140:
0141: public int lastIndexOf(Object value) {
0142: int i = size - 1;
0143: for (Node node = header.previous; node != header; node = node.previous) {
0144: if (isEqualValue(node.getValue(), value)) {
0145: return i;
0146: }
0147: i--;
0148: }
0149: return -1;
0150: }
0151:
0152: public boolean contains(Object value) {
0153: return indexOf(value) != -1;
0154: }
0155:
0156: public boolean containsAll(Collection coll) {
0157: Iterator it = coll.iterator();
0158: while (it.hasNext()) {
0159: if (contains(it.next()) == false) {
0160: return false;
0161: }
0162: }
0163: return true;
0164: }
0165:
0166: //-----------------------------------------------------------------------
0167: public Object[] toArray() {
0168: return toArray(new Object[size]);
0169: }
0170:
0171: public Object[] toArray(Object[] array) {
0172: // Extend the array if needed
0173: if (array.length < size) {
0174: Class componentType = array.getClass().getComponentType();
0175: array = (Object[]) Array.newInstance(componentType, size);
0176: }
0177: // Copy the values into the array
0178: int i = 0;
0179: for (Node node = header.next; node != header; node = node.next, i++) {
0180: array[i] = node.getValue();
0181: }
0182: // Set the value after the last value to null
0183: if (array.length > size) {
0184: array[size] = null;
0185: }
0186: return array;
0187: }
0188:
0189: /**
0190: * Gets a sublist of the main list.
0191: *
0192: * @param fromIndexInclusive the index to start from
0193: * @param toIndexExclusive the index to end at
0194: * @return the new sublist
0195: */
0196: public List subList(int fromIndexInclusive, int toIndexExclusive) {
0197: return new LinkedSubList(this , fromIndexInclusive,
0198: toIndexExclusive);
0199: }
0200:
0201: //-----------------------------------------------------------------------
0202: public boolean add(Object value) {
0203: addLast(value);
0204: return true;
0205: }
0206:
0207: public void add(int index, Object value) {
0208: Node node = getNode(index, true);
0209: addNodeBefore(node, value);
0210: }
0211:
0212: public boolean addAll(Collection coll) {
0213: return addAll(size, coll);
0214: }
0215:
0216: public boolean addAll(int index, Collection coll) {
0217: Node node = getNode(index, true);
0218: for (Iterator itr = coll.iterator(); itr.hasNext();) {
0219: Object value = itr.next();
0220: addNodeBefore(node, value);
0221: }
0222: return true;
0223: }
0224:
0225: //-----------------------------------------------------------------------
0226: public Object remove(int index) {
0227: Node node = getNode(index, false);
0228: Object oldValue = node.getValue();
0229: removeNode(node);
0230: return oldValue;
0231: }
0232:
0233: public boolean remove(Object value) {
0234: for (Node node = header.next; node != header; node = node.next) {
0235: if (isEqualValue(node.getValue(), value)) {
0236: removeNode(node);
0237: return true;
0238: }
0239: }
0240: return false;
0241: }
0242:
0243: public boolean removeAll(Collection coll) {
0244: boolean modified = false;
0245: Iterator it = iterator();
0246: while (it.hasNext()) {
0247: if (coll.contains(it.next())) {
0248: it.remove();
0249: modified = true;
0250: }
0251: }
0252: return modified;
0253: }
0254:
0255: //-----------------------------------------------------------------------
0256: public boolean retainAll(Collection coll) {
0257: boolean modified = false;
0258: Iterator it = iterator();
0259: while (it.hasNext()) {
0260: if (coll.contains(it.next()) == false) {
0261: it.remove();
0262: modified = true;
0263: }
0264: }
0265: return modified;
0266: }
0267:
0268: public Object set(int index, Object value) {
0269: Node node = getNode(index, false);
0270: Object oldValue = node.getValue();
0271: updateNode(node, value);
0272: return oldValue;
0273: }
0274:
0275: public void clear() {
0276: removeAllNodes();
0277: }
0278:
0279: //-----------------------------------------------------------------------
0280: public Object getFirst() {
0281: Node node = header.next;
0282: if (node == header) {
0283: throw new NoSuchElementException();
0284: }
0285: return node.getValue();
0286: }
0287:
0288: public Object getLast() {
0289: Node node = header.previous;
0290: if (node == header) {
0291: throw new NoSuchElementException();
0292: }
0293: return node.getValue();
0294: }
0295:
0296: public boolean addFirst(Object o) {
0297: addNodeAfter(header, o);
0298: return true;
0299: }
0300:
0301: public boolean addLast(Object o) {
0302: addNodeBefore(header, o);
0303: return true;
0304: }
0305:
0306: public Object removeFirst() {
0307: Node node = header.next;
0308: if (node == header) {
0309: throw new NoSuchElementException();
0310: }
0311: Object oldValue = node.getValue();
0312: removeNode(node);
0313: return oldValue;
0314: }
0315:
0316: public Object removeLast() {
0317: Node node = header.previous;
0318: if (node == header) {
0319: throw new NoSuchElementException();
0320: }
0321: Object oldValue = node.getValue();
0322: removeNode(node);
0323: return oldValue;
0324: }
0325:
0326: //-----------------------------------------------------------------------
0327: public boolean equals(Object obj) {
0328: if (obj == this ) {
0329: return true;
0330: }
0331: if (obj instanceof List == false) {
0332: return false;
0333: }
0334: List other = (List) obj;
0335: if (other.size() != size()) {
0336: return false;
0337: }
0338: ListIterator it1 = listIterator();
0339: ListIterator it2 = other.listIterator();
0340: while (it1.hasNext() && it2.hasNext()) {
0341: Object o1 = it1.next();
0342: Object o2 = it2.next();
0343: if (!(o1 == null ? o2 == null : o1.equals(o2)))
0344: return false;
0345: }
0346: return !(it1.hasNext() || it2.hasNext());
0347: }
0348:
0349: public int hashCode() {
0350: int hashCode = 1;
0351: Iterator it = iterator();
0352: while (it.hasNext()) {
0353: Object obj = it.next();
0354: hashCode = 31 * hashCode
0355: + (obj == null ? 0 : obj.hashCode());
0356: }
0357: return hashCode;
0358: }
0359:
0360: public String toString() {
0361: if (size() == 0) {
0362: return "[]";
0363: }
0364: StringBuffer buf = new StringBuffer(16 * size());
0365: buf.append("[");
0366:
0367: Iterator it = iterator();
0368: boolean hasNext = it.hasNext();
0369: while (hasNext) {
0370: Object value = it.next();
0371: buf.append(value == this ? "(this Collection)" : value);
0372: hasNext = it.hasNext();
0373: if (hasNext) {
0374: buf.append(", ");
0375: }
0376: }
0377: buf.append("]");
0378: return buf.toString();
0379: }
0380:
0381: //-----------------------------------------------------------------------
0382: /**
0383: * Compares two values for equals.
0384: * This implementation uses the equals method.
0385: * Subclasses can override this to match differently.
0386: *
0387: * @param value1 the first value to compare, may be null
0388: * @param value2 the second value to compare, may be null
0389: * @return true if equal
0390: */
0391: protected boolean isEqualValue(Object value1, Object value2) {
0392: return (value1 == value2 || (value1 == null ? false : value1
0393: .equals(value2)));
0394: }
0395:
0396: /**
0397: * Updates the node with a new value.
0398: * This implementation sets the value on the node.
0399: * Subclasses can override this to record the change.
0400: *
0401: * @param node node to update
0402: * @param value new value of the node
0403: */
0404: protected void updateNode(Node node, Object value) {
0405: node.setValue(value);
0406: }
0407:
0408: /**
0409: * Creates a new node with previous, next and element all set to null.
0410: * This implementation creates a new empty Node.
0411: * Subclasses can override this to create a different class.
0412: *
0413: * @return newly created node
0414: */
0415: protected Node createHeaderNode() {
0416: return new Node();
0417: }
0418:
0419: /**
0420: * Creates a new node with the specified properties.
0421: * This implementation creates a new Node with data.
0422: * Subclasses can override this to create a different class.
0423: *
0424: * @param value value of the new node
0425: */
0426: protected Node createNode(Object value) {
0427: return new Node(value);
0428: }
0429:
0430: /**
0431: * Creates a new node with the specified object as its
0432: * <code>value</code> and inserts it before <code>node</code>.
0433: * <p>
0434: * This implementation uses {@link #createNode(Object)} and
0435: * {@link #addNode(AbstractLinkedList.Node,AbstractLinkedList.Node)}.
0436: *
0437: * @param node node to insert before
0438: * @param value value of the newly added node
0439: * @throws NullPointerException if <code>node</code> is null
0440: */
0441: protected void addNodeBefore(Node node, Object value) {
0442: Node newNode = createNode(value);
0443: addNode(newNode, node);
0444: }
0445:
0446: /**
0447: * Creates a new node with the specified object as its
0448: * <code>value</code> and inserts it after <code>node</code>.
0449: * <p>
0450: * This implementation uses {@link #createNode(Object)} and
0451: * {@link #addNode(AbstractLinkedList.Node,AbstractLinkedList.Node)}.
0452: *
0453: * @param node node to insert after
0454: * @param value value of the newly added node
0455: * @throws NullPointerException if <code>node</code> is null
0456: */
0457: protected void addNodeAfter(Node node, Object value) {
0458: Node newNode = createNode(value);
0459: addNode(newNode, node.next);
0460: }
0461:
0462: /**
0463: * Inserts a new node into the list.
0464: *
0465: * @param nodeToInsert new node to insert
0466: * @param insertBeforeNode node to insert before
0467: * @throws NullPointerException if either node is null
0468: */
0469: protected void addNode(Node nodeToInsert, Node insertBeforeNode) {
0470: nodeToInsert.next = insertBeforeNode;
0471: nodeToInsert.previous = insertBeforeNode.previous;
0472: insertBeforeNode.previous.next = nodeToInsert;
0473: insertBeforeNode.previous = nodeToInsert;
0474: size++;
0475: modCount++;
0476: }
0477:
0478: /**
0479: * Removes the specified node from the list.
0480: *
0481: * @param node the node to remove
0482: * @throws NullPointerException if <code>node</code> is null
0483: */
0484: protected void removeNode(Node node) {
0485: node.previous.next = node.next;
0486: node.next.previous = node.previous;
0487: size--;
0488: modCount++;
0489: }
0490:
0491: /**
0492: * Removes all nodes by resetting the circular list marker.
0493: */
0494: protected void removeAllNodes() {
0495: header.next = header;
0496: header.previous = header;
0497: size = 0;
0498: modCount++;
0499: }
0500:
0501: /**
0502: * Gets the node at a particular index.
0503: *
0504: * @param index the index, starting from 0
0505: * @param endMarkerAllowed whether or not the end marker can be returned if
0506: * startIndex is set to the list's size
0507: * @throws IndexOutOfBoundsException if the index is less than 0; equal to
0508: * the size of the list and endMakerAllowed is false; or greater than the
0509: * size of the list
0510: */
0511: protected Node getNode(int index, boolean endMarkerAllowed)
0512: throws IndexOutOfBoundsException {
0513: // Check the index is within the bounds
0514: if (index < 0) {
0515: throw new IndexOutOfBoundsException(
0516: "Couldn't get the node: " + "index (" + index
0517: + ") less than zero.");
0518: }
0519: if (!endMarkerAllowed && index == size) {
0520: throw new IndexOutOfBoundsException(
0521: "Couldn't get the node: " + "index (" + index
0522: + ") is the size of the list.");
0523: }
0524: if (index > size) {
0525: throw new IndexOutOfBoundsException(
0526: "Couldn't get the node: " + "index (" + index
0527: + ") greater than the size of the "
0528: + "list (" + size + ").");
0529: }
0530: // Search the list and get the node
0531: Node node;
0532: if (index < (size / 2)) {
0533: // Search forwards
0534: node = header.next;
0535: for (int currentIndex = 0; currentIndex < index; currentIndex++) {
0536: node = node.next;
0537: }
0538: } else {
0539: // Search backwards
0540: node = header;
0541: for (int currentIndex = size; currentIndex > index; currentIndex--) {
0542: node = node.previous;
0543: }
0544: }
0545: return node;
0546: }
0547:
0548: //-----------------------------------------------------------------------
0549: /**
0550: * Creates an iterator for the sublist.
0551: *
0552: * @param subList the sublist to get an iterator for
0553: */
0554: protected Iterator createSubListIterator(LinkedSubList subList) {
0555: return createSubListListIterator(subList, 0);
0556: }
0557:
0558: /**
0559: * Creates a list iterator for the sublist.
0560: *
0561: * @param subList the sublist to get an iterator for
0562: * @param fromIndex the index to start from, relative to the sublist
0563: */
0564: protected ListIterator createSubListListIterator(
0565: LinkedSubList subList, int fromIndex) {
0566: return new LinkedSubListIterator(subList, fromIndex);
0567: }
0568:
0569: //-----------------------------------------------------------------------
0570: /**
0571: * Serializes the data held in this object to the stream specified.
0572: * <p>
0573: * The first serializable subclass must call this method from
0574: * <code>writeObject</code>.
0575: */
0576: protected void doWriteObject(ObjectOutputStream outputStream)
0577: throws IOException {
0578: // Write the size so we know how many nodes to read back
0579: outputStream.writeInt(size());
0580: for (Iterator itr = iterator(); itr.hasNext();) {
0581: outputStream.writeObject(itr.next());
0582: }
0583: }
0584:
0585: /**
0586: * Deserializes the data held in this object to the stream specified.
0587: * <p>
0588: * The first serializable subclass must call this method from
0589: * <code>readObject</code>.
0590: */
0591: protected void doReadObject(ObjectInputStream inputStream)
0592: throws IOException, ClassNotFoundException {
0593: init();
0594: int size = inputStream.readInt();
0595: for (int i = 0; i < size; i++) {
0596: add(inputStream.readObject());
0597: }
0598: }
0599:
0600: //-----------------------------------------------------------------------
0601: /**
0602: * A node within the linked list.
0603: * <p>
0604: * From Commons Collections 3.1, all access to the <code>value</code> property
0605: * is via the methods on this class.
0606: */
0607: protected static class Node {
0608:
0609: /** A pointer to the node before this node */
0610: protected Node previous;
0611: /** A pointer to the node after this node */
0612: protected Node next;
0613: /** The object contained within this node */
0614: protected Object value;
0615:
0616: /**
0617: * Constructs a new header node.
0618: */
0619: protected Node() {
0620: super ();
0621: previous = this ;
0622: next = this ;
0623: }
0624:
0625: /**
0626: * Constructs a new node.
0627: *
0628: * @param value the value to store
0629: */
0630: protected Node(Object value) {
0631: super ();
0632: this .value = value;
0633: }
0634:
0635: /**
0636: * Constructs a new node.
0637: *
0638: * @param previous the previous node in the list
0639: * @param next the next node in the list
0640: * @param value the value to store
0641: */
0642: protected Node(Node previous, Node next, Object value) {
0643: super ();
0644: this .previous = previous;
0645: this .next = next;
0646: this .value = value;
0647: }
0648:
0649: /**
0650: * Gets the value of the node.
0651: *
0652: * @return the value
0653: * @since Commons Collections 3.1
0654: */
0655: protected Object getValue() {
0656: return value;
0657: }
0658:
0659: /**
0660: * Sets the value of the node.
0661: *
0662: * @param value the value
0663: * @since Commons Collections 3.1
0664: */
0665: protected void setValue(Object value) {
0666: this .value = value;
0667: }
0668:
0669: /**
0670: * Gets the previous node.
0671: *
0672: * @return the previous node
0673: * @since Commons Collections 3.1
0674: */
0675: protected Node getPreviousNode() {
0676: return previous;
0677: }
0678:
0679: /**
0680: * Sets the previous node.
0681: *
0682: * @param previous the previous node
0683: * @since Commons Collections 3.1
0684: */
0685: protected void setPreviousNode(Node previous) {
0686: this .previous = previous;
0687: }
0688:
0689: /**
0690: * Gets the next node.
0691: *
0692: * @return the next node
0693: * @since Commons Collections 3.1
0694: */
0695: protected Node getNextNode() {
0696: return next;
0697: }
0698:
0699: /**
0700: * Sets the next node.
0701: *
0702: * @param next the next node
0703: * @since Commons Collections 3.1
0704: */
0705: protected void setNextNode(Node next) {
0706: this .next = next;
0707: }
0708: }
0709:
0710: //-----------------------------------------------------------------------
0711: /**
0712: * A list iterator over the linked list.
0713: */
0714: protected static class LinkedListIterator implements ListIterator,
0715: OrderedIterator {
0716:
0717: /** The parent list */
0718: protected final AbstractLinkedList parent;
0719:
0720: /**
0721: * The node that will be returned by {@link #next()}. If this is equal
0722: * to {@link AbstractLinkedList#header} then there are no more values to return.
0723: */
0724: protected Node next;
0725:
0726: /**
0727: * The index of {@link #next}.
0728: */
0729: protected int nextIndex;
0730:
0731: /**
0732: * The last node that was returned by {@link #next()} or {@link
0733: * #previous()}. Set to <code>null</code> if {@link #next()} or {@link
0734: * #previous()} haven't been called, or if the node has been removed
0735: * with {@link #remove()} or a new node added with {@link #add(Object)}.
0736: * Should be accessed through {@link #getLastNodeReturned()} to enforce
0737: * this behaviour.
0738: */
0739: protected Node current;
0740:
0741: /**
0742: * The modification count that the list is expected to have. If the list
0743: * doesn't have this count, then a
0744: * {@link java.util.ConcurrentModificationException} may be thrown by
0745: * the operations.
0746: */
0747: protected int expectedModCount;
0748:
0749: /**
0750: * Create a ListIterator for a list.
0751: *
0752: * @param parent the parent list
0753: * @param fromIndex the index to start at
0754: */
0755: protected LinkedListIterator(AbstractLinkedList parent,
0756: int fromIndex) throws IndexOutOfBoundsException {
0757: super ();
0758: this .parent = parent;
0759: this .expectedModCount = parent.modCount;
0760: this .next = parent.getNode(fromIndex, true);
0761: this .nextIndex = fromIndex;
0762: }
0763:
0764: /**
0765: * Checks the modification count of the list is the value that this
0766: * object expects.
0767: *
0768: * @throws ConcurrentModificationException If the list's modification
0769: * count isn't the value that was expected.
0770: */
0771: protected void checkModCount() {
0772: if (parent.modCount != expectedModCount) {
0773: throw new ConcurrentModificationException();
0774: }
0775: }
0776:
0777: /**
0778: * Gets the last node returned.
0779: *
0780: * @throws IllegalStateException If {@link #next()} or
0781: * {@link #previous()} haven't been called, or if the node has been removed
0782: * with {@link #remove()} or a new node added with {@link #add(Object)}.
0783: */
0784: protected Node getLastNodeReturned()
0785: throws IllegalStateException {
0786: if (current == null) {
0787: throw new IllegalStateException();
0788: }
0789: return current;
0790: }
0791:
0792: public boolean hasNext() {
0793: return next != parent.header;
0794: }
0795:
0796: public Object next() {
0797: checkModCount();
0798: if (!hasNext()) {
0799: throw new NoSuchElementException("No element at index "
0800: + nextIndex + ".");
0801: }
0802: Object value = next.getValue();
0803: current = next;
0804: next = next.next;
0805: nextIndex++;
0806: return value;
0807: }
0808:
0809: public boolean hasPrevious() {
0810: return next.previous != parent.header;
0811: }
0812:
0813: public Object previous() {
0814: checkModCount();
0815: if (!hasPrevious()) {
0816: throw new NoSuchElementException(
0817: "Already at start of list.");
0818: }
0819: next = next.previous;
0820: Object value = next.getValue();
0821: current = next;
0822: nextIndex--;
0823: return value;
0824: }
0825:
0826: public int nextIndex() {
0827: return nextIndex;
0828: }
0829:
0830: public int previousIndex() {
0831: // not normally overridden, as relative to nextIndex()
0832: return nextIndex() - 1;
0833: }
0834:
0835: public void remove() {
0836: checkModCount();
0837: if (current == next) {
0838: // remove() following previous()
0839: next = next.next;
0840: parent.removeNode(getLastNodeReturned());
0841: } else {
0842: // remove() following next()
0843: parent.removeNode(getLastNodeReturned());
0844: nextIndex--;
0845: }
0846: current = null;
0847: expectedModCount++;
0848: }
0849:
0850: public void set(Object obj) {
0851: checkModCount();
0852: getLastNodeReturned().setValue(obj);
0853: }
0854:
0855: public void add(Object obj) {
0856: checkModCount();
0857: parent.addNodeBefore(next, obj);
0858: current = null;
0859: nextIndex++;
0860: expectedModCount++;
0861: }
0862:
0863: }
0864:
0865: //-----------------------------------------------------------------------
0866: /**
0867: * A list iterator over the linked sub list.
0868: */
0869: protected static class LinkedSubListIterator extends
0870: LinkedListIterator {
0871:
0872: /** The parent list */
0873: protected final LinkedSubList sub;
0874:
0875: protected LinkedSubListIterator(LinkedSubList sub,
0876: int startIndex) {
0877: super (sub.parent, startIndex + sub.offset);
0878: this .sub = sub;
0879: }
0880:
0881: public boolean hasNext() {
0882: return (nextIndex() < sub.size);
0883: }
0884:
0885: public boolean hasPrevious() {
0886: return (previousIndex() >= 0);
0887: }
0888:
0889: public int nextIndex() {
0890: return (super .nextIndex() - sub.offset);
0891: }
0892:
0893: public void add(Object obj) {
0894: super .add(obj);
0895: sub.expectedModCount = parent.modCount;
0896: sub.size++;
0897: }
0898:
0899: public void remove() {
0900: super .remove();
0901: sub.expectedModCount = parent.modCount;
0902: sub.size--;
0903: }
0904: }
0905:
0906: //-----------------------------------------------------------------------
0907: /**
0908: * The sublist implementation for AbstractLinkedList.
0909: */
0910: protected static class LinkedSubList extends AbstractList {
0911: /** The main list */
0912: AbstractLinkedList parent;
0913: /** Offset from the main list */
0914: int offset;
0915: /** Sublist size */
0916: int size;
0917: /** Sublist modCount */
0918: int expectedModCount;
0919:
0920: protected LinkedSubList(AbstractLinkedList parent,
0921: int fromIndex, int toIndex) {
0922: if (fromIndex < 0) {
0923: throw new IndexOutOfBoundsException("fromIndex = "
0924: + fromIndex);
0925: }
0926: if (toIndex > parent.size()) {
0927: throw new IndexOutOfBoundsException("toIndex = "
0928: + toIndex);
0929: }
0930: if (fromIndex > toIndex) {
0931: throw new IllegalArgumentException("fromIndex("
0932: + fromIndex + ") > toIndex(" + toIndex + ")");
0933: }
0934: this .parent = parent;
0935: this .offset = fromIndex;
0936: this .size = toIndex - fromIndex;
0937: this .expectedModCount = parent.modCount;
0938: }
0939:
0940: public int size() {
0941: checkModCount();
0942: return size;
0943: }
0944:
0945: public Object get(int index) {
0946: rangeCheck(index, size);
0947: checkModCount();
0948: return parent.get(index + offset);
0949: }
0950:
0951: public void add(int index, Object obj) {
0952: rangeCheck(index, size + 1);
0953: checkModCount();
0954: parent.add(index + offset, obj);
0955: expectedModCount = parent.modCount;
0956: size++;
0957: LinkedSubList.this .modCount++;
0958: }
0959:
0960: public Object remove(int index) {
0961: rangeCheck(index, size);
0962: checkModCount();
0963: Object result = parent.remove(index + offset);
0964: expectedModCount = parent.modCount;
0965: size--;
0966: LinkedSubList.this .modCount++;
0967: return result;
0968: }
0969:
0970: public boolean addAll(Collection coll) {
0971: return addAll(size, coll);
0972: }
0973:
0974: public boolean addAll(int index, Collection coll) {
0975: rangeCheck(index, size + 1);
0976: int cSize = coll.size();
0977: if (cSize == 0) {
0978: return false;
0979: }
0980:
0981: checkModCount();
0982: parent.addAll(offset + index, coll);
0983: expectedModCount = parent.modCount;
0984: size += cSize;
0985: LinkedSubList.this .modCount++;
0986: return true;
0987: }
0988:
0989: public Object set(int index, Object obj) {
0990: rangeCheck(index, size);
0991: checkModCount();
0992: return parent.set(index + offset, obj);
0993: }
0994:
0995: public void clear() {
0996: checkModCount();
0997: Iterator it = iterator();
0998: while (it.hasNext()) {
0999: it.next();
1000: it.remove();
1001: }
1002: }
1003:
1004: public Iterator iterator() {
1005: checkModCount();
1006: return parent.createSubListIterator(this );
1007: }
1008:
1009: public ListIterator listIterator(final int index) {
1010: rangeCheck(index, size + 1);
1011: checkModCount();
1012: return parent.createSubListListIterator(this , index);
1013: }
1014:
1015: public List subList(int fromIndexInclusive, int toIndexExclusive) {
1016: return new LinkedSubList(parent, fromIndexInclusive
1017: + offset, toIndexExclusive + offset);
1018: }
1019:
1020: protected void rangeCheck(int index, int beyond) {
1021: if (index < 0 || index >= beyond) {
1022: throw new IndexOutOfBoundsException("Index '" + index
1023: + "' out of bounds for size '" + size + "'");
1024: }
1025: }
1026:
1027: protected void checkModCount() {
1028: if (parent.modCount != expectedModCount) {
1029: throw new ConcurrentModificationException();
1030: }
1031: }
1032: }
1033:
1034: }
|