y.util
Class SkipList

java.lang.Object
  y.util.SkipList

public class SkipList
extends java.lang.Object

A simple implementation of a randomized sorted skip list that uses SkipList.Cells to carry the values.

See Also:

YList

Nested Class Summary

static class

SkipList.Cell The cells that are used by SkipList.

Constructor Summary

SkipList()
Creates a skip list that uses a comparator that uses the Comparable of the instances in the cells.

SkipList(java.util.Comparator comparator)
Creates a skip list that uses the given comparator to sort the list.

Method Summary

void	clear() Clears this list.
void	clear(SkipList.Cell from, SkipList.Cell to) Removes all cells from from to to inclusive from this list.
SkipList.Cell	findCell(java.lang.Object o) Finds a cell in this list where the comparator yields 0 when it compares o with the cell's contents or null if no such cell could be found.
SkipList.Cell	findPredecessor(java.lang.Object o) Finds the greatest predecessor in this list where the comparator yields positive values when it compares o with the cell's contents or null if no such cell could be found.
SkipList.Cell	findSuccessor(java.lang.Object o) Finds the smallest successor in this list where the comparator yields negative values when it compares o with the cell's contents or null if no such cell could be found.
SkipList.Cell	firstCell() Gets the first cell in this list or null if there are no cells in this list.
SkipList.Cell	insertAfter(SkipList.Cell cell, java.lang.Object o) Inserts a new item after the provided cell.
SkipList.Cell	insertBefore(SkipList.Cell cell, java.lang.Object o) Inserts a new item before the provided cell.
SkipList.Cell	insertCell(java.lang.Object o) Inserts a new item into the list at the correct position.
java.util.Iterator	iterator() Creates a non-fail-save iterator that iterates over the cells in this list and yields their SkipList.Cell.getInfo()
SkipList.Cell	lastCell() Gets the last cell in this list or null if there are no cells in this list.
SkipList.Cell	predCell(SkipList.Cell cell) Returns the predecessor of the given cell or null.
void	removeCell(SkipList.Cell cell) Removes the given cell from this list.
int	size() Yields the number of cells in this list.
SkipList.Cell	succCell(SkipList.Cell cell) Returns the successor of the given cell or null.
java.lang.String	toString() Yields a human readable string version of the list.

Methods inherited from class java.lang.Object

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

Constructor Detail

SkipList

public SkipList(java.util.Comparator comparator)

Creates a skip list that uses the given comparator to sort the list.

Parameters:

comparator - The comparator to use for sorting.

SkipList

public SkipList()

Creates a skip list that uses a comparator that uses the Comparable of the instances in the cells.

Method Detail

insertCell

public SkipList.Cell insertCell(java.lang.Object o)

Inserts a new item into the list at the correct position.

Parameters:

o - The item to insert.

Returns:

The cell that holds the item.

clear

public void clear(SkipList.Cell from,
                  SkipList.Cell to)

Removes all cells from from to to inclusive from this list.

Parameters:

from - The first cell to remove

to - The last cell to remove

insertAfter

public SkipList.Cell insertAfter(SkipList.Cell cell,
                                 java.lang.Object o)

Inserts a new item after the provided cell. It is not checked whether this would violate the Comparator.

Parameters:

cell - The cell to insert the item after.

o - The item to insert.

Returns:

The cell that has just been created.

insertBefore

public SkipList.Cell insertBefore(SkipList.Cell cell,
                                  java.lang.Object o)

Inserts a new item before the provided cell. It is not checked whether this would violate the Comparator.

Parameters:

cell - The cell to insert the item before.

o - The item to insert.

Returns:

The cell that has just been created.

size

public int size()

Yields the number of cells in this list.

Returns:

The number of cells this list contains.

removeCell

public void removeCell(SkipList.Cell cell)

Removes the given cell from this list.

Parameters:

cell - The cell to remove.

clear

public void clear()

Clears this list.

succCell

public SkipList.Cell succCell(SkipList.Cell cell)

Returns the successor of the given cell or null.

Parameters:

cell - The cell to get the successor from.

Returns:

The successor or null if cell is the last cell in the list.

predCell

public SkipList.Cell predCell(SkipList.Cell cell)

Returns the predecessor of the given cell or null.

Parameters:

cell - The cell to get the predecessor from.

Returns:

The predecessor or null if cell is the first cell in the list.

firstCell

public SkipList.Cell firstCell()

Gets the first cell in this list or null if there are no cells in this list.

Returns:

The first cell in the list or null.

lastCell

public SkipList.Cell lastCell()

Gets the last cell in this list or null if there are no cells in this list.

Returns:

The last cell in the list or null.

iterator

public java.util.Iterator iterator()

Creates a non-fail-save iterator that iterates over the cells in this list and yields their SkipList.Cell.getInfo()

Returns:

An iterator over the values in the cells of this list.

findCell

public SkipList.Cell findCell(java.lang.Object o)

Finds a cell in this list where the comparator yields 0 when it compares o with the cell's contents or null if no such cell could be found.

Parameters:

o - the value to search.

Returns:

The cell that contains an equal value or null.

findPredecessor

public SkipList.Cell findPredecessor(java.lang.Object o)

Finds the greatest predecessor in this list where the comparator yields positive values when it compares o with the cell's contents or null if no such cell could be found.

Parameters:

o - the value to search.

Returns:

The greatest cell that contains a smaller value or null.

findSuccessor

public SkipList.Cell findSuccessor(java.lang.Object o)

Finds the smallest successor in this list where the comparator yields negative values when it compares o with the cell's contents or null if no such cell could be found.

Parameters:

o - the value to search.

Returns:

The smallest cell that contains a greater value or null.

toString

public java.lang.String toString()

Yields a human readable string version of the list.

Overrides:

toString in class java.lang.Object