Search this API

y.util.pq
Class DoubleObjectPQ

java.lang.Object
  extended by y.util.pq.DoubleObjectPQ

public class DoubleObjectPQ
extends java.lang.Object

This class implements a priority queue for objects whose priority values are of type double.

The implementation is based on binary heaps.

 

Constructor Summary
DoubleObjectPQ(int initialSize, DataProvider provider, DataAcceptor acceptor)
          Creates an empty ObjectPQ using the given DataProvider and DataAcceptor to store and retrieve Object support information.
 
Method Summary
 void add(java.lang.Object o, double priority)
          Adds the given object with given priority to this queue.
 void changePriority(java.lang.Object o, double priority)
          Changes the priority value of the given object.
 void clear()
          Makes this queue the empty queue.
 boolean contains(java.lang.Object o)
          Returns whether or not the given object is contained.
 void decreasePriority(java.lang.Object o, double priority)
          Decreases the priority value of the given object.
 void dispose()
          Does nothing.
 java.lang.Object getMin()
          Returns the object with smallest priority in this queue.
 double getMinPriority()
          Returns the minimum priority value in this queue.
 double getPriority(java.lang.Object o)
          Returns the current priority of the given object.
 void increasePriority(java.lang.Object o, double priority)
          Increases the priority value of the given object.
 boolean isEmpty()
          Returns whether or not this queue is empty.
 void remove(java.lang.Object o)
          Removes the given object from this queue.
 java.lang.Object removeMin()
          Removes the object with smallest priority from this queue.
 int size()
          Returns the number of nodes currently in this queue.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Constructor Detail

DoubleObjectPQ

public DoubleObjectPQ(int initialSize,
                      DataProvider provider,
                      DataAcceptor acceptor)
Creates an empty ObjectPQ using the given DataProvider and DataAcceptor to store and retrieve Object support information. The contents of the provider should be modified through the use of the acceptor, i.e. they should be based on the same initially empty backing store. Additionally this backing store should not be modified externally as long as this PQ is still in use.

Method Detail

add

public void add(java.lang.Object o,
                double priority)
Adds the given object with given priority to this queue.

Precondition:
!contains(o)
Complexity:
O(log(size()))

decreasePriority

public void decreasePriority(java.lang.Object o,
                             double priority)
Decreases the priority value of the given object.

Preconditions:
contains(o)
priority < getPriority(o)
Complexity:
O(log(size()))

increasePriority

public void increasePriority(java.lang.Object o,
                             double priority)
Increases the priority value of the given object.

Preconditions:
contains(o)
priority > getPriority(o)
Complexity:
O(log(size()))

changePriority

public void changePriority(java.lang.Object o,
                           double priority)
Changes the priority value of the given object.

Precondition:
contains(o)
Complexity:
O(log(size()))

removeMin

public java.lang.Object removeMin()
Removes the object with smallest priority from this queue.

Precondition:
!isEmpty()
Complexity:
O(log(size()))
Returns:
the removed object with smallest priority

getMin

public java.lang.Object getMin()
Returns the object with smallest priority in this queue.

Precondition:
!isEmpty()

getMinPriority

public double getMinPriority()
Returns the minimum priority value in this queue.


contains

public boolean contains(java.lang.Object o)
Returns whether or not the given object is contained. in this queue.

Complexity:
O(1)

isEmpty

public boolean isEmpty()
Returns whether or not this queue is empty.

Complexity:
O(1)

size

public int size()
Returns the number of nodes currently in this queue.

Complexity:
O(1)

getPriority

public double getPriority(java.lang.Object o)
Returns the current priority of the given object.

Precondition:
contains(o)

remove

public void remove(java.lang.Object o)
Removes the given object from this queue.

Precondition:
contains(o)
Complexity:
O(log(size()))

clear

public void clear()
Makes this queue the empty queue.

Complexity:
O(size())

dispose

public void dispose()
Does nothing.


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