Lightweight Bartering Grid

lbg.common.queueing.priority
Class PriorityQueue<E>

java.lang.Object
  extended by lbg.common.queueing.priority.PriorityQueue<E>
All Implemented Interfaces:
java.lang.Iterable<E>

public class PriorityQueue<E>
extends java.lang.Object
implements java.lang.Iterable<E>

Synchronized implementation of an unbounded PriorityQueue backed by a balanced tree and a doubly-linked list.

Nominal use is to keep a set of elements sorted with respect to their order of insertion.

This class has been developped to replace LinkedList. They may both be used to implement Tasks queues in the QueueManager. As inserting an element into such a queue is legal only if the element is not already present, it is required that a search operation is also performed. The cost of the search operation in LinkedList is linear, while it is logarithmic in PriorityQueue, because the latter is backed by a balanced tree.

IMPORTANT NOTE: as int != Integer, it is preferred not to use int keys when Integer keys are expected, to avoid that autoboxing skews Object.equals() tests.

NOTE: current implementation is not robust to non-Comparable keys.

Author:
Cyril Briquet

Constructor Summary
PriorityQueue()
          Builds a new PriorityQueue.
 
Method Summary
 boolean add(E e)
          Adds target element to the end of the PriorityQueue, if not already present.
 E extractHighestPriorityElement()
          Removes then returns the element with the higest priority in the PriorityQueue.
 boolean hasElement(E e)
          Returns if target element is stored in the PriorityQueue.
 java.util.Iterator<E> iterator()
          Returns an iterator over the elements in the PriorityQueue.
 boolean remove(E e)
          Removes target element from the PriorityQueue if it is present.
 int size()
          Returns the number of elements in the PriorityQueue.
 java.lang.String toString()
           
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
 

Constructor Detail

PriorityQueue

public PriorityQueue()
Builds a new PriorityQueue.

Method Detail

toString

public java.lang.String toString()
Overrides:
toString in class java.lang.Object

size

public int size()
Returns the number of elements in the PriorityQueue.

Returns:
the number of elements in the PriorityQueue

iterator

public java.util.Iterator<E> iterator()
Returns an iterator over the elements in the PriorityQueue. The elements are returned by decreasing priority.

Specified by:
iterator in interface java.lang.Iterable<E>
Returns:
an iterator over the elements in the PriorityQueue

hasElement

public boolean hasElement(E e)
Returns if target element is stored in the PriorityQueue.

Returns:
true if target element is stored in the PriorityQueue

extractHighestPriorityElement

public E extractHighestPriorityElement()
                                throws GridException
Removes then returns the element with the higest priority in the PriorityQueue.

Returns:
the element with the higest priority in the PriorityQueue, null if there is no element in the PriorityQueue
Throws:
GridException

add

public boolean add(E e)
            throws GridException,
                   java.lang.NullPointerException
Adds target element to the end of the PriorityQueue, if not already present.

Parameters:
e - target element
Returns:
true if target element was not already present in the PriorityQueue
Throws:
GridException - if data has been corrupted
java.lang.NullPointerException - if target element is null

remove

public boolean remove(E e)
               throws java.lang.NullPointerException
Removes target element from the PriorityQueue if it is present.

Parameters:
e - target element
Returns:
true if target element was present in the PriorityQueue
Throws:
java.lang.NullPointerException - if target element is null

Lightweight Bartering Grid

Copyright (c) 2005-2008, Cyril Briquet, parts Xavier Dalem.