org.jutil.java.collections
Class SkipList

java.lang.Object
  |
  +--java.util.AbstractCollection
        |
        +--org.jutil.java.collections.SkipList

All Implemented Interfaces:

java.util.Collection

public class SkipList

extends java.util.AbstractCollection

A collections which is actually a sorted list.

A skiplist is a sorted list with an average O(log(n)) behavior for add() and remove(). The worst case time complexity is O(n).

A skiplist looks like a linked list, but the difference is that the cells of a skiplist have a number of forward pointers. The number of forward pointers of a cell is called the level of that cell. The level of a SkipList is the maximum of the levels of its cells. The level of a SkipList can not exceed its maximum level.

The i'th forward pointer of a cell points to the next cell of level >= i, thus skipping a number of elements with level <i. An example a skiplist is shown in the figure below. The left cell is the header of the skiplist which contains getMaxLevel() forward pointers (but is not included in the level count for the list). The crossed arrows point to the end of the list, indicating there is no next cell of level i. The light grey field at the bottom of each cell is a reference to the element that is represented by that cell. As you can see, multiple cells can reference the same object because we are dealing with a list.

The elements of a SkipList are sorted using a Comparator, which is given to the list at the time of construction.

The level of a cell is a random number between 1 and getMaxLevel(). There is a fixed probability that a cell with a level >=i has a level >=i+1 (unless of course i==getMaxLevel()). It is the randomness that makes that a skiplist has an average O(log(n)) add() and remove() because only a fixed number of cells must be changed to insert of remove a cell (no structure has to be maintained).

With probability 0.25 the average number of forward pointers per element is 1.333. A maximum level L will be efficient for a SkipList containing about 4^L elements. If you add much more elements than that, the number of cell with the maximum level will increase, so searching an element will take longer. The default level is 8.

For more information, go to ftp://ftp.cs.umd.edu/pub/skipLists.

Version:

$Revision: 1.4 $

Author:

Marko van Dooren, Tom Schrijvers

Field Summary

static java.lang.String

CVS_REVISION

Constructor Summary

SkipList(java.util.Comparator comparator)
public behavior

pre comparator != null;

post getMaxLevel() == 8;
post size() == 0;
post getProbability() == 0.25;


private behavior

post level() == 1;
Initialize a new SkipList with the given comparator.

SkipList(int maxLevel, java.util.Comparator comparator, float probability)
public behavior

pre maxLevel >= 1;
pre comparator != null;
pre probability >= 0;
pre probability <= 1;

post getMaxLevel() == maxLevel;
post size() == 0;
post getProbability() == probability;


private behavior

post level() == 1;
Initialize a new SkipList with the given maximum level, comparator and probability.

Method Summary

boolean	add(java.lang.Object object) See superclass
void	clear() See superclass
boolean	contains(java.lang.Object o) See superclass
java.util.Comparator	getComparator() public behavior post \result != null; Return the Comparator used to determine the order in which the elements are added to this SkipList.
java.lang.Object	getFirst() public behavior pre ! isEmpty(); post contains(\result); post (\forall Object o; contains(o); getComparator().compare(\result,o)<=0); Return the first object of this SkipList.
int	getMaxLevel() public behavior post \result >= 1; Return the maximum level of this SkipList
float	getProbability() public behavior post \result >= 0; post \result <= 1; Return the probability that a node of level >= i is a node of level >= i + 1
java.util.Iterator	iterator() See superclass
boolean	remove(java.lang.Object object) See superclass
boolean	removeAll(java.lang.Object object) See superclass
void	removeFirst() public behavior pre ! isEmpty(); post (! \old(isEmpty())) ==> (size() == \old(size()) - 1); post (! \old(isEmpty())) ==> (Collections.nbExplicitOccurrences(\old(getFirst()),this) == \old(Collections.nbExplicitOccurrences(\old(getFirst()),this)) - 1); Remove the first element of this SkipList.
int	size() See superclass
java.lang.String	toString() See superclass

Methods inherited from class java.util.AbstractCollection

addAll, containsAll, isEmpty, removeAll, retainAll, toArray, toArray

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Methods inherited from interface java.util.Collection

equals, hashCode

Field Detail

CVS_REVISION

public static final java.lang.String CVS_REVISION

Constructor Detail

SkipList

public SkipList(java.util.Comparator comparator)

public behavior

pre comparator != null;

post getMaxLevel() == 8;
post size() == 0;
post getProbability() == 0.25;


private behavior

post level() == 1;
Initialize a new SkipList with the given comparator.

Parameters:

comparator - The Comparator used to determine the order of the elements in this SkipList.

SkipList

public SkipList(int maxLevel,
                java.util.Comparator comparator,
                float probability)

public behavior

pre maxLevel >= 1;
pre comparator != null;
pre probability >= 0;
pre probability <= 1;

post getMaxLevel() == maxLevel;
post size() == 0;
post getProbability() == probability;


private behavior

post level() == 1;
Initialize a new SkipList with the given maximum level, comparator and probability.

Parameters:

maxLevel - The maximum level of the nodes used internally by this SkipList.

comparator - The Comparator used to determine the order of the elements in this SkipList.

probability - The fraction of nodes of level >= i that has level >= i + 1

Method Detail

toString

public java.lang.String toString()

See superclass

Overrides:

toString in class java.util.AbstractCollection

size

public int size()

See superclass

Overrides:

size in class java.util.AbstractCollection

clear

public void clear()

See superclass

Overrides:

clear in class java.util.AbstractCollection

contains

public boolean contains(java.lang.Object o)

See superclass

Overrides:

contains in class java.util.AbstractCollection

getFirst

public java.lang.Object getFirst()

public behavior

pre ! isEmpty();

post contains(\result);
post (\forall Object o; contains(o);
getComparator().compare(\result,o)<=0);
Return the first object of this SkipList.

getMaxLevel

public int getMaxLevel()

public behavior

post \result >= 1;
Return the maximum level of this SkipList

getComparator

public java.util.Comparator getComparator()

public behavior

post \result != null;
Return the Comparator used to determine the order in which the elements are added to this SkipList.

getProbability

public float getProbability()

public behavior

post \result >= 0;
post \result <= 1;
Return the probability that a node of level >= i is a node of level >= i + 1

iterator

public java.util.Iterator iterator()

See superclass

Overrides:

iterator in class java.util.AbstractCollection

add

public boolean add(java.lang.Object object)

See superclass

Overrides:

add in class java.util.AbstractCollection

removeFirst

public void removeFirst()

public behavior

pre ! isEmpty();

post (! \old(isEmpty())) ==> (size() == \old(size()) - 1);
post (! \old(isEmpty())) ==> (Collections.nbExplicitOccurrences(\old(getFirst()),this) ==
\old(Collections.nbExplicitOccurrences(\old(getFirst()),this)) - 1);
Remove the first element of this SkipList.

remove

public boolean remove(java.lang.Object object)

See superclass

Overrides:

remove in class java.util.AbstractCollection

removeAll

public boolean removeAll(java.lang.Object object)

See superclass