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.
add
,remove
, andgetMin
(orgetMax
, depends on your queue) operations. \$\endgroup\$ – Ron Klein Oct 6 '19 at 11:18