SkipList (Javadocs [I2P+ 2.13.0+] - API Version 0.9.70+)

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` First span in the list.
`protected static int`	`P` The probability of each next higher level.
`static Random`	`rng` Random number generator.
`protected int`	`size` Number of items in the list.
`protected SkipLevels<K,V>`	`stack` Level stack above the first span.

Constructor Summary
Constructors
Modifier Constructor and Description
protected SkipList()
Constructor for subclass use.
SkipList(int span)
Create a new skip list.

Constructors
Modifier	Constructor and Description
`protected`	`SkipList()` Constructor for subclass use.
	`SkipList(int span)` Create a new skip list.

Method Summary

All Methods Instance Methods Concrete Methods
Modifier and Type	Method and Description
`void`	`addItem()` Increment item count.
`void`	`balance()` Rebalance the skip list levels.
`void`	`delItem()` Decrement item count, minimum zero.
`SkipIterator<K,V>`	`find(K key)`
`void`	`flush()` Flush any pending writes.
`int`	`generateColHeight()`
`V`	`get(K key)` Get the value for a key.
`SkipIterator<K,V>`	`iterator()` Return an iterator over all entries.
`int`	`maxLevels()`
`void`	`put(K key, V val)` Insert or update a key-value pair in the skip list.
`V`	`remove(K key)` Remove a key-value pair from the skip list.
`int`	`size()` Return the number of items.

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
```
    First span in the list.
  - P
```
protected static final int P
```
    The probability of each next higher level.
    See Also:
    Constant Field Values
  - rng
```
public static final Random rng
```
    Random number generator.
  - size
```
protected int size
```
    Number of items in the list.
  - stack
```
protected SkipLevels<K extends Comparable<? super K>,V> stack
```
    Level stack above the first span.
- Constructor Detail
  - SkipList
```
protected SkipList()
```
    Constructor for subclass use.
  - SkipList
```
public SkipList(int span)
```
    Create a new skip list.
    Parameters:
    span - span size
    Throws:
    IllegalArgumentException - if size too big or too small
- Method Detail
  - addItem
```
public void addItem()
```
    Increment item count.
  - balance
```
public void balance()
```
    Rebalance the skip list levels.
  - delItem
```
public void delItem()
```
    Decrement item count, minimum zero.
  - 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()
```
    Flush any pending writes.
    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)
```
    Get the value for a key.
    Parameters:
    key - the key
    Returns:
    the value, or null if not found
  - iterator
```
public SkipIterator<K,V> iterator()
```
    Return an iterator over all entries.
    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)
```
    Insert or update a key-value pair in the skip list.
    Parameters:
    key - the key
    val - the value
  - remove
```
public V remove(K key)
```
    Remove a key-value pair from the skip list.
    Parameters:
    key - the key
    Returns:
    the previous value, or null if not found
  - size
```
public int size()
```
    Return the number of items.

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

Field Summary

Constructor Summary

Method Summary

Methods inherited from class java.lang.Object

Methods inherited from interface java.lang.Iterable

Field Detail

first

P

rng

size

stack

Constructor Detail

SkipList

SkipList

Method Detail

addItem

balance

delItem

find

flush

generateColHeight

get

iterator

maxLevels

put

remove

size