ptolemy.actor.util
Class CalendarQueue

java.lang.Object
  ptolemy.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).

For efficiency, this implementation constrains minNumBuckets and binCountFactor to be powers of two. If something other than a power is two is given, the next power of two larger than the specified number is used. This has the effect of ensuring that the number of bins is always a power of two, and hence the modulo operation used to map virtual bin numbers onto actual bin numbers is a simple masking operation.

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:

• Randy Brown, CalendarQueues:A Fast Priority Queue Implementation for the Simulation Event Set Problem, Communications of the ACM, October 1988, Volume 31, Number 10.
• A. Banerjea and E. W. Knightly, Ptolemy Classic implementation of CalendarQueue class.

Since:

Ptolemy II 0.2

Version:

$Id: CalendarQueue.java 47513 2007-12-07 06:32:21Z cxh $

Author:

Lukito Muliadi and Edward A. Lee

See Also:

CQComparator

Accepted Rating:

Yellow (liuj)

Proposed Rating:

Green (eal)

Nested Class Summary

private static class	CalendarQueue.CQCell Simplified and specialized linked list cell.
private class	CalendarQueue.CQLinkedList

Field Summary

private int	_bottomThreshold
private CalendarQueue.CQLinkedList[]	_bucket
private java.lang.Object	_cachedMinimumBucket
private CQComparator	_cqComparator
private boolean	_debugging
private java.util.LinkedList	_debugListeners
private int	_indexOfMinimumBucket The index of the minmum bucket.
private boolean	_indexOfMinimumBucketValid Flag indicating whether the index of the minimum bucket is valid.
private boolean	_initialized
private int	_logMinNumBuckets
private int	_logNumberOfBuckets
private int	_logQueueBinCountFactor
private int	_minBucket
private java.lang.Object	_minimumEntry
private long	_minVirtualBucket
private int	_numberOfBuckets
private int	_numberOfBucketsMask
private java.lang.Object	_previousTakenEntry
private int	_queueSize
private int	_queueSizeOverThreshold
private int	_queueSizeUnderThreshold
private static int	_RESIZE_LAG
private boolean	_resizeEnabled
private static int	_SAMPLE_SIZE
private java.lang.Object[]	_sampleEntries
private int	_sampleEntryIndex
private boolean	_sampleValid
private int	_topThreshold

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

private void	_collect(java.lang.Object entry)
private void	_debug(java.lang.String message) Send a debug message to all debug listeners that have registered.
private int	_getBinIndex(java.lang.Object entry)
private java.lang.Object	_getFromBucket(int index) Get the first entry from the specified bucket and return its contents.
private int	_getIndexOfMinimumBucket() Get the index of the minimum bucket.
private void	_localInit(int logNumberOfBuckets, java.lang.Object firstEntry)
private void	_resize(boolean increasing)
private java.lang.Object	_takeFromBucket(int index)
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.
static int	log(int value) Return the power of two belonging to the least integer power of two larger than or equal to the specified integer.
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

Field Detail

_debugListeners

private java.util.LinkedList _debugListeners

_debugging

private boolean _debugging

_queueSizeOverThreshold

private int _queueSizeOverThreshold

_queueSizeUnderThreshold

private int _queueSizeUnderThreshold

_bottomThreshold

private int _bottomThreshold

_bucket

private CalendarQueue.CQLinkedList[] _bucket

_cachedMinimumBucket

private java.lang.Object _cachedMinimumBucket

_cqComparator

private CQComparator _cqComparator

_indexOfMinimumBucket

private int _indexOfMinimumBucket

The index of the minmum bucket.

_indexOfMinimumBucketValid

private boolean _indexOfMinimumBucketValid

Flag indicating whether the index of the minimum bucket is valid.

_initialized

private boolean _initialized

_logMinNumBuckets

private int _logMinNumBuckets

_logNumberOfBuckets

private int _logNumberOfBuckets

_logQueueBinCountFactor

private int _logQueueBinCountFactor

_minimumEntry

private java.lang.Object _minimumEntry

_minVirtualBucket

private long _minVirtualBucket

_minBucket

private int _minBucket

_numberOfBuckets

private int _numberOfBuckets

_numberOfBucketsMask

private int _numberOfBucketsMask

_previousTakenEntry

private java.lang.Object _previousTakenEntry

_queueSize

private int _queueSize

_resizeEnabled

private boolean _resizeEnabled

_RESIZE_LAG

private static final int _RESIZE_LAG

See Also:

Constant Field Values

_SAMPLE_SIZE

private static final int _SAMPLE_SIZE

See Also:

Constant Field Values

_sampleEntries

private java.lang.Object[] _sampleEntries

_sampleEntryIndex

private int _sampleEntryIndex

_sampleValid

private boolean _sampleValid

_topThreshold

private int _topThreshold

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.

See Also:

removeDebugListener(ptolemy.kernel.util.DebugListener)

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.

log

public static int log(int value)

Return the power of two belonging to the least integer power of two larger than or equal to the specified integer. The return value is always between 0 and 31, inclusive.

Parameters:

value - The value for which to find the next power of 2.

Returns:

A number n such that 2ⁿ is greater than or equal to value.

Throws:

java.lang.ArithmeticException - If the specified value is not positive.

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.

See Also:

addDebugListener(ptolemy.kernel.util.DebugListener)

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.

_collect

private void _collect(java.lang.Object entry)

_debug

private final void _debug(java.lang.String message)

Send a debug message to all debug listeners that have registered. By convention, messages should not include a newline at the end. The newline will be added by the listener, if appropriate.

Parameters:

message - The message.

_getBinIndex

private int _getBinIndex(java.lang.Object entry)

_getFromBucket

private java.lang.Object _getFromBucket(int index)

Get the first entry from the specified bucket and return its contents.

_getIndexOfMinimumBucket

private int _getIndexOfMinimumBucket()

Get the index of the minimum bucket. The index is cached. When this method is invoked, this method first checks whether the queue has changed, if so, find a new index, otherwise, return the cached index.

Returns:

The index of the minimum bucket.

_localInit

private void _localInit(int logNumberOfBuckets,
                        java.lang.Object firstEntry)

_resize

private void _resize(boolean increasing)

_takeFromBucket

private java.lang.Object _takeFromBucket(int index)