cursorablelinkedlist.java

初级java程序员如果想要更深一步提高自己的实力

     *  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
     *            &lt; 0 || index &gt;= 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 &lt; 0 || index &gt;= 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.
     * @exception 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);
        }