1
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.