PathPlan
Class PriorityQueue

java.lang.Object
  extended by PathPlan.PriorityQueue

public class PriorityQueue
extends java.lang.Object

A priority queue. Keeps a list of entries (small nonnegative integers) with real-valued priorities, and supports finding/removing the first entry (the one with numerically smallest priority) efficiently.


Constructor Summary
PriorityQueue(int limit)
          Make a new queue.
 
Method Summary
 void empty()
          Empty out the queue.
 int[] getIDs()
          Get the ids of all nodes in the queue.
 double getLastPriority()
          Find the priority of the last node that was removed from the queue (by remove or pop).
 int getMaxSize()
          Find the largest size that we can make the queue.
 double getPriority(int id)
          Get the priority of a given id.
 int getSize()
          Find the size of the queue (number of pops that we can do before emptying it).
 void insert(int id, double priority)
          Insert an element at the given priority.
 boolean isPresent(int id)
          Test for the presence of a known ID in the queue.
static void main(java.lang.String[] args)
           
 int pop()
          Remove and return the first element.
 boolean raise(int id, double priority)
          If an element is in the priority queue at a later priority, raise it; if it is not there, insert it.
 double remove(int id)
          Remove an element from the queue if it's there.
 void set(int id, double priority)
          Reset the priority of an element, or insert it if it's not already there.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Constructor Detail

PriorityQueue

public PriorityQueue(int limit)
Make a new queue.

Parameters:
limit - The queue can contain at most limit nodes.
Method Detail

isPresent

public boolean isPresent(int id)
Test for the presence of a known ID in the queue.

Parameters:
id - Is this ID present?

insert

public void insert(int id,
                   double priority)
Insert an element at the given priority. If the queue is full, throw an exception.

Parameters:
id - A number between 0 and getSize()-1. We can use the ID later to reset the element's priority. It is an error to attempt to put two distinct elements with the same ID in the queue simultaneously.
priority - The numerical priority. (Lower numbers mean the element will be accessed sooner, which some might say is reversed from the usual definition of priority.)

remove

public double remove(int id)
Remove an element from the queue if it's there. If it wasn't there, throw an exception.

Parameters:
id - The element to remove.
Returns:
The element's priority.

pop

public int pop()
Remove and return the first element. (The first element is the one with smallest numerical priority value, which some might say is reversed from the usual definition of priority.) If the queue was empty, throw an exception.


raise

public boolean raise(int id,
                     double priority)
If an element is in the priority queue at a later priority, raise it; if it is not there, insert it.

Parameters:
id - The element ID.
priority - The new priority.
Returns:
Returns true iff we changed anything.

set

public void set(int id,
                double priority)
Reset the priority of an element, or insert it if it's not already there.

Parameters:
id - The element ID.
priority - The element priority.

getLastPriority

public double getLastPriority()
Find the priority of the last node that was removed from the queue (by remove or pop).


getSize

public int getSize()
Find the size of the queue (number of pops that we can do before emptying it).


getMaxSize

public int getMaxSize()
Find the largest size that we can make the queue.


getIDs

public int[] getIDs()
Get the ids of all nodes in the queue.


getPriority

public double getPriority(int id)
Get the priority of a given id.

Parameters:
id - The node whose priority we need.

empty

public void empty()
Empty out the queue.


main

public static void main(java.lang.String[] args)