goldman.collection.ordered
Class SkipList<E>

java.lang.Object
  extended by goldman.collection.AbstractCollection<E>
      extended by goldman.collection.ordered.SkipList<E>
All Implemented Interfaces:
Collection<E>, OrderedCollection<E>, Tracked<E>, Iterable<E>

public class SkipList<E>
extends AbstractCollection<E>
implements OrderedCollection<E>, Tracked<E>

The skip list is a sorted list with additional structure that supports finding an element in expected logarithmic time. Unlike balanced search trees, a skip list achieves logarithmic performance without rearranging the structure when elements are added or removed from the collection. Furthermore, once an element is located, all other skip list methods (e.g., the insertion or removal of an element, or moving forward or backwards in the list) execute in expected constant time. The key drawback, as compared to a red-black tree, is that the search time is slower. While the probability of a search taking more than logarithmic time is extremely small, there is more variation in the search time than with a red-black tree.


Nested Class Summary
protected  class SkipList.Tracker
           
 
Nested classes/interfaces inherited from class goldman.collection.AbstractCollection
AbstractCollection.AbstractLocator<T extends E>, AbstractCollection.VisitingIterator
 
Field Summary
static int DEFAULT_HEIGHT
           
static int MAX_HEIGHT
           
 
Fields inherited from class goldman.collection.AbstractCollection
comp, DEFAULT_CAPACITY, FORE, NOT_FOUND, size, version
 
Constructor Summary
SkipList()
          Creates an empty skip list using the default height and comparator
SkipList(Comparator<? super E> comp)
          Creates an empty skip list that uses the given comparator and the default height for head and tail.
SkipList(int size)
          Creates an empty skip list using the default comparator and the provided size for the height of the head and tail.
SkipList(int size, Comparator<? super E> comp)
          Creates an empty skip list that uses the provided initial height for head and tail and the provided comparator.
 
Method Summary
 void add(E element)
          Inserts element into the collection.
 void addAll(Collection<? extends E> c)
          Iterates through c and adds each element in c to the collection
 Locator<E> addTracked(E element)
          Inserts element into the collection.
 boolean contains(E target)
          This implementation for contains takes linear time, so it is overridden by a more efficient method in most data structure implementations.
 E get(int r)
          Returns the rth element in the sorted order, where r=0 is the minimum element.
 E getEquivalentElement(E target)
          Returns an element in the collection that is equivalent to target.
 SkipList.Tracker getLocator(E element)
          Returns a locator that has been initialized to an element equivalent to target.
protected  goldman.collection.ordered.SkipList.Tower<E> insert(E element)
          Inserts element into the collection
 SkipList.Tracker iterator()
          Creates a new tracker at FORE.
 SkipList.Tracker iteratorAtEnd()
          Creates a new tracker at AFT.
 E max()
          Returns a greatest element in the collection (according to the comparator).
 E min()
          Returns a least element in the collection (according to the comparator).
 E predecessor(E target)
          This method does not require that target be in the collection.
 boolean remove(E element)
          Removes the first occurrence of the target from the collection, if an equivalent element exists in the collection.
 void retainAll(Collection<E> c)
          Updates the current collection to contain only elements that are also in c.
 E successor(E target)
          This method does not require that target be in the collection.
 void viewStructure()
           
 
Methods inherited from class goldman.collection.AbstractCollection
accept, checkRep, clear, compare, ensureCapacity, equivalent, getCapacity, getComparator, getElementAtRank, getElementAtRank, getSize, isEmpty, toArray, toArray, toString, traverseForVisitor, trimToSize, writeElements
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
 
Methods inherited from interface goldman.collection.Collection
accept, checkRep, clear, ensureCapacity, getCapacity, getComparator, getSize, isEmpty, toArray, toArray, toString, trimToSize
 
Methods inherited from interface goldman.collection.Collection
accept, checkRep, clear, ensureCapacity, getCapacity, getComparator, getSize, isEmpty, toArray, toArray, toString, trimToSize
 

Field Detail

DEFAULT_HEIGHT

public static final int DEFAULT_HEIGHT
See Also:
Constant Field Values

MAX_HEIGHT

public static final int MAX_HEIGHT
See Also:
Constant Field Values
Constructor Detail

SkipList

public SkipList(int size,
                Comparator<? super E> comp)
Creates an empty skip list that uses the provided initial height for head and tail and the provided comparator.

Parameters:
size - the initial size for head and tail
comp - the comparator that defines an ordering among the elements

SkipList

public SkipList()
Creates an empty skip list using the default height and comparator


SkipList

