You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@commons.apache.org by rw...@apache.org on 2003/01/07 16:18:15 UTC
cvs commit: jakarta-commons/collections/src/test/org/apache/commons/collections/comparators TestComparator.java
rwaldhoff 2003/01/07 07:18:15
Modified: collections/src/java/org/apache/commons/collections
NodeCachingLinkedList.java
collections/src/test/org/apache/commons/collections
TestAll.java TestMultiHashMap.java
TestNodeCachingLinkedList.java TestObject.java
TestReferenceMap.java TestSequencedHashMap.java
collections/src/test/org/apache/commons/collections/comparators
TestComparator.java
Added: collections/data/test
CommonsLinkedList.emptyCollection.version2.2.obj
CommonsLinkedList.fullCollection.version2.2.obj
NodeCachingLinkedList.emptyCollection.version2.2.obj
NodeCachingLinkedList.fullCollection.version2.2.obj
collections/src/java/org/apache/commons/collections
CommonsLinkedList.java
collections/src/test/org/apache/commons/collections
TestCommonsLinkedList.java TestLinkedList.java
Log:
apply Rich Dougherty's patch fixing NodeCachingLinkedList unit tests
this also adds CommonsLinkedList and tests
Revision Changes Path
1.1 jakarta-commons/collections/data/test/CommonsLinkedList.emptyCollection.version2.2.obj
<<Binary file>>
1.1 jakarta-commons/collections/data/test/CommonsLinkedList.fullCollection.version2.2.obj
<<Binary file>>
1.1 jakarta-commons/collections/data/test/NodeCachingLinkedList.emptyCollection.version2.2.obj
<<Binary file>>
1.1 jakarta-commons/collections/data/test/NodeCachingLinkedList.fullCollection.version2.2.obj
<<Binary file>>
1.2 +175 -876 jakarta-commons/collections/src/java/org/apache/commons/collections/NodeCachingLinkedList.java
Index: NodeCachingLinkedList.java
===================================================================
RCS file: /home/cvs/jakarta-commons/collections/src/java/org/apache/commons/collections/NodeCachingLinkedList.java,v
retrieving revision 1.1
retrieving revision 1.2
diff -u -r1.1 -r1.2
--- NodeCachingLinkedList.java 18 Nov 2002 23:58:17 -0000 1.1
+++ NodeCachingLinkedList.java 7 Jan 2003 15:18:14 -0000 1.2
@@ -1,876 +1,175 @@
-/*
- * $Header$
- * $Revision$
- * $Date$
- *
- * ====================================================================
- *
- * The Apache Software License, Version 1.1
- *
- * Copyright (c) 1999-2002 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 java.io.Serializable;
-import java.util.Collection;
-import java.util.ConcurrentModificationException;
-import java.util.Iterator;
-import java.util.LinkedList;
-import java.util.List;
-import java.util.ListIterator;
-import java.util.NoSuchElementException;
-/**
- * <code>NodeCachingLinkedList</code> is a linked list implementation that
- * provides better performance than java.util.LinkedList.
- * <p>
- * This class differs from java.util.LinkedList in that internal Node
- * objects used to hold the elements are not necessarily thrown away when an
- * entry is removed from the list. Instead, they are cached, which allows this
- * implementation to give better performance than java.util.LinkedList with a
- * small space penalty.
- * <p>
- * <b>Note that this implementation is not synchronized.</b> If multiple
- * threads access a list concurrently, and at least one of the threads
- * modifies the list structurally, it <i>must</i> be synchronized
- * externally.
- * <p>
- * The iterators returned by the this class's <code>iterator</code> and
- * <code>listIterator</code> methods are <i>fail-fast</i>: if the list is
- * structurally modified at any time after the iterator is created, in any way
- * except through the Iterator's own <code>remove</code> or <code>add</code> methods,
- * the iterator will throw a <code>ConcurrentModificationException</code>. Thus,
- * in the face of concurrent modification, the iterator fails quickly and
- * cleanly, rather than risking arbitrary, non-deterministic behavior at an
- * undetermined time in the future.
- * <p>
- * <p>Note that the fail-fast behavior of an iterator cannot be guaranteed
- * as it is, generally speaking, impossible to make any hard guarantees in the
- * presence of unsynchronized concurrent modification. Fail-fast iterators
- * throw <code>ConcurrentModificationException</code> on a best-effort basis.
- * Therefore, it would be wrong to write a program that depended on this
- * exception for its correctness: <i>the fail-fast behavior of iterators
- * should be used only to detect bugs.</i>
- *
- * @author Jeff Varszegi
- */
-public final class NodeCachingLinkedList
- extends LinkedList
- implements List, Cloneable, Serializable {
-
- private static final int MINIMUM_MAXIMUM_CACHE_SIZE = 100;
- private static final int DEFAULT_MAXIMUM_CACHE_SIZE = 1000000;
-
- private Node cacheHeader = new Node(null, null, null);
- private int cacheCount = 0;
-
- private int maximumCacheSize = DEFAULT_MAXIMUM_CACHE_SIZE;
-
- private Node header = new Node(null, null, null);
- private int size = 0;
-
- /**
- * Constructs an empty list.
- */
- public NodeCachingLinkedList() {
- header.next = header.previous = header;
- }
-
- /**
- * Constructs a list containing the elements of the specified
- * collection, in the order they are returned by the collection's
- * iterator.
- *
- * @param coll the collection whose elements are to be placed into this list.
- * @throws NullPointerException if the specified collection is null.
- */
- public NodeCachingLinkedList(Collection coll) {
- this();
- addAll(coll);
- }
-
- /**
- * Sets the maximum number of elements that may be held in the internal
- * reusable node cache.
- *
- * @return the maximum cache size
- */
- public int getMaximumCacheSize() {
- return maximumCacheSize;
- }
-
- /**
- * Sets the maximum number of elements that may be held in the internal
- * reusable node cache.
- *
- * @param maximumCacheSize the maximum cache size to set
- */
- public void setMaximumCacheSize(int maximumCacheSize) {
- this.maximumCacheSize = maximumCacheSize;
- }
-
- /**
- * Returns the first element in this list.
- *
- * @return the first object in the list
- * @throws NoSuchElementException if this list is empty
- */
- public Object getFirst() {
- if (size == 0) {
- throw new NoSuchElementException();
- }
- else {
- return header.next.element;
- }
- }
-
- /**
- * Returns the last element in this list.
- *
- * @return the last object in the list
- * @throws NoSuchElementException if this list is empty
- */
- public Object getLast() {
- if (size == 0) {
- throw new NoSuchElementException();
- }
- return header.previous.element;
- }
-
- /**
- * Removes and returns the first element from this list.
- *
- * @return the first element from this list, now removed
- * @throws NoSuchElementException if this list is empty
- */
- public Object removeFirst() {
- if (size == 0) {
- throw new NoSuchElementException();
- }
- Node firstNode = header.next;
- Object first = firstNode.element;
-
- firstNode.next.previous = header;
- header.next = firstNode.next;
- size--;
- modCount++;
-
- if (cacheCount < maximumCacheSize) {
-
- firstNode.element = null;
- firstNode.next = cacheHeader.next;
- cacheHeader.next = firstNode;
- cacheCount++;
- }
-
- return first;
- }
-
- /**
- * Removes and returns the last element from this list.
- *
- * @return the last element from this list, now removed
- * @throws NoSuchElementException if this list is empty
- */
- public Object removeLast() {
- if (size == 0) {
- throw new NoSuchElementException();
-
- }
- Node lastNode = header.previous;
- Object last = lastNode.element;
-
- lastNode.previous.next = header;
- header.previous = lastNode.previous;
- size--;
- modCount++;
-
- if (cacheCount < maximumCacheSize) {
- lastNode.element = null;
- lastNode.previous = null;
- lastNode.next = cacheHeader.next;
- cacheHeader.next = lastNode;
- cacheCount++;
- }
-
- return last;
- }
-
- /**
- * Inserts the given element at the beginning of this list.
- *
- * @param obj the element to be inserted at the beginning of this list
- */
- public void addFirst(Object obj) {
- Node newNode;
-
- if (cacheCount > 0) {
- newNode = cacheHeader.next;
- cacheHeader.next = newNode.next;
- newNode.element = obj;
- newNode.next = header.next;
- newNode.previous = header;
- cacheCount--;
- }
- else {
- newNode = new Node(obj, header.next, header);
- }
-
- newNode.previous.next = newNode;
- newNode.next.previous = newNode;
- size++;
- modCount++;
- }
-
- /**
- * Appends the given element to the end of this list. (Identical in
- * function to the <code>add</code> method; included only for consistency.)
- *
- * @param obj the element to be inserted at the end of this list
- */
- public void addLast(Object obj) {
- Node newNode;
-
- if (cacheCount > 0) {
- newNode = cacheHeader.next;
- cacheHeader.next = newNode.next;
- newNode.element = obj;
- newNode.next = header.next;
- newNode.previous = header;
- cacheCount--;
- }
- else {
- newNode = new Node(obj, header, header.previous);
- }
-
-
-
- newNode.previous.next = newNode;
- newNode.next.previous = newNode;
- size++;
- modCount++;
- }
-
- /**
- * Returns <code>true</code> if this list contains the specified element.
- * More formally, returns <code>true</code> if and only if this list contains
- * at least one element <code>e</code> such that <code>(o==null ? e==null
- * : o.equals(e))</code>.
- *
- * @param obj element whose presence in this list is to be tested
- * @return <code>true</code> if this list contains the specified element
- */
- public boolean contains(Object obj) {
- return indexOf(obj) != -1;
- }
-
- /**
- * Returns the number of elements in this list.
- *
- * @return the number of elements in this list
- */
- public int size() {
- return size;
- }
-
- /**
- * Appends the specified element to the end of this list.
- *
- * @param obj element to be appended to this list.
- * @return <code>true</code> (as per the general contract of
- * <code>Collection.add</code>)
- */
- public boolean add(Object obj) {
- addLast(obj);
- return true;
- }
-
- /**
- * Removes the first occurrence of the specified element in this list. If
- * the list does not contain the element, it is unchanged. More formally,
- * removes the element with the lowest index <code>i</code> such that
- * <code>(o==null ? get(i)==null : o.equals(get(i)))</code> (if such an
- * element exists).
- *
- * @param obj element to be removed from this list, if present
- * @return <code>true</code> if the list contained the specified element
- */
- public boolean remove(Object obj) {
- if (obj == null) {
- for (Node e = header.next; e != header; e = e.next) {
- if (e.element == null) {
- remove(e);
- return true;
- }
- }
- }
- else {
- for (Node e = header.next; e != header; e = e.next) {
- if (obj.equals(e.element)) {
- remove(e);
- return true;
- }
- }
- }
- return false;
- }
-
- /**
- * 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
- * collection's iterator. The behavior of this operation is undefined if
- * the specified collection is modified while the operation is in
- * progress. (This implies that the behavior of this call is undefined if
- * the specified Collection is this list, and this list is nonempty.)
- *
- * @param coll the elements to be inserted into this list
- * @return <code>true</code> if this list changed as a result of the call
- * @throws NullPointerException if the specified collection is null
- */
- public boolean addAll(Collection coll) {
- return addAll(size, coll);
- }
-
- /**
- * Inserts all of the elements in the specified collection into this
- * list, starting 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 the list in the order that they are returned by the
- * specified collection's iterator.
- *
- * @param index index at which to insert first element
- * from the specified collection
- * @param coll elements to be inserted into this list
- * @return <code>true</code> if this list changed as a result of the call
- * @throws IndexOutOfBoundsException if the specified index is out of
- * range (<code>index < 0 || index > size()</code>)
- * @throws NullPointerException if the specified collection is null
- */
- public boolean addAll(int index, Collection coll) {
- int numNew = coll.size();
- if (numNew == 0)
- return false;
- modCount++;
-
- Node successor = (index == size ? header : entry(index));
- Node predecessor = successor.previous;
- Iterator it = coll.iterator();
- for (int i = 0; i < numNew; i++) {
- Node e;
- if (cacheCount > 0) {
- e = cacheHeader.next;
- cacheHeader.next = e.next;
- e.element = it.next();
- e.next = successor;
- e.previous = predecessor;
- }
- else {
- e = new Node(it.next(), successor, predecessor);
- }
-
- predecessor.next = e;
- predecessor = e;
- }
- successor.previous = predecessor;
-
- size += numNew;
- return true;
- }
-
- /**
- * Removes all of the elements from this list.
- */
- public void clear() {
- modCount++;
- header.next = header.previous = header;
- size = 0;
- }
-
- // Positional Access Operations
-
- /**
- * 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 specified index is is out of
- * range (<code>index < 0 || index >= size()</code>)
- */
- public Object get(int index) {
- if (index < 0 || index >= size) {
- throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
- }
- Node e = header;
- if (index < (size >> 1)) {
- for (int i = 0; i <= index; i++) {
- e = e.next;
- }
- }
- else {
- for (int i = size; i > index; i--) {
- e = e.previous;
- }
- }
- return e.element;
- }
-
- /**
- * 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 IndexOutOfBoundsException if the specified index is out of
- * range (<code>index < 0 || index >= size()</code>)
- */
- public Object set(int index, Object element) {
- Node e = entry(index);
- Object oldVal = e.element;
- e.element = element;
- return oldVal;
- }
-
- /**
- * 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 IndexOutOfBoundsException if the specified index is out of
- * range (<code>index < 0 || index > size()</code>)
- */
- public void add(int index, Object element) {
- Node e = (index == size ? header : entry(index));
- Node newNode;
- if (cacheCount > 0) {
- newNode = cacheHeader.next;
- cacheHeader.next = newNode.next;
- newNode.element = element;
- newNode.next = e;
- newNode.previous = e.previous;
- }
- else {
- newNode = new Node(element, e, e.previous);
- }
-
- newNode.previous.next = newNode;
- newNode.next.previous = newNode;
- size++;
- modCount++;
- }
-
- /**
- * Removes the element at the specified position in this list. 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 specified index is out of
- * range (<code>index < 0 || index >= size()</code>)
- */
- public Object remove(int index) {
- Node e = entry(index);
- Object data = e.element;
- remove(e);
- return data;
- }
-
- /**
- * Return the indexed entry.
- */
- private Node entry(int index) {
- if (index < 0 || index >= size) {
- throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
- }
- Node e = header;
- if (index < (size >> 1)) {
- for (int i = 0; i <= index; i++) {
- e = e.next;
- }
- }
- else {
- for (int i = size; i > index; i--) {
- e = e.previous;
- }
- }
- return e;
- }
-
- // Search Operations
-
- /**
- * Returns the index in this list of the first occurrence of the
- * specified element, or -1 if the List does not contain this
- * element. More formally, returns the lowest index i such that
- * <code>(o==null ? get(i)==null : o.equals(get(i)))</code>, or -1 if
- * there is no such index.
- *
- * @param obj element to search for
- * @return the index in this list of the first occurrence of the
- * specified element, or -1 if the list does not contain this
- * element
- */
- public int indexOf(Object obj) {
- int index = 0;
- if (obj == null) {
- for (Node e = header.next; e != header; e = e.next) {
- if (e.element == null)
- return index;
- index++;
- }
- }
- else {
- for (Node e = header.next; e != header; e = e.next) {
- if (obj.equals(e.element))
- return index;
- index++;
- }
- }
- return -1;
- }
-
- /**
- * Returns the index in this list of the last occurrence of the
- * specified element, or -1 if the list does not contain this
- * element. More formally, returns the highest index i such that
- * <code>(o==null ? get(i)==null : o.equals(get(i)))</code>, or -1 if
- * there is no such index.
- *
- * @param obj element to search for
- * @return the index in this list of the last occurrence of the
- * specified element, or -1 if the list does not contain this
- * element
- */
- public int lastIndexOf(Object obj) {
- int index = size;
- if (obj == null) {
- for (Node e = header.previous; e != header; e = e.previous) {
- index--;
- if (e.element == null)
- return index;
- }
- }
- else {
- for (Node e = header.previous; e != header; e = e.previous) {
- index--;
- if (obj.equals(e.element))
- return index;
- }
- }
- return -1;
- }
-
- /**
- * Returns a list-iterator of the elements in this list (in proper
- * sequence), starting at the specified position in the list.
- * Obeys the general contract of <code>List.listIterator(int)</code>.<p>
- * <p>
- * The list-iterator is <i>fail-fast</i>: if the list is structurally
- * modified at any time after the Iterator is created, in any way except
- * through the list-iterator's own <code>remove</code> or <code>add</code>
- * methods, the list-iterator will throw a
- * <code>ConcurrentModificationException</code>. Thus, in the face of
- * concurrent modification, the iterator fails quickly and cleanly, rather
- * than risking arbitrary, non-deterministic behavior at an undetermined
- * time in the future.
- *
- * @param index index of first element to be returned from the
- * list-iterator (by a call to <code>next</code>)
- * @return a ListIterator of the elements in this list (in proper
- * sequence), starting at the specified position in the list
- * @throws IndexOutOfBoundsException if index is out of range
- * (<code>index < 0 || index > size()</code>)
- * @see List#listIterator(int)
- */
- public ListIterator listIterator(int index) {
- return new ListItr(index);
- }
-
- private final class ListItr implements ListIterator {
- private Node lastReturned = header;
- private Node next;
- private int nextIndex;
- private int expectedModCount = modCount;
-
- ListItr(int index) {
- if (index < 0 || index > size)
- throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
- if (index < (size >> 1)) {
- next = header.next;
- for (nextIndex = 0; nextIndex < index; nextIndex++)
- next = next.next;
- }
- else {
- next = header;
- for (nextIndex = size; nextIndex > index; nextIndex--)
- next = next.previous;
- }
- }
-
- public boolean hasNext() {
- return nextIndex != size;
- }
-
- public Object next() {
- checkForComodification();
- if (nextIndex == size)
- throw new NoSuchElementException();
-
- lastReturned = next;
- next = next.next;
- nextIndex++;
- return lastReturned.element;
- }
-
- public boolean hasPrevious() {
- return nextIndex != 0;
- }
-
- public Object previous() {
- if (nextIndex == 0)
- throw new NoSuchElementException();
-
- lastReturned = next = next.previous;
- nextIndex--;
- checkForComodification();
- return lastReturned.element;
- }
-
- public int nextIndex() {
- return nextIndex;
- }
-
- public int previousIndex() {
- return nextIndex - 1;
- }
-
- public void remove() {
- checkForComodification();
- try {
- NodeCachingLinkedList.this.remove(lastReturned);
- }
- catch (NoSuchElementException e) {
- throw new IllegalStateException();
- }
- if (next == lastReturned)
- next = lastReturned.next;
- else
- nextIndex--;
- lastReturned = header;
- expectedModCount++;
- }
-
- public void set(Object o) {
- if (lastReturned == header)
- throw new IllegalStateException();
- checkForComodification();
- lastReturned.element = o;
- }
-
- public void add(Object o) {
- checkForComodification();
- lastReturned = header;
-
- Node newNode;
- if (cacheCount > 0) {
- newNode = cacheHeader.next;
- cacheHeader.next = newNode.next;
- newNode.element = o;
- newNode.next = next;
- newNode.previous = next.previous;
- }
- else {
- newNode = new Node(o, next, next.previous);
- }
-
- newNode.previous.next = newNode;
- newNode.next.previous = newNode;
- size++;
- modCount++;
-
- nextIndex++;
- expectedModCount++;
- }
-
- private void checkForComodification() {
- if (modCount != expectedModCount)
- throw new ConcurrentModificationException();
- }
- }
-
- private final static class Node implements Serializable {
- Object element;
- Node next;
- Node previous;
-
- Node(Object element, Node next, Node previous) {
- this.element = element;
- this.next = next;
- this.previous = previous;
- }
- }
-
-
- private Node addsBefore(Object o, Node e) {
- Node newNode;
- if (cacheCount > 0) {
- newNode = cacheHeader.next;
- cacheHeader.next = newNode.next;
- newNode.element = o;
- newNode.next = e;
- newNode.previous = e.previous;
- }
- else {
- newNode = new Node(o, e, e.previous);
- }
-
- newNode.previous.next = newNode;
- newNode.next.previous = newNode;
- size++;
- modCount++;
- return newNode;
- }
-
-
- private void remove(Node e) {
- if (e == header) {
- throw new NoSuchElementException();
- }
- e.previous.next = e.next;
- e.next.previous = e.previous;
- size--;
- modCount++;
-
- if (cacheCount < maximumCacheSize) {
- e.element = null;
- e.previous = null;
- e.next = cacheHeader.next;
- cacheHeader.next = e;
- cacheCount++;
- }
- }
-
- /**
- * Returns a shallow copy of this <code>NodeCachingLinkedList</code>. (The elements
- * themselves are not cloned.)
- *
- * @return a shallow copy of this <code>NodeCachingLinkedList</code> instance
- */
- public Object clone() {
- NodeCachingLinkedList clone = new NodeCachingLinkedList();
- clone.setMaximumCacheSize(maximumCacheSize);
-
- // Initialize clone with our elements
- for (Node e = header.next; e != header; e = e.next) {
- clone.add(e.element);
- }
-
- return clone;
- }
-
- /**
- * Returns an array containing all of the elements in this list
- * in the correct order.
- *
- * @return an array containing all of the elements in this list
- * in the correct order
- */
- public Object[] toArray() {
- Object[] result = new Object[size];
- int i = 0;
- for (Node e = header.next; e != header; e = e.next)
- result[i++] = e.element;
- return result;
- }
-
- /**
- * Returns an array containing all of the elements in this list in
- * the correct order; the runtime type of the returned array is that of
- * the specified array. If the list fits in the specified array, it
- * is returned therein. Otherwise, a new array is allocated with the
- * runtime type of the specified array and the size of this list.<p>
- * <p>
- * If the list fits in the specified array with room to spare
- * (i.e., the array has more elements than the list),
- * the element in the array immediately following the end of the
- * collection is set to null. This is useful in determining the length
- * of the list <i>only</i> if the caller knows that the list
- * does not contain any null elements.
- *
- * @param a the array into which the elements of the 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 the list
- * @throws ArrayStoreException if the runtime type of a is not a
- * supertype of the runtime type of every element in this list
- * @throws NullPointerException if the specified array is null
- */
- public Object[] toArray(Object a[]) {
- if (a.length < size)
- a = (Object[]) java.lang.reflect.Array.newInstance(a.getClass().getComponentType(), size);
- int i = 0;
- for (Node e = header.next; e != header; e = e.next)
- a[i++] = e.element;
-
- if (a.length > size)
- a[size] = null;
-
- return a;
- }
-
-}
+package org.apache.commons.collections;
+
+import java.util.Collection;
+
+/**
+ * A linked list implementation that caches the nodes used internally to prevent
+ * unnecessary object creates and deletion. This should result in a performance
+ * improvement.
+ *
+ * @author Jeff Varszegi
+ * @author <a href="mailto:rich@rd.gen.nz">Rich Dougherty</a>
+ */
+public class NodeCachingLinkedList extends CommonsLinkedList {
+
+ private static final long serialVersionUID = 1;
+
+ /**
+ * The default value for {@link #maximumCacheSize}.
+ */
+ private static final int DEFAULT_MAXIMUM_CACHE_SIZE = 20;
+
+ /**
+ * The first cached node, or <code>null</code> if no nodes are cached.
+ * Cached nodes are stored in a singly-linked list with {@link Node#next}
+ * pointing to the next element.
+ */
+ private transient Node firstCachedNode;
+
+ /**
+ * The size of the cache.
+ */
+ private transient int cacheSize = 0;
+
+ /**
+ * The maximum size of the cache.
+ */
+ private int maximumCacheSize = DEFAULT_MAXIMUM_CACHE_SIZE;
+
+ public NodeCachingLinkedList() {
+ super();
+ }
+
+ public NodeCachingLinkedList(Collection c) {
+ super(c);
+ }
+
+ public NodeCachingLinkedList(int maximumCacheSize) {
+ super();
+ this.maximumCacheSize = maximumCacheSize;
+ }
+
+ // Cache operations
+
+ /**
+ * Gets the maximum size of the cache.
+ */
+ public int getMaximumCacheSize() {
+ return maximumCacheSize;
+ }
+
+ /**
+ * Sets the maximum size of the cache.
+ */
+ public void setMaximumCacheSize(int maximumCacheSize) {
+ this.maximumCacheSize = maximumCacheSize;
+ shrinkCacheToMaximumSize();
+ }
+
+ /**
+ * Reduce the size of the cache to the maximum, if necessary.
+ */
+ private void shrinkCacheToMaximumSize() {
+ // Rich Dougherty: This could be more efficient.
+ while (cacheSize > maximumCacheSize) {
+ getNodeFromCache();
+ }
+ }
+
+ /**
+ * Gets a node from the cache. If a node is returned, then the value of
+ * {@link #cacheSize} is decreased accordingly. The node that is returned
+ * will have <code>null</code> values for next, previous and element.
+ *
+ * @return A node, or <code>null</code> if there are no nodes in the cache.
+ */
+ private Node getNodeFromCache() {
+ if (cacheSize == 0) {
+ return null;
+ }
+ Node cachedNode = firstCachedNode;
+ firstCachedNode = cachedNode.next;
+ cachedNode.next = null; // This should be changed anyway, but defensively
+ // set it to null.
+ cacheSize--;
+ return cachedNode;
+ }
+
+ private boolean cacheFull() {
+ return cacheSize >= maximumCacheSize;
+ }
+
+ /**
+ * Adds a node to the cache, if the cache isn't full. The node's contents
+ * are cleared to so they can be garbage collected.
+ */
+ private void addNodeToCache(Node node) {
+ if (cacheFull()) {
+ // Don't cache the node.
+ return;
+ }
+ // Clear the node's contents and add it to the cache.
+ Node nextCachedNode = firstCachedNode;
+ node.previous = null;
+ node.next = nextCachedNode;
+ node.element = null;
+ firstCachedNode = node;
+ cacheSize++;
+ }
+
+ // Node operations
+
+ /**
+ * Create a node, getting it from the cache if possible.
+ */
+ protected Node createNode() {
+ Node cachedNode = getNodeFromCache();
+ if (cachedNode == null) {
+ return super.createNode();
+ } else {
+ return cachedNode;
+ }
+ }
+
+ /**
+ * Create a node, getting it from the cache if possible.
+ */
+ protected Node createNode(Node next, Node previous, Object element) {
+ Node cachedNode = getNodeFromCache();
+ if (cachedNode == null) {
+ return super.createNode(next, previous, element);
+ } else {
+ cachedNode.next = next;
+ cachedNode.previous = previous;
+ cachedNode.element = element;
+ return cachedNode;
+ }
+ }
+
+ /**
+ * Calls the superclass' implementation then calls
+ * {@link #addNodeToCache(Node)} on the node which has been removed.
+ *
+ * @see org.apache.commons.collections.CommonsLinkedList#removeNode(Node)
+ */
+ protected void removeNode(Node node) {
+ super.removeNode(node);
+ addNodeToCache(node);
+ }
+
+ protected void removeAllNodes() {
+ // Add the removed nodes to the cache, then remove the rest.
+ // We can add them to the cache before removing them, since
+ // {@link CommonsLinkedList.removeAllNodes()} removes the
+ // nodes by removing references directly from {@link #marker}.
+ int numberOfNodesToCache = Math.min(size, maximumCacheSize - cacheSize);
+ Node node = marker.next;
+ for (int currentIndex = 0; currentIndex < numberOfNodesToCache; currentIndex++) {
+ Node oldNode = node;
+ node = node.next;
+ addNodeToCache(oldNode);
+ }
+ super.removeAllNodes();
+ }
+
+}
1.1 jakarta-commons/collections/src/java/org/apache/commons/collections/CommonsLinkedList.java
Index: CommonsLinkedList.java
===================================================================
package org.apache.commons.collections;
import java.io.IOException;
import java.io.ObjectInputStream;
import java.io.ObjectOutputStream;
import java.io.Serializable;
import java.lang.reflect.Array;
import java.util.AbstractSequentialList;
import java.util.Collection;
import java.util.ConcurrentModificationException;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.ListIterator;
import java.util.NoSuchElementException;
/**
* An implementation of {@link java.util.List} which duplicates the behaviour
* of {@link java.util.LinkedList}, but which provides a more open interface for
* subclasses to extend.
*
* @author <a href="mailto:rich@rd.gen.nz">Rich Dougherty</a>
*/
class CommonsLinkedList extends LinkedList
implements List, Serializable {
/*
* Implementation notes:
* - a standard circular doubly-linked list
* - a marker node is stored to mark the start and the end of the list
* - node creation and removal always occurs through createNode() and
* removeNode().
* - a modification count is kept, with the same semantics as
* {@link java.util.LinkedList}.
* - respects {@link AbstractList#modCount}
*/
/**
* A node within the {@link CommonsLinkedList}.
*
* @author <a href="mailto:rich@nil.co.nz">Rich Dougherty</a>
*/
protected static class Node {
/**
* A pointer to the node before this node.
*/
public Node previous;
/**
* A pointer to the node after this node.
*/
public Node next;
/**
* The object contained within this node.
*/
public Object element;
public Node() {
}
public Node(Node previous, Node next, Object element) {
this.previous = previous;
this.next = next;
this.element = element;
}
/**
* Checks if a value is equal to this node's element.
*
* @return True if the elements are both null or both equal according
* to {@link Object#equals()}.
*/
public boolean elementEquals(Object otherElement) {
if (element == null) {
return otherElement == null;
} else {
return element.equals(otherElement);
}
}
}
/**
* A {@link java.util.ListIterator} {@link CommonsLinkedList}.
*
* @author <a href="mailto:rich@nil.co.nz">Rich Dougherty</a>
*/
protected class ListIteratorImpl implements ListIterator {
/**
* The node that will be returned by {@link #next()}. If this is equal
* to {@link #marker} then there are no more elements to return.
*/
protected Node nextNode;
/**
* The index of {@link #nextNode}.
*/
protected int nextIndex;
/**
* The last node that was returned by {@link #next()} or {@link
* #previous()}. Set to <code>null</code> if {@link #next()} or {@link
* #previous()} haven't been called, or if the node has been removed
* with {@link #remove()} or a new node added with {@link #add(Object)}.
* Should be accesed through {@link #getLastNodeReturned()} to enforce
* this behaviour.
*/
protected Node lastNodeReturned;
/**
* The modification count that the list is expected to have. If the list
* doesn't have this count, then a
* {@link java.util.ConcurrentModificationException} may be thrown by
* the operations.
*/
protected int expectedModCount;
/**
* Create a ListIterator for a list, starting at the first element in
* the list.
*/
public ListIteratorImpl() throws IndexOutOfBoundsException {
this(0);
}
/**
* Create a ListIterator for a list.
*
* @param startIndex The index to start at.
*/
public ListIteratorImpl(int startIndex)
throws IndexOutOfBoundsException {
expectedModCount = modCount;
nextNode = getNode(startIndex, true);
nextIndex = startIndex;
}
/**
* Checks the modification count of the list is the value that this
* object expects.
*
* @throws ConcurrentModificationException If the list's modification
* count isn't the value that was expected.
*/
protected void checkModCount()
throws ConcurrentModificationException {
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
}
/**
* Gets the last node returned.
*
* @throws IllegalStateException If {@link #next()} or {@link
* #previous()} haven't been called, or if the node has been removed
* with {@link #remove()} or a new node added with {@link #add(Object)}.
*/
protected Node getLastNodeReturned() throws IllegalStateException {
if (lastNodeReturned == null) {
throw new IllegalStateException();
}
return lastNodeReturned;
}
public boolean hasNext() {
return nextNode != marker;
}
public Object next() {
checkModCount();
if (!hasNext()) {
throw new NoSuchElementException("No element at index " +
nextIndex + ".");
}
Object element = nextNode.element;
lastNodeReturned = nextNode;
nextNode = nextNode.next;
nextIndex++;
return element;
}
public boolean hasPrevious() {
return nextNode.previous != marker;
}
public Object previous() {
checkModCount();
if (!hasPrevious()) {
throw new NoSuchElementException("Already at start of list.");
}
nextNode = nextNode.previous;
Object element = nextNode.element;
lastNodeReturned = nextNode;
nextIndex--;
return element;
}
public int nextIndex() {
return nextIndex;
}
public int previousIndex() {
return nextIndex - 1;
}
public void remove() {
checkModCount();
removeNode(getLastNodeReturned());
lastNodeReturned = null;
nextIndex--;
expectedModCount++;
}
public void set(Object o) {
checkModCount();
getLastNodeReturned().element = o;
}
public void add(Object o) {
checkModCount();
addNodeBefore(nextNode, o);
lastNodeReturned = null;
nextIndex++;
expectedModCount++;
}
}
private static final long serialVersionUID = 1L;
/**
* A {@link Node} which ndicates the start and end of the list and does not
* hold a value. The value of <code>next</code> is the first item in the
* list. The value of of <code>previous</code> is the last item in the list.
*/
protected transient Node marker;
/**
* The size of the list.
*/
protected transient int size;
public CommonsLinkedList() {
initializeEmptyList();
}
public CommonsLinkedList(Collection c) {
initializeEmptyList();
addAll(c);
}
/**
* The equivalent of a default constructor, broken out so it can be called
* by any constructor and by {@link #readObject(ObjectInputStream)}.
* Subclasses which override this method should make sure they call it so
* the list is initialised properly.
*/
protected void initializeEmptyList() {
marker = createNode();
marker.next = marker;
marker.previous = marker;
}
// Operations on nodes
protected Node createNode() {
return new Node();
}
protected Node createNode(Node next, Node previous, Object element) {
return new Node(next, previous, element);
}
private void addNodeBefore(Node node, Object o) {
Node newNode = createNode(node.previous, node, o);
node.previous.next = newNode;
node.previous = newNode;
size++;
modCount++;
}
protected void addNodeAfter(Node node, Object o) {
Node newNode = createNode(node, node.next, o);
node.next.previous = newNode;
node.next = newNode;
size++;
modCount++;
}
protected void removeNode(Node node) {
node.previous.next = node.next;
node.next.previous = node.previous;
size--;
modCount++;
}
protected void removeAllNodes() {
marker.next = marker;
marker.previous = marker;
size = 0;
modCount++;
}
/**
* Gets the node at a particular index.
*
* @param index The index, starting from 0.
* @param endMarkerAllowd Whether or not the end marker can be returned if
* startIndex is set to the list's size.
* @throws IndexOutOfBoundsException If the index is less than 0; equal to
* the size of the list and endMakerAllowed is false; or greater than the
* size of the list.
*/
protected Node getNode(int index, boolean endMarkerAllowed) throws IndexOutOfBoundsException {
// Check the index is within the bounds
if (index < 0) {
throw new IndexOutOfBoundsException("Couldn't get the node: " +
"index (" + index + ") less than zero.");
}
if (!endMarkerAllowed && index == size) {
throw new IndexOutOfBoundsException("Couldn't get the node: " +
"index (" + index + ") is the size of the list.");
}
if (index > size) {
throw new IndexOutOfBoundsException("Couldn't get the node: " +
"index (" + index + ") greater than the size of the " +
"list (" + size + ").");
}
// Search the list and get the node
Node node;
if (index < (size / 2)) {
// Search forwards
node = marker.next;
for (int currentIndex = 0; currentIndex < index; currentIndex++) {
node = node.next;
}
} else {
// Search backwards
node = marker;
for (int currentIndex = size; currentIndex > index; currentIndex--) {
node = node.previous;
}
}
return node;
}
// List implementation required by AbstractSequentialList
public ListIterator listIterator() {
return new ListIteratorImpl();
}
public ListIterator listIterator(int startIndex) {
return new ListIteratorImpl(startIndex);
}
public int size() {
return size;
}
// List implementation not required by AbstractSequentialList, but provided
// for efficiency or to override LinkedList's implementation.
public void clear() {
removeAllNodes();
}
public boolean add(Object o) {
addLast(o);
return true;
}
public void add(int index, Object element) {
Node node = getNode(index, true);
addNodeBefore(node, element);
}
public boolean addAll(Collection c) {
return addAll(size, c);
}
public boolean addAll(int index, Collection c) {
Node node = getNode(index, true);
for (Iterator itr = c.iterator(); itr.hasNext();) {
Object element = itr.next();
addNodeBefore(node, element);
}
return true;
}
public Object get(int index) {
Node node = getNode(index, false);
return node.element;
}
public Object set(int index, Object element) {
Node node = getNode(index, false);
Object oldElement = node.element;
node.element = element;
return oldElement;
}
public Object remove(int index) {
Node node = getNode(index, false);
Object oldElement = node.element;
removeNode(node);
return oldElement;
}
public boolean remove(Object element) {
for (Node node = marker.next; node != marker; node = node.next) {
if (node.elementEquals(element)) {
removeNode(node);
return true;
}
}
return false;
}
public int indexOf(Object element) {
int i = 0;
for (Node node = marker.next; node != marker; node = node.next) {
if (node.elementEquals(element)) {
return i;
}
i++;
}
return -1;
}
public int lastIndexOf(Object element) {
int i = size - 1;
for (Node node = marker.previous; node != marker; node = node.previous) {
if (node.elementEquals(element)) {
return i;
}
i--;
}
return -1;
}
public boolean contains(Object element) {
return indexOf(element) != -1;
}
public Object[] toArray() {
return toArray(new Object[size]);
}
public Object[] toArray(Object[] array) {
// Extend the array if needed
if (array.length < size) {
Class componentType = array.getClass().getComponentType();
array = (Object[]) Array.newInstance(componentType, size);
}
// Copy the values into the array
Node node = marker.next;
for (int i = 0; i < size; i++) {
array[i] = node.element;
node = node.next;
}
// Set the value after the last element to null
if (array.length > size) {
array[size] = null;
}
return array;
}
// Extra methods compatible with java.util.LinkedList.
public Object getFirst() {
Node node = marker.next;
if (node == marker) {
throw new NoSuchElementException();
}
return node.element;
}
public Object getLast() {
Node node = marker.previous;
if (node == marker) {
throw new NoSuchElementException();
}
return node.element;
}
public void addFirst(Object o) {
addNodeAfter(marker, o);
}
public void addLast(Object o) {
addNodeBefore(marker, o);
}
public Object removeFirst() {
Node node = marker.next;
if (node == marker) {
throw new NoSuchElementException();
}
Object oldElement = node.element;
removeNode(node);
return oldElement;
}
public Object removeLast() {
Node node = marker.previous;
if (node == marker) {
throw new NoSuchElementException();
}
Object oldElement = node.element;
removeNode(node);
return oldElement;
}
// Serialization methods
private void writeObject(ObjectOutputStream outputStream)
throws IOException, ClassNotFoundException {
outputStream.defaultWriteObject();
// Write the size so we know how many nodes to read back
outputStream.writeInt(size());
for (Iterator itr = iterator(); itr.hasNext();) {
outputStream.writeObject(itr.next());
}
}
private void readObject(ObjectInputStream inputStream)
throws IOException, ClassNotFoundException {
inputStream.defaultReadObject();
initializeEmptyList();
int size = inputStream.readInt();
for (int i = 0; i < size; i++) {
add(inputStream.readObject());
}
}
}
1.39 +5 -4 jakarta-commons/collections/src/test/org/apache/commons/collections/TestAll.java
Index: TestAll.java
===================================================================
RCS file: /home/cvs/jakarta-commons/collections/src/test/org/apache/commons/collections/TestAll.java,v
retrieving revision 1.38
retrieving revision 1.39
diff -u -r1.38 -r1.39
--- TestAll.java 7 Jan 2003 13:24:52 -0000 1.38
+++ TestAll.java 7 Jan 2003 15:18:14 -0000 1.39
@@ -81,6 +81,7 @@
suite.addTest(TestBoundedFifoBuffer.suite());
suite.addTest(TestBoundedFifoBuffer2.suite());
suite.addTest(TestCollectionUtils.suite());
+ suite.addTest(TestCommonsLinkedList.suite());
suite.addTest(TestBufferUtils.suite());
suite.addTest(TestSetUtils.suite());
suite.addTest(TestListUtils.suite());
1.10 +5 -5 jakarta-commons/collections/src/test/org/apache/commons/collections/TestMultiHashMap.java
Index: TestMultiHashMap.java
===================================================================
RCS file: /home/cvs/jakarta-commons/collections/src/test/org/apache/commons/collections/TestMultiHashMap.java,v
retrieving revision 1.9
retrieving revision 1.10
diff -u -r1.9 -r1.10
--- TestMultiHashMap.java 24 Nov 2002 20:24:49 -0000 1.9
+++ TestMultiHashMap.java 7 Jan 2003 15:18:14 -0000 1.10
@@ -92,8 +92,8 @@
}
// MutltiHashMap was introduced in Collections 2.x
- public int getCompatibilityVersion() {
- return 2;
+ public String getCompatibilityVersion() {
+ return "2";
}
public Map makeEmptyMap() {
1.2 +11 -6 jakarta-commons/collections/src/test/org/apache/commons/collections/TestNodeCachingLinkedList.java
Index: TestNodeCachingLinkedList.java
===================================================================
RCS file: /home/cvs/jakarta-commons/collections/src/test/org/apache/commons/collections/TestNodeCachingLinkedList.java,v
retrieving revision 1.1
retrieving revision 1.2
diff -u -r1.1 -r1.2
--- TestNodeCachingLinkedList.java 18 Nov 2002 23:58:46 -0000 1.1
+++ TestNodeCachingLinkedList.java 7 Jan 2003 15:18:15 -0000 1.2
@@ -68,14 +68,14 @@
*
* @author Jeff Varszegi
*/
-public class TestNodeCachingLinkedList extends TestList {
+public class TestNodeCachingLinkedList extends TestLinkedList {
protected NodeCachingLinkedList list = null;
public TestNodeCachingLinkedList(String _testName) {
super(_testName);
}
- public List makeEmptyList() {
+ public LinkedList makeEmptyLinkedList() {
return new NodeCachingLinkedList();
}
@@ -87,6 +87,10 @@
return BulkTest.makeSuite(TestNodeCachingLinkedList.class);
}
+ public String getCompatibilityVersion() {
+ return "2.2";
+ }
+
public static void compareSpeed() {
NodeCachingLinkedList ncll = new NodeCachingLinkedList();
LinkedList ll = new LinkedList();
@@ -157,8 +161,9 @@
public static void main(String args[]) {
+ compareSpeed();
String[] testCaseName = { TestNodeCachingLinkedList.class.getName()};
junit.textui.TestRunner.main(testCaseName);
}
-}
\ No newline at end of file
+}
1.16 +13 -9 jakarta-commons/collections/src/test/org/apache/commons/collections/TestObject.java
Index: TestObject.java
===================================================================
RCS file: /home/cvs/jakarta-commons/collections/src/test/org/apache/commons/collections/TestObject.java,v
retrieving revision 1.15
retrieving revision 1.16
diff -u -r1.15 -r1.16
--- TestObject.java 4 Jan 2003 13:43:10 -0000 1.15
+++ TestObject.java 7 Jan 2003 15:18:15 -0000 1.16
@@ -95,19 +95,23 @@
public static final int COLLECTIONS_MAJOR_VERSION = 2;
/**
+ * Get the version of Collections that this object tries to
+ * maintain serialization compatibility with. Defaults to 1, the
+ * earliest Collections version. (Note: some collections did not
+ * even exist in this version).
+ *
* This constant makes it possible for TestMap (and other subclasses,
* if necessary) to automatically check CVS for a versionX copy of a
* Serialized object, so we can make sure that compatibility is maintained.
* See, for example, TestMap.getCanonicalFullMapName(Map map).
* Subclasses can override this variable, indicating compatibility
* with earlier Collections versions.
- * Defaults to 1, the earliest Collections version. (Note: some
- * collections did not even exist in this version).
*
- * @return 1
+ * @return The version, or <code>null</code> if this object shouldn't be
+ * tested for compatibility with previous versions.
*/
- public int getCompatibilityVersion() {
- return 1;
+ public String getCompatibilityVersion() {
+ return "1";
}
/**
1.4 +6 -6 jakarta-commons/collections/src/test/org/apache/commons/collections/TestReferenceMap.java
Index: TestReferenceMap.java
===================================================================
RCS file: /home/cvs/jakarta-commons/collections/src/test/org/apache/commons/collections/TestReferenceMap.java,v
retrieving revision 1.3
retrieving revision 1.4
diff -u -r1.3 -r1.4
--- TestReferenceMap.java 7 Nov 2002 21:43:36 -0000 1.3
+++ TestReferenceMap.java 7 Jan 2003 15:18:15 -0000 1.4
@@ -184,8 +184,8 @@
*/
- public int getCompatibilityVersion() {
- return 2; // actually 2.1, but can't represent that as an int
+ public String getCompatibilityVersion() {
+ return "2.1";
}
1.18 +2 -2 jakarta-commons/collections/src/test/org/apache/commons/collections/TestSequencedHashMap.java
Index: TestSequencedHashMap.java
===================================================================
RCS file: /home/cvs/jakarta-commons/collections/src/test/org/apache/commons/collections/TestSequencedHashMap.java,v
retrieving revision 1.17
retrieving revision 1.18
diff -u -r1.17 -r1.18
--- TestSequencedHashMap.java 24 Nov 2002 20:49:29 -0000 1.17
+++ TestSequencedHashMap.java 7 Jan 2003 15:18:15 -0000 1.18
@@ -89,8 +89,8 @@
// current versions of SequencedHashMap and subclasses are not
// compatible with Collections 1.x
- public int getCompatibilityVersion() {
- return 2;
+ public String getCompatibilityVersion() {
+ return "2";
}
public static void main(String[] args) {
1.1 jakarta-commons/collections/src/test/org/apache/commons/collections/TestCommonsLinkedList.java
Index: TestCommonsLinkedList.java
===================================================================
/*
* $Header: /home/cvs/jakarta-commons/collections/src/test/org/apache/commons/collections/TestCommonsLinkedList.java,v 1.1 2003/01/07 15:18:14 rwaldhoff Exp $
* $Revision: 1.1 $
* $Date: 2003/01/07 15:18:14 $
*
* ====================================================================
*
* The Apache Software License, Version 1.1
*
* Copyright (c) 1999-2002 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 java.util.*;
import junit.framework.Test;
/**
* Test case for {@link CommonsLinkedList}.
*
* @author <a href="mailto:rich@rd.gen.nz">Rich Dougherty</a>
*/
public class TestCommonsLinkedList extends TestLinkedList {
public TestCommonsLinkedList(String testName) {
super(testName);
}
public LinkedList makeEmptyLinkedList() {
return new CommonsLinkedList();
}
public static Test suite() {
return BulkTest.makeSuite(TestCommonsLinkedList.class);
}
public String getCompatibilityVersion() {
return "2.2";
}
}
1.1 jakarta-commons/collections/src/test/org/apache/commons/collections/TestLinkedList.java
Index: TestLinkedList.java
===================================================================
/*
* $Header: /home/cvs/jakarta-commons/collections/src/test/org/apache/commons/collections/TestLinkedList.java,v 1.1 2003/01/07 15:18:14 rwaldhoff Exp $
* $Revision: 1.1 $
* $Date: 2003/01/07 15:18:14 $
*
* ====================================================================
*
* 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 java.io.IOException;
import java.io.Serializable;
import java.lang.reflect.InvocationTargetException;
import java.lang.reflect.Method;
import java.util.AbstractCollection;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.ConcurrentModificationException;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.ListIterator;
import java.util.NoSuchElementException;
/**
* Tests base {@link java.util.LinkedList} methods and contracts.
* <p>
* To use, simply extend this class, and implement
* the {@link #makeLinkedList} method.
* <p>
* If your {@link LinkedList} fails one of these tests by design,
* you may still use this base set of cases. Simply override the
* test case (method) your {@link List} fails.
*
* @author <a href="mailto:rich@rd.gen.nz">Rich Dougherty</a>
* @version $Id: TestLinkedList.java,v 1.1 2003/01/07 15:18:14 rwaldhoff Exp $
*/
public abstract class TestLinkedList extends TestList {
public TestLinkedList(String testName) {
super(testName);
}
protected List makeEmptyList() {
return makeEmptyLinkedList();
}
protected List makeFullList() {
return makeFullLinkedList();
}
/**
* Return a new, empty {@link LinkedList} to be used for testing.
*
* @return an empty list for testing.
*/
protected abstract LinkedList makeEmptyLinkedList();
/**
* Return a new, full {@link List} to be used for testing.
*
* @return a full list for testing
*/
protected LinkedList makeFullLinkedList() {
// only works if list supports optional "addAll(Collection)"
LinkedList list = makeEmptyLinkedList();
list.addAll(Arrays.asList(getFullElements()));
return list;
}
/**
* Returns the {@link #collection} field cast to a {@link LinkedList}.
*
* @return the collection field as a List
*/
protected LinkedList getLinkedList() {
return (LinkedList)collection;
}
/**
* Returns the {@link #confirmed} field cast to a {@link LinkedList}.
*
* @return the confirmed field as a List
*/
protected LinkedList getConfirmedLinkedList() {
return (LinkedList)confirmed;
}
/**
* Tests {@link LinkedList#addFirst(Object)}.
*/
public void testLinkedListAddFirst() {
if (!isAddSupported()) return;
Object o = "hello";
resetEmpty();
getLinkedList().addFirst(o);
getConfirmedLinkedList().addFirst(o);
verify();
resetFull();
getLinkedList().addFirst(o);
getConfirmedLinkedList().addFirst(o);
verify();
}
/**
* Tests {@link LinkedList#addLast(Object)}.
*/
public void testLinkedListAddLast() {
if (!isAddSupported()) return;
Object o = "hello";
resetEmpty();
getLinkedList().addLast(o);
getConfirmedLinkedList().addLast(o);
verify();
resetFull();
getLinkedList().addLast(o);
getConfirmedLinkedList().addLast(o);
verify();
}
/**
* Tests {@link LinkedList#getFirst(Object)}.
*/
public void testLinkedListGetFirst() {
resetEmpty();
try {
getLinkedList().getFirst();
fail("getFirst() should throw a NoSuchElementException for an " +
"empty list.");
} catch (NoSuchElementException e) {
// This is correct
}
verify();
resetFull();
Object first = getLinkedList().getFirst();
Object confirmedFirst = getConfirmedLinkedList().getFirst();
assertEquals("Result returned by getFirst() was wrong.",
confirmedFirst, first);
verify();
}
/**
* Tests {@link LinkedList#getLast(Object)}.
*/
public void testLinkedListGetLast() {
resetEmpty();
try {
getLinkedList().getLast();
fail("getLast() should throw a NoSuchElementException for an " +
"empty list.");
} catch (NoSuchElementException e) {
// This is correct
}
verify();
resetFull();
Object last = getLinkedList().getLast();
Object confirmedLast = getConfirmedLinkedList().getLast();
assertEquals("Result returned by getLast() was wrong.",
confirmedLast, last);
verify();
}
/**
* Tests {@link LinkedList#removeFirst(Object)}.
*/
public void testLinkedListRemoveFirst() {
if (!isRemoveSupported()) return;
resetEmpty();
try {
getLinkedList().removeFirst();
fail("removeFirst() should throw a NoSuchElementException for " +
"an empty list.");
} catch (NoSuchElementException e) {
// This is correct
}
verify();
resetFull();
Object first = getLinkedList().removeFirst();
Object confirmedFirst = getConfirmedLinkedList().removeFirst();
assertEquals("Result returned by removeFirst() was wrong.",
confirmedFirst, first);
verify();
}
/**
* Tests {@link LinkedList#removeLast(Object)}.
*/
public void testLinkedListRemoveLast() {
if (!isRemoveSupported()) return;
resetEmpty();
try {
getLinkedList().removeLast();
fail("removeLast() should throw a NoSuchElementException for " +
"an empty list.");
} catch (NoSuchElementException e) {
// This is correct
}
verify();
resetFull();
Object last = getLinkedList().removeLast();
Object confirmedLast = getConfirmedLinkedList().removeLast();
assertEquals("Result returned by removeLast() was wrong.",
confirmedLast, last);
verify();
}
/**
* Returns an empty {@link ArrayList}.
*/
protected Collection makeConfirmedCollection() {
return new LinkedList();
}
/**
* Returns a full {@link ArrayList}.
*/
protected Collection makeConfirmedFullCollection() {
List list = new LinkedList();
list.addAll(Arrays.asList(getFullElements()));
return list;
}
}
1.6 +2 -2 jakarta-commons/collections/src/test/org/apache/commons/collections/comparators/TestComparator.java
Index: TestComparator.java
===================================================================
RCS file: /home/cvs/jakarta-commons/collections/src/test/org/apache/commons/collections/comparators/TestComparator.java,v
retrieving revision 1.5
retrieving revision 1.6
diff -u -r1.5 -r1.6
--- TestComparator.java 12 Oct 2002 22:36:23 -0000 1.5
+++ TestComparator.java 7 Jan 2003 15:18:15 -0000 1.6
@@ -28,8 +28,8 @@
*
* @return 2
*/
- public int getCompatibilityVersion() {
- return 2;
+ public String getCompatibilityVersion() {
+ return "2";
}
public void reverseObjects(List list) {
--
To unsubscribe, e-mail: <ma...@jakarta.apache.org>
For additional commands, e-mail: <ma...@jakarta.apache.org>