be.ac.ulg.montefiore.run.totem.repository.CSPF
Class CSPFPriorityQueue

java.lang.Object
  be.ac.ulg.montefiore.run.totem.repository.CSPF.CSPFPriorityQueue

All Implemented Interfaces:

PriorityQueueIF

public class CSPFPriorityQueue
extends java.lang.Object
implements PriorityQueueIF

Priority Queue used in CSPF

Creation date: 23-Mar.-2004

Author:

Fabian Skivee (skivee@run.montefiore.ulg.ac.be)

Field Summary

protected PriorityQueueObject[]	heap
protected long	keyComps
protected java.util.HashMap<java.lang.String,java.lang.Integer>	pos
protected int	size

Constructor Summary

CSPFPriorityQueue(int capacity)
Get the object with the minimum key in the queue

Method Summary

void	add(PriorityQueueObject elem) Adds an object to the queue.
void	display()
PriorityQueueObject	getElem(java.lang.String id) Return the object for the specified id
long	getKeyComps()
PriorityQueueObject	next() Get the object with the minimum key in the queue
protected void	remove(PriorityQueueObject elem)
PriorityQueueObject	removeNext() Removes and returns the next object from the queue
protected void	siftup(int p, int q)
int	size() Get the size of the queue
void	update(PriorityQueueObject elem) Updates the Object with the same id in the queue Decreases (or increases) the value of elem's key and then performs sift-down (or siftup) until elem has been relocated to the correct position in the binary heap.

Methods inherited from class java.lang.Object

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

Field Detail

heap

protected PriorityQueueObject[] heap

pos

protected java.util.HashMap<java.lang.String,java.lang.Integer> pos

size

protected int size

keyComps

protected long keyComps

Constructor Detail

CSPFPriorityQueue

public CSPFPriorityQueue(int capacity)

Get the object with the minimum key in the queue

Parameters:

capacity - the maximum queue capacity

Method Detail

next

public PriorityQueueObject next()

Get the object with the minimum key in the queue

Specified by:

next in interface PriorityQueueIF

Returns:

the object with the minimum key

add

public void add(PriorityQueueObject elem)

Adds an object to the queue.

Specified by:

add in interface PriorityQueueIF

Parameters:

elem - the object to add

removeNext

public PriorityQueueObject removeNext()

Removes and returns the next object from the queue

Specified by:

removeNext in interface PriorityQueueIF

Returns:

The object removed from the queue

update

public void update(PriorityQueueObject elem)

Updates the Object with the same id in the queue Decreases (or increases) the value of elem's key and then performs sift-down (or siftup) until elem has been relocated to the correct position in the binary heap.

Specified by:

update in interface PriorityQueueIF

Parameters:

elem - The object to update in the queue

getElem

public PriorityQueueObject getElem(java.lang.String id)

Return the object for the specified id

Parameters:

id -

Returns:

size

public int size()

Get the size of the queue

Specified by:

size in interface PriorityQueueIF

Returns:

size of the queue

remove

protected void remove(PriorityQueueObject elem)

siftup

protected void siftup(int p,
                      int q)

display

public void display()

getKeyComps

public long getKeyComps()