jdsl.core.ref
Class ArraySkipList

java.lang.Object
  |
  +--jdsl.core.ref.ArraySkipList

All Implemented Interfaces:

Container, Dictionary, InspectableContainer, InspectableDictionary, InspectableKeyBasedContainer, InspectableOrderedDictionary, KeyBasedContainer, OrderedDictionary

public class ArraySkipList

extends Object

implements OrderedDictionary

Implementation of a skip list
• The ordered dictionary is a multi-map which means that it is possible for two elements to have the same key.
• Utilizes a head locator which comes before all locators and is the starting point for all traversals
• End of the list is denoted by the null pointer
• Duplicate keys are inserted in reverse order (the mostly recently inserted node is inserted closest to the head node
• When deletion is performed on nodes with identical keys, the most recently inserted node (closest to the head node) is removed
• Based on William Pugh's article in Communications of the ACM June 1990 Volume 33 Number 6

Version:

$Id: ArraySkipList.html,v 1.2 2000/12/30 06:03:52 lv Exp $

Author:

Benety Goh

Inner classes inherited from class jdsl.core.api.InspectableDictionary

InspectableDictionary.InvalidLocator

Field Summary

static int

DEFAULT_MAX_LEVEL Default maximum level of node.

Fields inherited from interface jdsl.core.api.InspectableOrderedDictionary

BOUNDARY_VIOLATION

Fields inherited from interface jdsl.core.api.InspectableDictionary

NO_SUCH_KEY

Constructor Summary

ArraySkipList(Comparator comparator)
Runs in O(1 + t) time where t is the time it takes to create the head node with (DEFAULT_MAX_LEVEL+1) forward links.

ArraySkipList(Comparator comparator, int maxLevel)
Runs in O(1 + t) time where t is the time it takes to create the head node with (DEFAULT_MAX_LEVEL+1) forward links.

ArraySkipList(Comparator comparator, int maxLevel, long seed)
Runs in O(1 + t) time where t is the time it takes to create the head node with (maxLevel+1) forward links.

Method Summary

Locator	after(Locator locator) Runs in O(1) time.
Locator	before(Locator locator) Runs in O(1) time.
Locator	closestAfter(Object key) Runs in expected O(log n) time, where n is the number of elements.
Locator	closestBefore(Object key) Runs in expected O(log n) time, where n is the number of elements.
boolean	contains(Accessor a) Runs in O(1) time.
ObjectIterator	elements() Runs in O(n) time, where n is the number of elements.
Locator	find(Object key) Runs in expected O(log n) time, where n is the number of elements finds first node within skip list with key.
LocatorIterator	findAll(Object key) Runs in expected O(log n + m) time where n is the total number of elements and m is the number of elements with key value equal to key.
Locator	first() Runs in O(1) time.
Locator	insert(Object key, Object element) Runs in expected O(log n) time, where n is the number of elements in the skip list.
boolean	isEmpty() Runs in O(1) time.
ObjectIterator	keys() Runs in O(n) time, where n is the number of elements.
Locator	last() Runs in O(1) time.
LocatorIterator	locators() Runs in O(n) time, where n is the number of elements.
Container	newContainer() Runs in O(1 + t) time where t is the time it takes to create the head node.
void	remove(Locator locator) Runs in expected O(log n) time, where n is the number of elements.
LocatorIterator	removeAll(Object searchKey) Runs in expected O(log n + k) where k is the number of duplicate keys and n is the number of elements.
Locator	removeKey(Object key) Runs in expected O(log n) time, where n is the number of elements.
Object	replaceElement(Accessor a, Object newElement) Runs in O(1) time.
Object	replaceKey(Locator locator, Object key) Runs in expected O(log n) time, where n is the number of elements.
int	size() Runs in O(1) time.
String	toString() Runs in O(n) time, where n is the number of elements.

Methods inherited from class java.lang.Object

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

Field Detail

DEFAULT_MAX_LEVEL

public static final int DEFAULT_MAX_LEVEL

Default maximum level of node. Highest level any node in the skip list may grow to. Set to 20 to accommodate 1 million elements by default.

Constructor Detail

ArraySkipList

public ArraySkipList(Comparator comparator,
                     int maxLevel,
                     long seed)

Runs in O(1 + t) time where t is the time it takes to create the head node with (maxLevel+1) forward links. An ideal value for maxLevel would be. log(N) where N is the total number of elements expected. Initializes head node. Sets current level to 0, which is the minimum.

Parameters:

comparator - comparator to use.

maxLevel - highest level for any node.

seed - seed for random number generator.

ArraySkipList

public ArraySkipList(Comparator comparator,
                     int maxLevel)

Runs in O(1 + t) time where t is the time it takes to create the head node with (DEFAULT_MAX_LEVEL+1) forward links.

Parameters:

comparator - comparator to use.

maxLevel - highest level for any node.

ArraySkipList

public ArraySkipList(Comparator comparator)

Runs in O(1 + t) time where t is the time it takes to create the head node with (DEFAULT_MAX_LEVEL+1) forward links.

Parameters:

comparator - comparator to use.

Method Detail

newContainer

public Container newContainer()

Runs in O(1 + t) time where t is the time it takes to create the head node. Creates a new skip list with the same maximum level and comparator. Random number generator will be initialized with default seed value (system time).

Specified by:

newContainer in interface Container

Following copied from interface: jdsl.core.api.Container

Returns:

A new, empty Container of the same class as this one.

replaceElement

public Object replaceElement(Accessor a,
                             Object newElement)
                      throws InvalidAccessorException

Runs in O(1) time.

Specified by:

replaceElement in interface Container

Following copied from interface: jdsl.core.api.Container

Parameters:

a - Accessor in this container

newElement - to be stored at a

Returns:

old element, previously stored at a

Throws:

InvalidAccessorException - if a is null or does not belong to this container

contains

public boolean contains(Accessor a)
                 throws InvalidAccessorException

Runs in O(1) time.

Specified by:

contains in interface InspectableContainer

Following copied from interface: jdsl.core.api.InspectableContainer

Throws:

InvalidAccessorException - if a is null

size

public int size()

Runs in O(1) time. This is due to the fact that we cache the value of the size of the container instead of traversing the list each time there is a query for the size.

Specified by:

size in interface InspectableContainer

Following copied from interface: jdsl.core.api.InspectableContainer

Returns:

Number of elements stored by the container.

isEmpty

public boolean isEmpty()

Runs in O(1) time.

Specified by:

isEmpty in interface InspectableContainer

Following copied from interface: jdsl.core.api.InspectableContainer

Returns:

true if and only if the container is empty (holds no elements)

See Also:

InspectableBinaryTree

elements

public ObjectIterator elements()

Runs in O(n) time, where n is the number of elements.

Specified by:

elements in interface InspectableContainer

Following copied from interface: jdsl.core.api.InspectableContainer

Returns:

an iterator over all the elements stored in this container

locators

public LocatorIterator locators()

Runs in O(n) time, where n is the number of elements.

Specified by:

locators in interface InspectableKeyBasedContainer

Following copied from interface: jdsl.core.api.InspectableKeyBasedContainer

Returns:

a LocatorIterator over all of the locators in the container

keys

public ObjectIterator keys()

Runs in O(n) time, where n is the number of elements.

Specified by:

keys in interface InspectableKeyBasedContainer

Following copied from interface: jdsl.core.api.InspectableKeyBasedContainer

Returns:

an iterator over all the keys stored in this container

replaceKey

public Object replaceKey(Locator locator,
                         Object key)
                  throws InvalidAccessorException,
                         InvalidKeyException

Runs in expected O(log n) time, where n is the number of elements.

Specified by:

replaceKey in interface KeyBasedContainer

Following copied from interface: jdsl.core.api.KeyBasedContainer

Parameters:

loc - the locator in the container whose key should be replaced

key - the new key to associate with loc.

Returns:

The old key

Throws:

InvalidAccessorException - If the locator is not valid or is not contained by this container

InvalidKeyException - If key cannot be used by this container

find

public Locator find(Object key)
             throws InvalidKeyException

Runs in expected O(log n) time, where n is the number of elements finds first node within skip list with key. All nodes before this node must have key value less than the node. In order to find duplicate keys, we can take this node and traverse forward in the list using after().

Specified by:

find in interface InspectableDictionary

Following copied from interface: jdsl.core.api.InspectableDictionary

Parameters:

key - The key mapped to search for.

Returns:

The Locator referring to the key-element pair that was found, or NO_SUCH_KEY if it could not be found.

Throws:

InvalidKeyException - if the specified key is not a valid key in this container.

See Also:

InspectableDictionary.NO_SUCH_KEY

findAll

public LocatorIterator findAll(Object key)
                        throws InvalidKeyException

Runs in expected O(log n + m) time where n is the total number of elements and m is the number of elements with key value equal to key. relies on find() returning first node in skip list containing key.

Specified by:

findAll in interface InspectableDictionary

Following copied from interface: jdsl.core.api.InspectableDictionary

Parameters:

key - The key to search for.

Returns:

A LocatorIterator over the set of (key, element) pairs whose keys match the parameter key

Throws:

InvalidKeyException - if the specified key is not valid in this container

closestBefore

public Locator closestBefore(Object key)
                      throws InvalidKeyException

Runs in expected O(log n) time, where n is the number of elements.

Specified by:

closestBefore in interface InspectableOrderedDictionary

Following copied from interface: jdsl.core.api.InspectableOrderedDictionary

Parameters:

key - A valid key.

Returns:

The locator with largest key less than or equal to key. Note: If no such locator exists, the returned locator will be BOUNDARY_VIOLATION.

Throws:

InvalidKeyException - If key is not of a type accepted by this Container (For example: the key is not comparable).

closestAfter

public Locator closestAfter(Object key)
                     throws InvalidKeyException

Runs in expected O(log n) time, where n is the number of elements.

Specified by:

closestAfter in interface InspectableOrderedDictionary

Following copied from interface: jdsl.core.api.InspectableOrderedDictionary

Parameters:

key - A valid key.

Returns:

The locator with smallest key greater than or equal to key. Note: If no such Locator exists, the returned locator will be BOUNDARY_VIOLATION.

Throws:

InvalidKeyException - If key is not of a type accepted by this Container (For example: the key is not comparable).

after

public Locator after(Locator locator)
              throws InvalidAccessorException

Runs in O(1) time.

Specified by:

after in interface InspectableOrderedDictionary

Following copied from interface: jdsl.core.api.InspectableOrderedDictionary

Parameters:

locator - An abstract position in this Container.

Returns:

A Locator which is sequentially after locator. Note: Will return the invalid BOUNDARY_VIOLATION Locator if no such locator exists.

Throws:

InvalidAccessorException - If locator is invalid (For example: It does not actually reference an element within this Container).

before

public Locator before(Locator locator)
               throws InvalidAccessorException

Runs in O(1) time.

Specified by:

before in interface InspectableOrderedDictionary

Following copied from interface: jdsl.core.api.InspectableOrderedDictionary

Parameters:

locator - An abstract position in this Container.

Returns:

A Locator which is sequentially before locator. Note: Will return the invalid BOUNDARY_VIOLATION Locator if no such locator exists.

Throws:

InvalidAccessorException - If locator is invalid (For example: It does not actually reference an element within this Container).

insert

public Locator insert(Object key,
                      Object element)
               throws InvalidKeyException

Runs in expected O(log n) time, where n is the number of elements in the skip list.

Specified by:

insert in interface KeyBasedContainer

Following copied from interface: jdsl.core.api.KeyBasedContainer

Parameters:

key - the key associated with the specified element.

element - the element to insert into the container.

Returns:

a locator associated with the inserted pair.

Throws:

InvalidKeyException - if key cannot be used by this container

removeAll

public LocatorIterator removeAll(Object searchKey)
                          throws InvalidKeyException

Runs in expected O(log n + k) where k is the number of duplicate keys and n is the number of elements. "carves" out region of nodes with key value equal to key.

Specified by:

removeAll in interface Dictionary

Following copied from interface: jdsl.core.api.Dictionary

Parameters:

key - the key to search for

Returns:

a LocatorIterator over the (key, element) pairs whose keys match the parameter key

Throws:

InvalidKeyException - if the specified key is not a valid key in this container

removeKey

public Locator removeKey(Object key)
                  throws InvalidKeyException

Runs in expected O(log n) time, where n is the number of elements. When there is more than a single node with the same key, the most recently inserted node (closest to the head node) is removed.

Parameters:

key - key to remove from container.

Throws:

InvalidKeyException - If the key is null or not compatible with container.

remove

public void remove(Locator locator)
            throws InvalidAccessorException

Runs in expected O(log n) time, where n is the number of elements.

Specified by:

remove in interface KeyBasedContainer

Following copied from interface: jdsl.core.api.KeyBasedContainer

Parameters:

loc - a locator in the container to remove

Throws:

InvalidAccessorException - if the locator is not valid or is not contained by this container

first

public Locator first()

Runs in O(1) time.

Specified by:

first in interface InspectableOrderedDictionary

Returns:

first non-head, non-null locator if non-empty list, or BOUNDARY_VIOLATION if list is empty.

last

public Locator last()

Runs in O(1) time. Backward pointer in head node is used to cache the reference to the last node.

Specified by:

last in interface InspectableOrderedDictionary

Following copied from interface: jdsl.core.api.InspectableOrderedDictionary

Returns:

A Locator which is sequentially after any other locator. Note: Will return the invalid BOUNDARY_VIOLATION Locator if no such locator exists.

toString

public String toString()

Runs in O(n) time, where n is the number of elements.

Overrides:

toString in class Object