engine_lsd
Class PriorityQueue

java.lang.Object
  engine_lsd.PriorityQueue

public class PriorityQueue
extends java.lang.Object

Implements a priority queue via a binary heap.

Author:

Mark Allen Weiss modified by Francesco Romani

Field Summary

private State[]	array
private int	currentSize
private static int	DEFAULT_CAPACITY

Constructor Summary

PriorityQueue()
Construct the priority queue

Method Summary

void	clear() Make the priority queue logically empty.
private void	doubleArray() Internal method to extend array.
State	get() Remove the smallest item from the priority queue.
boolean	isEmpty() Test if the priority queue is logically empty.
State	look() Find the smallest item in the priority queue.
private void	percolateDown(int hole) Internal method to percolate down in the heap.
void	put(State x) Insert into the priority queue.
int	size() Returns size.

Methods inherited from class java.lang.Object

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

Field Detail

DEFAULT_CAPACITY

private static final int DEFAULT_CAPACITY

See Also:

Constant Field Values

currentSize

private int currentSize

array

private State[] array

Constructor Detail

PriorityQueue

public PriorityQueue()

Construct the priority queue

Method Detail

put

public void put(State x)

Insert into the priority queue.

Parameters:

x - the item to insert.

look

public State look()

Find the smallest item in the priority queue.

Returns:

the smallest item, null if empty

get

public State get()

Remove the smallest item from the priority queue.

Returns:

the smallest item, null if empty

isEmpty

public boolean isEmpty()

Test if the priority queue is logically empty.

Returns:

true if empty, false otherwise.

size

public int size()

Returns size.

Returns:

current size.

clear

public void clear()

Make the priority queue logically empty.

percolateDown

private void percolateDown(int hole)

Internal method to percolate down in the heap.

Parameters:

hole - the index at which the percolate begins.

doubleArray

private void doubleArray()

Internal method to extend array.