goldman.collection
Class AbstractCollection<E>

java.lang.Object
  extended by goldman.collection.AbstractCollection<E>
All Implemented Interfaces:
Collection<E>, Iterable<E>
Direct Known Subclasses:
AbstractPositionalCollection, AbstractSearchTree, BinaryHeap, DirectAddressing, KDTree, LeftistHeap, PairingHeap, SeparateChaining, SkipList, SortedArray, Trie

public abstract class AbstractCollection<E>
extends Object
implements Collection<E>

The AbstractCollection class implements methods that can be shared by all data structures that implement a collection. Some of these methods involve maintaining and accessing the number of elements in the collection (e.g. size, isEmpty), and others are implemented in terms of abstract methods like add. In some cases, the implementations provided here are "brute-force," implementations but they can be overridden when a more efficient algorithm exists for a specific data structure. Also, the methodology and associated instance variable version, for triggering a ConcurrentModificationException when appropriate, is included where to be inherited by all collection data structures.


Nested Class Summary
 class AbstractCollection.AbstractLocator<T extends E>
           
 class AbstractCollection.VisitingIterator
           
 
Field Summary
 Comparator<? super E> comp
           
static int DEFAULT_CAPACITY
           
protected static int FORE
           
protected static int NOT_FOUND
           
protected  int size
           
protected  Version version
           
 
Constructor Summary
AbstractCollection(Comparator<? super E> comparator)
           
 
Method Summary
 void accept(Visitor<? super E> v)
          Traverses the entire collection on behalf of a visitor.
 void addAll(Collection<? extends E> c)
          Adds all elements in c to the collection.
 void checkRep()
          Checks, for the purposes of checking correctness, that the correctness properties are preserved.
 void clear()
          Removes all items from the collection.
protected  int compare(E e1, E e2)
           
 boolean contains(E value)
          This implementation for contains takes linear time, so it is overridden by a more efficient method in most data structure implementations.
 void ensureCapacity(int capacity)
          Increases the capacity of the collection, if necessary, to ensure that it can hold at least capacity elements.
protected  boolean equivalent(E e1, E e2)
           
 int getCapacity()
          By default this method returns Integer.MAX_VALUE.
 Comparator<? super E> getComparator()
          Returns the comparator for elements in this collection.
static
<T> T
getElementAtRank(Collection<T> coll, int rank)
          This is a non-mutating method.
static
<T> T
getElementAtRank(Collection<T> coll, int rank, Comparator<? super T> comp)
          This is a non-mutating method.
 E getEquivalentElement(E target)
          Returns an element in the collection that is equivalent to target.
 int getSize()
          Returns the number of elements, size, in this collection.
 boolean isEmpty()
          Returns true if this collection contains no elements, and otherwise returns false.
 void retainAll(Collection<E> c)
          Updates the current collection to contain only elements that are also in c
 Object[] toArray()
          Returns a Java primitive array of length n that holds the elements in this collection in the iteration order.
 E[] toArray(E[] array)
          Fills a Java array with the elements in this collection in the iteration order, and returns the array that was filled.
 String toString()
          Returns a string that includes each element in this collection (as produced by the toString method for that element), in the iteration order.
protected  void traverseForVisitor(Visitor<? super E> v)
          Traverses the collection applying v to each element
 void trimToSize()
          Trims the capacity of this collection to be its current size.
protected  void writeElements(StringBuilder s)
          Appends, to the string buffer a comma-separated string representation for each element in the collection, in the iteration order.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
 
Methods inherited from interface goldman.collection.Collection
add, getLocator, iterator, remove
 

Field Detail

FORE

protected static final int FORE
See Also:
Constant Field Values

NOT_FOUND

protected static final int NOT_FOUND
See Also:
Constant Field Values

DEFAULT_CAPACITY

public static final int DEFAULT_CAPACITY
See Also:
Constant Field Values

size

protected int size

version

protected Version version

comp

public Comparator<? super E> comp
Constructor Detail

AbstractCollection

public AbstractCollection(Comparator<? super E> comparator)
Method Detail

checkRep

public void checkRep()
Checks, for the purposes of checking correctness, that the correctness properties are preserved.

Specified by:
checkRep in interface Collection<E>

isEmpty

public boolean isEmpty()
Description copied from interface: Collection
Returns true if this collection contains no elements, and otherwise returns false.

Specified by:
isEmpty in interface Collection<E>
Returns:
true if and only if no elements are stored in the collection

getSize

public int getSize()
Description copied from interface: Collection
Returns the number of elements, size, in this collection.

Specified by:
getSize in interface Collection<E>
Returns:
the number of elements stored in the collection

getCapacity

public int getCapacity()
By default this method returns Integer.MAX_VALUE.

