Search this API

y.util
Class SkipList

java.lang.Object
  extended by 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
 
Your browser does not support SVG content.

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

© Copyright 2000-2022,
yWorks GmbH.
All rights reserved.