On Thu, 8 Nov 2001 01:54, Berin Loritsch wrote:
> 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.
It is not using "Stack semantics and idioms" but PriorityQueue semantics and
idioms. I guess everyone uses insert() rather than push() because push() has
idea of LIFO which is wrong.
> 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.
err I know what a stack is and a queue ... however we are talking about a
*priority* queue here. Basically when you insert something into construct it
will be sorted based on its "priority" relative to other elements. If you
insert the values "5 4 3 2 1" it will act as a stack and if you insert "1
2 3 4 5" it will act as your FIFO queue. But I don't know why you are talking
about LIFO/FIFO as they have little relevence to priority based queues.
Another term for Priority Queues is "Heap"s. That may make things clearer.
> interface Queue {
> void push(Object obj);
> Object pop();
> Object peek();
> void clear();
> }
>
> interface PriorityQueue extends Queue {
> void control(Controller control);
> }
-1
Queue != PriorityQueue and PriorityQueue's traditional interface does not use
push() (for better or worse).
If anything I would rename PriorityQueue.pop() to remove() (as that is what
it really should be). However I chose to keep pop() as thats what they use in
textbooks.
>
> interface Controller {
> void setComparator(Comparator comp);
> int getNextObjectRef();
> void addObjectRef();
> }
seems far more complicated than is really necessary. I can't even fathom why
you would choose to use such an interface.
> If this is not the set of issues the current PriorityQueue was designed to
> handle, then it was probably poorly named....
PriorityQueue was designed as interface to a ... PriorityQueue. It is a very
text-book interface (and BinaryHeap is simplest text book impl about). If you
have issues on naming you should talk with the people who write Computer
Science textbooks ;)
--
Cheers,
Pete
*---------------------------------------------------------*
| Programming today is a race between software engineers |
| striving to build bigger and better idiot-proof |
| programs,and the universe trying to produce bigger and |
| better idiots. So far, the universe is winning. |
| - Richard Cook |
*---------------------------------------------------------*
--
To unsubscribe, e-mail: <mailto:[EMAIL PROTECTED]>
For additional commands, e-mail: <mailto:[EMAIL PROTECTED]>
