org.jutil.java.collections
Class SkipListPQ

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

All Implemented Interfaces:

Dispenser, PriorityQueue

public class SkipListPQ

extends AbstractPriorityQueue

A SkipList based priority queue

Field Summary
static java.lang.String	CVS_REVISION

 

Constructor Summary

SkipListPQ(java.util.Comparator comparator)           Initialize a new SkipListPQ with the given comparator.

 

Method Summary
protected  void	addImpl(java.lang.Object element)           See superclass. average: O(log(n)) worst case: O(n)
void	clear()           See superclass.
java.util.Comparator	getComparator()           See superclass.
java.util.Iterator	iterator()           See superclass.
java.lang.Object	min()           See superclass. O(1)
int	nbExplicitOccurrences(java.lang.Object element)           See superclass.
java.lang.Object	pop()           See superclass. O(1)
int	size()           See superclass.

 

Methods inherited from class org.jutil.java.collections.AbstractPriorityQueue

getNext, removeNext

 

Methods inherited from class org.jutil.java.collections.AbstractDispenser

add, isEmpty

 

Methods inherited from class java.lang.Object

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

 

Methods inherited from interface org.jutil.java.collections.Dispenser

add, isEmpty

 

Field Detail

CVS_REVISION

public static final java.lang.String CVS_REVISION

SkipListPQ

public SkipListPQ(java.util.Comparator comparator)

Initialize a new SkipListPQ with the given comparator.

Parameters:

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

Specifications:

public behavior
ensures size() == 0;
ensures getComparator() == comparator;

addImpl

protected void addImpl(java.lang.Object element)

See superclass.

average: O(log(n))

worst case: O(n)

Specifications inherited from overridden method in class AbstractDispenser:

public behavior
requires item != null;
ensures nbExplicitOccurrences(item) == \old(nbExplicitOccurrences(item))+1;

min

public java.lang.Object min()

See superclass.

O(1)

Specifications inherited from overridden method in interface PriorityQueue:

public behavior
requires !isEmpty();
ensures nbExplicitOccurrences(\result ) > 0;
ensures ( \forall Object o; nbExplicitOccurrences(o) > 0; ExtendedComparator.ensureExtended(getComparator()).notGreater(o,\result ));

pop

public java.lang.Object pop()

See superclass.

O(1)

Specifications inherited from overridden method in interface PriorityQueue:

public behavior
requires !isEmpty();
ensures \result == \old(min());
ensures nbExplicitOccurrences(\result ) == \old(nbExplicitOccurrences(getNext()))-1;

nbExplicitOccurrences

public int nbExplicitOccurrences(java.lang.Object element)

See superclass.

Specifications inherited from overridden method in interface Dispenser:

public behavior
ensures \result >= 0;

size

public int size()

See superclass.

Specifications inherited from overridden method in interface Dispenser:

public behavior
ensures \result == ( \sum Object item; ; nbExplicitOccurrences(item));

getComparator

public java.util.Comparator getComparator()

See superclass.

Specifications inherited from overridden method in interface PriorityQueue:

public behavior
ensures \result != null;

clear

public void clear()

See superclass.

iterator

public java.util.Iterator iterator()

See superclass.