Initial revision
git-svn-id: https://svn.apache.org/repos/asf/jakarta/commons/proper/collections/trunk@130432 13f79535-47bb-0310-9956-ffa450edef68
diff --git a/.cvsignore b/.cvsignore
new file mode 100644
index 0000000..3995981
--- /dev/null
+++ b/.cvsignore
@@ -0,0 +1,2 @@
+build
+build.properties
\ No newline at end of file
diff --git a/PROPOSAL.html b/PROPOSAL.html
new file mode 100644
index 0000000..7ae899c
--- /dev/null
+++ b/PROPOSAL.html
@@ -0,0 +1,86 @@
+<html>
+<head>
+<title>Proposal for Collections Package</title>
+</head>
+<body bgcolor="white">
+
+<div align="center">
+<h1>Proposal for <em>Collections</em> Package</h1>
+</div>
+
+<h3>(0) Rationale</h3>
+<p>
+ The Java Collections Framework provides a set of abstract data
+ type interfaces and implementations that offer both a wealth
+ of useful functionality, and a solid foundation for extending
+ that functionality.
+</p>
+<p>
+ Many Jakarta projects have needs or design criteria that extend
+ beyond the core Collections API, such as introducing new abstract
+ data types (e.g., Avalon's BinaryHeap) or changing the behaviour of
+ existing abstract data types (e.g., Struts' FastHashMap).
+</p>
+<p>
+ In keeping with the spirit of the Collections API and of abstract
+ data types in general, these components can and should be shared
+ assets. A Commons package for abstract data types would provide
+ encourage the development and reuse of a robust set of collections
+ classes.
+</p>
+
+<h3>(1) Scope of the Package</h3>
+<p>
+ The package will create and maintain a set of collections and
+ related classes designed to be compatible with the Java Collections
+ Framework, and to be distributed under the ASF license.
+</p>
+
+<h3>(1.5) Interaction With Other Packages</h3>
+
+<p><em>Collections</em> relies only on standard JDK 1.2 (or later) APIs for
+production deployment. It utilizes the JUnit unit testing framework for
+developing and executing unit tests, but this is of interest only to
+developers of the component. Collections will also be a dependency for
+several future proposed components for the Jakarta Commons subproject.
+
+<p>No external configuration files are utilized.</p>
+
+<h3>(2) Initial Source of the Package</h3>
+
+<p>
+ The initial codebase was harvested from existing and purposed
+ Jakarta packages, including the Commons Database Connection Pool,
+ Struts, and Avalon.
+</p>
+
+<p>The proposed package name for the new component is
+<code>org.apache.commons.collections</code>.</p>
+
+
+<h3>(3) Required Jakarta-Commons Resources</h3>
+
+<ul>
+<li>CVS Repository - New directory <code>collections</code> in the
+ <code>jakarta-commons</code> CVS repository. All initial committers
+ are already committers on <code>jakarta-commons</code>, so no
+ additional user setups are required.</li>
+<li>Mailing List - Discussions will take place on the general
+ <em>jakarta-commons@jakarta.apache.org</em> mailing list. To help
+ list subscribers identify messages of interest, it is suggested that
+ the message subject of messages about this component be prefixed with
+ [Collections].</li>
+<li>Bugzilla - New component "Collections" under the "Commons" product
+ category, with appropriate version identifiers as needed.</li>
+<li>Jyve FAQ - New category "commons-collections" (when available).
+</ul>
+
+
+<h3>(4) Initial Committers</h3>
+<ul>
+ <li>Peter Donald</li>
+ <li>Craig McClanahan</li>
+ <li>Rodney Waldhoff</li>
+</ul>
+</body>
+</html>
diff --git a/STATUS.html b/STATUS.html
new file mode 100644
index 0000000..200b95f
--- /dev/null
+++ b/STATUS.html
@@ -0,0 +1,100 @@
+<html>
+<head>
+<title>Status File for Jakarta Commons "Collections" Package</title>
+<head>
+<body bgcolor="white">
+
+
+<div align="center">
+<h1>The Jakarta Commons <em>Collections</em> Package</h1>
+$Id: STATUS.html,v 1.1 2001/04/14 15:39:00 rwaldhoff Exp $<br>
+<a href="#Introduction">[Introduction]</a>
+<a href="#Dependencies">[Dependencies]</a>
+<a href="#Release Info">[Release Info]</a>
+<a href="#Committers">[Committers]</a>
+<a href="#Action Items">[Action Items]</a>
+<br><br>
+</div>
+
+
+<a name="Introduction"></a>
+<h3>1. INTRODUCTION</h3>
+
+<p>The <em>Collections</em> package contains a set of Java classes that
+extend or augment the Java Collections Framework.
+The following classes are included:</p>
+<ul>
+<li><strong>CursorableLinkedList</strong> - an implementing of the java.util.List
+ interface supporting a java.util.ListIterator that allows concurrent
+ modifications to the underlying list.</li>
+</ul>
+
+<a name="Dependencies"></a>
+<h3>2. DEPENDENCIES</h3>
+
+<p>The <em>Collections</em> package is dependent upon the following external
+components for development and use:</p>
+<ul>
+<li><a href="http://java.sun.com/j2se">Java Development Kit</a>
+ (Version 1.2 or later)</li>
+<li><a href="http://www.junit.org">JUnit Testing Framework</a>
+ (Version 3.2 or later) - for unit tests only, not required
+ for deployment</li>
+</ul>
+
+
+<a name="Release Info"></a>
+<h3>3. RELEASE INFO</h3>
+
+<p>Current Release: <strong>Unreleased, CVS Repository Only</strong></p>
+
+<p>Planned Next Release: TBD</p>
+
+<a name="Committers"></a>
+<h3>4. COMMITTERS</h3>
+
+<p>The following individuals are the primary developers and maintainers of this
+component. Developers who plan to use <em>Collections</em> in their own
+projects are encouraged to collaborate on the future development of this
+component to ensure that it continues to meet a variety of needs.</p>
+<ul>
+ <li><a href="mailto:donaldp@apache.org">Peter Donald</a></li>
+ <li><a href="mailto:craigmcc@apache.org">Craig McClanahan</a></li>
+ <li><a href="mailto:rwaldhoff@apache.org">Rodney Waldhoff</a></li>
+</ul>
+
+<a name="Action Items"></a>
+<h3>5. ACTION ITEMS</h3>
+
+<p>The following action items need to be completed prior to a Version 1.0
+release of this component:</p>
+
+<table border="1">
+ <tr>
+ <th width="80%">Action Item</th>
+ <th width="20%">Volunteer</th>
+ </tr>
+
+ <tr>
+ <td><strong>Additional Contributions</strong>. Other collections
+ classes from the existing Jakarta code base.</td>
+ <td align="center">Craig<br>Peter</td>
+ </tr>
+
+ <tr>
+ <td><strong>Generalized Unit Tests</strong>. Create a generic
+ set of Unit Tests that test the standard contracts of the basic
+ Java Collections interfaces (List, Set, etc.)</td>
+ <td align="center">Rod</td>
+ </tr>
+
+ <tr>
+ <td><strong>Install / Use Documentation</strong>. Create simple
+ installation and User's Guide documentation for this package.</td>
+ <td align="center"> </td>
+ </tr>
+
+</table>
+
+</body>
+</html>
diff --git a/build.properties.sample b/build.properties.sample
new file mode 100644
index 0000000..af7e803
--- /dev/null
+++ b/build.properties.sample
@@ -0,0 +1,2 @@
+# junit.jar - JUnit 3.2+ Classpath
+junit.jar=/java/junit/junit.jar
\ No newline at end of file
diff --git a/build.xml b/build.xml
new file mode 100644
index 0000000..1102adf
--- /dev/null
+++ b/build.xml
@@ -0,0 +1,225 @@
+<!-- $Id: build.xml,v 1.1 2001/04/14 15:39:03 rwaldhoff Exp $ -->
+<project name="commons-collections" default="test" basedir=".">
+
+ <!-- patternset describing files to be copied from the doc directory -->
+ <patternset id="patternset-doc"/>
+
+ <!-- patternset describing test classes -->
+ <patternset id="patternset-test-classes">
+ <include name="**/Test*.class"/>
+ </patternset>
+
+ <!-- patternset describing non test classes -->
+ <patternset id="patternset-non-test-classes">
+ <include name="**/*.class"/>
+ <exclude name="**/Test*.class"/>
+ </patternset>
+
+ <!-- patternset describing non test source files (*.java, *html, etc.) -->
+ <patternset id="patternset-javadocable-sources">
+ <include name="**/*"/>
+ <exclude name="**/Test*.java"/>
+ </patternset>
+
+ <!-- ######################################################### -->
+
+ <target name="init">
+ <tstamp/>
+
+ <!-- read properties from the ${user.home}/propfile, if any -->
+ <property name="user-propfile" value="${user.home}/build.properties"/>
+ <property file="${user-propfile}"/>
+ <property name="user-classpath" value=""/>
+ <!-- read properties from the build.properties, if any -->
+ <property file="${basedir}/build.properties"/>
+
+ <!-- command line classpath, if any -->
+ <property name="cp" value=""/>
+
+ <!-- now combine the classpaths -->
+ <property name="classpath" value="${cp}:${user-classpath}:${junit.jar}"/>
+
+ <property name="name" value="commons-collections"/>
+ <property name="Name" value="Commons-Collections"/>
+ <property name="Name-Long" value="Jakarta Commons Collections Package"/>
+
+ <property name="test.entry" value="org.apache.commons.collections.TestAll"/>
+ <property name="test.failonerror" value="true" />
+ <property name="test.runner" value="junit.textui.TestRunner" />
+
+ <property name="workdir" value="${java.io.tmpdir}/buildtemp_${DSTAMP}${TSTAMP}"/>
+ <property name="source" value="${basedir}"/>
+ <property name="source.src" value="${basedir}/src"/>
+ <property name="source.src.java" value="${source.src}/java"/>
+ <property name="source.src.test" value="${source.src}/test"/>
+ <property name="source.doc" value="${basedir}/doc"/>
+ <property name="dest" value="${basedir}/build"/>
+ <property name="dest.classes" value="${dest}/classes"/>
+ <property name="dest.doc" value="${dest}/doc"/>
+ <property name="dest.doc.api" value="${dest.doc}/api"/>
+ <property name="dest.jardir" value="${dest}"/>
+ <property name="dest.jardir.jar" value="${dest.jardir}/${name}.jar"/>
+
+ <available property="available-doc" file="${source.doc}"/> <!-- does this module have docs? -->
+ <available property="available-src-java" file="${source.src.java}"/> <!-- does this module have java src? -->
+ <available property="available-src-test" file="${source.src.test}"/> <!-- does this module have test src? -->
+
+ </target>
+
+ <!-- ######################################################### -->
+
+ <target name="copy-javadoc-source" depends="init" if="available-src-java">
+ <mkdir dir="${javadoc-source-dir}"/>
+ <copy todir="${javadoc-source-dir}" filtering="no">
+ <fileset dir="${source.src.java}">
+ <patternset refid="patternset-javadocable-sources"/>
+ </fileset>
+ </copy>
+ </target>
+
+ <target name="copy-doc" depends="init" if="available-doc">
+ <mkdir dir="${doc-source-dir}/${name}"/>
+ <copy todir="${doc-source-dir}/${name}" filtering="no">
+ <fileset dir="${source.doc}">
+ <patternset refid="patternset-doc"/>
+ </fileset>
+ </copy>
+ </target>
+
+ <!-- ######################################################### -->
+
+ <target name="clean" depends="init,clean-doc,clean-build,clean-dist" description="removes generated files">
+ <delete dir="${dest}"/>
+ </target>
+
+ <target name="clean-doc" depends="init,clean-javadoc">
+ <delete dir="${dest.doc}"/>
+ </target>
+
+ <target name="clean-javadoc" depends="init">
+ <delete dir="${dest.doc.api}"/>
+ </target>
+
+ <target name="clean-build" depends="init">
+ <delete dir="${dest.classes}"/>
+ </target>
+
+ <target name="clean-dist" depends="init">
+ <delete file="${dest.jardir.jar}"/>
+ </target>
+
+ <!-- ######################################################### -->
+
+ <target name="doc" depends="init,doc-copy,doc-javadoc" description="generates javadocs and other documentation">
+ </target>
+
+ <target name="doc-copy" depends="init" if="available-doc">
+ <mkdir dir="${dest.doc}"/>
+ <copy todir="${dest.doc}">
+ <fileset dir="${source.doc}">
+ <patternset refid="patternset-doc"/>
+ </fileset>
+ </copy>
+ </target>
+
+ <target name="doc-javadoc" depends="init" if="available-src-java">
+ <!-- copy all the non-test sources out to the work directory and javadoc that -->
+ <mkdir dir="${workdir}"/>
+ <copy todir="${workdir}">
+ <fileset dir="${source.src.java}">
+ <patternset refid="patternset-javadocable-sources"/>
+ </fileset>
+ </copy>
+ <mkdir dir="${dest.doc.api}"/>
+ <javadoc packagenames="org.*"
+ sourcepath="${workdir}"
+ classpath="${classpath}"
+ destdir="${dest.doc.api}"
+ windowtitle="${Name-Long}"
+ doctitle="${Name-Long}"
+ bottom="<small>Copyright &copy; 2001 Apache Software Foundation. Documenation generated ${TODAY}</small>."
+ public="true"
+ version="true"
+ author="false"
+ splitindex="false"
+ nodeprecated="true"
+ nodeprecatedlist="true"
+ notree="true"
+ noindex="false"
+ nohelp="true"
+ nonavbar="false"
+ serialwarn="false">
+ </javadoc>
+ <delete dir="${workdir}"/>
+ </target>
+
+ <!-- ######################################################### -->
+
+ <target name="build" depends="init,build-java" description="compiles source files"/>
+
+ <target name="build-java" depends="init" if="available-src-java">
+ <mkdir dir="${dest.classes}"/>
+ <javac destdir="${dest.classes}"
+ srcdir="${source.src.java}"
+ classpath="${classpath}"
+ debug="false"
+ deprecation="true"
+ optimize="true"/>
+ </target>
+
+ <target name="build-test" depends="init,build-java" if="available-src-test">
+ <mkdir dir="${dest.classes}"/>
+ <javac destdir="${dest.classes}"
+ srcdir="${source.src.test}"
+ classpath="${classpath}"
+ debug="false"
+ deprecation="true"
+ optimize="true"/>
+ </target>
+
+ <!-- ######################################################### -->
+
+ <target name="test" depends="build-test" if="test.entry" description="runs (junit) unit tests">
+ <!--
+ <junit printsummary="yes" fork="on" haltonfailure="yes">
+ <formatter type="plain" usefile="false"/>
+ <test name="${test.entry}"/>
+ <classpath>
+ <pathelement location="${dest.classes}" />
+ <pathelement path="${classpath}" />
+ <pathelement path="${java.class.path}" />
+ </classpath>
+ </junit>
+ -->
+
+ <java classname="${test.runner}" fork="yes" failonerror="${test.failonerror}">
+ <arg value="${test.entry}"/>
+ <classpath>
+ <pathelement location="${dest.classes}" />
+ <pathelement path="${classpath}" />
+ <pathelement path="${java.class.path}" />
+ </classpath>
+ </java>
+ </target>
+
+ <!-- ######################################################### -->
+
+ <target name="dist" depends="dist-jar" description="builds production jar"/>
+
+ <target name="dist-jar" depends="build">
+ <mkdir dir="${dest.jardir}"/>
+ <mkdir dir="${workdir}"/>
+ <copy todir="${workdir}">
+ <fileset dir="${dest.classes}">
+ <patternset refid="patternset-non-test-classes"/>
+ </fileset>
+ </copy>
+ <jar jarfile="${dest.jardir.jar}">
+ <fileset dir="${workdir}"/>
+ </jar>
+ <delete dir="${workdir}"/>
+ </target>
+
+ <!-- ######################################################### -->
+
+</project>
\ No newline at end of file
diff --git a/src/java/org/apache/commons/collections/CursorableLinkedList.java b/src/java/org/apache/commons/collections/CursorableLinkedList.java
new file mode 100644
index 0000000..59b749c
--- /dev/null
+++ b/src/java/org/apache/commons/collections/CursorableLinkedList.java
@@ -0,0 +1,1415 @@
+/*
+ * $Header: /home/jerenkrantz/tmp/commons/commons-convert/cvs/home/cvs/jakarta-commons//collections/src/java/org/apache/commons/collections/CursorableLinkedList.java,v 1.1 2001/04/14 15:39:24 rwaldhoff Exp $
+ * $Revision: 1.1 $
+ * $Date: 2001/04/14 15:39:24 $
+ *
+ * ====================================================================
+ *
+ * The Apache Software License, Version 1.1
+ *
+ * Copyright (c) 1999-2001 The Apache Software Foundation. All rights
+ * reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ *
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ *
+ * 2. Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in
+ * the documentation and/or other materials provided with the
+ * distribution.
+ *
+ * 3. The end-user documentation included with the redistribution, if
+ * any, must include the following acknowlegement:
+ * "This product includes software developed by the
+ * Apache Software Foundation (http://www.apache.org/)."
+ * Alternately, this acknowlegement may appear in the software itself,
+ * if and wherever such third-party acknowlegements normally appear.
+ *
+ * 4. The names "The Jakarta Project", "Commons", and "Apache Software
+ * Foundation" must not be used to endorse or promote products derived
+ * from this software without prior written permission. For written
+ * permission, please contact apache@apache.org.
+ *
+ * 5. Products derived from this software may not be called "Apache"
+ * nor may "Apache" appear in their names without prior written
+ * permission of the Apache Group.
+ *
+ * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED
+ * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
+ * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+ * DISCLAIMED. IN NO EVENT SHALL THE APACHE SOFTWARE FOUNDATION OR
+ * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+ * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
+ * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
+ * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
+ * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
+ * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
+ * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ * ====================================================================
+ *
+ * This software consists of voluntary contributions made by many
+ * individuals on behalf of the Apache Software Foundation. For more
+ * information on the Apache Software Foundation, please see
+ * <http://www.apache.org/>.
+ *
+ */
+
+// to do: use weak references to cursors in case they aren't closed directly
+
+package org.apache.commons.collections;
+
+import java.util.Collection;
+import java.util.List;
+import java.util.ArrayList;
+import java.util.Iterator;
+import java.util.ListIterator;
+import java.util.ConcurrentModificationException;
+import java.util.NoSuchElementException;
+import java.io.Serializable;
+import java.io.ObjectInputStream;
+import java.io.ObjectOutputStream;
+import java.io.IOException;
+import java.lang.reflect.Array;
+
+/**
+ * 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>
+ *
+ * @author Rodney Waldhoff
+ * @version $Id: CursorableLinkedList.java,v 1.1 2001/04/14 15:39:24 rwaldhoff Exp $
+ * @see java.util.LinkedList
+ */
+public class CursorableLinkedList implements List, Serializable {
+
+ //--- 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 {
+ 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.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>
+ * Clients must close the cursor when they are done using it.
+ * The returned {@link ListIterator} will be an instance of
+ * {@link CursorableLinkedList.Cursor}. To close the cursor,
+ * cast the {@link ListIterator} to {@link CursorableLinkedList.Cursor}
+ * and invoke the {@link CursorableLinkedList.Cursor#close} method.
+ *
+ * @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 preceeding 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;
+ for(Listable elt = _head.next(), past = null; null != elt && past != _head.prev(); elt = (past = elt).next()) {
+ if(null == o && null == elt.value()) {
+ return ndx;
+ } else 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;
+ for(Listable elt = _head.prev(), past = null; null != elt && past != _head.next(); elt = (past = elt).prev()) {
+ if(null == o && null == elt.value()) {
+ return ndx;
+ } else 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.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.
+ * @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
+ *
+ * @returns the newly created {@link 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 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 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();
+ }
+ 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) {
+ _cursors.add(cur);
+ }
+
+ /**
+ * Removes a {@link CursorableLinkedList.Cursor} from
+ * the set of cursors to be notified of changes to this list.
+ */
+ protected void unregisterCursor(Cursor cur) {
+ _cursors.remove(cur);
+ }
+
+ /**
+ * Informs all of my registerd cursors that they are now
+ * invalid.
+ */
+ protected void invalidateCursors() {
+ Iterator it = _cursors.iterator();
+ while(it.hasNext()) {
+ ((Cursor)it.next()).invalidate();
+ it.remove();
+ }
+ }
+
+ /**
+ * Informs all of my registerd 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()) {
+ ((Cursor)it.next()).listableChanged(elt);
+ }
+ }
+
+ /**
+ * Informs all of my registered cursors tha the specifed
+ * element was just removed from my list.
+ */
+ protected void broadcastListableRemoved(Listable elt) {
+ Iterator it = _cursors.iterator();
+ while(it.hasNext()) {
+ ((Cursor)it.next()).listableRemoved(elt);
+ }
+ }
+
+ /**
+ * Informs all of my registered cursors tha the specifed
+ * element was just added to my list.
+ */
+ protected void broadcastListableInserted(Listable elt) {
+ Iterator it = _cursors.iterator();
+ while(it.hasNext()) {
+ ((Cursor)it.next()).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;
+ _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. */
+ transient protected 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 Listable} is the first or last element in the list.
+ */
+ transient protected Listable _head = new Listable(null,null,null);
+
+ /** Tracks the number of structural modifications to me. */
+ protected int _modCount = 0;
+
+ /**
+ * A list of the currently {@link CursorableLinkedList.Cursor}s currently
+ * open in this list.
+ */
+ protected List _cursors = new ArrayList();
+
+ //--- inner classes ----------------------------------------------
+
+ 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;
+ }
+
+ public void close() {
+ if(_valid) {
+ _valid = false;
+ unregisterCursor(this);
+ }
+ }
+ }
+
+}
+
+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
+ *
+ * @returns 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;
+
+}
diff --git a/src/java/org/apache/commons/collections/package.html b/src/java/org/apache/commons/collections/package.html
new file mode 100644
index 0000000..e0c4c4c
--- /dev/null
+++ b/src/java/org/apache/commons/collections/package.html
@@ -0,0 +1,14 @@
+<!-- $Id: package.html,v 1.1 2001/04/14 15:39:24 rwaldhoff Exp $ -->
+<html>
+ <head>
+ <title>Package Documentation for org.apache.commons.collections</title>
+ </head>
+ <body>
+ <p>
+ Java Collections Framework extensions.
+ </p>
+ <p>
+ See also the {@link java.util} package.
+ </p>
+ </body>
+</html>
diff --git a/src/test/org/apache/commons/collections/TestAll.java b/src/test/org/apache/commons/collections/TestAll.java
new file mode 100644
index 0000000..606b798
--- /dev/null
+++ b/src/test/org/apache/commons/collections/TestAll.java
@@ -0,0 +1,85 @@
+/*
+ * $Header: /home/jerenkrantz/tmp/commons/commons-convert/cvs/home/cvs/jakarta-commons//collections/src/test/org/apache/commons/collections/TestAll.java,v 1.1 2001/04/14 15:39:25 rwaldhoff Exp $
+ * $Revision: 1.1 $
+ * $Date: 2001/04/14 15:39:25 $
+ *
+ * ====================================================================
+ *
+ * The Apache Software License, Version 1.1
+ *
+ * Copyright (c) 1999-2001 The Apache Software Foundation. All rights
+ * reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ *
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ *
+ * 2. Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in
+ * the documentation and/or other materials provided with the
+ * distribution.
+ *
+ * 3. The end-user documentation included with the redistribution, if
+ * any, must include the following acknowlegement:
+ * "This product includes software developed by the
+ * Apache Software Foundation (http://www.apache.org/)."
+ * Alternately, this acknowlegement may appear in the software itself,
+ * if and wherever such third-party acknowlegements normally appear.
+ *
+ * 4. The names "The Jakarta Project", "Commons", and "Apache Software
+ * Foundation" must not be used to endorse or promote products derived
+ * from this software without prior written permission. For written
+ * permission, please contact apache@apache.org.
+ *
+ * 5. Products derived from this software may not be called "Apache"
+ * nor may "Apache" appear in their names without prior written
+ * permission of the Apache Group.
+ *
+ * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED
+ * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
+ * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+ * DISCLAIMED. IN NO EVENT SHALL THE APACHE SOFTWARE FOUNDATION OR
+ * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+ * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
+ * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
+ * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
+ * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
+ * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
+ * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ * ====================================================================
+ *
+ * This software consists of voluntary contributions made by many
+ * individuals on behalf of the Apache Software Foundation. For more
+ * information on the Apache Software Foundation, please see
+ * <http://www.apache.org/>.
+ *
+ */
+
+package org.apache.commons.collections;
+
+import junit.framework.*;
+
+/**
+ * @author Rodney Waldhoff
+ * @version $Id: TestAll.java,v 1.1 2001/04/14 15:39:25 rwaldhoff Exp $
+ */
+public class TestAll extends TestCase {
+ public TestAll(String testName) {
+ super(testName);
+ }
+
+ public static Test suite() {
+ TestSuite suite = new TestSuite();
+ suite.addTest(TestCursorableLinkedList.suite());
+ return suite;
+ }
+
+ public static void main(String args[]) {
+ String[] testCaseName = { TestAll.class.getName() };
+ junit.textui.TestRunner.main(testCaseName);
+ }
+}
diff --git a/src/test/org/apache/commons/collections/TestCollection.java b/src/test/org/apache/commons/collections/TestCollection.java
new file mode 100644
index 0000000..96a806c
--- /dev/null
+++ b/src/test/org/apache/commons/collections/TestCollection.java
@@ -0,0 +1,505 @@
+/*
+ * $Header: /home/jerenkrantz/tmp/commons/commons-convert/cvs/home/cvs/jakarta-commons//collections/src/test/org/apache/commons/collections/Attic/TestCollection.java,v 1.1 2001/04/14 15:39:51 rwaldhoff Exp $
+ * $Revision: 1.1 $
+ * $Date: 2001/04/14 15:39:51 $
+ *
+ * ====================================================================
+ *
+ * The Apache Software License, Version 1.1
+ *
+ * Copyright (c) 1999-2001 The Apache Software Foundation. All rights
+ * reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ *
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ *
+ * 2. Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in
+ * the documentation and/or other materials provided with the
+ * distribution.
+ *
+ * 3. The end-user documentation included with the redistribution, if
+ * any, must include the following acknowlegement:
+ * "This product includes software developed by the
+ * Apache Software Foundation (http://www.apache.org/)."
+ * Alternately, this acknowlegement may appear in the software itself,
+ * if and wherever such third-party acknowlegements normally appear.
+ *
+ * 4. The names "The Jakarta Project", "Commons", and "Apache Software
+ * Foundation" must not be used to endorse or promote products derived
+ * from this software without prior written permission. For written
+ * permission, please contact apache@apache.org.
+ *
+ * 5. Products derived from this software may not be called "Apache"
+ * nor may "Apache" appear in their names without prior written
+ * permission of the Apache Group.
+ *
+ * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED
+ * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
+ * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+ * DISCLAIMED. IN NO EVENT SHALL THE APACHE SOFTWARE FOUNDATION OR
+ * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+ * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
+ * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
+ * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
+ * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
+ * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
+ * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ * ====================================================================
+ *
+ * This software consists of voluntary contributions made by many
+ * individuals on behalf of the Apache Software Foundation. For more
+ * information on the Apache Software Foundation, please see
+ * <http://www.apache.org/>.
+ *
+ */
+
+package org.apache.commons.collections;
+
+import junit.framework.*;
+import java.util.Collection;
+import java.util.ArrayList;
+import java.util.Iterator;
+import java.util.NoSuchElementException;
+
+/**
+ * @author Rodney Waldhoff
+ * @version $Id: TestCollection.java,v 1.1 2001/04/14 15:39:51 rwaldhoff Exp $
+ */
+public abstract class TestCollection extends TestCase {
+ public TestCollection(String testName) {
+ super(testName);
+ }
+
+ private Collection _collection = null;
+
+ protected void setCollection(Collection c) {
+ _collection = c;
+ }
+
+ // optional operation
+ public void testCollectionAdd() {
+ boolean added1 = false;
+ try {
+ added1 = _collection.add("element1");
+ } catch(UnsupportedOperationException e) {
+ // ignored, must not be supported
+ } catch(ClassCastException e) {
+ // ignored, type must not be supported
+ } catch(IllegalArgumentException e) {
+ // ignored, element must not be supported
+ } catch(Throwable t) {
+ t.printStackTrace();
+ fail("Collection.add should only throw UnsupportedOperationException, ClassCastException or IllegalArgumentException. Found " + t.toString());
+ }
+
+ boolean added2 = false;
+ try {
+ added2 = _collection.add("element2");
+ } catch(UnsupportedOperationException e) {
+ // ignored, must not be supported
+ } catch(ClassCastException e) {
+ // ignored, type must not be supported
+ } catch(IllegalArgumentException e) {
+ // ignored, element must not be supported
+ } catch(Throwable t) {
+ t.printStackTrace();
+ fail("Collection.add should only throw UnsupportedOperationException, ClassCastException or IllegalArgumentException. Found " + t.toString());
+ }
+ }
+
+ // optional operation
+ public void testCollectionAddAll() {
+ Collection col = new ArrayList();
+ col.add("element1");
+ col.add("element2");
+ col.add("element3");
+ boolean added = false;
+ try {
+ added = _collection.addAll(col);
+ } catch(UnsupportedOperationException e) {
+ // ignored, must not be supported
+ } catch(ClassCastException e) {
+ // ignored, type must not be supported
+ } catch(IllegalArgumentException e) {
+ // ignored, element must not be supported
+ } catch(Throwable t) {
+ t.printStackTrace();
+ fail("Collection.addAll should only throw UnsupportedOperationException, ClassCastException or IllegalArgumentException. Found " + t.toString());
+ }
+ }
+
+ // optional operation
+ public void testCollectionClear() {
+ boolean cleared = false;
+ try {
+ _collection.clear();
+ cleared = true;
+ } catch(UnsupportedOperationException e) {
+ // ignored, must not be supported
+ } catch(Throwable t) {
+ t.printStackTrace();
+ fail("Collection.clear should only throw UnsupportedOperationException. Found " + t.toString());
+ }
+
+ if(cleared) {
+ assert("After Collection.clear(), Collection.isEmpty() should be true.",_collection.isEmpty());
+ }
+
+ boolean added = false;
+ try {
+ added = _collection.add("element1");
+ } catch(UnsupportedOperationException e) {
+ // ignored, must not be supported
+ } catch(ClassCastException e) {
+ // ignored, type must not be supported
+ } catch(IllegalArgumentException e) {
+ // ignored, element must not be supported
+ } catch(Throwable t) {
+ t.printStackTrace();
+ fail("Collection.add should only throw UnsupportedOperationException, ClassCastException or IllegalArgumentException. Found " + t.toString());
+ }
+
+ if(added) {
+ assert("After element is added, Collection.isEmpty() should be false.",!_collection.isEmpty());
+ boolean cleared2 = false;
+ try {
+ _collection.clear();
+ cleared2 = true;
+ } catch(UnsupportedOperationException e) {
+ // ignored, must not be supported
+ } catch(Throwable t) {
+ t.printStackTrace();
+ fail("Collection.clear should only throw UnsupportedOperationException. Found " + t.toString());
+ }
+ if(cleared2) {
+ assert("After Collection.clear(), Collection.isEmpty() should be true.",_collection.isEmpty());
+ }
+ }
+ }
+
+ public void testCollectionContains() {
+ boolean added1 = false;
+ try {
+ added1 = _collection.add("element1");
+ } catch(UnsupportedOperationException e) {
+ // ignored, must not be supported
+ } catch(ClassCastException e) {
+ // ignored, type must not be supported
+ } catch(IllegalArgumentException e) {
+ // ignored, element must not be supported
+ } catch(Throwable t) {
+ t.printStackTrace();
+ fail("Collection.add should only throw UnsupportedOperationException, ClassCastException or IllegalArgumentException. Found " + t.toString());
+ }
+ assert("If an element was added, it should be contained.",added1 == _collection.contains("element1"));
+
+ boolean added2 = false;
+ try {
+ added2 = _collection.add("element2");
+ } catch(UnsupportedOperationException e) {
+ // ignored, must not be supported
+ } catch(ClassCastException e) {
+ // ignored, type must not be supported
+ } catch(IllegalArgumentException e) {
+ // ignored, element must not be supported
+ } catch(Throwable t) {
+ t.printStackTrace();
+ fail("Collection.add should only throw UnsupportedOperationException, ClassCastException or IllegalArgumentException. Found " + t.toString());
+ }
+ assert("If an element was added, it should be contained.",added1 == _collection.contains("element1"));
+ assert("If an element was added, it should be contained.",added2 == _collection.contains("element2"));
+ }
+
+ public void testCollectionContainsAll() {
+ Collection col = new ArrayList();
+ assert("Every Collection should contain all elements of an empty Collection.",_collection.containsAll(col));
+ col.add("element1");
+ assert("Empty Collection shouldn't contain all elements of a non-empty Collection.",!_collection.containsAll(col));
+
+ boolean added1 = false;
+ try {
+ added1 = _collection.add("element1");
+ } catch(UnsupportedOperationException e) {
+ // ignored, must not be supported
+ } catch(ClassCastException e) {
+ // ignored, type must not be supported
+ } catch(IllegalArgumentException e) {
+ // ignored, element must not be supported
+ } catch(Throwable t) {
+ t.printStackTrace();
+ fail("Collection.add should only throw UnsupportedOperationException, ClassCastException or IllegalArgumentException. Found " + t.toString());
+ }
+ if(added1) {
+ assert("Should contain all.",_collection.containsAll(col));
+ }
+
+ col.add("element2");
+ assert("Shouldn't contain all.",!_collection.containsAll(col));
+
+ boolean added2 = false;
+ try {
+ added2 = _collection.add("element2");
+ } catch(UnsupportedOperationException e) {
+ // ignored, must not be supported
+ } catch(ClassCastException e) {
+ // ignored, type must not be supported
+ } catch(IllegalArgumentException e) {
+ // ignored, element must not be supported
+ } catch(Throwable t) {
+ t.printStackTrace();
+ fail("Collection.add should only throw UnsupportedOperationException, ClassCastException or IllegalArgumentException. Found " + t.toString());
+ }
+ if(added1 && added2) {
+ assert("Should contain all.",_collection.containsAll(col));
+ }
+ }
+
+ public void testCollectionEquals() {
+ assertEquals("A Collection should equal itself",_collection,_collection);
+ try {
+ _collection.add("element1");
+ } catch(UnsupportedOperationException e) {
+ // ignored, must not be supported
+ } catch(ClassCastException e) {
+ // ignored, type must not be supported
+ } catch(IllegalArgumentException e) {
+ // ignored, element must not be supported
+ } catch(Throwable t) {
+ t.printStackTrace();
+ fail("Collection.add should only throw UnsupportedOperationException, ClassCastException or IllegalArgumentException. Found " + t.toString());
+ }
+ assertEquals("A Collection should equal itself",_collection,_collection);
+ try {
+ _collection.add("element1");
+ } catch(UnsupportedOperationException e) {
+ // ignored, must not be supported
+ } catch(ClassCastException e) {
+ // ignored, type must not be supported
+ } catch(IllegalArgumentException e) {
+ // ignored, element must not be supported
+ } catch(Throwable t) {
+ t.printStackTrace();
+ fail("Collection.add should only throw UnsupportedOperationException, ClassCastException or IllegalArgumentException. Found " + t.toString());
+ }
+ assertEquals("A Collection should equal itself",_collection,_collection);
+ }
+
+ public void testCollectionHashCode() {
+ assertEquals("A Collection's hashCode should equal itself",_collection.hashCode(),_collection.hashCode());
+ }
+
+ public void testCollectionIsEmpty() {
+ assert("New Collection should be empty.",_collection.isEmpty());
+ boolean added = false;
+ try {
+ added = _collection.add("element1");
+ } catch(UnsupportedOperationException e) {
+ // ignored, must not be supported
+ } catch(ClassCastException e) {
+ // ignored, type must not be supported
+ } catch(IllegalArgumentException e) {
+ // ignored, element must not be supported
+ } catch(Throwable t) {
+ t.printStackTrace();
+ fail("Collection.add should only throw UnsupportedOperationException, ClassCastException or IllegalArgumentException. Found " + t.toString());
+ }
+ if(added) {
+ assert("If an element was added, the Collection.isEmpty() should return false.",!_collection.isEmpty());
+ }
+ }
+
+ public void testCollectionIterator() {
+ Iterator it1 = _collection.iterator();
+ assert("Iterator for empty Collection shouldn't have next.",!it1.hasNext());
+ try {
+ it1.next();
+ fail("Iterator at end of Collection should throw NoSuchElementException when next is called.");
+ } catch(NoSuchElementException e) {
+ // expected
+ } catch(Throwable t) {
+ t.printStackTrace();
+ fail("Collection.iterator.next() should only throw NoSuchElementException. Found " + t.toString());
+ }
+
+ boolean added = false;
+ try {
+ added = _collection.add("element1");
+ } catch(UnsupportedOperationException e) {
+ // ignored, must not be supported
+ } catch(ClassCastException e) {
+ // ignored, type must not be supported
+ } catch(IllegalArgumentException e) {
+ // ignored, element must not be supported
+ } catch(Throwable t) {
+ t.printStackTrace();
+ fail("Collection.add should only throw UnsupportedOperationException, ClassCastException or IllegalArgumentException. Found " + t.toString());
+ }
+ if(added) {
+ Iterator it2 = _collection.iterator();
+ assert("Iterator for non-empty Collection should have next.",it2.hasNext());
+ assertEquals("element1",it2.next());
+ assert("Iterator at end of Collection shouldn't have next.",!it2.hasNext());
+ try {
+ it2.next();
+ fail("Iterator at end of Collection should throw NoSuchElementException when next is called.");
+ } catch(NoSuchElementException e) {
+ // expected
+ } catch(Throwable t) {
+ t.printStackTrace();
+ fail("Collection.iterator.next() should only throw NoSuchElementException. Found " + t.toString());
+ }
+ }
+ }
+
+ // optional operation
+ public void testCollectionRemove() {
+ boolean added = false;
+ try {
+ added = _collection.add("element1");
+ } catch(UnsupportedOperationException e) {
+ // ignored, must not be supported
+ } catch(ClassCastException e) {
+ // ignored, type must not be supported
+ } catch(IllegalArgumentException e) {
+ // ignored, element must not be supported
+ } catch(Throwable t) {
+ t.printStackTrace();
+ fail("Collection.add should only throw UnsupportedOperationException, ClassCastException or IllegalArgumentException. Found " + t.toString());
+ }
+
+ try {
+ assert("Shouldn't be able to remove an element that wasn't added.",!_collection.remove("element2"));
+ } catch(UnsupportedOperationException e) {
+ } catch(Throwable t) {
+ t.printStackTrace();
+ fail("Collection.remove should only throw UnsupportedOperationException. Found " + t.toString());
+ }
+
+ try {
+ assert("If added, should be removed by call to remove.",added == _collection.remove("element1"));
+ assert("If removed, shouldn't be contained.",!_collection.contains("element1"));
+ } catch(UnsupportedOperationException e) {
+ } catch(Throwable t) {
+ t.printStackTrace();
+ fail("Collection.remove should only throw UnsupportedOperationException. Found " + t.toString());
+ }
+ }
+
+ // optional operation
+ public void testCollectionRemoveAll() {
+ assert("Initial Collection is empty.",_collection.isEmpty());
+ try {
+ _collection.removeAll(_collection);
+ } catch(UnsupportedOperationException e) {
+ // expected
+ } catch(Throwable t) {
+ t.printStackTrace();
+ fail("Collection.removeAll should only throw UnsupportedOperationException. Found " + t.toString());
+ }
+ assert("Collection is still empty.",_collection.isEmpty());
+
+ boolean added = false;
+ try {
+ added = _collection.add("element1");
+ } catch(UnsupportedOperationException e) {
+ // ignored, must not be supported
+ } catch(ClassCastException e) {
+ // ignored, type must not be supported
+ } catch(IllegalArgumentException e) {
+ // ignored, element must not be supported
+ } catch(Throwable t) {
+ t.printStackTrace();
+ fail("Collection.add should only throw UnsupportedOperationException, ClassCastException or IllegalArgumentException. Found " + t.toString());
+ }
+ if(added) {
+ assert("Collection is not empty.",!_collection.isEmpty());
+ try {
+ _collection.removeAll(_collection);
+ assert("Collection is empty.",_collection.isEmpty());
+ } catch(UnsupportedOperationException e) {
+ // expected
+ } catch(Throwable t) {
+ t.printStackTrace();
+ fail("Collection.removeAll should only throw UnsupportedOperationException. Found " + t.toString());
+ }
+ }
+ }
+
+ // optional operation
+ public void testCollectionRemoveAll2() {
+ Collection col = new ArrayList();
+ col.add("element1");
+ col.add("element2");
+ col.add("element3");
+ boolean added = false;
+ try {
+ added = _collection.addAll(col);
+ if(added) {
+ added = _collection.add("element0");
+ }
+ } catch(UnsupportedOperationException e) {
+ // ignored, must not be supported
+ } catch(ClassCastException e) {
+ // ignored, type must not be supported
+ } catch(IllegalArgumentException e) {
+ // ignored, element must not be supported
+ } catch(Throwable t) {
+ t.printStackTrace();
+ fail("Collection.addAll should only throw UnsupportedOperationException, ClassCastException or IllegalArgumentException. Found " + t.toString());
+ }
+ col.add("element4");
+ if(added) {
+ assert("Collection is not empty.",!_collection.isEmpty());
+ try {
+ assert("Should be changed",_collection.removeAll(col));
+ assert("Collection is not empty.",!_collection.isEmpty());
+ assert("Collection should contain element",_collection.contains("element0"));
+ assert("Collection shouldn't contain removed element",!_collection.contains("element1"));
+ assert("Collection shouldn't contain removed element",!_collection.contains("element2"));
+ assert("Collection shouldn't contain removed element",!_collection.contains("element3"));
+ assert("Collection shouldn't contain removed element",!_collection.contains("element4"));
+ } catch(UnsupportedOperationException e) {
+ // expected
+ } catch(Throwable t) {
+ t.printStackTrace();
+ fail("Collection.removeAll should only throw UnsupportedOperationException. Found " + t.toString());
+ }
+ }
+ }
+
+ // optional operation
+ public void testCollectionRetainAll() {
+ }
+
+ public void testCollectionSize() {
+ assertEquals("Size of new Collection is 0.",0,_collection.size());
+ boolean added = false;
+ try {
+ added = _collection.add("element1");
+ } catch(UnsupportedOperationException e) {
+ // ignored, must not be supported
+ } catch(ClassCastException e) {
+ // ignored, type must not be supported
+ } catch(IllegalArgumentException e) {
+ // ignored, element must not be supported
+ } catch(Throwable t) {
+ t.printStackTrace();
+ fail("Collection.add should only throw UnsupportedOperationException, ClassCastException or IllegalArgumentException. Found " + t.toString());
+ }
+ if(added) {
+ assertEquals("If one element was added, the Collection.size() should be 1.",1,_collection.size());
+ }
+ }
+
+ public void testCollectionToArray() {
+ }
+
+ public void testCollectionToArray2() {
+ }
+}
diff --git a/src/test/org/apache/commons/collections/TestCursorableLinkedList.java b/src/test/org/apache/commons/collections/TestCursorableLinkedList.java
new file mode 100644
index 0000000..7fa5444
--- /dev/null
+++ b/src/test/org/apache/commons/collections/TestCursorableLinkedList.java
@@ -0,0 +1,949 @@
+/*
+ * $Header: /home/jerenkrantz/tmp/commons/commons-convert/cvs/home/cvs/jakarta-commons//collections/src/test/org/apache/commons/collections/TestCursorableLinkedList.java,v 1.1 2001/04/14 15:39:44 rwaldhoff Exp $
+ * $Revision: 1.1 $
+ * $Date: 2001/04/14 15:39:44 $
+ *
+ * ====================================================================
+ *
+ * The Apache Software License, Version 1.1
+ *
+ * Copyright (c) 1999-2001 The Apache Software Foundation. All rights
+ * reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ *
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ *
+ * 2. Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in
+ * the documentation and/or other materials provided with the
+ * distribution.
+ *
+ * 3. The end-user documentation included with the redistribution, if
+ * any, must include the following acknowlegement:
+ * "This product includes software developed by the
+ * Apache Software Foundation (http://www.apache.org/)."
+ * Alternately, this acknowlegement may appear in the software itself,
+ * if and wherever such third-party acknowlegements normally appear.
+ *
+ * 4. The names "The Jakarta Project", "Commons", and "Apache Software
+ * Foundation" must not be used to endorse or promote products derived
+ * from this software without prior written permission. For written
+ * permission, please contact apache@apache.org.
+ *
+ * 5. Products derived from this software may not be called "Apache"
+ * nor may "Apache" appear in their names without prior written
+ * permission of the Apache Group.
+ *
+ * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED
+ * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
+ * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+ * DISCLAIMED. IN NO EVENT SHALL THE APACHE SOFTWARE FOUNDATION OR
+ * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+ * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
+ * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
+ * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
+ * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
+ * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
+ * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ * ====================================================================
+ *
+ * This software consists of voluntary contributions made by many
+ * individuals on behalf of the Apache Software Foundation. For more
+ * information on the Apache Software Foundation, please see
+ * <http://www.apache.org/>.
+ *
+ */
+
+package org.apache.commons.collections;
+
+import junit.framework.*;
+import java.util.*;
+
+/**
+ * @author Rodney Waldhoff
+ * @version $Id: TestCursorableLinkedList.java,v 1.1 2001/04/14 15:39:44 rwaldhoff Exp $
+ */
+public class TestCursorableLinkedList extends TestList {
+ public TestCursorableLinkedList(String testName) {
+ super(testName);
+ }
+
+ public static Test suite() {
+ return new TestSuite(TestCursorableLinkedList.class);
+ }
+
+ public static void main(String args[]) {
+ String[] testCaseName = { TestCursorableLinkedList.class.getName() };
+ junit.textui.TestRunner.main(testCaseName);
+ }
+
+ private CursorableLinkedList list = null;
+
+ public void setUp() {
+ list = new CursorableLinkedList();
+ setList(list);
+ }
+
+ public void testAdd() {
+ assertEquals("[]",list.toString());
+ assert(list.add(new Integer(1)));
+ assertEquals("[1]",list.toString());
+ assert(list.add(new Integer(2)));
+ assertEquals("[1, 2]",list.toString());
+ assert(list.add(new Integer(3)));
+ assertEquals("[1, 2, 3]",list.toString());
+ assert(list.addFirst(new Integer(0)));
+ assertEquals("[0, 1, 2, 3]",list.toString());
+ assert(list.addLast(new Integer(4)));
+ assertEquals("[0, 1, 2, 3, 4]",list.toString());
+ list.add(0,new Integer(-2));
+ assertEquals("[-2, 0, 1, 2, 3, 4]",list.toString());
+ list.add(1,new Integer(-1));
+ assertEquals("[-2, -1, 0, 1, 2, 3, 4]",list.toString());
+ list.add(7,new Integer(5));
+ assertEquals("[-2, -1, 0, 1, 2, 3, 4, 5]",list.toString());
+
+ java.util.List list2 = new java.util.LinkedList();
+ list2.add("A");
+ list2.add("B");
+ list2.add("C");
+
+ assert(list.addAll(list2));
+ assertEquals("[-2, -1, 0, 1, 2, 3, 4, 5, A, B, C]",list.toString());
+ assert(list.addAll(3,list2));
+ assertEquals("[-2, -1, 0, A, B, C, 1, 2, 3, 4, 5, A, B, C]",list.toString());
+ }
+
+ public void testClear() {
+ assertEquals(0,list.size());
+ assert(list.isEmpty());
+ list.clear();
+ assertEquals(0,list.size());
+ assert(list.isEmpty());
+
+ list.add("element");
+ assertEquals(1,list.size());
+ assert(!list.isEmpty());
+
+ list.clear();
+ assertEquals(0,list.size());
+ assert(list.isEmpty());
+
+ list.add("element1");
+ list.add("element2");
+ assertEquals(2,list.size());
+ assert(!list.isEmpty());
+
+ list.clear();
+ assertEquals(0,list.size());
+ assert(list.isEmpty());
+
+ for(int i=0;i<1000;i++) {
+ list.add(new Integer(i));
+ }
+ assertEquals(1000,list.size());
+ assert(!list.isEmpty());
+
+ list.clear();
+ assertEquals(0,list.size());
+ assert(list.isEmpty());
+ }
+
+ public void testContains() {
+ assert(!list.contains("A"));
+ assert(list.add("A"));
+ assert(list.contains("A"));
+ assert(list.add("B"));
+ assert(list.contains("A"));
+ assert(list.addFirst("a"));
+ assert(list.contains("A"));
+ assert(list.remove("a"));
+ assert(list.contains("A"));
+ assert(list.remove("A"));
+ assert(!list.contains("A"));
+ }
+
+ public void testContainsAll() {
+ assert(list.containsAll(list));
+ java.util.List list2 = new java.util.LinkedList();
+ assert(list.containsAll(list2));
+ list2.add("A");
+ assert(!list.containsAll(list2));
+ list.add("B");
+ list.add("A");
+ assert(list.containsAll(list2));
+ list2.add("B");
+ assert(list.containsAll(list2));
+ list2.add("C");
+ assert(!list.containsAll(list2));
+ list.add("C");
+ assert(list.containsAll(list2));
+ list2.add("C");
+ assert(list.containsAll(list2));
+ assert(list.containsAll(list));
+ }
+
+ public void testCursorNavigation() {
+ list.add("1");
+ list.add("2");
+ list.add("3");
+ list.add("4");
+ list.add("5");
+ CursorableLinkedList.Cursor it = list.cursor();
+ assert(it.hasNext());
+ assert(!it.hasPrevious());
+ assertEquals("1",it.next());
+ assert(it.hasNext());
+ assert(it.hasPrevious());
+ assertEquals("1",it.previous());
+ assert(it.hasNext());
+ assert(!it.hasPrevious());
+ assertEquals("1",it.next());
+ assert(it.hasNext());
+ assert(it.hasPrevious());
+ assertEquals("2",it.next());
+ assert(it.hasNext());
+ assert(it.hasPrevious());
+ assertEquals("2",it.previous());
+ assert(it.hasNext());
+ assert(it.hasPrevious());
+ assertEquals("2",it.next());
+ assert(it.hasNext());
+ assert(it.hasPrevious());
+ assertEquals("3",it.next());
+ assert(it.hasNext());
+ assert(it.hasPrevious());
+ assertEquals("4",it.next());
+ assert(it.hasNext());
+ assert(it.hasPrevious());
+ assertEquals("5",it.next());
+ assert(!it.hasNext());
+ assert(it.hasPrevious());
+ assertEquals("5",it.previous());
+ assert(it.hasNext());
+ assert(it.hasPrevious());
+ assertEquals("4",it.previous());
+ assert(it.hasNext());
+ assert(it.hasPrevious());
+ assertEquals("3",it.previous());
+ assert(it.hasNext());
+ assert(it.hasPrevious());
+ assertEquals("2",it.previous());
+ assert(it.hasNext());
+ assert(it.hasPrevious());
+ assertEquals("1",it.previous());
+ assert(it.hasNext());
+ assert(!it.hasPrevious());
+ it.close();
+ }
+
+ public void testCursorSet() {
+ list.add("1");
+ list.add("2");
+ list.add("3");
+ list.add("4");
+ list.add("5");
+
+ CursorableLinkedList.Cursor it = list.cursor();
+ assertEquals("1",it.next());
+ it.set("a");
+ assertEquals("a",it.previous());
+ it.set("A");
+ assertEquals("A",it.next());
+ assertEquals("2",it.next());
+ it.set("B");
+ assertEquals("3",it.next());
+ assertEquals("4",it.next());
+ it.set("D");
+ assertEquals("5",it.next());
+ it.set("E");
+ assertEquals("[A, B, 3, D, E]",list.toString());
+ it.close();
+ }
+
+ public void testCursorRemove() {
+ list.add("1");
+ list.add("2");
+ list.add("3");
+ list.add("4");
+ list.add("5");
+
+ CursorableLinkedList.Cursor it = list.cursor();
+ try {
+ it.remove();
+ } catch(IllegalStateException e) {
+ // expected
+ }
+ assertEquals("1",it.next());
+ assertEquals("2",it.next());
+ assertEquals("[1, 2, 3, 4, 5]",list.toString());
+ it.remove();
+ assertEquals("[1, 3, 4, 5]",list.toString());
+ assertEquals("3",it.next());
+ assertEquals("3",it.previous());
+ assertEquals("1",it.previous());
+ it.remove();
+ assertEquals("[3, 4, 5]",list.toString());
+ assert(!it.hasPrevious());
+ assertEquals("3",it.next());
+ it.remove();
+ assertEquals("[4, 5]",list.toString());
+ try {
+ it.remove();
+ } catch(IllegalStateException e) {
+ // expected
+ }
+ assertEquals("4",it.next());
+ assertEquals("5",it.next());
+ it.remove();
+ assertEquals("[4]",list.toString());
+ assertEquals("4",it.previous());
+ it.remove();
+ assertEquals("[]",list.toString());
+ it.close();
+ }
+
+ public void testCursorAdd() {
+ CursorableLinkedList.Cursor it = list.cursor();
+ it.add("1");
+ assertEquals("[1]",list.toString());
+ it.add("3");
+ assertEquals("[1, 3]",list.toString());
+ it.add("5");
+ assertEquals("[1, 3, 5]",list.toString());
+ assertEquals("5",it.previous());
+ it.add("4");
+ assertEquals("[1, 3, 4, 5]",list.toString());
+ assertEquals("4",it.previous());
+ assertEquals("3",it.previous());
+ it.add("2");
+ assertEquals("[1, 2, 3, 4, 5]",list.toString());
+ it.close();
+ }
+
+ public void testEqualsAndHashCode() {
+ assert(list.equals(list));
+ assertEquals(list.hashCode(),list.hashCode());
+ list.add("A");
+ assert(list.equals(list));
+ assertEquals(list.hashCode(),list.hashCode());
+
+ CursorableLinkedList list2 = new CursorableLinkedList();
+ assert(!list.equals(list2));
+ assert(!list2.equals(list));
+
+ java.util.List list3 = new java.util.LinkedList();
+ assert(!list.equals(list3));
+ assert(!list3.equals(list));
+ assert(list2.equals(list3));
+ assert(list3.equals(list2));
+ assertEquals(list2.hashCode(),list3.hashCode());
+
+ list2.add("A");
+ assert(list.equals(list2));
+ assert(list2.equals(list));
+ assert(!list2.equals(list3));
+ assert(!list3.equals(list2));
+
+ list3.add("A");
+ assert(list2.equals(list3));
+ assert(list3.equals(list2));
+ assertEquals(list2.hashCode(),list3.hashCode());
+
+ list.add("B");
+ assert(list.equals(list));
+ assert(!list.equals(list2));
+ assert(!list2.equals(list));
+ assert(!list.equals(list3));
+ assert(!list3.equals(list));
+
+ list2.add("B");
+ list3.add("B");
+ assert(list.equals(list));
+ assert(list.equals(list2));
+ assert(list2.equals(list));
+ assert(list2.equals(list3));
+ assert(list3.equals(list2));
+ assertEquals(list2.hashCode(),list3.hashCode());
+
+ list.add("C");
+ list2.add("C");
+ list3.add("C");
+ assert(list.equals(list));
+ assert(list.equals(list2));
+ assert(list2.equals(list));
+ assert(list2.equals(list3));
+ assert(list3.equals(list2));
+ assertEquals(list.hashCode(),list2.hashCode());
+ assertEquals(list2.hashCode(),list3.hashCode());
+
+ list.add("D");
+ list2.addFirst("D");
+ assert(list.equals(list));
+ assert(!list.equals(list2));
+ assert(!list2.equals(list));
+ }
+
+ public void testGet() {
+ try {
+ list.get(0);
+ fail("shouldn't get here");
+ } catch(IndexOutOfBoundsException e) {
+ // expected
+ }
+
+ assert(list.add("A"));
+ assertEquals("A",list.get(0));
+ assert(list.add("B"));
+ assertEquals("A",list.get(0));
+ assertEquals("B",list.get(1));
+
+ try {
+ list.get(-1);
+ fail("shouldn't get here");
+ } catch(IndexOutOfBoundsException e) {
+ // expected
+ }
+
+ try {
+ list.get(2);
+ fail("shouldn't get here");
+ } catch(IndexOutOfBoundsException e) {
+ // expected
+ }
+ }
+
+ public void testIndexOf() {
+ assertEquals(-1,list.indexOf("A"));
+ assertEquals(-1,list.lastIndexOf("A"));
+ list.add("A");
+ assertEquals(0,list.indexOf("A"));
+ assertEquals(0,list.lastIndexOf("A"));
+ assertEquals(-1,list.indexOf("B"));
+ assertEquals(-1,list.lastIndexOf("B"));
+ list.add("B");
+ assertEquals(0,list.indexOf("A"));
+ assertEquals(0,list.lastIndexOf("A"));
+ assertEquals(1,list.indexOf("B"));
+ assertEquals(1,list.lastIndexOf("B"));
+ list.addFirst("B");
+ assertEquals(1,list.indexOf("A"));
+ assertEquals(1,list.lastIndexOf("A"));
+ assertEquals(0,list.indexOf("B"));
+ assertEquals(2,list.lastIndexOf("B"));
+ }
+
+ public void testIsEmpty() {
+ assert(list.isEmpty());
+ list.add("element");
+ assert(!list.isEmpty());
+ list.remove("element");
+ assert(list.isEmpty());
+ list.add("element");
+ assert(!list.isEmpty());
+ list.clear();
+ assert(list.isEmpty());
+ }
+
+ public void testIterator() {
+ list.add("1");
+ list.add("2");
+ list.add("3");
+ list.add("4");
+ list.add("5");
+ Iterator it = list.iterator();
+ assert(it.hasNext());
+ assertEquals("1",it.next());
+ assert(it.hasNext());
+ assertEquals("2",it.next());
+ assert(it.hasNext());
+ assertEquals("3",it.next());
+ assert(it.hasNext());
+ assertEquals("4",it.next());
+ assert(it.hasNext());
+ assertEquals("5",it.next());
+ assert(!it.hasNext());
+
+ it = list.iterator();
+ assert(it.hasNext());
+ assertEquals("1",it.next());
+ it.remove();
+ assertEquals("[2, 3, 4, 5]",list.toString());
+ assert(it.hasNext());
+ assertEquals("2",it.next());
+ it.remove();
+ assertEquals("[3, 4, 5]",list.toString());
+ assert(it.hasNext());
+ assertEquals("3",it.next());
+ it.remove();
+ assertEquals("[4, 5]",list.toString());
+ assert(it.hasNext());
+ assertEquals("4",it.next());
+ it.remove();
+ assertEquals("[5]",list.toString());
+ assert(it.hasNext());
+ assertEquals("5",it.next());
+ it.remove();
+ assertEquals("[]",list.toString());
+ assert(!it.hasNext());
+ }
+
+ public void testListIteratorNavigation() {
+ list.add("1");
+ list.add("2");
+ list.add("3");
+ list.add("4");
+ list.add("5");
+ ListIterator it = list.listIterator();
+ assert(it.hasNext());
+ assert(!it.hasPrevious());
+ assertEquals(-1,it.previousIndex());
+ assertEquals(0,it.nextIndex());
+ assertEquals("1",it.next());
+ assert(it.hasNext());
+ assert(it.hasPrevious());
+ assertEquals(0,it.previousIndex());
+ assertEquals(1,it.nextIndex());
+ assertEquals("1",it.previous());
+ assert(it.hasNext());
+ assert(!it.hasPrevious());
+ assertEquals(-1,it.previousIndex());
+ assertEquals(0,it.nextIndex());
+ assertEquals("1",it.next());
+ assert(it.hasNext());
+ assert(it.hasPrevious());
+ assertEquals(0,it.previousIndex());
+ assertEquals(1,it.nextIndex());
+ assertEquals("2",it.next());
+ assert(it.hasNext());
+ assert(it.hasPrevious());
+ assertEquals(1,it.previousIndex());
+ assertEquals(2,it.nextIndex());
+ assertEquals("2",it.previous());
+ assert(it.hasNext());
+ assert(it.hasPrevious());
+ assertEquals(0,it.previousIndex());
+ assertEquals(1,it.nextIndex());
+ assertEquals("2",it.next());
+ assert(it.hasNext());
+ assert(it.hasPrevious());
+ assertEquals(1,it.previousIndex());
+ assertEquals(2,it.nextIndex());
+ assertEquals("3",it.next());
+ assert(it.hasNext());
+ assert(it.hasPrevious());
+ assertEquals(2,it.previousIndex());
+ assertEquals(3,it.nextIndex());
+ assertEquals("4",it.next());
+ assert(it.hasNext());
+ assert(it.hasPrevious());
+ assertEquals(3,it.previousIndex());
+ assertEquals(4,it.nextIndex());
+ assertEquals("5",it.next());
+ assert(!it.hasNext());
+ assert(it.hasPrevious());
+ assertEquals(4,it.previousIndex());
+ assertEquals(5,it.nextIndex());
+ assertEquals("5",it.previous());
+ assert(it.hasNext());
+ assert(it.hasPrevious());
+ assertEquals(3,it.previousIndex());
+ assertEquals(4,it.nextIndex());
+ assertEquals("4",it.previous());
+ assert(it.hasNext());
+ assert(it.hasPrevious());
+ assertEquals(2,it.previousIndex());
+ assertEquals(3,it.nextIndex());
+ assertEquals("3",it.previous());
+ assert(it.hasNext());
+ assert(it.hasPrevious());
+ assertEquals(1,it.previousIndex());
+ assertEquals(2,it.nextIndex());
+ assertEquals("2",it.previous());
+ assert(it.hasNext());
+ assert(it.hasPrevious());
+ assertEquals(0,it.previousIndex());
+ assertEquals(1,it.nextIndex());
+ assertEquals("1",it.previous());
+ assert(it.hasNext());
+ assert(!it.hasPrevious());
+ assertEquals(-1,it.previousIndex());
+ assertEquals(0,it.nextIndex());
+ }
+
+ public void testListIteratorSet() {
+ list.add("1");
+ list.add("2");
+ list.add("3");
+ list.add("4");
+ list.add("5");
+
+ ListIterator it = list.listIterator();
+ assertEquals("1",it.next());
+ it.set("a");
+ assertEquals("a",it.previous());
+ it.set("A");
+ assertEquals("A",it.next());
+ assertEquals("2",it.next());
+ it.set("B");
+ assertEquals("3",it.next());
+ assertEquals("4",it.next());
+ it.set("D");
+ assertEquals("5",it.next());
+ it.set("E");
+ assertEquals("[A, B, 3, D, E]",list.toString());
+ }
+
+ public void testListIteratorRemove() {
+ list.add("1");
+ list.add("2");
+ list.add("3");
+ list.add("4");
+ list.add("5");
+
+ ListIterator it = list.listIterator();
+ try {
+ it.remove();
+ } catch(IllegalStateException e) {
+ // expected
+ }
+ assertEquals("1",it.next());
+ assertEquals("2",it.next());
+ assertEquals("[1, 2, 3, 4, 5]",list.toString());
+ it.remove();
+ assertEquals("[1, 3, 4, 5]",list.toString());
+ assertEquals("3",it.next());
+ assertEquals("3",it.previous());
+ assertEquals("1",it.previous());
+ it.remove();
+ assertEquals("[3, 4, 5]",list.toString());
+ assert(!it.hasPrevious());
+ assertEquals("3",it.next());
+ it.remove();
+ assertEquals("[4, 5]",list.toString());
+ try {
+ it.remove();
+ } catch(IllegalStateException e) {
+ // expected
+ }
+ assertEquals("4",it.next());
+ assertEquals("5",it.next());
+ it.remove();
+ assertEquals("[4]",list.toString());
+ assertEquals("4",it.previous());
+ it.remove();
+ assertEquals("[]",list.toString());
+ }
+
+ public void testListIteratorAdd() {
+ ListIterator it = list.listIterator();
+ it.add("1");
+ assertEquals("[1]",list.toString());
+ it.add("3");
+ assertEquals("[1, 3]",list.toString());
+ it.add("5");
+ assertEquals("[1, 3, 5]",list.toString());
+ assertEquals("5",it.previous());
+ it.add("4");
+ assertEquals("[1, 3, 4, 5]",list.toString());
+ assertEquals("4",it.previous());
+ assertEquals("3",it.previous());
+ it.add("2");
+ assertEquals("[1, 2, 3, 4, 5]",list.toString());
+ }
+
+ public void testRemoveAll() {
+ list.add("1");
+ list.add("2");
+ list.add("3");
+ list.add("4");
+ list.add("5");
+
+ HashSet set = new HashSet();
+ set.add("A");
+ set.add("2");
+ set.add("C");
+ set.add("4");
+ set.add("D");
+
+ assert(list.removeAll(set));
+ assertEquals("[1, 3, 5]",list.toString());
+ assert(!list.removeAll(set));
+ }
+
+ public void testRemoveByIndex() {
+ list.add("1");
+ list.add("2");
+ list.add("3");
+ list.add("4");
+ list.add("5");
+ assertEquals("[1, 2, 3, 4, 5]",list.toString());
+ assertEquals("1",list.remove(0));
+ assertEquals("[2, 3, 4, 5]",list.toString());
+ assertEquals("3",list.remove(1));
+ assertEquals("[2, 4, 5]",list.toString());
+ assertEquals("4",list.remove(1));
+ assertEquals("[2, 5]",list.toString());
+ assertEquals("5",list.remove(1));
+ assertEquals("[2]",list.toString());
+ assertEquals("2",list.remove(0));
+ assertEquals("[]",list.toString());
+ }
+
+ public void testRemove() {
+ list.add("1");
+ list.add("1");
+ list.add("2");
+ list.add("3");
+ list.add("4");
+ list.add("5");
+ list.add("2");
+ list.add("3");
+ list.add("4");
+ list.add("5");
+ assertEquals("[1, 1, 2, 3, 4, 5, 2, 3, 4, 5]",list.toString());
+ assert(!list.remove("6"));
+ assert(list.remove("5"));
+ assertEquals("[1, 1, 2, 3, 4, 2, 3, 4, 5]",list.toString());
+ assert(list.remove("5"));
+ assertEquals("[1, 1, 2, 3, 4, 2, 3, 4]",list.toString());
+ assert(!list.remove("5"));
+ assert(list.remove("1"));
+ assertEquals("[1, 2, 3, 4, 2, 3, 4]",list.toString());
+ assert(list.remove("1"));
+ assertEquals("[2, 3, 4, 2, 3, 4]",list.toString());
+ assert(list.remove("2"));
+ assertEquals("[3, 4, 2, 3, 4]",list.toString());
+ assert(list.remove("2"));
+ assertEquals("[3, 4, 3, 4]",list.toString());
+ assert(list.remove("3"));
+ assertEquals("[4, 3, 4]",list.toString());
+ assert(list.remove("3"));
+ assertEquals("[4, 4]",list.toString());
+ assert(list.remove("4"));
+ assertEquals("[4]",list.toString());
+ assert(list.remove("4"));
+ assertEquals("[]",list.toString());
+ }
+
+ public void testRetainAll() {
+ list.add("1");
+ list.add("1");
+ list.add("2");
+ list.add("2");
+ list.add("3");
+ list.add("3");
+ list.add("4");
+ list.add("4");
+ list.add("5");
+ list.add("5");
+
+ HashSet set = new HashSet();
+ set.add("A");
+ set.add("2");
+ set.add("C");
+ set.add("4");
+ set.add("D");
+
+ assert(list.retainAll(set));
+ assertEquals("[2, 2, 4, 4]",list.toString());
+ assert(!list.retainAll(set));
+ }
+
+ public void testSet() {
+ list.add("1");
+ list.add("2");
+ list.add("3");
+ list.add("4");
+ list.add("5");
+ assertEquals("[1, 2, 3, 4, 5]",list.toString());
+ list.set(0,"A");
+ assertEquals("[A, 2, 3, 4, 5]",list.toString());
+ list.set(1,"B");
+ assertEquals("[A, B, 3, 4, 5]",list.toString());
+ list.set(2,"C");
+ assertEquals("[A, B, C, 4, 5]",list.toString());
+ list.set(3,"D");
+ assertEquals("[A, B, C, D, 5]",list.toString());
+ list.set(4,"E");
+ assertEquals("[A, B, C, D, E]",list.toString());
+ }
+
+ public void testSubList() {
+ list.add("A");
+ list.add("B");
+ list.add("C");
+ list.add("D");
+ list.add("E");
+
+ assertEquals("[A, B, C, D, E]",list.toString());
+ assertEquals("[A, B, C, D, E]",list.subList(0,5).toString());
+ assertEquals("[B, C, D, E]",list.subList(1,5).toString());
+ assertEquals("[C, D, E]",list.subList(2,5).toString());
+ assertEquals("[D, E]",list.subList(3,5).toString());
+ assertEquals("[E]",list.subList(4,5).toString());
+ assertEquals("[]",list.subList(5,5).toString());
+ }
+
+ public void testSubListAddEnd() {
+ list.add("A");
+ list.add("B");
+ list.add("C");
+ list.add("D");
+ list.add("E");
+
+ List sublist = list.subList(5,5);
+ sublist.add("F");
+ assertEquals("[A, B, C, D, E, F]",list.toString());
+ assertEquals("[F]",sublist.toString());
+ sublist.add("G");
+ assertEquals("[A, B, C, D, E, F, G]",list.toString());
+ assertEquals("[F, G]",sublist.toString());
+ }
+
+ public void testSubListAddBegin() {
+ list.add("A");
+ list.add("B");
+ list.add("C");
+ list.add("D");
+ list.add("E");
+
+ List sublist = list.subList(0,0);
+ sublist.add("a");
+ assertEquals("[a, A, B, C, D, E]",list.toString());
+ assertEquals("[a]",sublist.toString());
+ sublist.add("b");
+ assertEquals("[a, b, A, B, C, D, E]",list.toString());
+ assertEquals("[a, b]",sublist.toString());
+ }
+
+ public void testSubListAddMiddle() {
+ list.add("A");
+ list.add("B");
+ list.add("C");
+ list.add("D");
+ list.add("E");
+
+ List sublist = list.subList(1,3);
+ sublist.add("a");
+ assertEquals("[A, B, C, a, D, E]",list.toString());
+ assertEquals("[B, C, a]",sublist.toString());
+ sublist.add("b");
+ assertEquals("[A, B, C, a, b, D, E]",list.toString());
+ assertEquals("[B, C, a, b]",sublist.toString());
+ }
+
+ public void testSubListRemove() {
+ list.add("A");
+ list.add("B");
+ list.add("C");
+ list.add("D");
+ list.add("E");
+
+ List sublist = list.subList(1,4);
+ assertEquals("[B, C, D]",sublist.toString());
+ assertEquals("[A, B, C, D, E]",list.toString());
+ sublist.remove("C");
+ assertEquals("[B, D]",sublist.toString());
+ assertEquals("[A, B, D, E]",list.toString());
+ sublist.remove(1);
+ assertEquals("[B]",sublist.toString());
+ assertEquals("[A, B, E]",list.toString());
+ sublist.clear();
+ assertEquals("[]",sublist.toString());
+ assertEquals("[A, E]",list.toString());
+ }
+
+ public void testToArray() {
+ list.add("1");
+ list.add("2");
+ list.add("3");
+ list.add("4");
+ list.add("5");
+
+ Object[] elts = list.toArray();
+ assertEquals("1",elts[0]);
+ assertEquals("2",elts[1]);
+ assertEquals("3",elts[2]);
+ assertEquals("4",elts[3]);
+ assertEquals("5",elts[4]);
+ assertEquals(5,elts.length);
+
+ String[] elts2 = (String[])(list.toArray(new String[0]));
+ assertEquals("1",elts2[0]);
+ assertEquals("2",elts2[1]);
+ assertEquals("3",elts2[2]);
+ assertEquals("4",elts2[3]);
+ assertEquals("5",elts2[4]);
+ assertEquals(5,elts2.length);
+
+ String[] elts3 = new String[5];
+ assertSame(elts3,list.toArray(elts3));
+ assertEquals("1",elts3[0]);
+ assertEquals("2",elts3[1]);
+ assertEquals("3",elts3[2]);
+ assertEquals("4",elts3[3]);
+ assertEquals("5",elts3[4]);
+ assertEquals(5,elts3.length);
+
+ String[] elts4 = new String[3];
+ String[] elts4b = (String[])(list.toArray(elts4));
+ assert(elts4 != elts4b);
+ assertEquals("1",elts4b[0]);
+ assertEquals("2",elts4b[1]);
+ assertEquals("3",elts4b[2]);
+ assertEquals("4",elts4b[3]);
+ assertEquals("5",elts4b[4]);
+ assertEquals(5,elts4b.length);
+ }
+
+ public void testSerialization() throws Exception {
+ list.add("A");
+ list.add("B");
+ list.add("C");
+ list.add("D");
+ list.add("E");
+
+ java.io.ByteArrayOutputStream buf = new java.io.ByteArrayOutputStream();
+ java.io.ObjectOutputStream out = new java.io.ObjectOutputStream(buf);
+ out.writeObject(list);
+ out.flush();
+ out.close();
+
+ java.io.ByteArrayInputStream bufin = new java.io.ByteArrayInputStream(buf.toByteArray());
+ java.io.ObjectInputStream in = new java.io.ObjectInputStream(bufin);
+ Object list2 = in.readObject();
+
+ assert(list != list2);
+ assert(list2.equals(list));
+ assert(list.equals(list2));
+ }
+
+ public void testLongSerialization() throws Exception {
+ // recursive serialization will cause a stack
+ // overflow exception with long lists
+ for(int i=0;i<10000;i++) {
+ list.add(new Integer(i));
+ }
+
+ java.io.ByteArrayOutputStream buf = new java.io.ByteArrayOutputStream();
+ java.io.ObjectOutputStream out = new java.io.ObjectOutputStream(buf);
+ out.writeObject(list);
+ out.flush();
+ out.close();
+
+ java.io.ByteArrayInputStream bufin = new java.io.ByteArrayInputStream(buf.toByteArray());
+ java.io.ObjectInputStream in = new java.io.ObjectInputStream(bufin);
+ Object list2 = in.readObject();
+
+ assert(list != list2);
+ assert(list2.equals(list));
+ assert(list.equals(list2));
+ }
+
+}
\ No newline at end of file
diff --git a/src/test/org/apache/commons/collections/TestList.java b/src/test/org/apache/commons/collections/TestList.java
new file mode 100644
index 0000000..3759e3c
--- /dev/null
+++ b/src/test/org/apache/commons/collections/TestList.java
@@ -0,0 +1,84 @@
+/*
+ * $Header: /home/jerenkrantz/tmp/commons/commons-convert/cvs/home/cvs/jakarta-commons//collections/src/test/org/apache/commons/collections/Attic/TestList.java,v 1.1 2001/04/14 15:39:53 rwaldhoff Exp $
+ * $Revision: 1.1 $
+ * $Date: 2001/04/14 15:39:53 $
+ *
+ * ====================================================================
+ *
+ * The Apache Software License, Version 1.1
+ *
+ * Copyright (c) 1999-2001 The Apache Software Foundation. All rights
+ * reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ *
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ *
+ * 2. Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in
+ * the documentation and/or other materials provided with the
+ * distribution.
+ *
+ * 3. The end-user documentation included with the redistribution, if
+ * any, must include the following acknowlegement:
+ * "This product includes software developed by the
+ * Apache Software Foundation (http://www.apache.org/)."
+ * Alternately, this acknowlegement may appear in the software itself,
+ * if and wherever such third-party acknowlegements normally appear.
+ *
+ * 4. The names "The Jakarta Project", "Commons", and "Apache Software
+ * Foundation" must not be used to endorse or promote products derived
+ * from this software without prior written permission. For written
+ * permission, please contact apache@apache.org.
+ *
+ * 5. Products derived from this software may not be called "Apache"
+ * nor may "Apache" appear in their names without prior written
+ * permission of the Apache Group.
+ *
+ * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED
+ * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
+ * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+ * DISCLAIMED. IN NO EVENT SHALL THE APACHE SOFTWARE FOUNDATION OR
+ * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+ * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
+ * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
+ * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
+ * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
+ * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
+ * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ * ====================================================================
+ *
+ * This software consists of voluntary contributions made by many
+ * individuals on behalf of the Apache Software Foundation. For more
+ * information on the Apache Software Foundation, please see
+ * <http://www.apache.org/>.
+ *
+ */
+
+package org.apache.commons.collections;
+
+import junit.framework.*;
+import java.util.List;
+
+/**
+ * @author Rodney Waldhoff
+ * @version $Id: TestList.java,v 1.1 2001/04/14 15:39:53 rwaldhoff Exp $
+ */
+public abstract class TestList extends TestCollection {
+ public TestList(String testName) {
+ super(testName);
+ }
+
+ private List _list = null;
+
+ protected void setList(List l) {
+ _list = l;
+ setCollection(_list);
+ }
+
+ // placeholder. add list contract tests here
+}