A simple priority queue in Java via linked list sorted by priority keys

Question

Now I have this very simple priority queue. add and changePriority both run in \$\mathcal{O}(n)\$ and extractMinimum in \$\Theta(1)\$:

net.coderodde.util.pq.PriorityQueue:

package net.coderodde.util.pq;

/**
 * This interface defines the API for priority queue data structures.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6 (Oct 3, 2019)
 * @param <E>
 * @param <P>
 * @since 1.6 (Oct 3, 2019)
 */
public interface PriorityQueue<E, P extends Comparable<? super P>> {

    /**
     * Attempts to add an element to this queue only if it is not yet present.
     * 
     * @return {@code true} if no duplicates are present and, thus, the element
     * is added to this priority queue. {@code false} is returned otherwise.
     */
    public boolean add(E element, P priority);

    /**
     * Changes the priority of the element.
     * 
     * @param element the target element.
     * @param priority the new priority for the element.
     * @return {@code true} if the priority of the target element changed. 
     * {@code false} otherwise.
     */
    public boolean changePriority(E element, P priority);

    /**
     * Removes and returns the element with the highest element.
     * 
     * @return the highest priority element.
     * @throws {@link java.lang.IllegalStateException} if the queue is empty.
     */
    public E extractMinimum();

    /**
     * Checks wether the parameter element is in this queue.
     * 
     * @return {@code true} if the input parameter is in this queue, 
     * {@code false} otherwise.
     */
    public boolean containsElement(E element);

    /**
     * The number of elements currently in the queue.
     */
    public int size();

    /**
     * Checks whether this queue is empty.
     * 
     * @return {@code true} only if this queue contains no elements.
     */
    public boolean isEmpty();

    /**
     * Clears this queue removing all the elements from the queue.
     */
    public void clear();
}

net.coderodde.util.pq.impl.SimplePriorityQueue:

package net.coderodde.util.pq.impl;

import java.util.ConcurrentModificationException;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.NoSuchElementException;
import net.coderodde.util.pq.PriorityQueue;

/**
 * This class implements a simple priority queue.The elements are ordered in a
 * linked list, the head node of which contains the highest priority element,
 * and the tail node contains the lowest priority element.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6 (Oct 3, 2019)
 * @param <E> the element type.
 * @param <P> the priority key type.
 * @since 1.6 (Oct 3, 2019)
 */