Specified by:
getCapacity in interface Collection<E>
Returns:
the current capacity of the collection.

getComparator

public Comparator<? super E> getComparator()
Description copied from interface: Collection
Returns the comparator for elements in this collection.

Specified by:
getComparator in interface Collection<E>
Returns:
the comparator used for this collection

compare

protected int compare(E e1,
                      E e2)
Parameters:
e1 - the first element to compare
e2 - the second element to compare
Returns:
a negative value when e1 < e2, zero when e1 equals e2, and a positive value when e1 > e2.

equivalent

protected boolean equivalent(E e1,
                             E e2)
Parameters:
e1 - one element to compare
e2 - the second element to compare
Returns:
true if and only if e1 and e2 are equivalent with respect to the set

toArray

public Object[] toArray()
Description copied from interface: Collection
Returns a Java primitive array of length n that holds the elements in this collection in the iteration order.

Specified by:
toArray in interface Collection<E>
Returns:
a Java primitive array of capacity n that holds each element of the collection

toArray

public E[] toArray(E[] array)
Description copied from interface: Collection
Fills a Java array with the elements in this collection in the iteration order, and returns the array that was filled. If the array provided as a parameter is not large enough to hold all the elements of the collection, a new array of the same type is created with length n and is returned instead of the provided one.

Specified by:
toArray in interface Collection<E>
Parameters:
array - an array of the correct type into which the collection's elements are to be placed
Returns:
a Java primitive array of capacity at least n that holds each element of the collection

contains

public boolean contains(E value)
This implementation for contains takes linear time, so it is overridden by a more efficient method in most data structure implementations.

Specified by:
contains in interface Collection<E>
Parameters:
value - the element to be located
Returns:
true if and only if an equivalent element exists in the collection

getEquivalentElement

public E getEquivalentElement(E target)
Description copied from interface: Collection
Returns an element in the collection that is equivalent to target. It throws a NoSuchElementException when there is no equivalent element. The contains method should be used to determine if an element is in the collection.

Specified by:
getEquivalentElement in interface Collection<E>
Parameters:
target - the target element
Returns:
an equivalent element that is in the collection
Throws:
NoSuchElementException - there is no equivalent element in the collection.

writeElements

protected void writeElements(StringBuilder s)
Appends, to the string buffer a comma-separated string representation for each element in the collection, in the iteration order.

Parameters:
s - a string builder

toString

public String toString()
Description copied from interface: Collection
Returns a string that includes each element in this collection (as produced by the toString method for that element), in the iteration order.

Specified by:
toString in interface Collection<E>
Overrides:
toString in class Object
Returns:
a comma-separated string that shows the sequence held in the collection, in the iteration order. Braces mark the beginning and the end of the collection.

accept

public final void accept(Visitor<? super E> v)
Traverses the entire collection on behalf of a visitor.

Specified by:
accept in interface Collection<E>
Parameters:
v - a visitor
Throws:
VisitAbortedException - the traversal is aborted due to an exception raised by the visitor, in which case the cause held by the VisitAbortedException is the exception thrown by the visitor.

traverseForVisitor

protected void traverseForVisitor(Visitor<? super E> v)
                           throws Exception
Traverses the collection applying v to each element

Parameters:
v - a visitor
Throws:
Exception

getElementAtRank

public static <T> T getElementAtRank(Collection<T> coll,
                                     int rank)
This is a non-mutating method.

Parameters:
coll - the collection to use
rank - the rank of the desired element
Returns:
the element that would be in position r if the collection were sorted, where the smallest element is defined as rank 0

getElementAtRank

public static <T> T getElementAtRank(Collection<T> coll,
                                     int rank,
                                     Comparator<? super T> comp)
This is a non-mutating method.

Parameters:
coll - the collection to use
rank - the rank of the desired element
comp - the comparator that defines the ordering of the elements
Returns:
the element that would be in position r if the collection were sorted

ensureCapacity

public void ensureCapacity(int capacity)
Increases the capacity of the collection, if necessary, to ensure that it can hold at least capacity elements.

Specified by:
ensureCapacity in interface Collection<E>
Parameters:
capacity - the desired capacity for the collection

trimToSize

public void trimToSize()
Trims the capacity of this collection to be its current size. An application can use this operation to minimize space usage.

Specified by:
trimToSize in interface Collection<E>

addAll

public void addAll(Collection<? extends E> c)
Adds all elements in c to the collection.

Specified by:
addAll in interface Collection<E>
Parameters:
c - the collection to be added

retainAll

public void retainAll(Collection<E> c)
Updates the current collection to contain only elements that are also in c

Specified by:
retainAll in interface Collection<E>
Parameters:
c - a collection

clear

public void clear()
Removes all items from the collection.

Specified by:
clear in interface Collection<E>