util
Class FairWeightedQueue

java.lang.Object
  |
  +--util.FairWeightedQueue

All Implemented Interfaces:

Queue

public class FairWeightedQueue

extends Object

implements Queue

A queue structure that provides for weighted priorities while still dequeueing in a manner that allows lower priorities to be dequeued even when higher priority objects may still be in the system.

Version:

$Revision: 1.9 $

Author:

Dave Jurgens

, John Krettek

Field Summary

private double[]	distributions This array represent the numerical distributions for a given priority.
private util.PriorityProvider	pp This field provides a priority index for an enqueued object via the getPriority() call.
private util.Queue[]	queues These queues represent all possible probabilities from 1 to queues.length, with queues.length representing the lowest possible priority.
private Random	random The Random object provides a stochastic way of choosing the next priority from our array of distributions.
private static long	serialVersionUID
private int	size Total number of all objects enqueued in all queues.
private boolean	waiting To conserve the number of notify calls made, the dequeue method will set this field to true before it waits.

Constructor Summary

FairWeightedQueue(util.PriorityProvider pp)
The number of priorities is gotten from the PriorityProvider.

Method Summary

Object	dequeue() This method removes from a queue by selected a random number and then iterating through the distribution values until it finds a priority with a distribution that is greated than the ranged value.
void	enqueue(Object o) This method queries the given ProvidesPriority for the priority value Object o.
boolean	enqueue(util.PriorityEnqueueable p) This method queries the given ProvidesPriority for the priority value of the getEvaluationObject().
protected boolean	enqueueObject(Object o, int index) This method tries to enqueue the object at the specified index in the array of queues.
boolean	isEmpty() Returns whether the queue is currently empty.
int	size() Returns the number of items currently in the queue.

Methods inherited from class java.lang.Object

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

Field Detail

serialVersionUID

private static final long serialVersionUID

See Also:

Constant Field Values

pp

private util.PriorityProvider pp

This field provides a priority index for an enqueued object via the getPriority() call. It returns a value between 1 and the lowest priority specified for it, with 1 being the highest priority.

queues

private util.Queue[] queues

These queues represent all possible probabilities from 1 to queues.length, with queues.length representing the lowest possible priority. Values for priority are shifted over in the enqueue method to account for the array index starting at 0.

distributions

private double[] distributions

This array represent the numerical distributions for a given priority. The distributions operate in powers of two, with a higher priority having a distribution twice as large than the priority directly beneath it.

random

private Random random

The Random object provides a stochastic way of choosing the next priority from our array of distributions.

size

private int size

Total number of all objects enqueued in all queues.

waiting

private boolean waiting

To conserve the number of notify calls made, the dequeue method will set this field to true before it waits. EnqueueObject will then notify() only when this is true

Constructor Detail

FairWeightedQueue

public FairWeightedQueue(util.PriorityProvider pp)

The number of priorities is gotten from the PriorityProvider.

Method Detail

enqueue

public void enqueue(Object o)

This method queries the given ProvidesPriority for the priority value Object o. This priority will be on a scale from 1 to the highest priority. Therefore, the correct index would be (priority -1).

Specified by:

enqueue in interface Queue

enqueue

public boolean enqueue(util.PriorityEnqueueable p)

This method queries the given ProvidesPriority for the priority value of the getEvaluationObject(). This accessor method provides the opportunity for wrapped classes to provide an alternative field (other than themselves) to evaluate their priority. An example would be a runnable providing the field on which it executes method calls. This priority will be on a scale from 1 to the highest priority. Therefore, the correct index would be (priority -1). The method returns true only if the object was sucessfully enqueued at the specified priority.

enqueueObject

protected boolean enqueueObject(Object o,
                                int index)

This method tries to enqueue the object at the specified index in the array of queues. The IndexOutOfBounds exception is caught and subsequently causes the method to return false to denote that the object was not enqueued sucessfully.

isEmpty

public boolean isEmpty()

Description copied from interface: Queue

Returns whether the queue is currently empty.

Specified by:

isEmpty in interface Queue

size

public int size()

Description copied from interface: Queue

Returns the number of items currently in the queue.

Specified by:

size in interface Queue

dequeue

public Object dequeue()

This method removes from a queue by selected a random number and then iterating through the distribution values until it finds a priority with a distribution that is greated than the ranged value. The method blocks if there is nothing to dequeue.

Specified by:

dequeue in interface Queue