avalon-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Berin Loritsch <blorit...@apache.org>
Subject Re: [Excalibur] PriorityQueue & BinaryHeap proposal
Date Wed, 07 Nov 2001 14:54:24 GMT
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:avalon-dev-unsubscribe@jakarta.apache.org>
For additional commands, e-mail: <mailto:avalon-dev-help@jakarta.apache.org>

View raw message