0001: /*
0002: * Copyright 2002-2004 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;
0017:
0018: import java.io.IOException;
0019: import java.io.ObjectInputStream;
0020: import java.io.ObjectOutputStream;
0021: import java.io.Serializable;
0022: import java.lang.reflect.Array;
0023: import java.util.ArrayList;
0024: import java.util.Collection;
0025: import java.util.ConcurrentModificationException;
0026: import java.util.Iterator;
0027: import java.util.List;
0028: import java.util.ListIterator;
0029: import java.util.NoSuchElementException;
0030: import java.lang.ref.WeakReference;
0031:
0032: /**
0033: * A doubly-linked list implementation of the {@link List} interface,
0034: * supporting a {@link ListIterator} that allows concurrent modifications
0035: * to the underlying list.
0036: * <p>
0037: * Implements all of the optional {@link List} operations, the
0038: * stack/queue/dequeue operations available in {@link java.util.LinkedList}
0039: * and supports a {@link ListIterator} that allows concurrent modifications
0040: * to the underlying list (see {@link #cursor}).
0041: * <p>
0042: * <b>Note that this implementation is not synchronized.</b>
0043: *
0044: * @deprecated Use new version in list subpackage, which has been rewritten
0045: * and now returns the cursor from the listIterator method. Will be removed in v4.0
0046: * @see java.util.LinkedList
0047: * @since Commons Collections 1.0
0048: * @version $Revision: 404858 $ $Date: 2006-05-07 22:40:39 +0100 (Sun, 07 May 2006) $
0049: *
0050: * @author Rodney Waldhoff
0051: * @author Janek Bogucki
0052: * @author Simon Kitching
0053: */
0054: public class CursorableLinkedList implements List, Serializable {
0055: /** Ensure serialization compatibility */
0056: private static final long serialVersionUID = 8836393098519411393L;
0057:
0058: //--- public methods ---------------------------------------------
0059:
0060: /**
0061: * Appends the specified element to the end of this list.
0062: *
0063: * @param o element to be appended to this list.
0064: * @return <tt>true</tt>
0065: */
0066: public boolean add(Object o) {
0067: insertListable(_head.prev(), null, o);
0068: return true;
0069: }
0070:
0071: /**
0072: * Inserts the specified element at the specified position in this list.
0073: * Shifts the element currently at that position (if any) and any subsequent
0074: * elements to the right (adds one to their indices).
0075: *
0076: * @param index index at which the specified element is to be inserted.
0077: * @param element element to be inserted.
0078: *
0079: * @throws ClassCastException if the class of the specified element
0080: * prevents it from being added to this list.
0081: * @throws IllegalArgumentException if some aspect of the specified
0082: * element prevents it from being added to this list.
0083: * @throws IndexOutOfBoundsException if the index is out of range
0084: * (index < 0 || index > size()).
0085: */
0086: public void add(int index, Object element) {
0087: if (index == _size) {
0088: add(element);
0089: } else {
0090: if (index < 0 || index > _size) {
0091: throw new IndexOutOfBoundsException(String
0092: .valueOf(index)
0093: + " < 0 or "
0094: + String.valueOf(index)
0095: + " > "
0096: + _size);
0097: }
0098: Listable succ = (isEmpty() ? null : getListableAt(index));
0099: Listable pred = (null == succ ? null : succ.prev());
0100: insertListable(pred, succ, element);
0101: }
0102: }
0103:
0104: /**
0105: * Appends all of the elements in the specified collection to the end of
0106: * this list, in the order that they are returned by the specified
0107: * {@link Collection}'s {@link Iterator}. The behavior of this operation is
0108: * unspecified if the specified collection is modified while
0109: * the operation is in progress. (Note that this will occur if the
0110: * specified collection is this list, and it's nonempty.)
0111: *
0112: * @param c collection whose elements are to be added to this list.
0113: * @return <tt>true</tt> if this list changed as a result of the call.
0114: *
0115: * @throws ClassCastException if the class of an element in the specified
0116: * collection prevents it from being added to this list.
0117: * @throws IllegalArgumentException if some aspect of an element in the
0118: * specified collection prevents it from being added to this
0119: * list.
0120: */
0121: public boolean addAll(Collection c) {
0122: if (c.isEmpty()) {
0123: return false;
0124: }
0125: Iterator it = c.iterator();
0126: while (it.hasNext()) {
0127: insertListable(_head.prev(), null, it.next());
0128: }
0129: return true;
0130: }
0131:
0132: /**
0133: * Inserts all of the elements in the specified collection into this
0134: * list at the specified position. Shifts the element currently at
0135: * that position (if any) and any subsequent elements to the right
0136: * (increases their indices). The new elements will appear in this
0137: * list in the order that they are returned by the specified
0138: * {@link Collection}'s {@link Iterator}. The behavior of this operation is
0139: * unspecified if the specified collection is modified while the
0140: * operation is in progress. (Note that this will occur if the specified
0141: * collection is this list, and it's nonempty.)
0142: *
0143: * @param index index at which to insert first element from the specified
0144: * collection.
0145: * @param c elements to be inserted into this list.
0146: * @return <tt>true</tt> if this list changed as a result of the call.
0147: *
0148: * @throws ClassCastException if the class of one of elements of the
0149: * specified collection prevents it from being added to this
0150: * list.
0151: * @throws IllegalArgumentException if some aspect of one of elements of
0152: * the specified collection prevents it from being added to
0153: * this list.
0154: * @throws IndexOutOfBoundsException if the index is out of range (index
0155: * < 0 || index > size()).
0156: */
0157: public boolean addAll(int index, Collection c) {
0158: if (c.isEmpty()) {
0159: return false;
0160: } else if (_size == index || _size == 0) {
0161: return addAll(c);
0162: } else {
0163: Listable succ = getListableAt(index);
0164: Listable pred = (null == succ) ? null : succ.prev();
0165: Iterator it = c.iterator();
0166: while (it.hasNext()) {
0167: pred = insertListable(pred, succ, it.next());
0168: }
0169: return true;
0170: }
0171: }
0172:
0173: /**
0174: * Inserts the specified element at the beginning of this list.
0175: * (Equivalent to {@link #add(int,java.lang.Object) <tt>add(0,o)</tt>}).
0176: *
0177: * @param o element to be prepended to this list.
0178: * @return <tt>true</tt>
0179: */
0180: public boolean addFirst(Object o) {
0181: insertListable(null, _head.next(), o);
0182: return true;
0183: }
0184:
0185: /**
0186: * Inserts the specified element at the end of this list.
0187: * (Equivalent to {@link #add(java.lang.Object)}).
0188: *
0189: * @param o element to be appended to this list.
0190: * @return <tt>true</tt>
0191: */
0192: public boolean addLast(Object o) {
0193: insertListable(_head.prev(), null, o);
0194: return true;
0195: }
0196:
0197: /**
0198: * Removes all of the elements from this list. This
0199: * list will be empty after this call returns (unless
0200: * it throws an exception).
0201: */
0202: public void clear() {
0203: /*
0204: // this is the quick way, but would force us
0205: // to break all the cursors
0206: _modCount++;
0207: _head.setNext(null);
0208: _head.setPrev(null);
0209: _size = 0;
0210: */
0211: Iterator it = iterator();
0212: while (it.hasNext()) {
0213: it.next();
0214: it.remove();
0215: }
0216: }
0217:
0218: /**
0219: * Returns <tt>true</tt> if this list contains the specified element.
0220: * More formally, returns <tt>true</tt> if and only if this list contains
0221: * at least one element <tt>e</tt> such that
0222: * <tt>(o==null ? e==null : o.equals(e))</tt>.
0223: *
0224: * @param o element whose presence in this list is to be tested.
0225: * @return <tt>true</tt> if this list contains the specified element.
0226: */
0227: public boolean contains(Object o) {
0228: for (Listable elt = _head.next(), past = null; null != elt
0229: && past != _head.prev(); elt = (past = elt).next()) {
0230: if ((null == o && null == elt.value())
0231: || (o != null && o.equals(elt.value()))) {
0232: return true;
0233: }
0234: }
0235: return false;
0236: }
0237:
0238: /**
0239: * Returns <tt>true</tt> if this list contains all of the elements of the
0240: * specified collection.
0241: *
0242: * @param c collection to be checked for containment in this list.
0243: * @return <tt>true</tt> if this list contains all of the elements of the
0244: * specified collection.
0245: */
0246: public boolean containsAll(Collection c) {
0247: Iterator it = c.iterator();
0248: while (it.hasNext()) {
0249: if (!this .contains(it.next())) {
0250: return false;
0251: }
0252: }
0253: return true;
0254: }
0255:
0256: /**
0257: * Returns a {@link ListIterator} for iterating through the
0258: * elements of this list. Unlike {@link #iterator}, a cursor
0259: * is not bothered by concurrent modifications to the
0260: * underlying list.
0261: * <p>
0262: * Specifically, when elements are added to the list before or
0263: * after the cursor, the cursor simply picks them up automatically.
0264: * When the "current" (i.e., last returned by {@link ListIterator#next}
0265: * or {@link ListIterator#previous}) element of the list is removed,
0266: * the cursor automatically adjusts to the change (invalidating the
0267: * last returned value--i.e., it cannot be removed).
0268: * <p>
0269: * Note that the returned {@link ListIterator} does not support the
0270: * {@link ListIterator#nextIndex} and {@link ListIterator#previousIndex}
0271: * methods (they throw {@link UnsupportedOperationException} when invoked.
0272: * <p>
0273: * Historical Note: In previous versions of this class, the object
0274: * returned from this method was required to be explicitly closed. This
0275: * is no longer necessary.
0276: *
0277: * @see #cursor(int)
0278: * @see #listIterator
0279: * @see CursorableLinkedList.Cursor
0280: */
0281: public CursorableLinkedList.Cursor cursor() {
0282: return new Cursor(0);
0283: }
0284:
0285: /**
0286: * Returns a {@link ListIterator} for iterating through the
0287: * elements of this list, initialized such that
0288: * {@link ListIterator#next} will return the element at
0289: * the specified index (if any) and {@link ListIterator#previous}
0290: * will return the element immediately preceding it (if any).
0291: * Unlike {@link #iterator}, a cursor
0292: * is not bothered by concurrent modifications to the
0293: * underlying list.
0294: *
0295: * @see #cursor
0296: * @see #listIterator(int)
0297: * @see CursorableLinkedList.Cursor
0298: * @throws IndexOutOfBoundsException if the index is out of range (index
0299: * < 0 || index > size()).
0300: */
0301: public CursorableLinkedList.Cursor cursor(int i) {
0302: return new Cursor(i);
0303: }
0304:
0305: /**
0306: * Compares the specified object with this list for equality. Returns
0307: * <tt>true</tt> if and only if the specified object is also a list, both
0308: * lists have the same size, and all corresponding pairs of elements in
0309: * the two lists are <i>equal</i>. (Two elements <tt>e1</tt> and
0310: * <tt>e2</tt> are <i>equal</i> if <tt>(e1==null ? e2==null :
0311: * e1.equals(e2))</tt>.) In other words, two lists are defined to be
0312: * equal if they contain the same elements in the same order. This
0313: * definition ensures that the equals method works properly across
0314: * different implementations of the <tt>List</tt> interface.
0315: *
0316: * @param o the object to be compared for equality with this list.
0317: * @return <tt>true</tt> if the specified object is equal to this list.
0318: */
0319: public boolean equals(Object o) {
0320: if (o == this ) {
0321: return true;
0322: } else if (!(o instanceof List)) {
0323: return false;
0324: }
0325: Iterator it = ((List) o).listIterator();
0326: for (Listable elt = _head.next(), past = null; null != elt
0327: && past != _head.prev(); elt = (past = elt).next()) {
0328: if (!it.hasNext()
0329: || (null == elt.value() ? null != it.next() : !(elt
0330: .value().equals(it.next())))) {
0331: return false;
0332: }
0333: }
0334: return !it.hasNext();
0335: }
0336:
0337: /**
0338: * Returns the element at the specified position in this list.
0339: *
0340: * @param index index of element to return.
0341: * @return the element at the specified position in this list.
0342: *
0343: * @throws IndexOutOfBoundsException if the index is out of range (index
0344: * < 0 || index >= size()).
0345: */
0346: public Object get(int index) {
0347: return getListableAt(index).value();
0348: }
0349:
0350: /**
0351: * Returns the element at the beginning of this list.
0352: */
0353: public Object getFirst() {
0354: try {
0355: return _head.next().value();
0356: } catch (NullPointerException e) {
0357: throw new NoSuchElementException();
0358: }
0359: }
0360:
0361: /**
0362: * Returns the element at the end of this list.
0363: */
0364: public Object getLast() {
0365: try {
0366: return _head.prev().value();
0367: } catch (NullPointerException e) {
0368: throw new NoSuchElementException();
0369: }
0370: }
0371:
0372: /**
0373: * Returns the hash code value for this list. The hash code of a list
0374: * is defined to be the result of the following calculation:
0375: * <pre>
0376: * hashCode = 1;
0377: * Iterator i = list.iterator();
0378: * while (i.hasNext()) {
0379: * Object obj = i.next();
0380: * hashCode = 31*hashCode + (obj==null ? 0 : obj.hashCode());
0381: * }
0382: * </pre>
0383: * This ensures that <tt>list1.equals(list2)</tt> implies that
0384: * <tt>list1.hashCode()==list2.hashCode()</tt> for any two lists,
0385: * <tt>list1</tt> and <tt>list2</tt>, as required by the general
0386: * contract of <tt>Object.hashCode</tt>.
0387: *
0388: * @return the hash code value for this list.
0389: * @see Object#hashCode()
0390: * @see Object#equals(Object)
0391: * @see #equals(Object)
0392: */
0393: public int hashCode() {
0394: int hash = 1;
0395: for (Listable elt = _head.next(), past = null; null != elt
0396: && past != _head.prev(); elt = (past = elt).next()) {
0397: hash = 31
0398: * hash
0399: + (null == elt.value() ? 0 : elt.value().hashCode());
0400: }
0401: return hash;
0402: }
0403:
0404: /**
0405: * Returns the index in this list of the first occurrence of the specified
0406: * element, or -1 if this list does not contain this element.
0407: * More formally, returns the lowest index <tt>i</tt> such that
0408: * <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt>,
0409: * or -1 if there is no such index.
0410: *
0411: * @param o element to search for.
0412: * @return the index in this list of the first occurrence of the specified
0413: * element, or -1 if this list does not contain this element.
0414: */
0415: public int indexOf(Object o) {
0416: int ndx = 0;
0417:
0418: // perform the null check outside of the loop to save checking every
0419: // single time through the loop.
0420: if (null == o) {
0421: for (Listable elt = _head.next(), past = null; null != elt
0422: && past != _head.prev(); elt = (past = elt).next()) {
0423: if (null == elt.value()) {
0424: return ndx;
0425: }
0426: ndx++;
0427: }
0428: } else {
0429:
0430: for (Listable elt = _head.next(), past = null; null != elt
0431: && past != _head.prev(); elt = (past = elt).next()) {
0432: if (o.equals(elt.value())) {
0433: return ndx;
0434: }
0435: ndx++;
0436: }
0437: }
0438: return -1;
0439: }
0440:
0441: /**
0442: * Returns <tt>true</tt> if this list contains no elements.
0443: * @return <tt>true</tt> if this list contains no elements.
0444: */
0445: public boolean isEmpty() {
0446: return (0 == _size);
0447: }
0448:
0449: /**
0450: * Returns a fail-fast iterator.
0451: * @see List#iterator
0452: */
0453: public Iterator iterator() {
0454: return listIterator(0);
0455: }
0456:
0457: /**
0458: * Returns the index in this list of the last occurrence of the specified
0459: * element, or -1 if this list does not contain this element.
0460: * More formally, returns the highest index <tt>i</tt> such that
0461: * <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt>,
0462: * or -1 if there is no such index.
0463: *
0464: * @param o element to search for.
0465: * @return the index in this list of the last occurrence of the specified
0466: * element, or -1 if this list does not contain this element.
0467: */
0468: public int lastIndexOf(Object o) {
0469: int ndx = _size - 1;
0470:
0471: // perform the null check outside of the loop to save checking every
0472: // single time through the loop.
0473: if (null == o) {
0474: for (Listable elt = _head.prev(), past = null; null != elt
0475: && past != _head.next(); elt = (past = elt).prev()) {
0476: if (null == elt.value()) {
0477: return ndx;
0478: }
0479: ndx--;
0480: }
0481: } else {
0482: for (Listable elt = _head.prev(), past = null; null != elt
0483: && past != _head.next(); elt = (past = elt).prev()) {
0484: if (o.equals(elt.value())) {
0485: return ndx;
0486: }
0487: ndx--;
0488: }
0489: }
0490: return -1;
0491: }
0492:
0493: /**
0494: * Returns a fail-fast ListIterator.
0495: * @see List#listIterator
0496: */
0497: public ListIterator listIterator() {
0498: return listIterator(0);
0499: }
0500:
0501: /**
0502: * Returns a fail-fast ListIterator.
0503: * @see List#listIterator(int)
0504: */
0505: public ListIterator listIterator(int index) {
0506: if (index < 0 || index > _size) {
0507: throw new IndexOutOfBoundsException(index + " < 0 or > "
0508: + _size);
0509: }
0510: return new ListIter(index);
0511: }
0512:
0513: /**
0514: * Removes the first occurrence in this list of the specified element.
0515: * If this list does not contain the element, it is
0516: * unchanged. More formally, removes the element with the lowest index i
0517: * such that <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt> (if
0518: * such an element exists).
0519: *
0520: * @param o element to be removed from this list, if present.
0521: * @return <tt>true</tt> if this list contained the specified element.
0522: */
0523: public boolean remove(Object o) {
0524: for (Listable elt = _head.next(), past = null; null != elt
0525: && past != _head.prev(); elt = (past = elt).next()) {
0526: if (null == o && null == elt.value()) {
0527: removeListable(elt);
0528: return true;
0529: } else if (o != null && o.equals(elt.value())) {
0530: removeListable(elt);
0531: return true;
0532: }
0533: }
0534: return false;
0535: }
0536:
0537: /**
0538: * Removes the element at the specified position in this list (optional
0539: * operation). Shifts any subsequent elements to the left (subtracts one
0540: * from their indices). Returns the element that was removed from the
0541: * list.
0542: *
0543: * @param index the index of the element to removed.
0544: * @return the element previously at the specified position.
0545: *
0546: * @throws IndexOutOfBoundsException if the index is out of range (index
0547: * < 0 || index >= size()).
0548: */
0549: public Object remove(int index) {
0550: Listable elt = getListableAt(index);
0551: Object ret = elt.value();
0552: removeListable(elt);
0553: return ret;
0554: }
0555:
0556: /**
0557: * Removes from this list all the elements that are contained in the
0558: * specified collection.
0559: *
0560: * @param c collection that defines which elements will be removed from
0561: * this list.
0562: * @return <tt>true</tt> if this list changed as a result of the call.
0563: */
0564: public boolean removeAll(Collection c) {
0565: if (0 == c.size() || 0 == _size) {
0566: return false;
0567: } else {
0568: boolean changed = false;
0569: Iterator it = iterator();
0570: while (it.hasNext()) {
0571: if (c.contains(it.next())) {
0572: it.remove();
0573: changed = true;
0574: }
0575: }
0576: return changed;
0577: }
0578: }
0579:
0580: /**
0581: * Removes the first element of this list, if any.
0582: */
0583: public Object removeFirst() {
0584: if (_head.next() != null) {
0585: Object val = _head.next().value();
0586: removeListable(_head.next());
0587: return val;
0588: } else {
0589: throw new NoSuchElementException();
0590: }
0591: }
0592:
0593: /**
0594: * Removes the last element of this list, if any.
0595: */
0596: public Object removeLast() {
0597: if (_head.prev() != null) {
0598: Object val = _head.prev().value();
0599: removeListable(_head.prev());
0600: return val;
0601: } else {
0602: throw new NoSuchElementException();
0603: }
0604: }
0605:
0606: /**
0607: * Retains only the elements in this list that are contained in the
0608: * specified collection. In other words, removes
0609: * from this list all the elements that are not contained in the specified
0610: * collection.
0611: *
0612: * @param c collection that defines which elements this set will retain.
0613: *
0614: * @return <tt>true</tt> if this list changed as a result of the call.
0615: */
0616: public boolean retainAll(Collection c) {
0617: boolean changed = false;
0618: Iterator it = iterator();
0619: while (it.hasNext()) {
0620: if (!c.contains(it.next())) {
0621: it.remove();
0622: changed = true;
0623: }
0624: }
0625: return changed;
0626: }
0627:
0628: /**
0629: * Replaces the element at the specified position in this list with the
0630: * specified element.
0631: *
0632: * @param index index of element to replace.
0633: * @param element element to be stored at the specified position.
0634: * @return the element previously at the specified position.
0635: *
0636: * @throws ClassCastException if the class of the specified element
0637: * prevents it from being added to this list.
0638: * @throws IllegalArgumentException if some aspect of the specified
0639: * element prevents it from being added to this list.
0640: * @throws IndexOutOfBoundsException if the index is out of range
0641: * (index < 0 || index >= size()).
0642: */
0643: public Object set(int index, Object element) {
0644: Listable elt = getListableAt(index);
0645: Object val = elt.setValue(element);
0646: broadcastListableChanged(elt);
0647: return val;
0648: }
0649:
0650: /**
0651: * Returns the number of elements in this list.
0652: * @return the number of elements in this list.
0653: */
0654: public int size() {
0655: return _size;
0656: }
0657:
0658: /**
0659: * Returns an array containing all of the elements in this list in proper
0660: * sequence. Obeys the general contract of the {@link Collection#toArray} method.
0661: *
0662: * @return an array containing all of the elements in this list in proper
0663: * sequence.
0664: */
0665: public Object[] toArray() {
0666: Object[] array = new Object[_size];
0667: int i = 0;
0668: for (Listable elt = _head.next(), past = null; null != elt
0669: && past != _head.prev(); elt = (past = elt).next()) {
0670: array[i++] = elt.value();
0671: }
0672: return array;
0673: }
0674:
0675: /**
0676: * Returns an array containing all of the elements in this list in proper
0677: * sequence; the runtime type of the returned array is that of the
0678: * specified array. Obeys the general contract of the
0679: * {@link Collection#toArray} method.
0680: *
0681: * @param a the array into which the elements of this list are to
0682: * be stored, if it is big enough; otherwise, a new array of the
0683: * same runtime type is allocated for this purpose.
0684: * @return an array containing the elements of this list.
0685: * @exception ArrayStoreException
0686: * if the runtime type of the specified array
0687: * is not a supertype of the runtime type of every element in
0688: * this list.
0689: */
0690: public Object[] toArray(Object a[]) {
0691: if (a.length < _size) {
0692: a = (Object[]) Array.newInstance(a.getClass()
0693: .getComponentType(), _size);
0694: }
0695: int i = 0;
0696: for (Listable elt = _head.next(), past = null; null != elt
0697: && past != _head.prev(); elt = (past = elt).next()) {
0698: a[i++] = elt.value();
0699: }
0700: if (a.length > _size) {
0701: a[_size] = null; // should we null out the rest of the array also? java.util.LinkedList doesn't
0702: }
0703: return a;
0704: }
0705:
0706: /**
0707: * Returns a {@link String} representation of this list, suitable for debugging.
0708: * @return a {@link String} representation of this list, suitable for debugging.
0709: */
0710: public String toString() {
0711: StringBuffer buf = new StringBuffer();
0712: buf.append("[");
0713: for (Listable elt = _head.next(), past = null; null != elt
0714: && past != _head.prev(); elt = (past = elt).next()) {
0715: if (_head.next() != elt) {
0716: buf.append(", ");
0717: }
0718: buf.append(elt.value());
0719: }
0720: buf.append("]");
0721: return buf.toString();
0722: }
0723:
0724: /**
0725: * Returns a fail-fast sublist.
0726: * @see List#subList(int,int)
0727: */
0728: public List subList(int i, int j) {
0729: if (i < 0 || j > _size || i > j) {
0730: throw new IndexOutOfBoundsException();
0731: } else if (i == 0 && j == _size) {
0732: return this ;
0733: } else {
0734: return new CursorableSubList(this , i, j);
0735: }
0736: }
0737:
0738: //--- protected methods ------------------------------------------
0739:
0740: /**
0741: * Inserts a new <i>value</i> into my
0742: * list, after the specified <i>before</i> element, and before the
0743: * specified <i>after</i> element
0744: *
0745: * @return the newly created
0746: * {@link org.apache.commons.collections.CursorableLinkedList.Listable}
0747: */
0748: protected Listable insertListable(Listable before, Listable after,
0749: Object value) {
0750: _modCount++;
0751: _size++;
0752: Listable elt = new Listable(before, after, value);
0753: if (null != before) {
0754: before.setNext(elt);
0755: } else {
0756: _head.setNext(elt);
0757: }
0758:
0759: if (null != after) {
0760: after.setPrev(elt);
0761: } else {
0762: _head.setPrev(elt);
0763: }
0764: broadcastListableInserted(elt);
0765: return elt;
0766: }
0767:
0768: /**
0769: * Removes the given
0770: * {@link org.apache.commons.collections.CursorableLinkedList.Listable}
0771: * from my list.
0772: */
0773: protected void removeListable(Listable elt) {
0774: _modCount++;
0775: _size--;
0776: if (_head.next() == elt) {
0777: _head.setNext(elt.next());
0778: }
0779: if (null != elt.next()) {
0780: elt.next().setPrev(elt.prev());
0781: }
0782: if (_head.prev() == elt) {
0783: _head.setPrev(elt.prev());
0784: }
0785: if (null != elt.prev()) {
0786: elt.prev().setNext(elt.next());
0787: }
0788: broadcastListableRemoved(elt);
0789: }
0790:
0791: /**
0792: * Returns the
0793: * {@link org.apache.commons.collections.CursorableLinkedList.Listable}
0794: * at the specified index.
0795: *
0796: * @throws IndexOutOfBoundsException if index is less than zero or
0797: * greater than or equal to the size of this list.
0798: */
0799: protected Listable getListableAt(int index) {
0800: if (index < 0 || index >= _size) {
0801: throw new IndexOutOfBoundsException(String.valueOf(index)
0802: + " < 0 or " + String.valueOf(index) + " >= "
0803: + _size);
0804: }
0805: if (index <= _size / 2) {
0806: Listable elt = _head.next();
0807: for (int i = 0; i < index; i++) {
0808: elt = elt.next();
0809: }
0810: return elt;
0811: } else {
0812: Listable elt = _head.prev();
0813: for (int i = (_size - 1); i > index; i--) {
0814: elt = elt.prev();
0815: }
0816: return elt;
0817: }
0818: }
0819:
0820: /**
0821: * Registers a {@link CursorableLinkedList.Cursor} to be notified
0822: * of changes to this list.
0823: */
0824: protected void registerCursor(Cursor cur) {
0825: // We take this opportunity to clean the _cursors list
0826: // of WeakReference objects to garbage-collected cursors.
0827: for (Iterator it = _cursors.iterator(); it.hasNext();) {
0828: WeakReference ref = (WeakReference) it.next();
0829: if (ref.get() == null) {
0830: it.remove();
0831: }
0832: }
0833:
0834: _cursors.add(new WeakReference(cur));
0835: }
0836:
0837: /**
0838: * Removes a {@link CursorableLinkedList.Cursor} from
0839: * the set of cursors to be notified of changes to this list.
0840: */
0841: protected void unregisterCursor(Cursor cur) {
0842: for (Iterator it = _cursors.iterator(); it.hasNext();) {
0843: WeakReference ref = (WeakReference) it.next();
0844: Cursor cursor = (Cursor) ref.get();
0845: if (cursor == null) {
0846: // some other unrelated cursor object has been
0847: // garbage-collected; let's take the opportunity to
0848: // clean up the cursors list anyway..
0849: it.remove();
0850:
0851: } else if (cursor == cur) {
0852: ref.clear();
0853: it.remove();
0854: break;
0855: }
0856: }
0857: }
0858:
0859: /**
0860: * Informs all of my registered cursors that they are now
0861: * invalid.
0862: */
0863: protected void invalidateCursors() {
0864: Iterator it = _cursors.iterator();
0865: while (it.hasNext()) {
0866: WeakReference ref = (WeakReference) it.next();
0867: Cursor cursor = (Cursor) ref.get();
0868: if (cursor != null) {
0869: // cursor is null if object has been garbage-collected
0870: cursor.invalidate();
0871: ref.clear();
0872: }
0873: it.remove();
0874: }
0875: }
0876:
0877: /**
0878: * Informs all of my registered cursors that the specified
0879: * element was changed.
0880: * @see #set(int,java.lang.Object)
0881: */
0882: protected void broadcastListableChanged(Listable elt) {
0883: Iterator it = _cursors.iterator();
0884: while (it.hasNext()) {
0885: WeakReference ref = (WeakReference) it.next();
0886: Cursor cursor = (Cursor) ref.get();
0887: if (cursor == null) {
0888: it.remove(); // clean up list
0889: } else {
0890: cursor.listableChanged(elt);
0891: }
0892: }
0893: }
0894:
0895: /**
0896: * Informs all of my registered cursors that the specified
0897: * element was just removed from my list.
0898: */
0899: protected void broadcastListableRemoved(Listable elt) {
0900: Iterator it = _cursors.iterator();
0901: while (it.hasNext()) {
0902: WeakReference ref = (WeakReference) it.next();
0903: Cursor cursor = (Cursor) ref.get();
0904: if (cursor == null) {
0905: it.remove(); // clean up list
0906: } else {
0907: cursor.listableRemoved(elt);
0908: }
0909: }
0910: }
0911:
0912: /**
0913: * Informs all of my registered cursors that the specified
0914: * element was just added to my list.
0915: */
0916: protected void broadcastListableInserted(Listable elt) {
0917: Iterator it = _cursors.iterator();
0918: while (it.hasNext()) {
0919: WeakReference ref = (WeakReference) it.next();
0920: Cursor cursor = (Cursor) ref.get();
0921: if (cursor == null) {
0922: it.remove(); // clean up list
0923: } else {
0924: cursor.listableInserted(elt);
0925: }
0926: }
0927: }
0928:
0929: private void writeObject(ObjectOutputStream out) throws IOException {
0930: out.defaultWriteObject();
0931: out.writeInt(_size);
0932: Listable cur = _head.next();
0933: while (cur != null) {
0934: out.writeObject(cur.value());
0935: cur = cur.next();
0936: }
0937: }
0938:
0939: private void readObject(ObjectInputStream in) throws IOException,
0940: ClassNotFoundException {
0941: in.defaultReadObject();
0942: _size = 0;
0943: _modCount = 0;
0944: _cursors = new ArrayList();
0945: _head = new Listable(null, null, null);
0946: int size = in.readInt();
0947: for (int i = 0; i < size; i++) {
0948: this .add(in.readObject());
0949: }
0950: }
0951:
0952: //--- protected attributes ---------------------------------------
0953:
0954: /** The number of elements in me. */
0955: protected transient int _size = 0;
0956:
0957: /**
0958: * A sentry node.
0959: * <p>
0960: * <tt>_head.next()</tt> points to the first element in the list,
0961: * <tt>_head.prev()</tt> to the last. Note that it is possible for
0962: * <tt>_head.next().prev()</tt> and <tt>_head.prev().next()</tt> to be
0963: * non-null, as when I am a sublist for some larger list.
0964: * Use <tt>== _head.next()</tt> and <tt>== _head.prev()</tt> to determine
0965: * if a given
0966: * {@link org.apache.commons.collections.CursorableLinkedList.Listable}
0967: * is the first or last element in the list.
0968: */
0969: protected transient Listable _head = new Listable(null, null, null);
0970:
0971: /** Tracks the number of structural modifications to me. */
0972: protected transient int _modCount = 0;
0973:
0974: /**
0975: * A list of the currently {@link CursorableLinkedList.Cursor}s currently
0976: * open in this list.
0977: */
0978: protected transient List _cursors = new ArrayList();
0979:
0980: //--- inner classes ----------------------------------------------
0981:
0982: static class Listable implements Serializable {
0983: private Listable _prev = null;
0984: private Listable _next = null;
0985: private Object _val = null;
0986:
0987: Listable(Listable prev, Listable next, Object val) {
0988: _prev = prev;
0989: _next = next;
0990: _val = val;
0991: }
0992:
0993: Listable next() {
0994: return _next;
0995: }
0996:
0997: Listable prev() {
0998: return _prev;
0999: }
1000:
1001: Object value() {
1002: return _val;
1003: }
1004:
1005: void setNext(Listable next) {
1006: _next = next;
1007: }
1008:
1009: void setPrev(Listable prev) {
1010: _prev = prev;
1011: }
1012:
1013: Object setValue(Object val) {
1014: Object temp = _val;
1015: _val = val;
1016: return temp;
1017: }
1018: }
1019:
1020: class ListIter implements ListIterator {
1021: Listable _cur = null;
1022: Listable _lastReturned = null;
1023: int _expectedModCount = _modCount;
1024: int _nextIndex = 0;
1025:
1026: ListIter(int index) {
1027: if (index == 0) {
1028: _cur = new Listable(null, _head.next(), null);
1029: _nextIndex = 0;
1030: } else if (index == _size) {
1031: _cur = new Listable(_head.prev(), null, null);
1032: _nextIndex = _size;
1033: } else {
1034: Listable temp = getListableAt(index);
1035: _cur = new Listable(temp.prev(), temp, null);
1036: _nextIndex = index;
1037: }
1038: }
1039:
1040: public Object previous() {
1041: checkForComod();
1042: if (!hasPrevious()) {
1043: throw new NoSuchElementException();
1044: } else {
1045: Object ret = _cur.prev().value();
1046: _lastReturned = _cur.prev();
1047: _cur.setNext(_cur.prev());
1048: _cur.setPrev(_cur.prev().prev());
1049: _nextIndex--;
1050: return ret;
1051: }
1052: }
1053:
1054: public boolean hasNext() {
1055: checkForComod();
1056: return (null != _cur.next() && _cur.prev() != _head.prev());
1057: }
1058:
1059: public Object next() {
1060: checkForComod();
1061: if (!hasNext()) {
1062: throw new NoSuchElementException();
1063: } else {
1064: Object ret = _cur.next().value();
1065: _lastReturned = _cur.next();
1066: _cur.setPrev(_cur.next());
1067: _cur.setNext(_cur.next().next());
1068: _nextIndex++;
1069: return ret;
1070: }
1071: }
1072:
1073: public int previousIndex() {
1074: checkForComod();
1075: if (!hasPrevious()) {
1076: return -1;
1077: }
1078: return _nextIndex - 1;
1079: }
1080:
1081: public boolean hasPrevious() {
1082: checkForComod();
1083: return (null != _cur.prev() && _cur.next() != _head.next());
1084: }
1085:
1086: public void set(Object o) {
1087: checkForComod();
1088: try {
1089: _lastReturned.setValue(o);
1090: } catch (NullPointerException e) {
1091: throw new IllegalStateException();
1092: }
1093: }
1094:
1095: public int nextIndex() {
1096: checkForComod();
1097: if (!hasNext()) {
1098: return size();
1099: }
1100: return _nextIndex;
1101: }
1102:
1103: public void remove() {
1104: checkForComod();
1105: if (null == _lastReturned) {
1106: throw new IllegalStateException();
1107: } else {
1108: _cur.setNext(_lastReturned == _head.prev() ? null
1109: : _lastReturned.next());
1110: _cur.setPrev(_lastReturned == _head.next() ? null
1111: : _lastReturned.prev());
1112: removeListable(_lastReturned);
1113: _lastReturned = null;
1114: _nextIndex--;
1115: _expectedModCount++;
1116: }
1117: }
1118:
1119: public void add(Object o) {
1120: checkForComod();
1121: _cur.setPrev(insertListable(_cur.prev(), _cur.next(), o));
1122: _lastReturned = null;
1123: _nextIndex++;
1124: _expectedModCount++;
1125: }
1126:
1127: protected void checkForComod() {
1128: if (_expectedModCount != _modCount) {
1129: throw new ConcurrentModificationException();
1130: }
1131: }
1132: }
1133:
1134: public class Cursor extends ListIter implements ListIterator {
1135: boolean _valid = false;
1136:
1137: Cursor(int index) {
1138: super (index);
1139: _valid = true;
1140: registerCursor(this );
1141: }
1142:
1143: public int previousIndex() {
1144: throw new UnsupportedOperationException();
1145: }
1146:
1147: public int nextIndex() {
1148: throw new UnsupportedOperationException();
1149: }
1150:
1151: public void add(Object o) {
1152: checkForComod();
1153: Listable elt = insertListable(_cur.prev(), _cur.next(), o);
1154: _cur.setPrev(elt);
1155: _cur.setNext(elt.next());
1156: _lastReturned = null;
1157: _nextIndex++;
1158: _expectedModCount++;
1159: }
1160:
1161: protected void listableRemoved(Listable elt) {
1162: if (null == _head.prev()) {
1163: _cur.setNext(null);
1164: } else if (_cur.next() == elt) {
1165: _cur.setNext(elt.next());
1166: }
1167: if (null == _head.next()) {
1168: _cur.setPrev(null);
1169: } else if (_cur.prev() == elt) {
1170: _cur.setPrev(elt.prev());
1171: }
1172: if (_lastReturned == elt) {
1173: _lastReturned = null;
1174: }
1175: }
1176:
1177: protected void listableInserted(Listable elt) {
1178: if (null == _cur.next() && null == _cur.prev()) {
1179: _cur.setNext(elt);
1180: } else if (_cur.prev() == elt.prev()) {
1181: _cur.setNext(elt);
1182: }
1183: if (_cur.next() == elt.next()) {
1184: _cur.setPrev(elt);
1185: }
1186: if (_lastReturned == elt) {
1187: _lastReturned = null;
1188: }
1189: }
1190:
1191: protected void listableChanged(Listable elt) {
1192: if (_lastReturned == elt) {
1193: _lastReturned = null;
1194: }
1195: }
1196:
1197: protected void checkForComod() {
1198: if (!_valid) {
1199: throw new ConcurrentModificationException();
1200: }
1201: }
1202:
1203: protected void invalidate() {
1204: _valid = false;
1205: }
1206:
1207: /**
1208: * Mark this cursor as no longer being needed. Any resources
1209: * associated with this cursor are immediately released.
1210: * In previous versions of this class, it was mandatory to close
1211: * all cursor objects to avoid memory leaks. It is <i>no longer</i>
1212: * necessary to call this close method; an instance of this class
1213: * can now be treated exactly like a normal iterator.
1214: */
1215: public void close() {
1216: if (_valid) {
1217: _valid = false;
1218: unregisterCursor(this );
1219: }
1220: }
1221: }
1222:
1223: }
1224:
1225: /**
1226: * @deprecated Use new version in list subpackage, which has been rewritten
1227: * and now returns the cursor from the listIterator method. Will be removed in v4.0
1228: */
1229: class CursorableSubList extends CursorableLinkedList implements List {
1230:
1231: //--- constructors -----------------------------------------------
1232:
1233: CursorableSubList(CursorableLinkedList list, int from, int to) {
1234: if (0 > from || list.size() < to) {
1235: throw new IndexOutOfBoundsException();
1236: } else if (from > to) {
1237: throw new IllegalArgumentException();
1238: }
1239: _list = list;
1240: if (from < list.size()) {
1241: _head.setNext(_list.getListableAt(from));
1242: _pre = (null == _head.next()) ? null : _head.next().prev();
1243: } else {
1244: _pre = _list.getListableAt(from - 1);
1245: }
1246: if (from == to) {
1247: _head.setNext(null);
1248: _head.setPrev(null);
1249: if (to < list.size()) {
1250: _post = _list.getListableAt(to);
1251: } else {
1252: _post = null;
1253: }
1254: } else {
1255: _head.setPrev(_list.getListableAt(to - 1));
1256: _post = _head.prev().next();
1257: }
1258: _size = to - from;
1259: _modCount = _list._modCount;
1260: }
1261:
1262: //--- public methods ------------------------------------------
1263:
1264: public void clear() {
1265: checkForComod();
1266: Iterator it = iterator();
1267: while (it.hasNext()) {
1268: it.next();
1269: it.remove();
1270: }
1271: }
1272:
1273: public Iterator iterator() {
1274: checkForComod();
1275: return super .iterator();
1276: }
1277:
1278: public int size() {
1279: checkForComod();
1280: return super .size();
1281: }
1282:
1283: public boolean isEmpty() {
1284: checkForComod();
1285: return super .isEmpty();
1286: }
1287:
1288: public Object[] toArray() {
1289: checkForComod();
1290: return super .toArray();
1291: }
1292:
1293: public Object[] toArray(Object a[]) {
1294: checkForComod();
1295: return super .toArray(a);
1296: }
1297:
1298: public boolean contains(Object o) {
1299: checkForComod();
1300: return super .contains(o);
1301: }
1302:
1303: public boolean remove(Object o) {
1304: checkForComod();
1305: return super .remove(o);
1306: }
1307:
1308: public Object removeFirst() {
1309: checkForComod();
1310: return super .removeFirst();
1311: }
1312:
1313: public Object removeLast() {
1314: checkForComod();
1315: return super .removeLast();
1316: }
1317:
1318: public boolean addAll(Collection c) {
1319: checkForComod();
1320: return super .addAll(c);
1321: }
1322:
1323: public boolean add(Object o) {
1324: checkForComod();
1325: return super .add(o);
1326: }
1327:
1328: public boolean addFirst(Object o) {
1329: checkForComod();
1330: return super .addFirst(o);
1331: }
1332:
1333: public boolean addLast(Object o) {
1334: checkForComod();
1335: return super .addLast(o);
1336: }
1337:
1338: public boolean removeAll(Collection c) {
1339: checkForComod();
1340: return super .removeAll(c);
1341: }
1342:
1343: public boolean containsAll(Collection c) {
1344: checkForComod();
1345: return super .containsAll(c);
1346: }
1347:
1348: public boolean addAll(int index, Collection c) {
1349: checkForComod();
1350: return super .addAll(index, c);
1351: }
1352:
1353: public int hashCode() {
1354: checkForComod();
1355: return super .hashCode();
1356: }
1357:
1358: public boolean retainAll(Collection c) {
1359: checkForComod();
1360: return super .retainAll(c);
1361: }
1362:
1363: public Object set(int index, Object element) {
1364: checkForComod();
1365: return super .set(index, element);
1366: }
1367:
1368: public boolean equals(Object o) {
1369: checkForComod();
1370: return super .equals(o);
1371: }
1372:
1373: public Object get(int index) {
1374: checkForComod();
1375: return super .get(index);
1376: }
1377:
1378: public Object getFirst() {
1379: checkForComod();
1380: return super .getFirst();
1381: }
1382:
1383: public Object getLast() {
1384: checkForComod();
1385: return super .getLast();
1386: }
1387:
1388: public void add(int index, Object element) {
1389: checkForComod();
1390: super .add(index, element);
1391: }
1392:
1393: public ListIterator listIterator(int index) {
1394: checkForComod();
1395: return super .listIterator(index);
1396: }
1397:
1398: public Object remove(int index) {
1399: checkForComod();
1400: return super .remove(index);
1401: }
1402:
1403: public int indexOf(Object o) {
1404: checkForComod();
1405: return super .indexOf(o);
1406: }
1407:
1408: public int lastIndexOf(Object o) {
1409: checkForComod();
1410: return super .lastIndexOf(o);
1411: }
1412:
1413: public ListIterator listIterator() {
1414: checkForComod();
1415: return super .listIterator();
1416: }
1417:
1418: public List subList(int fromIndex, int toIndex) {
1419: checkForComod();
1420: return super .subList(fromIndex, toIndex);
1421: }
1422:
1423: //--- protected methods ------------------------------------------
1424:
1425: /**
1426: * Inserts a new <i>value</i> into my
1427: * list, after the specified <i>before</i> element, and before the
1428: * specified <i>after</i> element
1429: *
1430: * @return the newly created {@link CursorableLinkedList.Listable}
1431: */
1432: protected Listable insertListable(Listable before, Listable after,
1433: Object value) {
1434: _modCount++;
1435: _size++;
1436: Listable elt = _list.insertListable((null == before ? _pre
1437: : before), (null == after ? _post : after), value);
1438: if (null == _head.next()) {
1439: _head.setNext(elt);
1440: _head.setPrev(elt);
1441: }
1442: if (before == _head.prev()) {
1443: _head.setPrev(elt);
1444: }
1445: if (after == _head.next()) {
1446: _head.setNext(elt);
1447: }
1448: broadcastListableInserted(elt);
1449: return elt;
1450: }
1451:
1452: /**
1453: * Removes the given {@link CursorableLinkedList.Listable} from my list.
1454: */
1455: protected void removeListable(Listable elt) {
1456: _modCount++;
1457: _size--;
1458: if (_head.next() == elt && _head.prev() == elt) {
1459: _head.setNext(null);
1460: _head.setPrev(null);
1461: }
1462: if (_head.next() == elt) {
1463: _head.setNext(elt.next());
1464: }
1465: if (_head.prev() == elt) {
1466: _head.setPrev(elt.prev());
1467: }
1468: _list.removeListable(elt);
1469: broadcastListableRemoved(elt);
1470: }
1471:
1472: /**
1473: * Test to see if my underlying list has been modified
1474: * by some other process. If it has, throws a
1475: * {@link ConcurrentModificationException}, otherwise
1476: * quietly returns.
1477: *
1478: * @throws ConcurrentModificationException
1479: */
1480: protected void checkForComod()
1481: throws ConcurrentModificationException {
1482: if (_modCount != _list._modCount) {
1483: throw new ConcurrentModificationException();
1484: }
1485: }
1486:
1487: //--- protected attributes ---------------------------------------
1488:
1489: /** My underlying list */
1490: protected CursorableLinkedList _list = null;
1491:
1492: /** The element in my underlying list preceding the first element in my list. */
1493: protected Listable _pre = null;
1494:
1495: /** The element in my underlying list following the last element in my list. */
1496: protected Listable _post = null;
1497:
1498: }
|