websphinx.util
Class PriorityQueue

java.lang.Object
  |
  +--websphinx.util.PriorityQueue

public class PriorityQueue

extends java.lang.Object

Priority queue. Objects stored in a priority queue must implement the Prioritized interface.

Field Summary

private java.util.Vector

q

Constructor Summary

PriorityQueue()
Make an empty PriorityQueue.

PriorityQueue(int initialCapacity)
Make an empty PriorityQueue with an initial capacity.

Method Summary

void	clear() Remove all objects from queue.
boolean	delete(Prioritized x) Delete an object from queue.
(package private) void	deleteElement(int i)
java.lang.Object	deleteMin() Get and delete the object with lowest priority.
static void	dump(PriorityQueue q)
java.util.Enumeration	elements() Enumerate the objects in the queue, in no particular order
boolean	empty() Test whether queue is empty.
java.lang.Object	getMin() Get object with lowest priority from queue.
(package private) float	getPriority(int i)
(package private) void	heapify(int i)
static void	main(java.lang.String[] args)
void	put(Prioritized x) Put an object on the queue.
int	size() Get number of objects in queue.
(package private) void	swap(int i, int j)
void	update() Rebuild priority queuein case the priorities of its elements have changed since they were inserted.

Methods inherited from class java.lang.Object

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

Field Detail

q

private java.util.Vector q

Constructor Detail

PriorityQueue

public PriorityQueue()

Make an empty PriorityQueue.

PriorityQueue

public PriorityQueue(int initialCapacity)

Make an empty PriorityQueue with an initial capacity.

Parameters:

initialCapacity - number of elements initially allocated in queue

Method Detail

put

public void put(Prioritized x)

Put an object on the queue. Doesn't check for duplicate puts.

Parameters:

x - object to put on the queue

getMin

public java.lang.Object getMin()

Get object with lowest priority from queue.

Returns:

object with lowest priority, or null if queue is empty

deleteMin

public java.lang.Object deleteMin()

Get and delete the object with lowest priority.

Returns:

object with lowest priority, or null if queue is empty

delete

public boolean delete(Prioritized x)

Delete an object from queue. If object was inserted more than once, this method deletes only one occurrence of it.

Parameters:

x - object to delete

Returns:

true if x was found and deleted, false if x not found in queue

clear

public void clear()

Remove all objects from queue.

elements

public java.util.Enumeration elements()

Enumerate the objects in the queue, in no particular order

Returns:

enumeration of objects in queue

size

public int size()

Get number of objects in queue.

Returns:

number of objects

empty

public boolean empty()

Test whether queue is empty.

Returns:

true iff queue is empty.

update

public void update()

Rebuild priority queuein case the priorities of its elements have changed since they were inserted. If the priority of any element changes, this method must be called to update the priority queue.

deleteElement

final void deleteElement(int i)

heapify

final void heapify(int i)

swap

final void swap(int i,
                int j)

getPriority

final float getPriority(int i)

main

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

dump

public static void dump(PriorityQueue q)