net.metanotion.util.skiplist
Class SkipList

java.lang.Object
  extended by net.metanotion.util.skiplist.SkipList
Direct Known Subclasses:
BSkipList

public class SkipList
extends Object


Field Summary
protected  SkipSpan first
           
protected static int P
          the probability of each next higher level
static Random rng
           
protected  int size
           
protected  SkipLevels stack
           
 
Constructor Summary
protected SkipList()
           
  SkipList(int span)
           
 
Method Summary
 void addItem()
           
 void balance()
           
 void delItem()
           
 SkipIterator find(Comparable key)
           
 void flush()
           
 int generateColHeight()
           
 Object get(Comparable key)
           
 SkipIterator iterator()
           
 SkipIterator max()
           
 int maxLevels()
           
 SkipIterator min()
           
 void print()
          Deprecated. goes to System.out
 void printSL()
          Deprecated. goes to System.out
 void put(Comparable key, Object val)
           
 Object remove(Comparable key)
           
 int size()
           
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Field Detail

P

protected static final int P
the probability of each next higher level

See Also:
Constant Field Values

first

protected SkipSpan first

stack

protected SkipLevels stack

rng

public static final Random rng

size

protected int size
Constructor Detail

SkipList

protected SkipList()

SkipList

public SkipList(int span)
Method Detail

flush

public void flush()

size

public int size()

addItem

public void addItem()

delItem

public void delItem()

maxLevels

public int maxLevels()
Returns:
4 since we don't track span count here any more - see override Fix if for some reason you want a huge in-memory skiplist.

generateColHeight

public int generateColHeight()
Returns:
0..maxLevels(), each successive one with probability 1 / P

put

public void put(Comparable key,
                Object val)

remove

public Object remove(Comparable key)

printSL

public void printSL()
Deprecated. goes to System.out

dumps all the skip levels


print

public void print()
Deprecated. goes to System.out

dumps all the data


get

public Object get(Comparable key)

iterator

public SkipIterator iterator()

min

public SkipIterator min()

max

public SkipIterator max()

find

public SkipIterator find(Comparable key)
Returns:
an iterator where nextKey() is the first one greater than or equal to 'key'

balance

public void balance()