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 69607 2014-07-30 17:07:26Z cxh $

Author:

Lukito Muliadi and Edward A. Lee

See Also:

CQComparator

Accepted Rating:
Yellow (liuj)

Proposed Rating:
Green (eal)

Constructor Summary

Constructors
Constructor and Description
`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

All Methods Static Methods Instance Methods Concrete Methods
Modifier and Type	Method and Description
`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

- 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.

Class CalendarQueue

Constructor Summary

Method Summary

Methods inherited from class java.lang.Object

Constructor Detail

CalendarQueue

CalendarQueue

Method Detail

addDebugListener

clear

get

includes

isEmpty

log

put

remove

removeDebugListener

setAdaptive

size

take

toArray

toArray