public SkipList(int size)
Creates an empty skip list using the default comparator and the provided size for the height of the head and tail.

Parameters:
size - the initial size for head and tail,

SkipList

public SkipList(Comparator<? super E> comp)
Creates an empty skip list that uses the given comparator and the default height for head and tail.

Parameters:
comp - the comparator that defines an ordering among the elements
Method Detail

viewStructure

public void viewStructure()

contains

public boolean contains(E target)
Description copied from class: AbstractCollection
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>
Overrides:
contains in class AbstractCollection<E>
Parameters:
target - the element being tested for membership in the collection
Returns:
true if and only if an equivalent value exists in the collection

get

public E get(int r)
Description copied from interface: OrderedCollection
Returns the rth element in the sorted order, where r=0 is the minimum element. It throws an IllegalArgumentException when r < 0 or r ≥ n.

Specified by:
get in interface OrderedCollection<E>
Parameters:
r - the desired rank
Returns:
the rth element in the sorted order, where r = 0 is the minimum.
Throws:
IllegalArgumentException - r < 0 or r ≥ n

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>
Specified by:
getEquivalentElement in interface OrderedCollection<E>
Overrides:
getEquivalentElement in class AbstractCollection<E>
Parameters:
target - the element for which an equivalent element is sought
Returns:
an equivalent element in the collection
Throws:
NoSuchElementException - there is no equivalent element in the collection.

min

public E min()
Description copied from interface: OrderedCollection
Returns a least element in the collection (according to the comparator). More specifically, the first element in the iteration order is returned. This method throws a NoSuchElementException when the collection is empty.

Specified by:
min in interface OrderedCollection<E>
Returns:
a least element in the collection.
Throws:
NoSuchElementException - the collection is empty.

max

public E max()
Description copied from interface: OrderedCollection
Returns a greatest element in the collection (according to the comparator). More specifically, the last element in the iteration order is returned. This method throws a NoSuchElementException when the collection is empty.

Specified by:
max in interface OrderedCollection<E>
Returns:
a greatest element in the collection.
Throws:
NoSuchElementException - the collection is empty.

predecessor

public E predecessor(E target)
This method does not require that target be in the collection.

Specified by:
predecessor in interface OrderedCollection<E>
Parameters:
target - the element for which to find the predecessor
Returns:
the largest element in the ordered collection that is less than target.
Throws:
NoSuchElementException - no element in the collection is smaller than target

successor

public E successor(E target)
This method does not require that target be in the collection.

Specified by:
successor in interface OrderedCollection<E>
Parameters:
target - the element for which to find the successor
Returns:
the smallest element in the ordered collection that is greater than target
Throws:
NoSuchElementException - no element in the collection is greater than target

insert

protected goldman.collection.ordered.SkipList.Tower<E> insert(E element)
Inserts element into the collection

Parameters:
element - the new element
Returns:
a reference to the newly created tower that holds the given element

add

public void add(E element)
Inserts element into the collection.

Specified by:
add in interface Collection<E>
Parameters:
element - the new element

addTracked

public Locator<E> addTracked(E element)
Inserts element into the collection.

Specified by:
addTracked in interface Tracked<E>
Parameters:
element - the new element
Returns:
a tracker that tracks the new element

addAll

public void addAll(Collection<? extends E> c)
Iterates through c and adds each element in c to the collection

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

remove

public boolean remove(E element)
Removes the first occurrence of the target from the collection, if an equivalent element exists in the collection.

Specified by:
remove in interface Collection<E>
Parameters:
element - the element to remove
Returns:
true if an element was removed, and false otherwise.

retainAll

public void retainAll(Collection<E> c)
Updates the current collection to contain only elements that are also in c. When c is an ordered collection with the same comparator, this method takes advantage of that fact for improved efficiency.

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

iterator

public SkipList.Tracker iterator()
Creates a new tracker at FORE.

Specified by:
iterator in interface Collection<E>
Specified by:
iterator in interface Iterable<E>

iteratorAtEnd

public SkipList.Tracker iteratorAtEnd()
Creates a new tracker at AFT.

Specified by:
iteratorAtEnd in interface OrderedCollection<E>

getLocator

public SkipList.Tracker getLocator(E element)
Description copied from interface: Collection
Returns a locator that has been initialized to an element equivalent to target. Like the iterator method, this method enables navigation, but from a specified starting point. This method throws a NoSuchElementException if there is no equivalent element in the collection.

Specified by:
getLocator in interface Collection<E>
Parameters:
element - an element to locate
Returns:
a tracker to the specified element
Throws:
NoSuchElementException - there is no equivalent element in the ordered collection.