|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Objectgoldman.collection.AbstractCollection<E>
goldman.collection.ordered.SkipList<E>
public class SkipList<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 |
---|
public static final int DEFAULT_HEIGHT
public static final int MAX_HEIGHT
Constructor Detail |
---|
public SkipList(int size, Comparator<? super E> comp)
size
- the initial size for
head and tailcomp
- the comparator that defines an ordering
among the elementspublic SkipList()
public SkipList(int size)
size
- the initial size for
head and tail,public SkipList(Comparator<? super E> comp)
comp
- the comparator that defines an ordering
among the elementsMethod Detail |
---|
public void viewStructure()
public boolean contains(E target)
AbstractCollection
contains
takes linear time, so it
is overridden by a more efficient method in most data structure
implementations.
contains
in interface Collection<E>
contains
in class AbstractCollection<E>
target
- the element being tested for membership in the collection
public E get(int r)
OrderedCollection
IllegalArgumentException
when r < 0 or r ≥ n.
get
in interface OrderedCollection<E>
r
- the desired rank
IllegalArgumentException
- r < 0 or r ≥ npublic E getEquivalentElement(E target)
Collection
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.
getEquivalentElement
in interface Collection<E>
getEquivalentElement
in interface OrderedCollection<E>
getEquivalentElement
in class AbstractCollection<E>
target
- the element for which an equivalent element is sought
NoSuchElementException
- there is no equivalent element in the
collection.public E min()
OrderedCollection
NoSuchElementException
when the collection is empty.
min
in interface OrderedCollection<E>
NoSuchElementException
- the collection is empty.public E max()
OrderedCollection
NoSuchElementException
when the collection is empty.
max
in interface OrderedCollection<E>
NoSuchElementException
- the collection is empty.public E predecessor(E target)
target
be in the collection.
predecessor
in interface OrderedCollection<E>
target
- the element for which to find
the predecessor
target
.
NoSuchElementException
- no element in the collection
is smaller than target
public E successor(E target)
target
be in the collection.
successor
in interface OrderedCollection<E>
target
- the element for which to find
the successor
target
NoSuchElementException
- no element in the collection
is greater than target
protected goldman.collection.ordered.SkipList.Tower<E> insert(E element)
element
into the collection
element
- the
new element
public void add(E element)
element
into the collection.
add
in interface Collection<E>
element
- the new elementpublic Locator<E> addTracked(E element)
element
into the collection.
addTracked
in interface Tracked<E>
element
- the new element
public void addAll(Collection<? extends E> c)
c
and adds each element in
c
to the collection
addAll
in interface Collection<E>
addAll
in class AbstractCollection<E>
c
- the collection to be addedpublic boolean remove(E element)
remove
in interface Collection<E>
element
- the element to remove
true
if an element was removed, and false
otherwise.public void retainAll(Collection<E> c)
c
. When c is an ordered collection with
the same comparator, this method takes advantage of that fact for improved
efficiency.
retainAll
in interface Collection<E>
retainAll
in class AbstractCollection<E>
c
- a collectionpublic SkipList.Tracker iterator()
iterator
in interface Collection<E>
iterator
in interface Iterable<E>
public SkipList.Tracker iteratorAtEnd()
iteratorAtEnd
in interface OrderedCollection<E>
public SkipList.Tracker getLocator(E element)
Collection
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.
getLocator
in interface Collection<E>
element
- an element to locate
NoSuchElementException
- there is no equivalent element
in the ordered collection.
|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |