5 Replies Latest reply: Nov 17, 2010 2:32 PM by DMF RSS

    FIFO behavior with a PriorityQueue?

    DMF
      What I want is FIFI behavior within a priority. In other words, a poll() would get the first (chronological) element of all those with the highest priority. I've developed a set of classes based on PriorityQueue to do it, but IMO the solution is anything but elegant. I'll show it if anyone is interested; it involves a dedicated ordering field in each element. (Specification of PriorityQueue is that ordering ties are broken randomly.)

      The question is, has a better programmer developed a better solution? (Or a good programmer a good solution?)
        • 1. Re: FIFO behavior with a PriorityQueue?
          EJP
          You just need a Comparator that uses insertion sequence as the minor key, and (obviously) an insertion sequence (or time) field in the objects being queued.
          • 2. Re: FIFO behavior with a PriorityQueue?
            796440
            DMF wrote:
            What I want is FIFI behavior within a priority. In other words, a poll() would get the first (chronological) element of all those with the highest priority. I've developed a set of classes based on PriorityQueue to do it, but IMO the solution is anything but elegant. I'll show it if anyone is interested; it involves a dedicated ordering field in each element.
            I don't necessarily see a problem with that. I've done exactly the same thing. There are a handful of message types I enqueue, and, while I added a sequence number to those types specifically to solve this problem, it's not unreasonable for those sequence numbers to be there in general, as ordering the messages that way can be useful elsewhere.

            If you want a more general solution that doesn't require you mucking about with the internals of the enqueued objects, just create a simple wrapper class that adds a sequence number and use a comparator that uses the wrapped object's priority first ant the wrapper's sequence number as the tiebreaker.
            • 3. Re: FIFO behavior with a PriorityQueue?
              DMF
              Sometimes I get my best design ideas after completing the implementation. This morning I got two. I'll talk about what I have first:
              public class OrderedPriorityQueue<T extends OpqOrderable<T>> extends PriorityQueue<T> { 
              ... }
              
              public interface OpqOrderable<T> extends Comparable<T> {
                   int getOrder();
                   void setOrder( int order );
              }
              I don't like exposing the order attribute so someone can muck about with it, as you say. But there's also a problem with making it part of the element: if a user adds the element to a second OPQ, order is corrupted. To guard against that, OPQ could refuse to accept an OpqOrderable with a non-zero order attribute. But then you have to zero the attribute every time an element is removed, which, in the case of remove(Object), may not be possible.

              Anyway, my first morning idea is (I think) the one you suggested - the PriorityQueue element would be a private wrapper class on which the ordering attribute is defined. Then an object occupying two queues is not a problem, and the 'real' element need only implement Comparable.

              The second idea might be too cute for its own good. If the values of priority are known and a comparator provided, OrderedPriorityQueue could mimic the desired behavior by maintaining a FIFO collection for each priority value and return elements from its set of collections in priority order. If the set of Priorities is an Enum, it could be passed in at construction and then the OPQ element need not implement even Comparable.

              Both have merit and both seem to be superior to my first cut. They are worth exploring.
              • 4. Re: FIFO behavior with a PriorityQueue?
                doremifasollatido
                DMF wrote:
                The second idea might be too cute for its own good. If the values of priority are known and a comparator provided, OrderedPriorityQueue could mimic the desired behavior by maintaining a FIFO collection for each priority value and return elements from its set of collections in priority order. If the set of Priorities is an Enum, it could be passed in at construction and then the OPQ element need not implement even Comparable.
                Our code at work has something similar to what you describe here--a "queue" class that contains a FIFO collection for each priority value, and then the "get" method returns the first item from the highest priority that has any items on it. It doesn't implement java.util.Queue (so, you can't swap it out for any other Queue), but it does the basic things you need for a queue. Underneath, there is a map of lists keyed by priority (e.g., "Map<PriorityLevel, List>"). The concept does work--but note that your "add" method has to allow the user to specify the priority for the new object, since the objects don't have to be "Comparable". The code has been around for a while (long before I was), but I recently abandoned it for the standard PriorityBlockingQueue (to get the blocking capability without figuring it out myself). Note that if you implement your own class, you are responsible for proper synchronization of the queue.


                Note that the Javadoc for PriorityBlockingQueue gives an example FIFOEntry class whose compareTo method sorts first by priority and then by insertion order:
                http://download.oracle.com/javase/6/docs/api/java/util/concurrent/PriorityBlockingQueue.html
                • 5. Re: FIFO behavior with a PriorityQueue?
                  DMF
                  Hey, thanks for the pointer. I don't need a blocking queue so I didn't look at that variation. The FIFOEntry class looks strangely familiar ;) I think I wrote its brother yesterday while implementing the private wrapper class alternative. In retrospect, making the wrapper (and the PriorityQueue) private and implementing Queue is more of an effort than I originally estimated. Making Wrapper a top-level class would have been the better part of valor.

                  And this here AtomicLong class is new to me. I think I like it already!