ptolemy.actor.util
Class CalendarQueue

java.lang.Object
  extended byptolemy.actor.util.CalendarQueue
All Implemented Interfaces:
Debuggable

public class CalendarQueue
extends java.lang.Object
implements Debuggable

This class implements a fast priority queue. Entries are sorted with the help of a comparator provided to the constructor. A dequeue operation will remove the smallest entry according to this sort. Entries can be any instance of Object that are acceptable to the specified comparator.

Entries are enqueued using the put() method, and dequeued using the take() method. The get() method returns the smallest entry in the queue, but without removing it from the queue. The toArray() methods can be used to examine the contents of the queue.

This class operates like a 'bag' or multiset collection. This simply means that an entry can be added into the queue even if it already exists in the queue. If a 'set' behavior is desired, one can subclass CalendarQueue and override the put() method.

The queue works as follows. Entries are conceptually stored in an infinite set of virtual bins (or buckets). The instance of CQComparator is consulted to determine which virtual bin should be used for an entry (by calling its getVirtualBinNumber() method). Each virtual bin has a width, which can be altered by calling the setBinWidth() method of the CQComparator. Within each virtual bin, entries are sorted.

Having an infinite number of bins, however, is not practical. Thus, the virtual bins are mapped into physical bins (or buckets) by a modulo operation. If there are n physical bins, then virtual bin i maps into physical bin i mod n.

This is analogous to a calendar showing 12 months. Here, n = 12. An event that happens in January of any year is placed in the first month (bin) of this calendar. Its virtual bin number might be year*12 + month. Its physical bin number is just month.

The performance of a calendar queue is very sensitive to the number of bins, the width of the bins, and the relationship of these quantities to the entries that are observed. Thus, this implementation may frequently change the number of bins. When it does change the number of bins, it changes them by a specifiable bin count factor. This defaults to 2, but can be specified as a constructor argument. Suppose the bin count factor is binCountFactor and the current number of buckets is n (by default, this starts at 2, but can be specified by a constructor argument, minNumBuckets). The number of bins will be multiplied by binCountFactor if the queue size exceeds n * binCountFactor. The number of bins will be divided by binCountFactor if the queue size falls below n/binCountFactor. Thus, the queue attempts to keep the number of bins close to the size of the queue. Each time it changes the number of bins, it uses recently dequeued entries to calculate a reasonable bin width (actually, it defers to the associated CQComparator for this calculation).

Changing the number of bins is a relatively expensive operation, so it may be worthwhile to increase binCountFactor to reduce the frequency of change operations. Working counter to this, however, is that the queue is most efficient when there is on average one event per bin. Thus, the queue becomes less efficient if change operations are less frequent. Change operations can be entirely disabled by calling setAdaptive() with argument false.

This implementation is not synchronized, so if multiple threads depend on it, the caller must be. This implementation is based on:

Since:
Ptolemy II 0.2
Version:
$Id: CalendarQueue.java,v 1.69 2004/04/13 05:13:13 cxh Exp $
Author:
Lukito Muliadi and Edward A. Lee
See Also:
CQComparator
Accepted Rating:
Yellow (liuj)
Proposed Rating:
Green (eal)

Constructor Summary
CalendarQueue(CQComparator comparator)
          Construct an empty queue with a given comparator, which is used to sort the entries.
CalendarQueue(CQComparator comparator, int minNumBuckets, int binCountFactor)
          Construct an empty queue with the specified comparator, which is used to sort the entries, the specified minimum number of buckets, and the specified bin count factor.
 
Method Summary
 void addDebugListener(DebugListener listener)
          Append a listener to the current set of debug listeners.
 void clear()
          Empty the queue, discarding all current information.
 java.lang.Object get()
          Return entry that is at the head of the queue (i.e. the one that will be obtained by the next take()).
 boolean includes(java.lang.Object entry)
          Return true if the specified entry is in the queue.
 boolean isEmpty()
          Return true if the queue is empty, and false otherwise.
 boolean put(java.lang.Object entry)
          Add an entry to the queue.
 boolean remove(java.lang.Object entry)
          Remove the specified entry and return true if the entry is found and successfully removed, and false if it is not found.
 void removeDebugListener(DebugListener listener)
          Unregister a debug listener.
 void setAdaptive(boolean flag)
          Enable or disable changing the number of bins (or buckets) in the queue.
 int size()
          Return the queue size, which is the number of entries currently in the queue.
 java.lang.Object take()
          Remove the smallest entry and return it.
 java.lang.Object[] toArray()
          Return the entries currently in the queue as an array.
 java.lang.Object[] toArray(int limit)
          Return the entries currently in the queue, but no more of them than the number given as an argument.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Constructor Detail

