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

java.lang.Object
  extended by 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()


Copyright © 2004-2007 Research Unit in Networking, All Rights Reserved.