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 java.lang.Object
implements OrderedDictionary

Version:
$Id: ArraySkipList.java,v 1.12 2001/02/21 13:34:24 bg 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(java.lang.Object key)
          Runs in expected O(log n) time, where n is the number of elements.
 Locator closestBefore(java.lang.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(java.lang.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(java.lang.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(java.lang.Object key, java.lang.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(java.lang.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(java.lang.Object key)
          Runs in expected O(log n) time, where n is the number of elements.
 java.lang.Object replaceElement(Accessor a, java.lang.Object newElement)
          Runs in O(1) time.
 java.lang.Object replaceKey(Locator locator, java.lang.Object key)
          Runs in expected O(log n) time, where n is the number of elements.
 int size()
          Runs in O(1) time.
 java.lang.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 java.lang.Object replaceElement(Accessor a,
                                       java.lang.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 java.lang.Object replaceKey(Locator locator,
                                   java.lang.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(java.lang.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(java.lang.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(java.lang.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(java.lang.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(java.lang.Object key,
                      java.lang.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(java.lang.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(java.lang.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 java.lang.String toString()
Runs in O(n) time, where n is the number of elements.
Overrides:
toString in class java.lang.Object