net.metanotion.util.skiplist

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

java.lang.Object

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

Type Parameters:

K - type of keys, must be comparable

V - type of values

All Implemented Interfaces:

Flushable, Iterable<V>

Direct Known Subclasses:

BSkipList

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

Skip list data structure implementation for efficient key-value storage and retrieval. Provides O(log n) average time complexity for search, insertion, and deletion operations.

Field Summary

Fields

Modifier and Type	Field and Description
protected SkipSpan<K,V>	first
protected static int	P the probability of each next higher level
static Random	rng
protected int	size
protected SkipLevels<K,V>	stack

Constructor Summary

Constructors

Modifier	Constructor and Description
protected	SkipList()
	SkipList(int span)

Method Summary

Modifier and Type	Method and Description
void	addItem()
void	balance()
void	delItem()
SkipIterator<K,V>	find(K key)
void	flush()
int	generateColHeight()
V	get(K key)
SkipIterator<K,V>	iterator()
int	maxLevels()
void	put(K key, V val)
V	remove(K key)
int	size()

Methods inherited from class java.lang.Object

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

Methods inherited from interface java.lang.Iterable

forEach, spliterator

Field Detail

first

protected SkipSpan<K extends Comparable<? super K>,V> first

P

protected static final int P

the probability of each next higher level

See Also:

Constant Field Values

rng

public static final Random rng

size

protected int size

stack

protected SkipLevels<K extends Comparable<? super K>,V> stack

Constructor Detail

SkipList

protected SkipList()

SkipList

public SkipList(int span)

Method Detail

addItem

public void addItem()

balance

public void balance()

delItem

public void delItem()

find

public SkipIterator<K,V> find(K key)

Returns:

an iterator where nextKey() is the first one greater than or equal to 'key'

flush

public void flush()

Specified by:

flush in interface Flushable

generateColHeight

public int generateColHeight()

Returns:

0..maxLevels(), each successive one with probability 1 / P

get

public V get(K key)

iterator

public SkipIterator<K,V> iterator()

Specified by:

iterator in interface Iterable<V>

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.

put

public void put(K key,
                V val)

remove

public V remove(K key)

size

public int size()