public final class SimplePriorityQueue<E, P extends Comparable<? super P>>
implements PriorityQueue<E, P>, Iterable<E> {

    @Override
    public Iterator<E> iterator() {
        return new SimplePriorityQueueIterator();
    }

    /**
     * This static inner class holds an element along with its priority.
     * 
     * @param <E> the element type.
     * @param <P> the priority key type.
     */
    private static final class Node<E, P> {
        E element;
        P priority;
        Node<E, P> next;
        Node<E, P> prev;

        Node(E element, P priority) {
            this.element = element;
            this.priority = priority;
        }

        E getElement() {
            return element;
        }

        P getPriority() {
            return priority;
        }

        void setPriority(P priority) {
            this.priority = priority;
        }

        Node<E, P> getNextNode() {
            return next;
        }

        Node<E, P> getPreviousNode() {
            return prev;
        }

        void setNextNode(Node<E, P> next) {
            this.next = next;
        }

        void setPreviousNode(Node<E, P> prev) {
            this.prev = prev;
        }
    }

    /**
     * Maps each element to the linked list node holding it.
     */
    private final Map<E, Node<E, P>> map = new HashMap<>();

    private Node<E, P> headNode = null;
    private Node<E, P> tailNode = null;
    private int size = 0;
    private int modCount = 0;

    /**
     * {@inheritDoc}
     */
    @Override
    public boolean containsElement(E element) {
        return map.containsKey(element);
    }

    /**
     * {@inheritDoc}
     */
    @Override
    public boolean add(E element, P priority) {
        if (map.containsKey(element)) {
            // Do not add the duplicates:
            return false;
        }

        Node<E, P> newNode = new Node<>(element, priority);

        if (headNode == null) {
            headNode = newNode;
            tailNode = newNode;
            size = 1;
            modCount++;
            map.put(element, newNode);
            return true;
        }

        insertNode(newNode);
        map.put(element, newNode);
        size++;
        modCount++;
        return true;
    }

    /**
     * {@inheritDoc}
     */
    @Override
    public boolean changePriority(E element, P priority) {
        if (!map.containsKey(element)) {
            return false;
        }

        Node<E, P> node = map.get(element);
        node.setPriority(priority);
        unlinkNode(node);
        insertNode(node);
        return true;
    }

    /**
     * {@inheritDoc}
     */
    @Override
    public E extractMinimum() {
        if (size == 0) {
            throw new NoSuchElementException("Extracting from an empty queue.");
        }

        Node<E, P> topPriorityNode = headNode;
        headNode = headNode.getNextNode();

        if (headNode == null) {
            tailNode = null;
            size = 0;
        } else {
            headNode.setPreviousNode(null);
            size--;
        }

        map.remove(topPriorityNode.getElement());
        modCount++;
        return topPriorityNode.getElement();
    }

    /**
     * {@inheritDoc}
     */
    @Override
    public int size() {
        return size;
    }

    /**
     * {@inheritDoc}
     */
    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    /**
     * {@inheritDoc}
     */
    @Override
    public void clear() {
        size = 0;
        modCount++;
        map.clear();
    }

    /**
     * Inserts the given node to its correct location. 
     */
    private void insertNode(Node<E, P> node) {
        Node<E, P> currentNode = headNode;

        // Comparator operator <= instead of < guarantees stability:
        while (currentNode != null 
                && currentNode.priority.compareTo(node.getPriority()) <= 0) {
            currentNode = currentNode.getNextNode();
        }

        if (currentNode == null) {
            tailNode.setNextNode(node);
            node.setPreviousNode(tailNode);
            tailNode = node;
        } else if (currentNode.getPreviousNode() == null) {
            // The priority of the new element is smaller than the minimum 
            // priority throughout the queue:
            headNode.setPreviousNode(node);
            node.setNextNode(headNode);
            headNode = node;
        } else {
            node.setNextNode(currentNode);
            node.setPreviousNode(currentNode.getPreviousNode());
            currentNode.setPreviousNode(node);
            node.getPreviousNode().setNextNode(node);
        }
    }

    /**
     * Unlinks the parameter node from the linked list.
     */
    private void unlinkNode(Node<E, P> node) {
        if (node.getPreviousNode() != null) {
            node.getPreviousNode().setNextNode(node.getNextNode());
        } else {
            headNode = node.getNextNode();
        }

        if (node.getNextNode() != null) {
            node.getNextNode().setPreviousNode(node.getPreviousNode());
        } else {
            tailNode = node.getPreviousNode();
        }
    }

    /**
     * This inner class implements an iterator over the priority queue.
     */
    private final class SimplePriorityQueueIterator implements Iterator<E> {

        private Node<E, P> node = headNode;
        private final int expectedModCount = SimplePriorityQueue.this.modCount;

        @Override
        public boolean hasNext() {
            checkComodification();

            return node != null;
        }

        @Override
        public E next() {
            checkComodification();

            if (!hasNext()) {
                throw new NoSuchElementException();
            }

            E returnValue = node.getElement();
            node = node.getNextNode();
            return returnValue;
        }

        private void checkComodification() {
            if (expectedModCount != SimplePriorityQueue.this.modCount) {
                throw new ConcurrentModificationException(
                "Expected modification count: " + expectedModCount + ", " +
                "actual modification count: " + 
                        SimplePriorityQueue.this.modCount);
            }
        }
    }
}

net.coderodde.util.pq.impl.SimplePriorityQueueTest:

package net.coderodde.util.pq.impl;

import java.util.Iterator;
import org.junit.Before;
import org.junit.Test;
import static org.junit.Assert.*;

public class SimplePriorityQueueTest {

    private SimplePriorityQueue<Integer, Integer> queue;

    @Before
    public void setUp() {
        queue = new SimplePriorityQueue<>();
    }

