cursorablelinkedlist.java

mysql集群

/*
 *  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.
 */
/*
 * 	This program is free software; you can redistribute it and/or modify it under the terms of 
 * the GNU General Public License as published by the Free Software Foundation; either version 3 of the License, 
 * or (at your option) any later version. 
 * 
 * 	This program is distributed in the hope that it will be useful, 
 * but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  
 * See the GNU General Public License for more details. 
 * 	You should have received a copy of the GNU General Public License along with this program; 
 * if not, write to the Free Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
 */
package com.meidusa.amoeba.net.poolable;

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;

/**
 * <p>
 * This class has been copied from Commons Collections, version 3.1 in order
 * to eliminate the dependency of pool on collections.  It has package scope
 * to prevent its inclusion in the pool public API. The class declaration below
 * should *not* be changed to public.
 * </p>
 * 
 * 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>
 *
 * @see java.util.LinkedList
 * 
 * @version $Revision: 480452 $ $Date: 2006-11-29 00:45:14 -0700 (Wed, 29 Nov 2006) $
 * 
 * @author Rodney Waldhoff
 * @author Janek Bogucki
 * @author Simon Kitching
 */
@SuppressWarnings("unchecked")
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 &lt; 0 || index &gt; 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
     *	      &lt; 0 || index &gt; 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&nbsp;?&nbsp;e==null&nbsp;:&nbsp;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
     *	        &lt; 0 || index &gt; 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
     * 		  &lt; 0 || index &gt;= 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.