Berin -
PriorityQueue is the commonly used name for this type of functionality
(almost always being implemented using a BinaryHeap). You'll see this
terminology used everywhere (in the C++ STL, in the ObjectSpace JGL, and
most textbooks I've read). See
http://hissa.nist.gov/dads/HTML/priorityque.html.
You seem to be describing some sort of probablistic scheduler, which
involves a random component and is therefore not deterministic. A
PriorityQueue's behavior is deterministic given a certain set of data, and
is very important for this to be the case. Basically a PriorityQueue's
'top' method is always guaranteed to give you the 'max' value for that given
dataset (and if you use a BinaryHeap it will do so in O(1)).
Chad
----- Original Message -----
From: "Berin Loritsch" <[EMAIL PROTECTED]>
To: "Avalon Developers List" <avalon-dev@jakarta.apache.org>
Sent: Wednesday, November 07, 2001 7:54 AM
Subject: Re: [Excalibur] PriorityQueue & BinaryHeap proposal
> Chad Stansbury wrote:
> >
> > Okay - here's the problem. The current BinaryHeap interface expects a
> > Comparable for it's public interface. In order to maintain backwards
> > compatibility I must either:
> >
> > 1. Add new public methods to the BinaryHeap class (e.g., insertObject,
> > peekObject, popObject) and change the insert, peek, and pop methods to
> > invoke these new methods, or
> > 2. I can create a new BinaryObjectHeap class and have the BinaryHeap
class
> > act as a wrapper class.
> >
> > I am also wondering how I would modify the PriorityQueue interface w/o
> > breaking backwards compatibility...
> >
> > Any suggestions would be appreciated.
>
> Peter, could you give a quick overview of how it is supposed to work?
> BTW, I don't like the insert() when you have pop() and peek(). If you
> are going to use Stack semantics and idioms, then use push() for the
> same purpose.
>
> If we are dealing with a queue, that is primarily a FIFO implementation
> (IOW merely a buffer). That means that if you push the following into
> the queue:
>
> 1 2 3 4 5
>
> You pop the information out of the queue in this order:
>
> 1 2 3 4 5
>
> A Stack works in the opposite direction. In other words, it is a LIFO
> implementation (Last In First Out). So if you push the same information
> on to the Stack, you pop the information out in this order:
>
> 5 4 3 2 1
>
> This is useful in situations where you have to keep track of return
> adresses or hierarchy in configurations, etc.
>
> The Priority Queue should be something like the original FIFO (First In
> First Out) buffer, BUT based on a Controller, the _proportion_ of
priorities
> popped out of the Queue depends on the Controller.
>
> For instance, if we have a group of objects that all implement a
getUserType()
> the Comparitor/Controller would test the User Type. The Controller
decides
> if the user is a PRIORITY_USER or a REGULAR_USER. The proportion of
PRIORITY_USER
> objects to REGULAR_USERs is 60% to 40% then the queue would pop them
accordingly.
>
> That means we should have a reqular Queue (FIFO buffer--can be used for
interface
> of persistent Queue to guarantee delivery of messages...). We should also
have
> a PriorityQueue with a Controller, and the Controller with a Comparator.
The
> Controller decides how the objects are moved through (i.e. proportions,
etc.)
> and the Comparator helps the Controller decide what the Objects are.
>
> With that goal in mind, that would change the interfaces to be like this:
>
> interface Queue {
> void push(Object obj);
> Object pop();
> Object peek();
> void clear();
> }
>
> interface PriorityQueue extends Queue {
> void control(Controller control);
> }
>
> interface Controller {
> void setComparator(Comparator comp);
> int getNextObjectRef();
> void addObjectRef();
> }
>
> The Comparator is in java.util.Comparator
>
>
> Not on the Controller, the API for the ObjectRefs can be played with, but
it is
> simply a way of letting the Controller know what is in the Queue, and a
way for
> the Queue to ask the controller what it next to come out.
>
>
> If this is not the set of issues the current PriorityQueue was designed to
handle,
> then it was probably poorly named....
>
>
> --
>
> "Those who would trade liberty for
> temporary security deserve neither"
> - Benjamin Franklin
>
> --
> To unsubscribe, e-mail:
<mailto:[EMAIL PROTECTED]>
> For additional commands, e-mail:
<mailto:[EMAIL PROTECTED]>
>
--
To unsubscribe, e-mail: <mailto:[EMAIL PROTECTED]>
For additional commands, e-mail: <mailto:[EMAIL PROTECTED]>
