2
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ In terms of performance, IFAIK priority queue can be implemented in O(log(n)) for add, remove, and getMin (or getMax, depends on your queue) operations. \$\endgroup\$ – Ron Klein Oct 6 '19 at 11:18
  • \$\begingroup\$ @RonKlein I know: binary heap, d-ary heap, Fibonacci heap, binomial heap, Dial's heap, pairing heap. I have implemented all of those in one language or another. \$\endgroup\$ – coderodde Oct 6 '19 at 11:28
1
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.