    @Test
    public void testIterator() {
        queue.add(1, 1);
        queue.add(4, 4);
        queue.add(3, 3);
        queue.add(2, 2);

        Iterator<Integer> iter = queue.iterator();

        assertTrue(iter.hasNext());
        assertEquals((Integer) 1, iter.next());

        assertTrue(iter.hasNext());
        assertEquals((Integer) 2, iter.next());

        assertTrue(iter.hasNext());
        assertEquals((Integer) 3, iter.next());

        assertTrue(iter.hasNext());
        assertEquals((Integer) 4, iter.next());
        // Arrived to the end of the queue:
        assertFalse(iter.hasNext());
    }

    @Test
    public void testContainsElement() {
        assertFalse(queue.containsElement(100));
        assertFalse(queue.containsElement(90));
        assertFalse(queue.containsElement(80));

        queue.add(100, 100);
        queue.add(80, 80);
        queue.add(90, 90);

        assertTrue(queue.containsElement(100));
        assertTrue(queue.containsElement(90));
        assertTrue(queue.containsElement(80));
        assertFalse(queue.containsElement(70));
        assertFalse(queue.containsElement(60));
    }

    @Test
    public void testAdd() {
        assertFalse(queue.containsElement(3));
        queue.add(3, 3);
        assertTrue(queue.containsElement(3));

        assertFalse(queue.containsElement(2));
        queue.add(2, 2);
        assertTrue(queue.containsElement(2));

        assertFalse(queue.containsElement(4));
        queue.add(4, 4);
        assertTrue(queue.containsElement(4));
    }

    @Test
    public void testChangePriority() {
        for (int i = 0; i < 10; i++) {
            queue.add(i, i);
        }

        queue.changePriority(5, -1);
        assertEquals((Integer) 5, queue.extractMinimum());
        assertEquals((Integer) 0, queue.extractMinimum());

        queue.changePriority(1, 100);

        assertEquals((Integer) 2, queue.extractMinimum());
        assertEquals((Integer) 3, queue.extractMinimum());
        assertEquals((Integer) 4, queue.extractMinimum());
        assertEquals((Integer) 6, queue.extractMinimum());
        assertEquals((Integer) 7, queue.extractMinimum());
        assertEquals((Integer) 8, queue.extractMinimum());
        assertEquals((Integer) 9, queue.extractMinimum());
        assertEquals((Integer) 1, queue.extractMinimum());
    }

    @Test
    public void testExtractMinimum() {
        queue.add(5, 5);
        queue.add(3, 3);
        queue.add(4, 4);
        queue.add(7, 7);
        queue.add(6, 6);

        for (int i = 3; i <= 7; i++) {
            assertEquals((Integer) i, queue.extractMinimum());
        }

        // Is the queue stable?
        queue.add(2, 1);
        queue.add(3, 1);
        queue.add(1, 1);

        assertEquals((Integer) 2, queue.extractMinimum());
        assertEquals((Integer) 3, queue.extractMinimum());
        assertEquals((Integer) 1, 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());
        }
    }

    @Test
    public void testIsEmpty() {
        assertTrue(queue.isEmpty());

        queue.add(2, 2);

        assertFalse(queue.isEmpty());

        queue.add(1, 1);

        assertFalse(queue.isEmpty());
    }

    @Test
    public void testClear() {
        queue.clear(); // No-op.

        assertTrue(queue.isEmpty());

        for (int i = 0; i < 5; i++) {
            queue.add(i, i);
            assertFalse(queue.isEmpty());
        }

        queue.clear();
        assertTrue(queue.isEmpty());
    }    
}

Critique request

I would like to hear comments on test coverage, coding style, maintainability and readability, to name a few. Thank you in advance.

Answer 1

Small issue

    if (!map.containsKey(element)) {
        return false;
    }

    Node<E, P> node = map.get(element);

You can simply write Node<E, P> node = map.get(element); and check if node is null. This increases performance and atomicity.

Design issue

I think you could improve readability if you split the implementation to a Doubly-Linked-List ("DLL") inside the priority queue.

This way, you could have the following code encapsulated in your DLL

    // Comparator operator <= instead of < guarantees stability:
    while (currentNode != null 
            && currentNode.priority.compareTo(node.getPriority()) <= 0) {
        currentNode = currentNode.getNextNode();
    }

You could gain a better separation of concerns. Tests could also improve this way.

Small implementation issue

As for your implementation of the DLL, perhaps you could consider using a sentinel rather than check for null for the head/tail operations.