| /* |
| * Licensed to the Apache Software Foundation (ASF) under one or more |
| * contributor license agreements. See the NOTICE file distributed with |
| * this work for additional information regarding copyright ownership. |
| * The ASF licenses this file to You under the Apache License, Version 2.0 |
| * (the "License"); you may not use this file except in compliance with |
| * the License. You may obtain a copy of the License at |
| * |
| * http://www.apache.org/licenses/LICENSE-2.0 |
| * |
| * Unless required by applicable law or agreed to in writing, software |
| * distributed under the License is distributed on an "AS IS" BASIS, |
| * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| * See the License for the specific language governing permissions and |
| * limitations under the License. |
| */ |
| package org.apache.commons.collections; |
| |
| import java.io.IOException; |
| import java.io.ObjectInputStream; |
| import java.io.ObjectOutputStream; |
| import java.io.Serializable; |
| import java.lang.reflect.Array; |
| import java.util.ArrayList; |
| import java.util.Collection; |
| import java.util.ConcurrentModificationException; |
| import java.util.Iterator; |
| import java.util.List; |
| import java.util.ListIterator; |
| import java.util.NoSuchElementException; |
| import java.lang.ref.WeakReference; |
| |
| /** |
| * A doubly-linked list implementation of the {@link List} interface, |
| * supporting a {@link ListIterator} that allows concurrent modifications |
| * to the underlying list. |
| * <p> |
| * Implements all of the optional {@link List} operations, the |
| * stack/queue/dequeue operations available in {@link java.util.LinkedList} |
| * and supports a {@link ListIterator} that allows concurrent modifications |
| * to the underlying list (see {@link #cursor}). |
| * <p> |
| * <b>Note that this implementation is not synchronized.</b> |
| * |
| * @deprecated Use new version in list subpackage, which has been rewritten |
| * and now returns the cursor from the listIterator method. Will be removed in v4.0 |
| * @see java.util.LinkedList |
| * @since Commons Collections 1.0 |
| * @version $Revision$ $Date$ |
| * |
| * @author Rodney Waldhoff |
| * @author Janek Bogucki |
| * @author Simon Kitching |
| */ |
| public class CursorableLinkedList implements List, Serializable { |
| /** Ensure serialization compatibility */ |
| private static final long serialVersionUID = 8836393098519411393L; |
| |
| //--- public methods --------------------------------------------- |
| |
| /** |
| * Appends the specified element to the end of this list. |
| * |
| * @param o element to be appended to this list. |
| * @return <tt>true</tt> |
| */ |
| public boolean add(Object o) { |
| insertListable(_head.prev(),null,o); |
| return true; |
| } |
| |
| /** |
| * Inserts the specified element at the specified position in this list. |
| * Shifts the element currently at that position (if any) and any subsequent |
| * elements to the right (adds one to their indices). |
| * |
| * @param index index at which the specified element is to be inserted. |
| * @param element element to be inserted. |
| * |
| * @throws ClassCastException if the class of the specified element |
| * prevents it from being added to this list. |
| * @throws IllegalArgumentException if some aspect of the specified |
| * element prevents it from being added to this list. |
| * @throws IndexOutOfBoundsException if the index is out of range |
| * (index < 0 || index > size()). |
| */ |
| public void add(int index, Object element) { |
| if(index == _size) { |
| add(element); |
| } else { |
| if(index < 0 || index > _size) { |
| throw new IndexOutOfBoundsException(String.valueOf(index) + " < 0 or " + String.valueOf(index) + " > " + _size); |
| } |
| Listable succ = (isEmpty() ? null : getListableAt(index)); |
| Listable pred = (null == succ ? null : succ.prev()); |
| insertListable(pred,succ,element); |
| } |
| } |
| |
| /** |
| * Appends all of the elements in the specified collection to the end of |
| * this list, in the order that they are returned by the specified |
| * {@link Collection}'s {@link Iterator}. The behavior of this operation is |
| * unspecified if the specified collection is modified while |
| * the operation is in progress. (Note that this will occur if the |
| * specified collection is this list, and it's nonempty.) |
| * |
| * @param c collection whose elements are to be added to this list. |
| * @return <tt>true</tt> if this list changed as a result of the call. |
| * |
| * @throws ClassCastException if the class of an element in the specified |
| * collection prevents it from being added to this list. |
| * @throws IllegalArgumentException if some aspect of an element in the |
| * specified collection prevents it from being added to this |
| * list. |
| */ |
| public boolean addAll(Collection c) { |
| if(c.isEmpty()) { |
| return false; |
| } |
| Iterator it = c.iterator(); |
| while(it.hasNext()) { |
| insertListable(_head.prev(),null,it.next()); |
| } |
| return true; |
| } |
| |
| /** |
| * Inserts all of the elements in the specified collection into this |
| * list at the specified position. Shifts the element currently at |
| * that position (if any) and any subsequent elements to the right |
| * (increases their indices). The new elements will appear in this |
| * list in the order that they are returned by the specified |
| * {@link Collection}'s {@link Iterator}. The behavior of this operation is |
| * unspecified if the specified collection is modified while the |
| * operation is in progress. (Note that this will occur if the specified |
| * collection is this list, and it's nonempty.) |
| * |
| * @param index index at which to insert first element from the specified |
| * collection. |
| * @param c elements to be inserted into this list. |
| * @return <tt>true</tt> if this list changed as a result of the call. |
| * |
| * @throws ClassCastException if the class of one of elements of the |
| * specified collection prevents it from being added to this |
| * list. |
| * @throws IllegalArgumentException if some aspect of one of elements of |
| * the specified collection prevents it from being added to |
| * this list. |
| * @throws IndexOutOfBoundsException if the index is out of range (index |
| * < 0 || index > size()). |
| */ |
| public boolean addAll(int index, Collection c) { |
| if(c.isEmpty()) { |
| return false; |
| } else if(_size == index || _size == 0) { |
| return addAll(c); |
| } else { |
| Listable succ = getListableAt(index); |
| Listable pred = (null == succ) ? null : succ.prev(); |
| Iterator it = c.iterator(); |
| while(it.hasNext()) { |
| pred = insertListable(pred,succ,it.next()); |
| } |
| return true; |
| } |
| } |
| |
| /** |
| * Inserts the specified element at the beginning of this list. |
| * (Equivalent to {@link #add(int,java.lang.Object) <tt>add(0,o)</tt>}). |
| * |
| * @param o element to be prepended to this list. |
| * @return <tt>true</tt> |
| */ |
| public boolean addFirst(Object o) { |
| insertListable(null,_head.next(),o); |
| return true; |
| } |
| |
| /** |
| * Inserts the specified element at the end of this list. |
| * (Equivalent to {@link #add(java.lang.Object)}). |
| * |
| * @param o element to be appended to this list. |
| * @return <tt>true</tt> |
| */ |
| public boolean addLast(Object o) { |
| insertListable(_head.prev(),null,o); |
| return true; |
| } |
| |
| /** |
| * Removes all of the elements from this list. This |
| * list will be empty after this call returns (unless |
| * it throws an exception). |
| */ |
| public void clear() { |
| /* |
| // this is the quick way, but would force us |
| // to break all the cursors |
| _modCount++; |
| _head.setNext(null); |
| _head.setPrev(null); |
| _size = 0; |
| */ |
| Iterator it = iterator(); |
| while(it.hasNext()) { |
| it.next(); |
| it.remove(); |
| } |
| } |
| |
| /** |
| * Returns <tt>true</tt> if this list contains the specified element. |
| * More formally, returns <tt>true</tt> if and only if this list contains |
| * at least one element <tt>e</tt> such that |
| * <tt>(o==null ? e==null : o.equals(e))</tt>. |
| * |
| * @param o element whose presence in this list is to be tested. |
| * @return <tt>true</tt> if this list contains the specified element. |
| */ |
| public boolean contains(Object o) { |
| for(Listable elt = _head.next(), past = null; null != elt && past != _head.prev(); elt = (past = elt).next()) { |
| if((null == o && null == elt.value()) || |
| (o != null && o.equals(elt.value()))) { |
| return true; |
| } |
| } |
| return false; |
| } |
| |
| /** |
| * Returns <tt>true</tt> if this list contains all of the elements of the |
| * specified collection. |
| * |
| * @param c collection to be checked for containment in this list. |
| * @return <tt>true</tt> if this list contains all of the elements of the |
| * specified collection. |
| */ |
| public boolean containsAll(Collection c) { |
| Iterator it = c.iterator(); |
| while(it.hasNext()) { |
| if(!this.contains(it.next())) { |
| return false; |
| } |
| } |
| return true; |
| } |
| |
| /** |
| * Returns a {@link ListIterator} for iterating through the |
| * elements of this list. Unlike {@link #iterator}, a cursor |
| * is not bothered by concurrent modifications to the |
| * underlying list. |
| * <p> |
| * Specifically, when elements are added to the list before or |
| * after the cursor, the cursor simply picks them up automatically. |
| * When the "current" (i.e., last returned by {@link ListIterator#next} |
| * or {@link ListIterator#previous}) element of the list is removed, |
| * the cursor automatically adjusts to the change (invalidating the |
| * last returned value--i.e., it cannot be removed). |
| * <p> |
| * Note that the returned {@link ListIterator} does not support the |
| * {@link ListIterator#nextIndex} and {@link ListIterator#previousIndex} |
| * methods (they throw {@link UnsupportedOperationException} when invoked. |
| * <p> |
| * Historical Note: In previous versions of this class, the object |
| * returned from this method was required to be explicitly closed. This |
| * is no longer necessary. |
| * |
| * @see #cursor(int) |
| * @see #listIterator |
| * @see CursorableLinkedList.Cursor |
| */ |
| public CursorableLinkedList.Cursor cursor() { |
| return new Cursor(0); |
| } |
| |
| /** |
| * Returns a {@link ListIterator} for iterating through the |
| * elements of this list, initialized such that |
| * {@link ListIterator#next} will return the element at |
| * the specified index (if any) and {@link ListIterator#previous} |
| * will return the element immediately preceding it (if any). |
| * Unlike {@link #iterator}, a cursor |
| * is not bothered by concurrent modifications to the |
| * underlying list. |
| * |
| * @see #cursor |
| * @see #listIterator(int) |
| * @see CursorableLinkedList.Cursor |
| * @throws IndexOutOfBoundsException if the index is out of range (index |
| * < 0 || index > size()). |
| */ |
| public CursorableLinkedList.Cursor cursor(int i) { |
| return new Cursor(i); |
| } |
| |
| /** |
| * Compares the specified object with this list for equality. Returns |
| * <tt>true</tt> if and only if the specified object is also a list, both |
| * lists have the same size, and all corresponding pairs of elements in |
| * the two lists are <i>equal</i>. (Two elements <tt>e1</tt> and |
| * <tt>e2</tt> are <i>equal</i> if <tt>(e1==null ? e2==null : |
| * e1.equals(e2))</tt>.) In other words, two lists are defined to be |
| * equal if they contain the same elements in the same order. This |
| * definition ensures that the equals method works properly across |
| * different implementations of the <tt>List</tt> interface. |
| * |
| * @param o the object to be compared for equality with this list. |
| * @return <tt>true</tt> if the specified object is equal to this list. |
| */ |
| public boolean equals(Object o) { |
| if(o == this) { |
| return true; |
| } else if(!(o instanceof List)) { |
| return false; |
| } |
| Iterator it = ((List)o).listIterator(); |
| for(Listable elt = _head.next(), past = null; null != elt && past != _head.prev(); elt = (past = elt).next()) { |
| if(!it.hasNext() || (null == elt.value() ? null != it.next() : !(elt.value().equals(it.next()))) ) { |
| return false; |
| } |
| } |
| return !it.hasNext(); |
| } |
| |
| /** |
| * Returns the element at the specified position in this list. |
| * |
| * @param index index of element to return. |
| * @return the element at the specified position in this list. |
| * |
| * @throws IndexOutOfBoundsException if the index is out of range (index |
| * < 0 || index >= size()). |
| */ |
| public Object get(int index) { |
| return getListableAt(index).value(); |
| } |
| |
| /** |
| * Returns the element at the beginning of this list. |
| */ |
| public Object getFirst() { |
| try { |
| return _head.next().value(); |
| } catch(NullPointerException e) { |
| throw new NoSuchElementException(); |
| } |
| } |
| |
| /** |
| * Returns the element at the end of this list. |
| */ |
| public Object getLast() { |
| try { |
| return _head.prev().value(); |
| } catch(NullPointerException e) { |
| throw new NoSuchElementException(); |
| } |
| } |
| |
| /** |
| * Returns the hash code value for this list. The hash code of a list |
| * is defined to be the result of the following calculation: |
| * <pre> |
| * hashCode = 1; |
| * Iterator i = list.iterator(); |
| * while (i.hasNext()) { |
| * Object obj = i.next(); |
| * hashCode = 31*hashCode + (obj==null ? 0 : obj.hashCode()); |
| * } |
| * </pre> |
| * This ensures that <tt>list1.equals(list2)</tt> implies that |
| * <tt>list1.hashCode()==list2.hashCode()</tt> for any two lists, |
| * <tt>list1</tt> and <tt>list2</tt>, as required by the general |
| * contract of <tt>Object.hashCode</tt>. |
| * |
| * @return the hash code value for this list. |
| * @see Object#hashCode() |
| * @see Object#equals(Object) |
| * @see #equals(Object) |
| */ |
| public int hashCode() { |
| int hash = 1; |
| for(Listable elt = _head.next(), past = null; null != elt && past != _head.prev(); elt = (past = elt).next()) { |
| hash = 31*hash + (null == elt.value() ? 0 : elt.value().hashCode()); |
| } |
| return hash; |
| } |
| |
| /** |
| * Returns the index in this list of the first occurrence of the specified |
| * element, or -1 if this list does not contain this element. |
| * More formally, returns the lowest index <tt>i</tt> such that |
| * <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt>, |
| * or -1 if there is no such index. |
| * |
| * @param o element to search for. |
| * @return the index in this list of the first occurrence of the specified |
| * element, or -1 if this list does not contain this element. |
| */ |
| public int indexOf(Object o) { |
| int ndx = 0; |
| |
| // perform the null check outside of the loop to save checking every |
| // single time through the loop. |
| if (null == o) { |
| for(Listable elt = _head.next(), past = null; null != elt && past != _head.prev(); elt = (past = elt).next()) { |
| if (null == elt.value()) { |
| return ndx; |
| } |
| ndx++; |
| } |
| } else { |
| |
| for(Listable elt = _head.next(), past = null; null != elt && past != _head.prev(); elt = (past = elt).next()) { |
| if (o.equals(elt.value())) { |
| return ndx; |
| } |
| ndx++; |
| } |
| } |
| return -1; |
| } |
| |
| /** |
| * Returns <tt>true</tt> if this list contains no elements. |
| * @return <tt>true</tt> if this list contains no elements. |
| */ |
| public boolean isEmpty() { |
| return(0 == _size); |
| } |
| |
| /** |
| * Returns a fail-fast iterator. |
| * @see List#iterator |
| */ |
| public Iterator iterator() { |
| return listIterator(0); |
| } |
| |
| /** |
| * Returns the index in this list of the last occurrence of the specified |
| * element, or -1 if this list does not contain this element. |
| * More formally, returns the highest index <tt>i</tt> such that |
| * <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt>, |
| * or -1 if there is no such index. |
| * |
| * @param o element to search for. |
| * @return the index in this list of the last occurrence of the specified |
| * element, or -1 if this list does not contain this element. |
| */ |
| public int lastIndexOf(Object o) { |
| int ndx = _size-1; |
| |
| // perform the null check outside of the loop to save checking every |
| // single time through the loop. |
| if (null == o) { |
| for(Listable elt = _head.prev(), past = null; null != elt && past != _head.next(); elt = (past = elt).prev()) { |
| if (null == elt.value()) { |
| return ndx; |
| } |
| ndx--; |
| } |
| } else { |
| for(Listable elt = _head.prev(), past = null; null != elt && past != _head.next(); elt = (past = elt).prev()) { |
| if (o.equals(elt.value())) { |
| return ndx; |
| } |
| ndx--; |
| } |
| } |
| return -1; |
| } |
| |
| /** |
| * Returns a fail-fast ListIterator. |
| * @see List#listIterator |
| */ |
| public ListIterator listIterator() { |
| return listIterator(0); |
| } |
| |
| /** |
| * Returns a fail-fast ListIterator. |
| * @see List#listIterator(int) |
| */ |
| public ListIterator listIterator(int index) { |
| if(index<0 || index > _size) { |
| throw new IndexOutOfBoundsException(index + " < 0 or > " + _size); |
| } |
| return new ListIter(index); |
| } |
| |
| /** |
| * Removes the first occurrence in this list of the specified element. |
| * If this list does not contain the element, it is |
| * unchanged. More formally, removes the element with the lowest index i |
| * such that <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt> (if |
| * such an element exists). |
| * |
| * @param o element to be removed from this list, if present. |
| * @return <tt>true</tt> if this list contained the specified element. |
| */ |
| public boolean remove(Object o) { |
| for(Listable elt = _head.next(), past = null; null != elt && past != _head.prev(); elt = (past = elt).next()) { |
| if(null == o && null == elt.value()) { |
| removeListable(elt); |
| return true; |
| } else if(o != null && o.equals(elt.value())) { |
| removeListable(elt); |
| return true; |
| } |
| } |
| return false; |
| } |
| |
| /** |
| * Removes the element at the specified position in this list (optional |
| * operation). Shifts any subsequent elements to the left (subtracts one |
| * from their indices). Returns the element that was removed from the |
| * list. |
| * |
| * @param index the index of the element to removed. |
| * @return the element previously at the specified position. |
| * |
| * @throws IndexOutOfBoundsException if the index is out of range (index |
| * < 0 || index >= size()). |
| */ |
| public Object remove(int index) { |
| Listable elt = getListableAt(index); |
| Object ret = elt.value(); |
| removeListable(elt); |
| return ret; |
| } |
| |
| /** |
| * Removes from this list all the elements that are contained in the |
| * specified collection. |
| * |
| * @param c collection that defines which elements will be removed from |
| * this list. |
| * @return <tt>true</tt> if this list changed as a result of the call. |
| */ |
| public boolean removeAll(Collection c) { |
| if(0 == c.size() || 0 == _size) { |
| return false; |
| } else { |
| boolean changed = false; |
| Iterator it = iterator(); |
| while(it.hasNext()) { |
| if(c.contains(it.next())) { |
| it.remove(); |
| changed = true; |
| } |
| } |
| return changed; |
| } |
| } |
| |
| /** |
| * Removes the first element of this list, if any. |
| */ |
| public Object removeFirst() { |
| if(_head.next() != null) { |
| Object val = _head.next().value(); |
| removeListable(_head.next()); |
| return val; |
| } else { |
| throw new NoSuchElementException(); |
| } |
| } |
| |
| /** |
| * Removes the last element of this list, if any. |
| */ |
| public Object removeLast() { |
| if(_head.prev() != null) { |
| Object val = _head.prev().value(); |
| removeListable(_head.prev()); |
| return val; |
| } else { |
| throw new NoSuchElementException(); |
| } |
| } |
| |
| /** |
| * Retains only the elements in this list that are contained in the |
| * specified collection. In other words, removes |
| * from this list all the elements that are not contained in the specified |
| * collection. |
| * |
| * @param c collection that defines which elements this set will retain. |
| * |
| * @return <tt>true</tt> if this list changed as a result of the call. |
| */ |
| public boolean retainAll(Collection c) { |
| boolean changed = false; |
| Iterator it = iterator(); |
| while(it.hasNext()) { |
| if(!c.contains(it.next())) { |
| it.remove(); |
| changed = true; |
| } |
| } |
| return changed; |
| } |
| |
| /** |
| * Replaces the element at the specified position in this list with the |
| * specified element. |
| * |
| * @param index index of element to replace. |
| * @param element element to be stored at the specified position. |
| * @return the element previously at the specified position. |
| * |
| * @throws ClassCastException if the class of the specified element |
| * prevents it from being added to this list. |
| * @throws IllegalArgumentException if some aspect of the specified |
| * element prevents it from being added to this list. |
| * @throws IndexOutOfBoundsException if the index is out of range |
| * (index < 0 || index >= size()). |
| */ |
| public Object set(int index, Object element) { |
| Listable elt = getListableAt(index); |
| Object val = elt.setValue(element); |
| broadcastListableChanged(elt); |
| return val; |
| } |
| |
| /** |
| * Returns the number of elements in this list. |
| * @return the number of elements in this list. |
| */ |
| public int size() { |
| return _size; |
| } |
| |
| /** |
| * Returns an array containing all of the elements in this list in proper |
| * sequence. Obeys the general contract of the {@link Collection#toArray} method. |
| * |
| * @return an array containing all of the elements in this list in proper |
| * sequence. |
| */ |
| public Object[] toArray() { |
| Object[] array = new Object[_size]; |
| int i = 0; |
| for(Listable elt = _head.next(), past = null; null != elt && past != _head.prev(); elt = (past = elt).next()) { |
| array[i++] = elt.value(); |
| } |
| return array; |
| } |
| |
| /** |
| * Returns an array containing all of the elements in this list in proper |
| * sequence; the runtime type of the returned array is that of the |
| * specified array. Obeys the general contract of the |
| * {@link Collection#toArray} method. |
| * |
| * @param a the array into which the elements of this list are to |
| * be stored, if it is big enough; otherwise, a new array of the |
| * same runtime type is allocated for this purpose. |
| * @return an array containing the elements of this list. |
| * @throws ArrayStoreException |
| * if the runtime type of the specified array |
| * is not a supertype of the runtime type of every element in |
| * this list. |
| */ |
| public Object[] toArray(Object a[]) { |
| if(a.length < _size) { |
| a = (Object[])Array.newInstance(a.getClass().getComponentType(), _size); |
| } |
| int i = 0; |
| for(Listable elt = _head.next(), past = null; null != elt && past != _head.prev(); elt = (past = elt).next()) { |
| a[i++] = elt.value(); |
| } |
| if(a.length > _size) { |
| a[_size] = null; // should we null out the rest of the array also? java.util.LinkedList doesn't |
| } |
| return a; |
| } |
| |
| /** |
| * Returns a {@link String} representation of this list, suitable for debugging. |
| * @return a {@link String} representation of this list, suitable for debugging. |
| */ |
| public String toString() { |
| StringBuffer buf = new StringBuffer(); |
| buf.append("["); |
| for(Listable elt = _head.next(), past = null; null != elt && past != _head.prev(); elt = (past = elt).next()) { |
| if(_head.next() != elt) { |
| buf.append(", "); |
| } |
| buf.append(elt.value()); |
| } |
| buf.append("]"); |
| return buf.toString(); |
| } |
| |
| /** |
| * Returns a fail-fast sublist. |
| * @see List#subList(int,int) |
| */ |
| public List subList(int i, int j) { |
| if(i < 0 || j > _size || i > j) { |
| throw new IndexOutOfBoundsException(); |
| } else if(i == 0 && j == _size) { |
| return this; |
| } else { |
| return new CursorableSubList(this,i,j); |
| } |
| } |
| |
| //--- protected methods ------------------------------------------ |
| |
| /** |
| * Inserts a new <i>value</i> into my |
| * list, after the specified <i>before</i> element, and before the |
| * specified <i>after</i> element |
| * |
| * @return the newly created |
| * {@link org.apache.commons.collections.CursorableLinkedList.Listable} |
| */ |
| protected Listable insertListable(Listable before, Listable after, Object value) { |
| _modCount++; |
| _size++; |
| Listable elt = new Listable(before,after,value); |
| if(null != before) { |
| before.setNext(elt); |
| } else { |
| _head.setNext(elt); |
| } |
| |
| if(null != after) { |
| after.setPrev(elt); |
| } else { |
| _head.setPrev(elt); |
| } |
| broadcastListableInserted(elt); |
| return elt; |
| } |
| |
| /** |
| * Removes the given |
| * {@link org.apache.commons.collections.CursorableLinkedList.Listable} |
| * from my list. |
| */ |
| protected void removeListable(Listable elt) { |
| _modCount++; |
| _size--; |
| if(_head.next() == elt) { |
| _head.setNext(elt.next()); |
| } |
| if(null != elt.next()) { |
| elt.next().setPrev(elt.prev()); |
| } |
| if(_head.prev() == elt) { |
| _head.setPrev(elt.prev()); |
| } |
| if(null != elt.prev()) { |
| elt.prev().setNext(elt.next()); |
| } |
| broadcastListableRemoved(elt); |
| } |
| |
| /** |
| * Returns the |
| * {@link org.apache.commons.collections.CursorableLinkedList.Listable} |
| * at the specified index. |
| * |
| * @throws IndexOutOfBoundsException if index is less than zero or |
| * greater than or equal to the size of this list. |
| */ |
| protected Listable getListableAt(int index) { |
| if(index < 0 || index >= _size) { |
| throw new IndexOutOfBoundsException(String.valueOf(index) + " < 0 or " + String.valueOf(index) + " >= " + _size); |
| } |
| if(index <=_size/2) { |
| Listable elt = _head.next(); |
| for(int i = 0; i < index; i++) { |
| elt = elt.next(); |
| } |
| return elt; |
| } else { |
| Listable elt = _head.prev(); |
| for(int i = (_size-1); i > index; i--) { |
| elt = elt.prev(); |
| } |
| return elt; |
| } |
| } |
| |
| /** |
| * Registers a {@link CursorableLinkedList.Cursor} to be notified |
| * of changes to this list. |
| */ |
| protected void registerCursor(Cursor cur) { |
| // We take this opportunity to clean the _cursors list |
| // of WeakReference objects to garbage-collected cursors. |
| for (Iterator it = _cursors.iterator(); it.hasNext(); ) { |
| WeakReference ref = (WeakReference) it.next(); |
| if (ref.get() == null) { |
| it.remove(); |
| } |
| } |
| |
| _cursors.add( new WeakReference(cur) ); |
| } |
| |
| /** |
| * Removes a {@link CursorableLinkedList.Cursor} from |
| * the set of cursors to be notified of changes to this list. |
| */ |
| protected void unregisterCursor(Cursor cur) { |
| for (Iterator it = _cursors.iterator(); it.hasNext(); ) { |
| WeakReference ref = (WeakReference) it.next(); |
| Cursor cursor = (Cursor) ref.get(); |
| if (cursor == null) { |
| // some other unrelated cursor object has been |
| // garbage-collected; let's take the opportunity to |
| // clean up the cursors list anyway.. |
| it.remove(); |
| |
| } else if (cursor == cur) { |
| ref.clear(); |
| it.remove(); |
| break; |
| } |
| } |
| } |
| |
| /** |
| * Informs all of my registered cursors that they are now |
| * invalid. |
| */ |
| protected void invalidateCursors() { |
| Iterator it = _cursors.iterator(); |
| while (it.hasNext()) { |
| WeakReference ref = (WeakReference) it.next(); |
| Cursor cursor = (Cursor) ref.get(); |
| if (cursor != null) { |
| // cursor is null if object has been garbage-collected |
| cursor.invalidate(); |
| ref.clear(); |
| } |
| it.remove(); |
| } |
| } |
| |
| /** |
| * Informs all of my registered cursors that the specified |
| * element was changed. |
| * @see #set(int,java.lang.Object) |
| */ |
| protected void broadcastListableChanged(Listable elt) { |
| Iterator it = _cursors.iterator(); |
| while (it.hasNext()) { |
| WeakReference ref = (WeakReference) it.next(); |
| Cursor cursor = (Cursor) ref.get(); |
| if (cursor == null) { |
| it.remove(); // clean up list |
| } else { |
| cursor.listableChanged(elt); |
| } |
| } |
| } |
| |
| /** |
| * Informs all of my registered cursors that the specified |
| * element was just removed from my list. |
| */ |
| protected void broadcastListableRemoved(Listable elt) { |
| Iterator it = _cursors.iterator(); |
| while (it.hasNext()) { |
| WeakReference ref = (WeakReference) it.next(); |
| Cursor cursor = (Cursor) ref.get(); |
| if (cursor == null) { |
| it.remove(); // clean up list |
| } else { |
| cursor.listableRemoved(elt); |
| } |
| } |
| } |
| |
| /** |
| * Informs all of my registered cursors that the specified |
| * element was just added to my list. |
| */ |
| protected void broadcastListableInserted(Listable elt) { |
| Iterator it = _cursors.iterator(); |
| while (it.hasNext()) { |
| WeakReference ref = (WeakReference) it.next(); |
| Cursor cursor = (Cursor) ref.get(); |
| if (cursor == null) { |
| it.remove(); // clean up list |
| } else { |
| cursor.listableInserted(elt); |
| } |
| } |
| } |
| |
| private void writeObject(ObjectOutputStream out) throws IOException { |
| out.defaultWriteObject(); |
| out.writeInt(_size); |
| Listable cur = _head.next(); |
| while (cur != null) { |
| out.writeObject(cur.value()); |
| cur = cur.next(); |
| } |
| } |
| |
| private void readObject(ObjectInputStream in) throws IOException, ClassNotFoundException { |
| in.defaultReadObject(); |
| _size = 0; |
| _modCount = 0; |
| _cursors = new ArrayList(); |
| _head = new Listable(null,null,null); |
| int size = in.readInt(); |
| for (int i=0;i<size;i++) { |
| this.add(in.readObject()); |
| } |
| } |
| |
| //--- protected attributes --------------------------------------- |
| |
| /** The number of elements in me. */ |
| protected transient int _size = 0; |
| |
| /** |
| * A sentry node. |
| * <p> |
| * <tt>_head.next()</tt> points to the first element in the list, |
| * <tt>_head.prev()</tt> to the last. Note that it is possible for |
| * <tt>_head.next().prev()</tt> and <tt>_head.prev().next()</tt> to be |
| * non-null, as when I am a sublist for some larger list. |
| * Use <tt>== _head.next()</tt> and <tt>== _head.prev()</tt> to determine |
| * if a given |
| * {@link org.apache.commons.collections.CursorableLinkedList.Listable} |
| * is the first or last element in the list. |
| */ |
| protected transient Listable _head = new Listable(null,null,null); |
| |
| /** Tracks the number of structural modifications to me. */ |
| protected transient int _modCount = 0; |
| |
| /** |
| * A list of the currently {@link CursorableLinkedList.Cursor}s currently |
| * open in this list. |
| */ |
| protected transient List _cursors = new ArrayList(); |
| |
| //--- inner classes ---------------------------------------------- |
| |
| static class Listable implements Serializable { |
| private Listable _prev = null; |
| private Listable _next = null; |
| private Object _val = null; |
| |
| Listable(Listable prev, Listable next, Object val) { |
| _prev = prev; |
| _next = next; |
| _val = val; |
| } |
| |
| Listable next() { |
| return _next; |
| } |
| |
| Listable prev() { |
| return _prev; |
| } |
| |
| Object value() { |
| return _val; |
| } |
| |
| void setNext(Listable next) { |
| _next = next; |
| } |
| |
| void setPrev(Listable prev) { |
| _prev = prev; |
| } |
| |
| Object setValue(Object val) { |
| Object temp = _val; |
| _val = val; |
| return temp; |
| } |
| } |
| |
| class ListIter implements ListIterator { |
| Listable _cur = null; |
| Listable _lastReturned = null; |
| int _expectedModCount = _modCount; |
| int _nextIndex = 0; |
| |
| ListIter(int index) { |
| if(index == 0) { |
| _cur = new Listable(null,_head.next(),null); |
| _nextIndex = 0; |
| } else if(index == _size) { |
| _cur = new Listable(_head.prev(),null,null); |
| _nextIndex = _size; |
| } else { |
| Listable temp = getListableAt(index); |
| _cur = new Listable(temp.prev(),temp,null); |
| _nextIndex = index; |
| } |
| } |
| |
| public Object previous() { |
| checkForComod(); |
| if(!hasPrevious()) { |
| throw new NoSuchElementException(); |
| } else { |
| Object ret = _cur.prev().value(); |
| _lastReturned = _cur.prev(); |
| _cur.setNext(_cur.prev()); |
| _cur.setPrev(_cur.prev().prev()); |
| _nextIndex--; |
| return ret; |
| } |
| } |
| |
| public boolean hasNext() { |
| checkForComod(); |
| return(null != _cur.next() && _cur.prev() != _head.prev()); |
| } |
| |
| public Object next() { |
| checkForComod(); |
| if(!hasNext()) { |
| throw new NoSuchElementException(); |
| } else { |
| Object ret = _cur.next().value(); |
| _lastReturned = _cur.next(); |
| _cur.setPrev(_cur.next()); |
| _cur.setNext(_cur.next().next()); |
| _nextIndex++; |
| return ret; |
| } |
| } |
| |
| public int previousIndex() { |
| checkForComod(); |
| if(!hasPrevious()) { |
| return -1; |
| } |
| return _nextIndex-1; |
| } |
| |
| public boolean hasPrevious() { |
| checkForComod(); |
| return(null != _cur.prev() && _cur.next() != _head.next()); |
| } |
| |
| public void set(Object o) { |
| checkForComod(); |
| try { |
| _lastReturned.setValue(o); |
| } catch(NullPointerException e) { |
| throw new IllegalStateException(); |
| } |
| } |
| |
| public int nextIndex() { |
| checkForComod(); |
| if(!hasNext()) { |
| return size(); |
| } |
| return _nextIndex; |
| } |
| |
| public void remove() { |
| checkForComod(); |
| if(null == _lastReturned) { |
| throw new IllegalStateException(); |
| } else { |
| _cur.setNext(_lastReturned == _head.prev() ? null : _lastReturned.next()); |
| _cur.setPrev(_lastReturned == _head.next() ? null : _lastReturned.prev()); |
| removeListable(_lastReturned); |
| _lastReturned = null; |
| _nextIndex--; |
| _expectedModCount++; |
| } |
| } |
| |
| public void add(Object o) { |
| checkForComod(); |
| _cur.setPrev(insertListable(_cur.prev(),_cur.next(),o)); |
| _lastReturned = null; |
| _nextIndex++; |
| _expectedModCount++; |
| } |
| |
| protected void checkForComod() { |
| if(_expectedModCount != _modCount) { |
| throw new ConcurrentModificationException(); |
| } |
| } |
| } |
| |
| public class Cursor extends ListIter implements ListIterator { |
| boolean _valid = false; |
| |
| Cursor(int index) { |
| super(index); |
| _valid = true; |
| registerCursor(this); |
| } |
| |
| public int previousIndex() { |
| throw new UnsupportedOperationException(); |
| } |
| |
| public int nextIndex() { |
| throw new UnsupportedOperationException(); |
| } |
| |
| public void add(Object o) { |
| checkForComod(); |
| Listable elt = insertListable(_cur.prev(),_cur.next(),o); |
| _cur.setPrev(elt); |
| _cur.setNext(elt.next()); |
| _lastReturned = null; |
| _nextIndex++; |
| _expectedModCount++; |
| } |
| |
| protected void listableRemoved(Listable elt) { |
| if(null == _head.prev()) { |
| _cur.setNext(null); |
| } else if(_cur.next() == elt) { |
| _cur.setNext(elt.next()); |
| } |
| if(null == _head.next()) { |
| _cur.setPrev(null); |
| } else if(_cur.prev() == elt) { |
| _cur.setPrev(elt.prev()); |
| } |
| if(_lastReturned == elt) { |
| _lastReturned = null; |
| } |
| } |
| |
| protected void listableInserted(Listable elt) { |
| if(null == _cur.next() && null == _cur.prev()) { |
| _cur.setNext(elt); |
| } else if(_cur.prev() == elt.prev()) { |
| _cur.setNext(elt); |
| } |
| if(_cur.next() == elt.next()) { |
| _cur.setPrev(elt); |
| } |
| if(_lastReturned == elt) { |
| _lastReturned = null; |
| } |
| } |
| |
| protected void listableChanged(Listable elt) { |
| if(_lastReturned == elt) { |
| _lastReturned = null; |
| } |
| } |
| |
| protected void checkForComod() { |
| if(!_valid) { |
| throw new ConcurrentModificationException(); |
| } |
| } |
| |
| protected void invalidate() { |
| _valid = false; |
| } |
| |
| /** |
| * Mark this cursor as no longer being needed. Any resources |
| * associated with this cursor are immediately released. |
| * In previous versions of this class, it was mandatory to close |
| * all cursor objects to avoid memory leaks. It is <i>no longer</i> |
| * necessary to call this close method; an instance of this class |
| * can now be treated exactly like a normal iterator. |
| */ |
| public void close() { |
| if(_valid) { |
| _valid = false; |
| unregisterCursor(this); |
| } |
| } |
| } |
| |
| } |
| |
| /** |
| * @deprecated Use new version in list subpackage, which has been rewritten |
| * and now returns the cursor from the listIterator method. Will be removed in v4.0 |
| */ |
| class CursorableSubList extends CursorableLinkedList implements List { |
| |
| //--- constructors ----------------------------------------------- |
| |
| CursorableSubList(CursorableLinkedList list, int from, int to) { |
| if(0 > from || list.size() < to) { |
| throw new IndexOutOfBoundsException(); |
| } else if(from > to) { |
| throw new IllegalArgumentException(); |
| } |
| _list = list; |
| if(from < list.size()) { |
| _head.setNext(_list.getListableAt(from)); |
| _pre = (null == _head.next()) ? null : _head.next().prev(); |
| } else { |
| _pre = _list.getListableAt(from-1); |
| } |
| if(from == to) { |
| _head.setNext(null); |
| _head.setPrev(null); |
| if(to < list.size()) { |
| _post = _list.getListableAt(to); |
| } else { |
| _post = null; |
| } |
| } else { |
| _head.setPrev(_list.getListableAt(to-1)); |
| _post = _head.prev().next(); |
| } |
| _size = to - from; |
| _modCount = _list._modCount; |
| } |
| |
| //--- public methods ------------------------------------------ |
| |
| public void clear() { |
| checkForComod(); |
| Iterator it = iterator(); |
| while(it.hasNext()) { |
| it.next(); |
| it.remove(); |
| } |
| } |
| |
| public Iterator iterator() { |
| checkForComod(); |
| return super.iterator(); |
| } |
| |
| public int size() { |
| checkForComod(); |
| return super.size(); |
| } |
| |
| public boolean isEmpty() { |
| checkForComod(); |
| return super.isEmpty(); |
| } |
| |
| public Object[] toArray() { |
| checkForComod(); |
| return super.toArray(); |
| } |
| |
| public Object[] toArray(Object a[]) { |
| checkForComod(); |
| return super.toArray(a); |
| } |
| |
| public boolean contains(Object o) { |
| checkForComod(); |
| return super.contains(o); |
| } |
| |
| public boolean remove(Object o) { |
| checkForComod(); |
| return super.remove(o); |
| } |
| |
| public Object removeFirst() { |
| checkForComod(); |
| return super.removeFirst(); |
| } |
| |
| public Object removeLast() { |
| checkForComod(); |
| return super.removeLast(); |
| } |
| |
| public boolean addAll(Collection c) { |
| checkForComod(); |
| return super.addAll(c); |
| } |
| |
| public boolean add(Object o) { |
| checkForComod(); |
| return super.add(o); |
| } |
| |
| public boolean addFirst(Object o) { |
| checkForComod(); |
| return super.addFirst(o); |
| } |
| |
| public boolean addLast(Object o) { |
| checkForComod(); |
| return super.addLast(o); |
| } |
| |
| public boolean removeAll(Collection c) { |
| checkForComod(); |
| return super.removeAll(c); |
| } |
| |
| public boolean containsAll(Collection c) { |
| checkForComod(); |
| return super.containsAll(c); |
| } |
| |
| public boolean addAll(int index, Collection c) { |
| checkForComod(); |
| return super.addAll(index,c); |
| } |
| |
| public int hashCode() { |
| checkForComod(); |
| return super.hashCode(); |
| } |
| |
| public boolean retainAll(Collection c) { |
| checkForComod(); |
| return super.retainAll(c); |
| } |
| |
| public Object set(int index, Object element) { |
| checkForComod(); |
| return super.set(index,element); |
| } |
| |
| public boolean equals(Object o) { |
| checkForComod(); |
| return super.equals(o); |
| } |
| |
| public Object get(int index) { |
| checkForComod(); |
| return super.get(index); |
| } |
| |
| public Object getFirst() { |
| checkForComod(); |
| return super.getFirst(); |
| } |
| |
| public Object getLast() { |
| checkForComod(); |
| return super.getLast(); |
| } |
| |
| public void add(int index, Object element) { |
| checkForComod(); |
| super.add(index,element); |
| } |
| |
| public ListIterator listIterator(int index) { |
| checkForComod(); |
| return super.listIterator(index); |
| } |
| |
| public Object remove(int index) { |
| checkForComod(); |
| return super.remove(index); |
| } |
| |
| public int indexOf(Object o) { |
| checkForComod(); |
| return super.indexOf(o); |
| } |
| |
| public int lastIndexOf(Object o) { |
| checkForComod(); |
| return super.lastIndexOf(o); |
| } |
| |
| public ListIterator listIterator() { |
| checkForComod(); |
| return super.listIterator(); |
| } |
| |
| public List subList(int fromIndex, int toIndex) { |
| checkForComod(); |
| return super.subList(fromIndex,toIndex); |
| } |
| |
| //--- protected methods ------------------------------------------ |
| |
| /** |
| * Inserts a new <i>value</i> into my |
| * list, after the specified <i>before</i> element, and before the |
| * specified <i>after</i> element |
| * |
| * @return the newly created {@link CursorableLinkedList.Listable} |
| */ |
| protected Listable insertListable(Listable before, Listable after, Object value) { |
| _modCount++; |
| _size++; |
| Listable elt = _list.insertListable((null == before ? _pre : before), (null == after ? _post : after),value); |
| if(null == _head.next()) { |
| _head.setNext(elt); |
| _head.setPrev(elt); |
| } |
| if(before == _head.prev()) { |
| _head.setPrev(elt); |
| } |
| if(after == _head.next()) { |
| _head.setNext(elt); |
| } |
| broadcastListableInserted(elt); |
| return elt; |
| } |
| |
| /** |
| * Removes the given {@link CursorableLinkedList.Listable} from my list. |
| */ |
| protected void removeListable(Listable elt) { |
| _modCount++; |
| _size--; |
| if(_head.next() == elt && _head.prev() == elt) { |
| _head.setNext(null); |
| _head.setPrev(null); |
| } |
| if(_head.next() == elt) { |
| _head.setNext(elt.next()); |
| } |
| if(_head.prev() == elt) { |
| _head.setPrev(elt.prev()); |
| } |
| _list.removeListable(elt); |
| broadcastListableRemoved(elt); |
| } |
| |
| /** |
| * Test to see if my underlying list has been modified |
| * by some other process. If it has, throws a |
| * {@link ConcurrentModificationException}, otherwise |
| * quietly returns. |
| * |
| * @throws ConcurrentModificationException |
| */ |
| protected void checkForComod() throws ConcurrentModificationException { |
| if(_modCount != _list._modCount) { |
| throw new ConcurrentModificationException(); |
| } |
| } |
| |
| //--- protected attributes --------------------------------------- |
| |
| /** My underlying list */ |
| protected CursorableLinkedList _list = null; |
| |
| /** The element in my underlying list preceding the first element in my list. */ |
| protected Listable _pre = null; |
| |
| /** The element in my underlying list following the last element in my list. */ |
| protected Listable _post = null; |
| |
| } |
