I have this stable priority queue. It runs all the operations within \$\mathcal{O}(\log P)\$, where \$P\$ is the number of distinct priority keys (which may be smaller than the number of elements stored).
StablePriorityQueue.java
package net.coderodde.util;
import java.util.Comparator;
import java.util.HashMap;
import java.util.Map;
import java.util.NoSuchElementException;
import java.util.Objects;
import java.util.SortedMap;
import java.util.TreeMap;
public class StablePriorityQueue<E, P> {
private static final class ElementListNode<E, P> {
E element;
ElementListNode<E, P> next;
ElementListNode<E, P> prev;
ElementList<E, P> ownerList;
}
private static final class ElementList<E, P> {
P priority;
ElementListNode<E, P> head;
ElementListNode<E, P> tail;
void appendElementListNode(ElementListNode<E, P> elementListNode) {
if (head == null) {
head = elementListNode;
tail = elementListNode;
elementListNode.prev = null;
elementListNode.next = null;
} else {
tail.next = elementListNode;
elementListNode.prev = tail;
elementListNode.next = null;
tail = elementListNode;
}
}
E removeHead() {
E result = head.element;
head = head.next;
if (head != null) {
head.prev = null;
}
return result;
}
boolean isEmpty() {
return head == null;
}
}
/**
* Maps each distinct priority key to a linked list containing all the
* elements with that priority key in the FIFO-order (oldest entries are at
* the beginning of the list).
*/
private final SortedMap<P, ElementList<E, P>> priorityMap;
/**
* Maps each element in this queue to its holder element node.
*/
private final Map<E, ElementListNode<E, P>> elementMap = new HashMap<>();
public StablePriorityQueue(Comparator<? super P> comparator) {
Objects.requireNonNull(comparator, "The input comparator is null.");
this.priorityMap = new TreeMap<>(comparator);
}
/**
* If {@code element} is not present in this queue, adds it and associates
* it with priority key {@code priority}. Otherwise, it updates its
* priority. The updated priority may be smaller, equal or larger than the
* current priority.
*
* @param element the element to add.
* @param priority the element priority.
*/
public void add(E element, P priority) {
ElementListNode<E, P> elementListNode = elementMap.get(element);
if (elementListNode == null) {
addNewEntry(element, priority);
} else {
updateEntry(elementListNode, priority);
}
}
/**
* Returns the top element.
*
* @return the top element.
* @throws NoSuchElementException if the queue is empty.
*/
public E top() {
checkQueueNotEmpty();
return priorityMap.get(priorityMap.firstKey()).head.element;
}
/**
* Removes and returns the top element.
*
* @return the top element.
* @throws NoSuchElementException if the queue is empty.
*/
public E extractMinimum() {
checkQueueNotEmpty();
ElementList<E, P> elementList = priorityMap.get(priorityMap.firstKey());
E result = elementList.removeHead();
if (elementList.isEmpty()) {
priorityMap.remove(elementList.priority);
}
elementMap.remove(result);
return result;
}
public boolean isEmpty() {
return elementMap.isEmpty();
}
public int size() {
return elementMap.size();
}
public void clear() {
priorityMap.clear();
elementMap.clear();
}
private void addNewEntry(E element, P priority) {
ElementList<E, P> elementList = priorityMap.get(priority);
if (elementList == null) {
elementList = new ElementList<>();
elementList.priority = priority;
priorityMap.put(priority, elementList);
}
ElementListNode<E, P> elementListNode = new ElementListNode<>();
elementListNode.element = element;
elementListNode.ownerList = elementList;
elementList.appendElementListNode(elementListNode);
elementMap.put(element, elementListNode);
}
private void updateEntry(ElementListNode<E, P> elementListNode,
P newPriority) {
unlink(elementListNode);
relink(elementListNode, newPriority);
}
private void checkQueueNotEmpty() {
if (isEmpty()) {
throw new NoSuchElementException(
"Trying to read from an empty " +
getClass().getSimpleName());
}
}
private void unlink(ElementListNode<E, P> elementListNode) {
ElementList<E, P> elementList = elementListNode.ownerList;
if (elementListNode.prev != null) {
elementListNode.prev.next = elementListNode.next;
} else {
elementList.head = elementList.head.next;
if (elementList.head != null) {
elementList.head.prev = null;
}
}
if (elementListNode.next != null) {
elementListNode.next.prev = elementListNode.prev;
} else {
elementList.tail = elementList.tail.prev;
if (elementList.tail != null) {
elementList.tail.next = null;
}
}
if (elementList.isEmpty()) {
priorityMap.remove(elementList.priority);
}
}
private void relink(ElementListNode<E, P> elementListNode, P priority) {
ElementList<E, P> elementList = priorityMap.get(priority);
if (elementList == null) {
elementList = new ElementList<>();
elementList.priority = priority;
priorityMap.put(priority, elementList);
}
elementList.appendElementListNode(elementListNode);
}
}
StablePriorityQueueTest.java
package net.coderodde.util;
import java.util.Comparator;
import java.util.NoSuchElementException;
import org.junit.After;
import org.junit.AfterClass;
import org.junit.Before;
import org.junit.BeforeClass;
import org.junit.Test;
import static org.junit.Assert.*;
public class StablePriorityQueueTest {
private final StablePriorityQueue<String, Integer> queue;
public StablePriorityQueueTest() {
class IntegerComparator implements Comparator<Integer> {
@Override
public int compare(Integer o1, Integer o2) {
return Integer.compare(o1, o2);
}
}
this.queue = new StablePriorityQueue<>(new IntegerComparator());
}
@Before
public void before() {
this.queue.clear();
}
@Test
public void test1() {
queue.add("B", 2);
queue.add("C", 3);
queue.add("A", 1);
assertEquals("A", queue.extractMinimum());
assertEquals("B", queue.extractMinimum());
assertEquals("C", queue.extractMinimum());
}
@Test
public void test2() {
queue.add("A", 10);
queue.add("B", 10);
queue.add("C", 1);
assertEquals("C", queue.extractMinimum());
assertEquals("A", queue.extractMinimum());
assertEquals("B", queue.extractMinimum());
}
@Test
public void test3() {
queue.add("X", 10);
queue.add("Y", 10);
queue.add("Z", 10);
queue.add("Y", 9);
queue.add("X", 11);
assertEquals("Y", queue.extractMinimum());
assertEquals("Z", queue.extractMinimum());
assertEquals("X", queue.extractMinimum());
}
@Test(expected = NoSuchElementException.class)
public void testThrowsOnEmptyQueueWhenTop() {
queue.top();
}
@Test(expected = NoSuchElementException.class)
public void testThrowsOnEmptyQueueWhenExtractMinimum() {
queue.extractMinimum();
}
@Test
public void testSize() {
for (int i = 0; i < 10; ++i) {
assertEquals(i, queue.size());
queue.add("" + i, i);
assertEquals(i + 1, queue.size());
}
for (int i = 10; i > 0; --i) {
assertEquals(i, queue.size());
queue.extractMinimum();
assertEquals(i - 1, queue.size());
}
}
@Test
public void testIsEmpty() {
assertTrue(queue.isEmpty());
queue.add("A", 1);
assertFalse(queue.isEmpty());
queue.add("B", 2);
assertFalse(queue.isEmpty());
queue.extractMinimum();
assertFalse(queue.isEmpty());
queue.extractMinimum();
assertTrue(queue.isEmpty());
}
}
Critique request
Please tell me anything that comes to mind.
