net.metanotion.util.skiplist

Class SkipLevels<K extends Comparable<? super K>,V>

java.lang.Object

net.metanotion.util.skiplist.SkipLevels<K,V>

Type Parameters:

K - type of keys, must be comparable

V - type of values

All Implemented Interfaces:

Flushable

Direct Known Subclasses:

BSkipLevels

public class SkipLevels<K extends Comparable<? super K>,V>
extends Object
implements Flushable

Manages the level structure for a skip list data structure. Maintains pointers to different levels in the skip list hierarchy.

Field Summary

Fields

Modifier and Type	Field and Description
SkipSpan<K,V>	bottom Bottom level pointer to the actual SkipSpan
SkipLevels<K,V>[]	levels Array of level pointers at each height
static int	MAX_SIZE Maximum number of levels in a skip list

Constructor Summary

Constructors

Modifier	Constructor and Description
protected	SkipLevels() Protected constructor for subclasses.
	SkipLevels(int size, SkipSpan<K,V> span) Create a new SkipLevels with the specified size.

Method Summary

Modifier and Type	Method and Description
boolean	blvlck(boolean fix) Run an integrity check on this level.
boolean	blvlck(boolean fix, int width, SkipLevels<K,V>[] prevLevels) Run an integrity check on this level with additional parameters.
void	flush() Flush this level to disk.
V	get(int start, K key) Get the value associated with the given key.
SkipSpan<K,V>	getEnd() Get the end span of this level.
SkipSpan<K,V>	getSpan(int start, K key, int[] search) Get the span containing or following the given key.
K	key() Get the key at the bottom of this level.
void	killInstance() Mark this instance as killed.
SkipLevels<K,V>	newInstance(int levels, SkipSpan<K,V> ss, SkipList<K,V> sl) Create a new instance of this SkipLevels.
String	print() Print this level and all levels below it.
String	printAll() Print this level and all levels below it, recursively.
SkipLevels<K,V>	put(int start, K key, V val, SkipList<K,V> sl) Put a key-value pair into the skip list.
Object[]	remove(int start, K key, SkipList<K,V> sl) Remove a key-value pair from the skip list.

Methods inherited from class java.lang.Object

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

Field Detail

bottom

public SkipSpan<K extends Comparable<? super K>,V> bottom

Bottom level pointer to the actual SkipSpan

levels

public SkipLevels<K extends Comparable<? super K>,V>[] levels

Array of level pointers at each height

MAX_SIZE

public static final int MAX_SIZE

Maximum number of levels in a skip list

See Also:

Constant Field Values

Constructor Detail

SkipLevels

protected SkipLevels()

Protected constructor for subclasses.

SkipLevels

public SkipLevels(int size,
                  SkipSpan<K,V> span)

Create a new SkipLevels with the specified size.

Parameters:

size - the number of levels

span - the bottom SkipSpan

Throws:

IllegalArgumentException - if size too big or too small

Method Detail

blvlck

public boolean blvlck(boolean fix)

Run an integrity check on this level.

Parameters:

fix - if true, attempt to fix corruption

Returns:

true if corruption was found

blvlck

public boolean blvlck(boolean fix,
                      int width,
                      SkipLevels<K,V>[] prevLevels)

Run an integrity check on this level with additional parameters.

Parameters:

fix - if true, attempt to fix corruption

width - the current width

prevLevels - previous levels to check

Returns:

true if corruption was found

flush

public void flush()

Flush this level to disk.

Specified by:

flush in interface Flushable

get

public V get(int start,
             K key)

Get the value associated with the given key.

Parameters:

start - the starting level

key - the key to search for

Returns:

the value, or null if not found

getEnd

public SkipSpan<K,V> getEnd()

Get the end span of this level.

Returns:

the last SkipSpan in this chain

getSpan

public SkipSpan<K,V> getSpan(int start,
                             K key,
                             int[] search)

Get the span containing or following the given key.

Parameters:

start - the starting level

key - the key to search for

search - search parameters and results

Returns:

the SkipSpan containing the key

key

public K key()

Get the key at the bottom of this level.

Returns:

the first key

killInstance

public void killInstance()

Mark this instance as killed.

newInstance

public SkipLevels<K,V> newInstance(int levels,
                                   SkipSpan<K,V> ss,
                                   SkipList<K,V> sl)

Create a new instance of this SkipLevels.

Parameters:

levels - the number of levels to create

ss - the SkipSpan to use

sl - the SkipList

Returns:

a new SkipLevels instance

print

public String print()

Print this level and all levels below it.

Returns:

a string representation of this level

printAll

public String printAll()

Print this level and all levels below it, recursively.

Returns:

a string representation of all levels

put

public SkipLevels<K,V> put(int start,
                           K key,
                           V val,
                           SkipList<K,V> sl)

Put a key-value pair into the skip list.

Parameters:

start - the starting level

key - the key

val - the value

sl - the SkipList

Returns:

the new level if it caused a split and we made a new level, and the new level is taller than our level; else null if it went in an existing level or the new level is our height or less.

remove

public Object[] remove(int start,
                       K key,
                       SkipList<K,V> sl)

Remove a key-value pair from the skip list.

Parameters:

start - the starting level

key - the key to remove

sl - the SkipList

Returns:

An array of two objects or null. rv[0] is the removed object. rv[1] is the deleted SkipLevels if the removed object was the last in the SkipLevels, and the deleted SkipLevels is taller than this SkipLevels. rv is null if no object was removed.