Class Skiplist<K extends java.lang.Comparable<K>,D>

java.lang.Object
  Dictionary<K,D>
      Skiplist<K,D>

Type Parameters:

K - The type of the key. Must be comparable.

D - The type of the data.

All Implemented Interfaces:

Map<K,D>

public class Skiplist<K extends java.lang.Comparable<K>,D>
extends Dictionary<K,D>

This class implements the Map-interface as skiplists. In a skiplist each key-value element is inserted into the n lowest lists. Here, n is determined randomly in a geometric distribution. So, given a propability p with 0 < p < 1 a new key-value element is inserted into n lists with propability p * (1-p)^n-1. All standard operations like insertion, deletion, finding, etc. need O(log n) time in average.

Author:

Rossmanith

See Also:

Comparable

Constructor Summary

Skiplist()
Creates a new empty skiplist with default geometric distribution (where p = 0.5).

Skiplist(int r)
Creates a new skiplist with given random seed.

Skiplist(int r, double p)
Creates a new skiplist with given random seed and given probability p.

Method Summary

void	delete(K k) Deletes the key-data association for the given key in this skiplist in O(log n) in average.
D	find(K k) Looks up the data associated to the key k.
void	insert(K k, D d) Associates the data d to the key k in this skiplist.
boolean	iselement(K k) Checks whether the key is present in this skiplist (in O(log n) time in average).
boolean	isempty() Returns whether this skiplist is empty (in constant time).
Iterator<K,D>	iterator() Creates a new iterator over all associations between keys and data.
void	print() Prints the map to stdout
int	size() Returns the size of this skiplist (in constant time).

Methods inherited from class Dictionary

array, simpleiterator

Methods inherited from class java.lang.Object

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

Constructor Detail

Skiplist

public Skiplist()

Creates a new empty skiplist with default geometric distribution (where p = 0.5).

Skiplist

public Skiplist(int r)

Creates a new skiplist with given random seed.

Parameters:

r - The seed that is used to initialize the random number generator for the created skiplist.

Skiplist

public Skiplist(int r,
                double p)

Creates a new skiplist with given random seed and given probability p.

Parameters:

r - The seed that is used to initialize the random number generator for the created skiplist.

p - The probability p as mentioned in the desription of the Skiplist-class.

Method Detail

insert

public void insert(K k,
                   D d)

Associates the data d to the key k in this skiplist. Takes O(log n) time in average.

Specified by:

insert in interface Map<K extends java.lang.Comparable<K>,D>

Specified by:

insert in class Dictionary<K extends java.lang.Comparable<K>,D>

Parameters:

k - The key to store.

d - The data associated to the key k.

See Also:

Map.insert(Object, Object)

find

public D find(K k)

Looks up the data associated to the key k. Needs logarithmic time in average.

Specified by:

find in interface Map<K extends java.lang.Comparable<K>,D>

Overrides:

find in class Dictionary<K extends java.lang.Comparable<K>,D>

Parameters:

k - The key for which the data should be found.

Returns:

null, if there is no data for k, or the associated data, otherwise.

See Also:

Map.find(Object)

iselement

public boolean iselement(K k)

Checks whether the key is present in this skiplist (in O(log n) time in average).

Specified by:

iselement in interface Map<K extends java.lang.Comparable<K>,D>

Overrides:

iselement in class Dictionary<K extends java.lang.Comparable<K>,D>

Parameters:

k - The key to look for.

Returns:

true, iff the k is present in this skiplist.

See Also:

Map.iselement(Object)

delete

public void delete(K k)

Deletes the key-data association for the given key in this skiplist in O(log n) in average.

Specified by:

delete in interface Map<K extends java.lang.Comparable<K>,D>

Specified by:

delete in class Dictionary<K extends java.lang.Comparable<K>,D>

Parameters:

k - The key which should be deleted

See Also:

Map.delete(Object)

size

public int size()

Returns the size of this skiplist (in constant time).

Specified by:

size in interface Map<K extends java.lang.Comparable<K>,D>

Overrides:

size in class Dictionary<K extends java.lang.Comparable<K>,D>

Returns:

The size of this skiplist.

See Also:

Map.size()

isempty

public boolean isempty()

Returns whether this skiplist is empty (in constant time).

Specified by:

isempty in interface Map<K extends java.lang.Comparable<K>,D>

Overrides:

isempty in class Dictionary<K extends java.lang.Comparable<K>,D>

Returns:

true, if this list is empty, and false, otherwise.

See Also:

Map.isempty()

iterator

public Iterator<K,D> iterator()

Description copied from interface: Map

Creates a new iterator over all associations between keys and data.

Specified by:

iterator in interface Map<K extends java.lang.Comparable<K>,D>

Specified by:

iterator in class Dictionary<K extends java.lang.Comparable<K>,D>

Returns:

The Iterator over all keys with associated data.

print

public void print()

Description copied from interface: Map

Prints the map to stdout

Specified by:

print in interface Map<K extends java.lang.Comparable<K>,D>

Overrides:

print in class Dictionary<K extends java.lang.Comparable<K>,D>