fi.uef.cs.tra

Class AdjustablePriorityQueue<E extends java.lang.Comparable>

java.lang.Object

fi.uef.cs.tra.AdjustablePriorityQueue<E>

Type Parameters:

E - element type.

public class AdjustablePriorityQueue<E extends java.lang.Comparable>
extends java.lang.Object

Priority queue with operation to improve/demote the priority of an element (node). To improve the priority, you need to provide the BTreeNode holding the element. Thus offer will return BTreeNode of the new element. Elements are prioritized by their natural order (Comparable). You must ensure that when the priority of an element is improved / demoted you call improvePriority() / decreasePriority(), respecticely.

Constructor Summary

Constructors

Constructor and Description
AdjustablePriorityQueue() Default constructor.

Method Summary

Modifier and Type	Method and Description
void	decreasePriority(BTreeNode<E> x) Fix the priority queue after the priority of the element in BTreeNode has been changed to worse one.
void	improvePriority(BTreeNode<E> node) Fix the priority queue after the priority of the element in BTreeNode has been changed to better one.
boolean	isEmpty() Operation to check if priority queue is empty or not.
BTreeNode<E>	offer(E x) Inserts an element to priority queue.
E	poll() Remove and return the most important element of the priority queue.
java.lang.String	toString() String representation of priority queue.

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, wait, wait, wait

Constructor Detail

AdjustablePriorityQueue

public AdjustablePriorityQueue()

Default constructor. Creates an empty priority queue.

Method Detail

offer

public BTreeNode<E> offer(E x)

Inserts an element to priority queue.

Parameters:

x - the element to be inserted.

Returns:

the new BTreeNode holding the element.

poll

public E poll()

Remove and return the most important element of the priority queue. Throws NoSuchMethodException if there are no elements.

Returns:

the most important element.

improvePriority

public void improvePriority(BTreeNode<E> node)

Fix the priority queue after the priority of the element in BTreeNode has been changed to better one.

Parameters:

node - the node containing the element which was changed.

decreasePriority

public void decreasePriority(BTreeNode<E> x)

Fix the priority queue after the priority of the element in BTreeNode has been changed to worse one.

Parameters:

node - the node containing the element which was changed.

isEmpty

public boolean isEmpty()

Operation to check if priority queue is empty or not.

Returns:

true if there are no elements in the queue, false otherwise.

toString

public java.lang.String toString()

String representation of priority queue. Nodes by levels.

Overrides:

toString in class java.lang.Object

Returns:

the string.