|
||||||||||
| PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
| SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD | |||||||||
java.lang.Objectptolemy.actor.util.CalendarQueue
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:
CQComparator
| Yellow (liuj) |
| 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 |
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.| Method Detail |
public void addDebugListener(DebugListener listener)
addDebugListener in interface Debuggablelistener - The listener to which to send debug messages.public void clear()
CQComparator.setZeroReference(java.lang.Object)
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 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 Debuggablelistener - The listener to remove from the list of listeners
to which debug messages are sent.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.
|
||||||||||
| PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
| SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD | |||||||||