public class CalendarQueue extends java.lang.Object implements Debuggable
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:
CQComparator
Yellow (liuj) 
Green (eal) 
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.

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.

public CalendarQueue(CQComparator comparator)
comparator
 The comparator used to sort entries.public CalendarQueue(CQComparator comparator, int minNumBuckets, int binCountFactor)
comparator
 The comparator used to sort entries.minNumBuckets
 The minimum number of buckets.binCountFactor
 The bin count factor.public void addDebugListener(DebugListener listener)
addDebugListener
in interface Debuggable
listener
 The listener to which to send debug messages.removeDebugListener(ptolemy.kernel.util.DebugListener)
public void clear()
public final java.lang.Object get() throws InvalidStateException
InvalidStateException
 If the queue is empty.public boolean includes(java.lang.Object entry)
entry
 The entry.public final boolean isEmpty()
public static int log(int value)
value
 The value for which to find the next power of 2.java.lang.ArithmeticException
 If the specified value is
not positive.public boolean put(java.lang.Object entry)
entry
 The entry to be added to the queue.java.lang.ClassCastException
 If the specified entry cannot
be compared by the associated comparator.public boolean remove(java.lang.Object entry)
entry
 The entry to remove.public void removeDebugListener(DebugListener listener)
removeDebugListener
in interface Debuggable
listener
 The listener to remove from the list of listeners
to which debug messages are sent.addDebugListener(ptolemy.kernel.util.DebugListener)
public void setAdaptive(boolean flag)
flag
 If false, disable changing the number of bins.public final int size()
public final java.lang.Object take() throws InvalidStateException
InvalidStateException
 If the queue is empty.public final java.lang.Object[] toArray()
public final java.lang.Object[] toArray(int limit)
limit
 The maximum number of entries desired.