org.jutil.java.collections
Class SkipListPQ

java.lang.Object
  |
  +--org.jutil.java.collections.SkipListPQ

All Implemented Interfaces:

PriorityQueue

public class SkipListPQ

extends java.lang.Object

implements PriorityQueue

A SkipList based priority queue

Version:

$Revision: 1.2 $

Author:

Tom Schrijvers, Marko van Dooren

Field Summary

static java.lang.String

CVS_REVISION

Constructor Summary

SkipListPQ(java.util.Comparator comparator)
public behavior

post size() == 0;
post getComparator() == comparator;
Initialize a new SkipListPQ with the given comparator.

Method Summary

void	add(java.lang.Object element) See superclass.
void	clear() See superclass.
java.util.Comparator	getComparator() See superclass.
boolean	isEmpty() See superclass.
java.lang.Object	min() See superclass.
int	nbExplicitOccurrences(java.lang.Object element) See superclass.
java.lang.Object	pop() See superclass.
int	size() See superclass.

Methods inherited from class java.lang.Object

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

Field Detail

CVS_REVISION

public static final java.lang.String CVS_REVISION

Constructor Detail

SkipListPQ

public SkipListPQ(java.util.Comparator comparator)

public behavior

post size() == 0;
post getComparator() == comparator;
Initialize a new SkipListPQ with the given comparator.

Parameters:

comparator - The comparator that is used to determine the order of the added elements.

Method Detail

add

public void add(java.lang.Object element)

See superclass.

average: O(log(n))

worst case: O(n)

Specified by:

add in interface PriorityQueue

Following copied from interface: org.jutil.java.collections.PriorityQueue

Parameters:

element - The object to be added.

min

public java.lang.Object min()

See superclass.

O(1)

Specified by:

min in interface PriorityQueue

pop

public java.lang.Object pop()

See superclass.

O(1)

Specified by:

pop in interface PriorityQueue

isEmpty

public boolean isEmpty()

See superclass.

Specified by:

isEmpty in interface PriorityQueue

nbExplicitOccurrences

public int nbExplicitOccurrences(java.lang.Object element)

See superclass.

Specified by:

nbExplicitOccurrences in interface PriorityQueue

Following copied from interface: org.jutil.java.collections.PriorityQueue

Parameters:

element - The object of which the number of explicit occurrences is requested.

size

public int size()

See superclass.

Specified by:

size in interface PriorityQueue

getComparator

public java.util.Comparator getComparator()

See superclass.

Specified by:

getComparator in interface PriorityQueue

clear

public void clear()

See superclass.

Specified by:

clear in interface PriorityQueue