dataStructures
Class SkipList

java.lang.Object
  |
  +--dataStructures.SkipList

public class SkipList
extends java.lang.Object
implements Dictionary


Inner Class Summary
protected static class SkipList.SkipNode
           
 
Field Summary
protected  SkipList.SkipNode headNode
           
protected  SkipList.SkipNode[] last
           
protected  int levels
           
protected  int maxLevel
           
protected  float prob
           
protected  java.util.Random r
           
protected  int size
           
protected  java.lang.Comparable tailKey
           
protected  SkipList.SkipNode tailNode
           
 
Constructor Summary
SkipList(java.lang.Comparable largeKey, int maxElements, float theProb)
          create an empty skip list
 
Method Summary
 java.lang.Object get(java.lang.Object theKey)
           
 boolean isEmpty()
           
 java.util.Iterator iterator()
          create and return an iterator
static void main(java.lang.String[] args)
          test program
 java.lang.Object put(java.lang.Object theKey, java.lang.Object theElement)
          insert an element with the specified key overwrite old element if there is already an element with the given key
 java.lang.Object remove(java.lang.Object theKey)
           
 int size()
           
 java.lang.String toString()
          convert to a string
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
 

Field Detail

prob

protected float prob

maxLevel

protected int maxLevel

levels

protected int levels

size

protected int size

tailKey

protected java.lang.Comparable tailKey

headNode

protected SkipList.SkipNode headNode

tailNode

protected SkipList.SkipNode tailNode

last

protected SkipList.SkipNode[] last

r

protected java.util.Random r
Constructor Detail

SkipList

public SkipList(java.lang.Comparable largeKey,
                int maxElements,
                float theProb)
create an empty skip list
Parameters:
largekey - used as key in tail node all elements must have a smaller key than this
maxElements - largest number of elements to be stored in the dictionary
theProb - probability that element on one level is also on the next level
Method Detail

isEmpty

public boolean isEmpty()
Returns:
true iff the skip list is empty

size

public int size()
Returns:
current number of elements in the skip list

get

public java.lang.Object get(java.lang.Object theKey)
Specified by:
get in interface Dictionary
Returns:
element with specified key

put

public java.lang.Object put(java.lang.Object theKey,
                            java.lang.Object theElement)
insert an element with the specified key overwrite old element if there is already an element with the given key
Specified by:
put in interface Dictionary
Returns:
old element (if any) with key theKey
Throws:
java.lang.IllegalArgumentException - when theKey >= largeKey = tailKey

remove

public java.lang.Object remove(java.lang.Object theKey)
Specified by:
remove in interface Dictionary
Returns:
matching element and remove it

toString

public java.lang.String toString()
convert to a string
Overrides:
toString in class java.lang.Object

iterator

public java.util.Iterator iterator()
create and return an iterator

main

public static void main(java.lang.String[] args)
test program