Package nl.tue.astar.util

Class AbstractFastLookupPriorityQueue

java.lang.Object

nl.tue.astar.util.AbstractFastLookupPriorityQueue

All Implemented Interfaces:

FastLookupPriorityQueue

Direct Known Subclasses:

BreadthFirstFastLookupPriorityQueue, DepthFirstFastLookupPriorityQueue, RandomFastLookupPriorityQueue

public abstract class AbstractFastLookupPriorityQueue
extends java.lang.Object
implements FastLookupPriorityQueue

Field Summary

Fields

Modifier and Type	Field	Description
protected gnu.trove.map.TLongIntMap	locationMap
protected int	maxCost	The maximum total cost for any record in this queue.
protected static int	NEV
protected Record[]	queue	Priority queue represented as a balanced binary heap: the two children of queue[n] are queue[2*n+1] and queue[2*(n+1)].
protected int	size	The number of elements in the priority queue.

Constructor Summary

Constructors

Constructor	Description
AbstractFastLookupPriorityQueue(int initialCapacity)
AbstractFastLookupPriorityQueue(int initialCapacity, int maxCost)

Method Summary

Modifier and Type	Method	Description
boolean	add(Record newE)	Inserts the specified element into this priority queue.
boolean	checkInv()
protected boolean	checkInv(int loc)
Record	contains(Record newRec)	Checks if the queue contains a record pointing to the same state as the given record.
int	getMaxCost()
protected void	grow(int minCapacity)	Increases the capacity of the array.
int	hashCode()
protected abstract boolean	isBetter(Record r1, Record r2)
boolean	isEmpty()
protected void	offer(Record e)	Inserts the specified element into this priority queue.
Record	peek()
protected Record	peek(int location)
Record	poll()
void	setMaxCost(int maxCost)
protected void	siftDown(int k, Record x)	Inserts item x at position k, maintaining heap invariant by demoting x down the tree repeatedly until it is less than or equal to its children or is a leaf.
protected void	siftUp(int k, Record x)	Inserts item x at position k, maintaining heap invariant by promoting x up the tree until it is greater than or equal to its parent, or is the root.
int	size()
java.lang.String	toString()
protected void	updateToBetter(int index, Record newRecord)

Methods inherited from class java.lang.Object

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

Field Detail

locationMap

protected final gnu.trove.map.TLongIntMap locationMap

NEV

protected static final int NEV

See Also:

Constant Field Values

queue

protected Record[] queue

Priority queue represented as a balanced binary heap: the two children of queue[n] are queue[2*n+1] and queue[2*(n+1)]. The priority queue is ordered by the record's natural ordering: For each node n in the heap and each descendant d of n, n <= d. The element with the best value is in queue[0], assuming the queue is nonempty.

size

protected int size

The number of elements in the priority queue.

maxCost

protected int maxCost

The maximum total cost for any record in this queue. If the cost of a record which is added is higher that this value, it is not added

Constructor Detail

AbstractFastLookupPriorityQueue

public AbstractFastLookupPriorityQueue(int initialCapacity)

AbstractFastLookupPriorityQueue

public AbstractFastLookupPriorityQueue(int initialCapacity,
                                       int maxCost)

Method Detail

isEmpty

public boolean isEmpty()

Specified by:

isEmpty in interface FastLookupPriorityQueue

hashCode

public int hashCode()

Overrides:

hashCode in class java.lang.Object

setMaxCost

public void setMaxCost(int maxCost)

Specified by:

setMaxCost in interface FastLookupPriorityQueue

getMaxCost

public int getMaxCost()

Specified by:

getMaxCost in interface FastLookupPriorityQueue

contains

public Record contains(Record newRec)

Description copied from interface: FastLookupPriorityQueue

Checks if the queue contains a record pointing to the same state as the given record. If so, it returns that record, if not, it returns null;

Specified by:

contains in interface FastLookupPriorityQueue

Returns:

checkInv

public boolean checkInv()

grow

protected void grow(int minCapacity)

Increases the capacity of the array.

Parameters:

minCapacity - the desired minimum capacity

peek

public Record peek()

Specified by:

peek in interface FastLookupPriorityQueue

size

public int size()

Specified by:

size in interface FastLookupPriorityQueue

poll

public Record poll()

Specified by:

poll in interface FastLookupPriorityQueue

peek

protected Record peek(int location)

toString

public java.lang.String toString()

Overrides:

toString in class java.lang.Object

updateToBetter

protected void updateToBetter(int index,
                              Record newRecord)

add

public boolean add(Record newE)

Inserts the specified element into this priority queue.

Specified by:

add in interface FastLookupPriorityQueue

Returns:

true (as specified by Collection.add(E))

Throws:

java.lang.ClassCastException - if the specified element cannot be compared with elements currently in this priority queue according to the priority queue's ordering

java.lang.NullPointerException - if the specified element is null

isBetter

protected abstract boolean isBetter(Record r1,
                                    Record r2)

offer

protected void offer(Record e)

Inserts the specified element into this priority queue.

Throws:

java.lang.ClassCastException - if the specified element cannot be compared with elements currently in this priority queue according to the priority queue's ordering

java.lang.NullPointerException - if the specified element is null

siftUp

protected void siftUp(int k,
                      Record x)

Inserts item x at position k, maintaining heap invariant by promoting x up the tree until it is greater than or equal to its parent, or is the root.

Parameters:

k -

x - the item to insert

siftDown

protected void siftDown(int k,
                        Record x)

Inserts item x at position k, maintaining heap invariant by demoting x down the tree repeatedly until it is less than or equal to its children or is a leaf.

Parameters:

k - the position to fill

x - the item to insert

checkInv

protected boolean checkInv(int loc)