CalendarQueue

public CalendarQueue(CQComparator comparator)
Construct an empty queue with a given comparator, which is used to sort the entries. The bin count factor and the initial and minimum number of bins are set to 2.

Parameters:
comparator - The comparator used to sort entries.

CalendarQueue

public CalendarQueue(CQComparator comparator,
                     int minNumBuckets,
                     int binCountFactor)
Construct an empty queue with the specified comparator, which is used to sort the entries, the specified minimum number of buckets, and the specified bin count factor. The bin count factor multiplies or divides the number of bins when the number of bins is changed. The specified minimum number of buckets is also the initial number of buckets.

Parameters:
comparator - The comparator used to sort entries.
minNumBuckets - The minimum number of buckets.
binCountFactor - The bin count factor.
Method Detail

addDebugListener

public void addDebugListener(DebugListener listener)
Append a listener to the current set of debug listeners. If the listener is already in the set, do not add it again.

Specified by:
addDebugListener in interface Debuggable
Parameters:
listener - The listener to which to send debug messages.

clear

public void clear()
Empty the queue, discarding all current information. On the next put(), the queue will be reinitialized, including setting the bin width and zero reference of the comparator.

See Also:
CQComparator.setZeroReference(java.lang.Object)

get

public final java.lang.Object get()
                           throws InvalidStateException
Return entry that is at the head of the queue (i.e. the one that will be obtained by the next take()). If the queue is empty, then throw an InvalidStateException, since the emptiness can be tested.

Returns:
Object The smallest entry in the queue.
Throws:
InvalidStateException - If the queue is empty.

includes

public boolean includes(java.lang.Object entry)
Return true if the specified entry is in the queue. This is checked using the equals() method.

Parameters:
entry - The entry.
Returns:
True if the specified entry is in the queue.

isEmpty

public final boolean isEmpty()
Return true if the queue is empty, and false otherwise.

Returns:
True if empty, false otherwise.

put

public boolean put(java.lang.Object entry)
Add an entry to the queue. The first time this is called after queue creation or after calling clear() results in the comparator having its zero reference set to the argument and its bin width set to the default. Also, the number of buckets is set to the minimum (which has been given to the constructor). If the specified entry cannot be compared by the comparator associated with this queue, then a ClassCastException will be thrown. This method always returns true, but the return value may be used in derived classes to indicate that the entry is already on the queue and is not added again. In this class, the entry is always added, even if an identical entry already exists on the queue.

Parameters:
entry - The entry to be added to the queue.
Returns:
True.
Throws:
java.lang.ClassCastException - If the specified entry cannot be compared by the associated comparator.

remove

public boolean remove(java.lang.Object entry)
Remove the specified entry and return true if the entry is found and successfully removed, and false if it is not found. Equality is tested using the equals() method of the entry. If there are multiple entries in the queue that match, then only the first one is removed. The first one always corresponds to the one enqueued first among those multiple entries. Therefore, the queue has FIFO behavior.

Parameters:
entry - The entry to remove.
Returns:
True If a match is found and the entry is removed.

removeDebugListener

public void removeDebugListener(DebugListener listener)
Unregister a debug listener. If the specified listener has not been previously registered, then do nothing.

Specified by:
removeDebugListener in interface Debuggable
Parameters:
listener - The listener to remove from the list of listeners to which debug messages are sent.

setAdaptive

public void setAdaptive(boolean flag)
Enable or disable changing the number of bins (or buckets) in the queue. These change operations are fairly expensive, so in some circumstances you may wish to simply set the number of bins (using the constructor) and leave it fixed. If however the queue size becomes much larger or much smaller than the number of bins, the queue will become much less efficient.

Parameters:
flag - If false, disable changing the number of bins.

size

public final int size()
Return the queue size, which is the number of entries currently in the queue.

Returns:
The queue size.

take

public final java.lang.Object take()
                            throws InvalidStateException
Remove the smallest entry and return it. If there are multiple smallest entries, then return the first one that was put in the queue (FIFO behavior). If the queue is empty, then through an InvalidStateException, since the emptiness can be tested.

Returns:
The entry that is smallest, per the comparator.
Throws:
InvalidStateException - If the queue is empty.

toArray

public final java.lang.Object[] toArray()
Return the entries currently in the queue as an array.

Returns:
The entries currently in the queue.

toArray

public final java.lang.Object[] toArray(int limit)
Return the entries currently in the queue, but no more of them than the number given as an argument. To get all the entries in the queue, call this method with argument Integer.MAX_VALUE.

Parameters:
limit - The maximum number of entries desired.
Returns:
The entries currently in the queue.