be.ac.ulg.montefiore.run.totem.util
Class PriorityQueue

java.lang.Object
  be.ac.ulg.montefiore.run.totem.util.PriorityQueue

All Implemented Interfaces:

PriorityQueueIFInt

public class PriorityQueue
extends java.lang.Object
implements PriorityQueueIFInt

Priority queue with integers

Creation date: 22-Jun.-2004

Author:

Olivier Delcourt (delcourt@run.montefiore.ulg.ac.be)

Field Summary

protected PriorityQueueObjectInt[]	heap
protected long	keyComps
protected java.util.HashMap	pos
protected int	size

Constructor Summary

PriorityQueue(int capacity)
Constructor

Method Summary

void	add(PriorityQueueObjectInt elem) Adds an object to the queue.
void	display()
long	getKeyComps()
PriorityQueueObjectInt	next() Get the object with the minimum key in the queue
protected void	remove(PriorityQueueObjectInt elem)
PriorityQueueObjectInt	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(PriorityQueueObjectInt elem) Updates the Object with the same id in the queue Decreases the value of elem's key and then performs sift-down 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 PriorityQueueObjectInt[] heap

pos

protected java.util.HashMap pos

size

protected int size

keyComps

protected long keyComps

Constructor Detail

PriorityQueue

public PriorityQueue(int capacity)

Constructor

Parameters:

capacity - the maximum queue capacity

Method Detail

next

public PriorityQueueObjectInt next()

Get the object with the minimum key in the queue

Specified by:

next in interface PriorityQueueIFInt

Returns:

the object with the minimum key

add

public void add(PriorityQueueObjectInt elem)

Adds an object to the queue.

Specified by:

add in interface PriorityQueueIFInt

Parameters:

elem - the object to add

removeNext

public PriorityQueueObjectInt removeNext()

Removes and returns the next object from the queue

Specified by:

removeNext in interface PriorityQueueIFInt

Returns:

The object removed from the queue

update

public void update(PriorityQueueObjectInt elem)

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

Specified by:

update in interface PriorityQueueIFInt

Parameters:

elem - The object to update in the queue

size

public int size()

Get the size of the queue

Specified by:

size in interface PriorityQueueIFInt

Returns:

size of the queue

remove

protected void remove(PriorityQueueObjectInt elem)

siftup

protected void siftup(int p,
                      int q)

display

public void display()

getKeyComps

public long getKeyComps()