Making a Java PriorityQueue into a stable priority queue

Question

I'm trying to implement a stable (first in first out) priority queue in Java. Supposing that the key is a name and the value is an age, I know I can make an unstable priority queue like this:

Queue<Map.Entry<String, Integer>> pq = new PriorityQueue<Map.Entry<String, Integer>>(100, ageComparator);

This does pretty much everything that I need it to, except that it doesn't maintain order of key-value pairs as I insert them (or remove them).

I've found a "work around" by making a LinkedList, which offers essentially all of the same functionality, except that it doesn't include a constructor with a comparator option, and I feel that it must be slower since I maintain value ordering by calling Collections.sort() after each queue operation.

So I guess that really there are two options that I'm interested in. First, how could I edit the PriorityQueue above to maintain insertion and removal order? Or second, how could I force my LinkedList option to use a comparator immediately rather than having to call a sort on each operation? Thanks!

EDIT:

Thanks for the good question in the first comment that was posted. By FIFO, I mean that for key-value pairs with equal values, the pair which is put in first should be extracted first.

Answer 1

You need something like this:

import java.util.AbstractMap;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.concurrent.atomic.AtomicInteger;

public class PriorityTest {
  @SuppressWarnings("serial")
  private static class Entry extends AbstractMap.SimpleEntry<String, Integer> {
    private final static AtomicInteger seq = new AtomicInteger(0);
    final int order;
    public Entry(final String _key, final Integer _value) {
      super(_key, _value);
      order = seq.incrementAndGet();
    }
  }

  private static class OrderedComparator implements Comparator<Entry> {
    @Override
    public int compare(final Entry _e1, final Entry _e2) {
      int r = _e1.getValue().compareTo(_e2.getValue());
      if (r == 0)
        return Integer.compare(_e1.order, _e2.order);
      return r;
    }
  }

  public static void main(String[] args) {
    final PriorityQueue<Entry> pq = new PriorityQueue<Entry>(10, new OrderedComparator());
    pq.add(new Entry("Jane", 22));
    pq.add(new Entry("John", 15));
    pq.add(new Entry("Bill", 45));
    pq.add(new Entry("Bob", 22));
    while(!pq.isEmpty()) {
      System.out.println(pq.remove());
    }
  }
}

Answer 2

Keap-based PriorityQueue is naturally stable. It's written in Kotlin, so it can replace java.util.PriorityQueue in Java code.

Answer 3

Very simple implementation based on multiple lists and TreeMap I've done today to solve some task:

import javax.annotation.Nonnull;
import java.util.*;
import java.util.Map.Entry;
import java.util.function.Function;

public class PriorityFifo<E> {

     protected TreeMap<Integer, LinkedList<E>> storage = new TreeMap<>();

     public void push(E element, int priority) {
        storage.computeIfAbsent(priority, it -> new LinkedList<>()).addLast(element);
     }

     public Optional<E> poll() {
        return doWithNextElement(LinkedList::pollFirst);
     }

     public Optional<E> peek() {
        return doWithNextElement(LinkedList::getFirst);
     }

     protected Optional<E> doWithNextElement(@Nonnull Function<LinkedList<E>, E> f) {
         Entry<Integer, LinkedList<E>> entry = storage.firstEntry();
         if (entry==null)
             return Optional.empty();
         LinkedList<E> list = entry.getValue();
         E element = f.apply(list);
         if (list.isEmpty())
             storage.remove(entry.getKey());
         return Optional.of(Objects.requireNonNull(element));

     }

}

No comparator used for elements, but used internally by TreeMap for queues. My case is that I have only a few of priorities, but a lot of elements, so it should go faster than something using element comparison.