package com.github.coderodde.util;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.NoSuchElementException;
/**
* This class implements a priority queue data structure called a Dial's heap.
*
* @param <D> the type of the satellite data.
*
* @version 1.0.0 (May 10, 2024)
* @since 1.0.0
*/
public class DialsHeap<D> implements IntegerMinimumPriorityQueue<D> {
/**
* This static inner class implements the node type for this heap.
*
* @param <D> the satellite data type.
*/
private static final class DialsHeapNode<D> {
/**
* The actual satellite datum.
*/
final D datum;
/**
* The priority key of this node. Must be at least zero (0).
*/
int priority;
/**
* The previous node in the collision chain or {@code null} if this node
* is the head of the collision chain.
*/
DialsHeapNode<D> prev;
/**
* The next node in the collision chain or {@code null} if this node is
* the tail of the collision chain.
*/
DialsHeapNode<D> next;
/**
* Constructs a new heap node.'
*
* @param datum the satellite datum.
* @param priority the priority key.
*/
DialsHeapNode(final D datum, final int priority) {
this.datum = datum;
this.priority = priority;
}
}
/**
* This inner class implements the iterator over all satellite data in this
* heap in the ascending priority key order.
*/
private final class DialsHeapIterator implements Iterator<D> {
/**
* Caches the number of nodes already iterated.
*/
private int iterated = 0;
/**
* The current heap node.
*/
private DialsHeapNode<D> currentDialsHeapNode;
/**
* Constructs a new iterator over the enclosing heap.
*/
private DialsHeapIterator() {
// Attempt to find the head node:
for (final DialsHeapNode<D> headNode : table) {
if (headNode != null) {
currentDialsHeapNode = headNode;
return;
}
}
// Once here, the heap is empty, return null:
currentDialsHeapNode = null;
}
/**
* {@inheritDoc }
*/
@Override
public boolean hasNext() {
return iterated < size;
}
/**
* {@inheritDoc}
*/
@Override
public D next() {
if (!hasNext()) {
throw new NoSuchElementException("Nothing to iterate left.");
}
final D returnElement = currentDialsHeapNode.datum;
iterated++;
currentDialsHeapNode = computeNextDialsHeapNode();
return returnElement;
}
/**
* Returns the next heap node.
*
* @return the next heap node in the iteration order.
*/
private DialsHeapNode<D> computeNextDialsHeapNode() {
if (iterated == size) {
// Once here, iteration is complete.
return null;
}
if (currentDialsHeapNode.next != null) {
// currentDialsHeapNode has minimum priority key, move to its
// right sibling/neighbor in the collision chain:
return currentDialsHeapNode.next;
}
// Search the next smallest priority node:
for (int p = currentDialsHeapNode.priority + 1;
p < table.length;
p++) {
if (table[p] != null) {
// Found!
return table[p];
}
}
// We should never ever get here.
throw new IllegalStateException("Should not get here.");
}
}
/**
* The default table capacity.
*/
private static final int DEFAULT_TABLE_CAPACITY = 8;
/**
* The table mapping each slot to the head of a collision chain.
*/
private DialsHeapNode<D>[] table;
/**
* The map mapping the satellite datums to their respective heap nodes.
*/
private final Map<D, DialsHeapNode<D>> nodeMap = new HashMap<>();
/**
* Caches the number of satellite datums in this heap.
*/
private int size = 0;
/**
* Constructs a heap with {@code tableCapacity} as the capacity of the
* internal collision chain table.
*
* @param tableCapacity the requested collision chain capacity.
*/
public DialsHeap(final int tableCapacity) {
this.table = new DialsHeapNode[tableCapacity];
}
/**
* Constructs a heap0 with default collision chain table capacity.
*/
public DialsHeap() {
this(DEFAULT_TABLE_CAPACITY);
}
/**
* {@inheritDoc }
*/
@Override
public Iterator<D> iterator() {
return new DialsHeapIterator();
}
/**
* {@inheritDoc}
*/
@Override
public void insert(final D datum, final int priority) {
if (nodeMap.containsKey(datum)) {
// Once here, the input datum is already in this heap. Use
// updatePriority for adjusting the priority key.
return;
}
checkPriority(priority);
if (mustExpand(priority)) {
expand(priority);
}
final DialsHeapNode<D> newTreeHeapNode =
new DialsHeapNode<>(datum, priority);
nodeMap.put(datum, newTreeHeapNode);
linkImpl(newTreeHeapNode, priority);
size++;
}
/**
* {@inheritDoc}
*/
@Override
public void updatePriority(final D datum, final int priority) {
if (mustExpand(priority)) {
expand(priority);
}
final DialsHeapNode<D> node = nodeMap.get(datum);
unlinkImpl(node);
linkImpl(node, priority);
node.priority = priority;
}
/**
* {@inheritDoc}
*/
@Override
public int minimumPriority() {
return accessMinimumPriorityNode().priority;
}
/**
* {@inheritDoc}
*/
@Override
public D minimumNode() {
if (size == 0) {
return null;
}
return accessMinimumPriorityNode().datum;
}
/**
* {@inheritDoc}
*/
@Override
public boolean containsDatum(final D datum) {
return nodeMap.containsKey(datum);
}
/**
* {@inheritDoc}
*/
@Override
public int getPriority(final D datum) {
return nodeMap.get(datum).priority;
}
/**
* {@inheritDoc}
*/
@Override
public D extractMinimum() {
if (size == 0) {
return null;
}
final DialsHeapNode<D> treeNode = accessMinimumPriorityNode();
unlinkImpl(treeNode);
nodeMap.remove(treeNode.datum);
size--;
return treeNode.datum;
}
/**
* {@inheritDoc}
*/
@Override
public void remove(final D datum) {
unlinkImpl(nodeMap.get(datum));
size--;
}
/**
* {@inheritDoc}
*/
@Override
public void clear() {
size = 0;
nodeMap.clear();
Arrays.fill(table, null);
}
/**
* {@inheritDoc}
*/
@Override
public Object clone() {
final int maximumPriorityKey = getMaximumPriority();
final int cloneCapacity = getNextCapacity(maximumPriorityKey);
final DialsHeap<D> copy = new DialsHeap<>(cloneCapacity);
for (final Map.Entry<D, DialsHeapNode<D>> entry : nodeMap.entrySet()) {
copy.insert(entry.getValue().datum, entry.getValue().priority);
}
return copy;
}
/**
* {@inheritDoc}
*/
@Override
public int size() {
return size;
}
/**
* Returns the head of the collision chain with the lowest priority key.
*
* @return the head of the collision chain with the lowest priority key.
*/
private DialsHeapNode<D> accessMinimumPriorityNode() {
for (int p = 0; p != table.length; p++) {
if (table[p] != null) {
return table[p];
}
}
throw new IllegalStateException("Should not get here.");
}
/**
* Links the node {@code node} to the head of the collision chain with
* priority key {@code priority}.
*
* @param node the node to link.
* @param priority the priority key to link with.
*/
private void linkImpl(final DialsHeapNode<D> node, final int priority) {
final DialsHeapNode<D> currentBucketHead = table[priority];
if (currentBucketHead != null) {
node.next = currentBucketHead;
currentBucketHead.prev = node;
}
table[priority] = node;
}
/**
* Unlinks the node {@code node} from this heap.
*
* @param node the node to unlink.
*/
private void unlinkImpl(final DialsHeapNode<D> node) {
if (node.prev != null) {
node.prev.next = node.next;
node.prev = null;
if (node.next != null) {
node.next.prev = node.prev;
node.next = null;
}
} else {
// Once here, node.prev == null!
if (node.next != null) {
node.next.prev = null;
table[node.priority] = node.next;
node.next = null;
} else {
// Remove the last node in the collision chain:
table[node.priority] = null;
}
}
}
/**
* Returns {@code true} if this heap's table cannot accommodate a node with
* priority {@code priority}.
*
* @param priority the priority to query.
*
* @return {@code true} if the table must be expanded.
*/
private boolean mustExpand(final int priority) {
return priority >= table.length;
}
/**
* Expands the internal table {@code table} such that it can accommodate the
* priority key {@code priority}, while being smallest such table.
*
* @param priority the requested priority key.
*/
private void expand(final int priority) {
final int nextCapacity = getNextCapacity(priority);
this.table = Arrays.copyOf(table, nextCapacity);
}
/**
* Returns the capacity that is sufficiently large in order to accommodate
* the heap nodes with priority {@code priority}.
*
* @param priority the requested priority.
*
* @return the next capacity to expand with.
*/
private int getNextCapacity(final int priority) {
int nextCapacity = table.length;
while (nextCapacity <= priority) {
nextCapacity *= 2;
}
return nextCapacity;
}
/**
* Returns the maximum priority key in this heap.
*
* @return the maximum priority key in this heap.
*/
private int getMaximumPriority() {
for (int priority = table.length - 1; priority >= 0; priority--) {
if (table[priority] != null) {
return priority;
}
}
return -1;
}
/**
* Makes sure that the input priority is non-negative.
*
* @param priority the priority to check.
*
* @throws IllegalArgumentException if the input priority is negative.
*/
private void checkPriority(final int priority) {
if (priority < 0) {
throw new IllegalArgumentException(
String.format(
"The input priority is negtive (%d).\n",
priority));
}
}
}
import java.util.Arrays;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.NoSuchElementException;
/**
* This class implements a priority queue data structure called a Dial's heap.
*
* @param <D> the type of the satellite data.
*
* @version 1.0.1 (May 12, 2024)
* @since 1.0.0 (May 10, 2024)
*/
public class DialsHeap<D> implements IntegerMinimumPriorityQueue<D> {
/**
* This static inner class implements the node type for this heap.
*
* @param <D> the satellite data type.
*/
private static final class DialsHeapNode<D> {
/**
* The actual satellite datum.
*/
final D datum;
/**
* The priority key of this node. Must be at least zero (0).
*/
int priority;
/**
* The previous node in the collision chain or {@code null} if this node
* is the head of the collision chain.
*/
DialsHeapNode<D> prev;
/**
* The next node in the collision chain or {@code null} if this node is
* the tail of the collision chain.
*/
DialsHeapNode<D> next;
/**
* Constructs a new heap node.'
*
* @param datum the satellite datum.
* @param priority the priority key.
*/
DialsHeapNode(final D datum, final int priority) {
this.datum = datum;
this.priority = priority;
}
}
/**
* This inner class implements the iterator over all satellite data in this
* heap in the ascending priority key order.
*/
private final class DialsHeapIterator implements Iterator<D> {
/**
* Caches the number of nodes already iterated.
*/
private int iterated = 0;
/**
* The current heap node.
*/
private DialsHeapNode<D> currentDialsHeapNode;
/**
* Constructs a new iterator over the enclosing heap.
*/
private DialsHeapIterator() {
// Attempt to find the head node:
for (final DialsHeapNode<D> headNode : table) {
if (headNode != null) {
currentDialsHeapNode = headNode;
return;
}
}
// Once here, the heap is empty, return null:
currentDialsHeapNode = null;
}
/**
* {@inheritDoc }
*/
@Override
public boolean hasNext() {
return iterated < nodeMap.size();
}
/**
* {@inheritDoc}
*/
@Override
public D next() {
if (!hasNext()) {
throw new NoSuchElementException("Nothing to iterate left.");
}
final D returnElement = currentDialsHeapNode.datum;
iterated++;
currentDialsHeapNode = computeNextDialsHeapNode();
return returnElement;
}
/**
* Returns the next heap node.
*
* @return the next heap node in the iteration order.
*/
private DialsHeapNode<D> computeNextDialsHeapNode() {
if (iterated == nodeMap.size()) {
// Once here, iteration is complete.
return null;
}
if (currentDialsHeapNode.next != null) {
// currentDialsHeapNode has minimum priority key, move to its
// right sibling/neighbor in the collision chain:
return currentDialsHeapNode.next;
}
// Search the next smallest priority node:
for (int p = currentDialsHeapNode.priority + 1;
p < table.length;
p++) {
if (table[p] != null) {
// Found!
return table[p];
}
}
// We should never ever get here.
throw new IllegalStateException("Should not get here.");
}
}
/**
* The default table capacity.
*/
private static final int DEFAULT_TABLE_CAPACITY = 8;
/**
* The table mapping each slot to the head of a collision chain.
*/
private DialsHeapNode<D>[] table;
/**
* The map mapping the satellite datums to their respective heap nodes.
*/
private final Map<D, DialsHeapNode<D>> nodeMap = new HashMap<>();
/**
* Constructs a heap with {@code tableCapacity} as the capacity of the
* internal collision chain table.
*
* @param tableCapacity the requested collision chain capacity.
*/
public DialsHeap(final int tableCapacity) {
this.table = new DialsHeapNode[tableCapacity];
}
/**
* Constructs a heap0 with default collision chain table capacity.
*/
public DialsHeap() {
this(DEFAULT_TABLE_CAPACITY);
}
/**
* {@inheritDoc }
*/
@Override
public Iterator<D> iterator() {
return new DialsHeapIterator();
}
/**
* {@inheritDoc}
*/
@Override
public void insert(final D datum, final int priority) {
if (nodeMap.containsKey(datum)) {
// Once here, the input datum is already in this heap. Use
// updatePriority for adjusting the priority key.
return;
}
checkPriority(priority);
if (mustExpand(priority)) {
expand(priority);
}
final DialsHeapNode<D> node = new DialsHeapNode<>(datum, priority);
nodeMap.put(datum, node);
linkImpl(node, priority);
}
/**
* {@inheritDoc}
*/
@Override
public void updatePriority(final D datum, final int priority) {
if (mustExpand(priority)) {
expand(priority);
}
final DialsHeapNode<D> node = nodeMap.get(datum);
unlinkImpl(node);
linkImpl(node, priority);
node.priority = priority;
}
/**
* {@inheritDoc}
*/
@Override
public int minimumPriority() {
return accessMinimumPriorityNode().priority;
}
/**
* {@inheritDoc}
*/
@Override
public D minimumNode() {
if (nodeMap.isEmpty()) {
return null;
}
return accessMinimumPriorityNode().datum;
}
/**
* {@inheritDoc}
*/
@Override
public boolean containsDatum(final D datum) {
return nodeMap.containsKey(datum);
}
/**
* {@inheritDoc}
*/
@Override
public int getPriority(final D datum) {
return nodeMap.get(datum).priority;
}
/**
* {@inheritDoc}
*/
@Override
public D extractMinimum() {
if (nodeMap.isEmpty()) {
return null;
}
final DialsHeapNode<D> node = accessMinimumPriorityNode();
unlinkImpl(node);
nodeMap.remove(node.datum);
return node.datum;
}
/**
* {@inheritDoc}
*/
@Override
public void remove(final D datum) {
unlinkImpl(nodeMap.get(datum));
nodeMap.remove(datum);
}
/**
* {@inheritDoc}
*/
@Override
public void clear() {
nodeMap.clear();
Arrays.fill(table, null);
}
/**
* {@inheritDoc}
*/
@Override
public Object clone() {
final int maximumPriorityKey = getMaximumPriority();
final int cloneCapacity = getNextCapacity(maximumPriorityKey);
final DialsHeap<D> copy = new DialsHeap<>(cloneCapacity);
for (final Map.Entry<D, DialsHeapNode<D>> entry : nodeMap.entrySet()) {
copy.insert(entry.getValue().datum, entry.getValue().priority);
}
return copy;
}
/**
* {@inheritDoc}
*/
@Override
public int size() {
return nodeMap.size();
}
/**
* {@inheritDoc }
*/
@Override
public boolean isEmpty() {
return nodeMap.isEmpty();
}
/**
* Returns the head of the collision chain with the lowest priority key.
*
* @return the head of the collision chain with the lowest priority key.
*/
private DialsHeapNode<D> accessMinimumPriorityNode() {
for (int p = 0; p != table.length; p++) {
if (table[p] != null) {
return table[p];
}
}
throw new IllegalStateException("Should not get here.");
}
/**
* Links the node {@code node} to the head of the collision chain with
* priority key {@code priority}.
*
* @param node the node to link.
* @param priority the priority key to link with.
*/
private void linkImpl(final DialsHeapNode<D> node, final int priority) {
final DialsHeapNode<D> currentBucketHead = table[priority];
if (currentBucketHead != null) {
node.next = currentBucketHead;
currentBucketHead.prev = node;
}
table[priority] = node;
}
/**
* Unlinks the node {@code node} from this heap.
*
* @param node the node to unlink.
*/
private void unlinkImpl(final DialsHeapNode<D> node) {
if (node.prev != null) {
node.prev.next = node.next;
if (node.next != null) {
node.next.prev = node.prev;
node.next = null;
}
node.prev = null;
} else {
// Once here, node.prev == null!
if (node.next != null) {
node.next.prev = null;
table[node.priority] = node.next;
node.next = null;
} else {
// Remove the last node in the collision chain:
table[node.priority] = null;
}
}
}
/**
* Returns {@code true} if this heap's table cannot accommodate a node with
* priority {@code priority}.
*
* @param priority the priority to query.
*
* @return {@code true} if the table must be expanded.
*/
private boolean mustExpand(final int priority) {
return priority >= table.length;
}
/**
* Expands the internal table {@code table} such that it can accommodate the
* priority key {@code priority}, while being smallest such table.
*
* @param priority the requested priority key.
*/
private void expand(final int priority) {
final int nextCapacity = getNextCapacity(priority);
this.table = Arrays.copyOf(table, nextCapacity);
}
/**
* Returns the capacity that is sufficiently large in order to accommodate
* the heap nodes with priority {@code priority}.
*
* @param priority the requested priority.
*
* @return the next capacity to expand with.
*/
private int getNextCapacity(final int priority) {
int nextCapacity = table.length;
while (nextCapacity <= priority) {
nextCapacity *= 2;
}
return nextCapacity;
}
/**
* Returns the maximum priority key in this heap.
*
* @return the maximum priority key in this heap.
*/
private int getMaximumPriority() {
for (int priority = table.length - 1; priority >= 0; priority--) {
if (table[priority] != null) {
return priority;
}
}
return -1;
}
/**
* Makes sure that the input priority is non-negative.
*
* @param priority the priority to check.
*
* @throws IllegalArgumentException if the input priority is negative.
*/
private void checkPriority(final int priority) {
if (priority < 0) {
throw new IllegalArgumentException(
String.format(
"The input priority is negtive (%d).\n",
priority));
}
}
}
package com.github.coderodde.util;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.NoSuchElementException;
/**
* This class implements a priority queue data structure called a Dial's heap.
*
* @param <D> the type of the satellite data.
*
* @version 1.0.0 (May 10, 2024)
* @since 1.0.0
*/
public class CachedDialsHeap<D> implements IntegerMinimumPriorityQueue<D> {
/**
* This static inner class implements the node type for this heap.
*
* @param <D> the satellite data type.
*/
private static final class CachedDialsHeapNode<D> {
/**
* The actual satellite datum.
*/
final D datum;
/**
* The priority key of this node. Must be at least zero (0).
*/
int priority;
/**
* The previous node in the collision chain or {@code null} if this node
* is the head of the collision chain.
*/
CachedDialsHeapNode<D> prev;
/**
* The next node in the collision chain or {@code null} if this node is
* the tail of the collision chain.
*/
CachedDialsHeapNode<D> next;
/**
* Constructs a new heap node.'
*
* @param datum the satellite datum.
* @param priority the priority key.
*/
CachedDialsHeapNode(final D datum, final int priority) {
this.datum = datum;
this.priority = priority;
}
}
/**
* This inner class implements the iterator over all satellite data in this
* heap in the ascending priority key order.
*/
private final class CachedDialsHeapIterator implements Iterator<D> {
/**
* Caches the number of nodes already iterated.
*/
private int iterated = 0;
/**
* The current heap node.
*/
private CachedDialsHeapNode<D> currentDialsHeapNode;
/**
* Constructs a new iterator over the enclosing heap.
*/
private CachedDialsHeapIterator() {
// Attempt to find the head node:
for (final CachedDialsHeapNode<D> headNode : table) {
if (headNode != null) {
currentDialsHeapNode = headNode;
return;
}
}
// Once here, the heap is empty, return null:
currentDialsHeapNode = null;
}
/**
* {@inheritDoc }
*/
@Override
public boolean hasNext() {
return iterated < size;nodeMap.size();
}
/**
* {@inheritDoc}
*/
@Override
public D next() {
if (!hasNext()) {
throw new NoSuchElementException("Nothing to iterate left.");
}
final D returnElement = currentDialsHeapNode.datum;
iterated++;
currentDialsHeapNode = computeNextDialsHeapNode();
return returnElement;
}
/**
* Returns the next heap node.
*
* @return the next heap node in the iteration order.
*/
private CachedDialsHeapNode<D> computeNextDialsHeapNode() {
if (iterated == nodeMap.size()) {
// Once here, iteration is complete.
return null;
}
if (currentDialsHeapNode.next != null) {
// currentDialsHeapNode has minimum priority key, move to its
// right sibling/neighbor in the collision chain:
return currentDialsHeapNode.next;
}
// Search the next smallest priority node:
for (int p = currentDialsHeapNode.priority + 1;
p < table.length;
p++) {
if (table[p] != null) {
// Found!
return table[p];
}
}
// We should never ever get here.
throw new IllegalStateException("Should not get here.");
}
}
/**
* The default table capacity.
*/
private static final int DEFAULT_TABLE_CAPACITY = 8;
/**
* The table mapping each slot to the head of a collision chain.
*/
private CachedDialsHeapNode<D>[] table;
/**
* The map mapping the satellite datums to their respective heap nodes.
*/
private final Map<D, CachedDialsHeapNode<D>> nodeMap = new HashMap<>();
/**
* Caches the number of satellite datums in this heap.
*/
private int size = 0;
/**
* Caches the minimum priority so that {@link #extractMinimum()} and
* {@link #minimumNode()} and {@link #minimumPriority()} run in constant
* time.
*/
private int minimumPriority = Integer.MAX_VALUE;
/**
* Constructs a heap with {@code tableCapacity} as the capacity of the
* internal collision chain table.
*
* @param tableCapacity the requested collision chain capacity.
*/
public CachedDialsHeap(final int tableCapacity) {
this.table = new CachedDialsHeapNode[tableCapacity];
}
/**
* Constructs a heap0 with default collision chain table capacity.
*/
public CachedDialsHeap() {
this(DEFAULT_TABLE_CAPACITY);
}
/**
* {@inheritDoc }
*/
@Override
public Iterator<D> iterator() {
return new CachedDialsHeapIterator();
}
/**
* {@inheritDoc}
*/
@Override
public void insert(final D datum, final int priority) {
if (nodeMap.containsKey(datum)) {
// Once here, the input datum is already in this heap. Use
// updatePriority for adjusting the priority key.
return;
}
checkPriority(priority);
minimumPriority = Math.min(minimumPriority, priority);
if (mustExpand(priority)) {
expand(priority);
}
final CachedDialsHeapNode<D> newTreeHeapNodenode =
new CachedDialsHeapNode<>(
datum,
priority);
nodeMap.put(datum, newTreeHeapNodenode);
linkImpl(newTreeHeapNodenode, priority);
size++;
}
/**
* {@inheritDoc}
*/
@Override
public void updatePriority(final D datum, final int priority) {
checkPriority(priority);
minimumPriority = Math.min(minimumPriority, priority);
if (mustExpand(priority)) {
expand(priority);
}
final CachedDialsHeapNode<D> node = nodeMap.get(datum);
unlinkImpl(node);
linkImpl(node, priority);
node.priority = priority;
}
/**
* {@inheritDoc}
*/
@Override
public int minimumPriority() {
return minimumPriority;
}
/**
* {@inheritDoc}
*/
@Override
public D minimumNode() {
if (size == 0nodeMap.isEmpty()) {
return null;
}
return table[minimumPriority].datum;
}
/**
* {@inheritDoc}
*/
@Override
public boolean containsDatum(final D datum) {
return nodeMap.containsKey(datum);
}
/**
* {@inheritDoc}
*/
@Override
public int getPriority(final D datum) {
return nodeMap.get(datum).priority;
}
/**
* {@inheritDoc}
*/
@Override
public D extractMinimum() {
if (size == 0nodeMap.isEmpty()) {
return null;
}
final CachedDialsHeapNode<D> treeNodenode = accessMinimumPriorityNode();
unlinkImpl(treeNodenode);
nodeMap.remove(treeNodenode.datum);
size--;
if (table[minimumPriority] == null) {
updateMinimumPriority();
}
return treeNodenode.datum;
}
/**
* {@inheritDoc}
*/
@Override
public void remove(final D datum) {
final CachedDialsHeapNode<D> node = nodeMap.get(datum);
unlinkImpl(node);
nodeMap.remove(datum);
if (table[node.priority] == null) {
updateMinimumPriority();
}
size--;
}
/**
* {@inheritDoc}
*/
@Override
public void clear() {
minimumPriority = Integer.MAX_VALUE;
size = 0;
nodeMap.clear();
Arrays.fill(table, null);
}
/**
* {@inheritDoc}
*/
@Override
public Object clone() {
final int maximumPriorityKey = getMaximumPriority();
final int cloneCapacity = getNextCapacity(maximumPriorityKey);
final CachedDialsHeap<D> copy = new CachedDialsHeap<>(cloneCapacity);
for (final Map.Entry<D, CachedDialsHeapNode<D>> entry : nodeMap.entrySet()) {
copy.insert(entry.getValue().datum, entry.getValue().priority);
}
return copy;
}
/**
* {@inheritDoc}
*/
@Override
public int size() {
return size;nodeMap.size();
}
/**
* {@inheritDoc }
*/
@Override
public boolean isEmpty() {
return nodeMap.isEmpty();
}
/**
* Returns the head of the collision chain with the lowest priority key.
*
* @return the head of the collision chain with the lowest priority key.
*/
private CachedDialsHeapNode<D> accessMinimumPriorityNode() {
for (int p = 0; p != table.length; p++) {
if (table[p] != null) {
return table[p];
}
}
throw new IllegalStateException("Should not get here.");
}
/**
* Links the node {@code node} to the head of the collision chain with
* priority key {@code priority}.
*
* @param node the node to link.
* @param priority the priority key to link with.
*/
private void linkImpl(final CachedDialsHeapNode<D> node, final int priority) {
final CachedDialsHeapNode<D> currentBucketHead = table[priority];
if (currentBucketHead != null) {
node.next = currentBucketHead;
currentBucketHead.prev = node;
}
table[priority] = node;
}
/**
* Unlinks the node {@code node} from this heap.
*
* @param node the node to unlink.
*/
private void unlinkImpl(final CachedDialsHeapNode<D> node) {
if (node.prev != null) {
node.prev.next = node.next;
node.prev = null;
if (node.next != null) {
node.next.prev = node.prev;
node.next = null;
}
node.prev = null;
} else {
// Once here, node.prev == null!
if (node.next != null) {
node.next.prev = null;
table[node.priority] = node.next;
node.next = null;
} else {
// Remove the last node in the collision chain:
table[node.priority] = null;
}
}
}
/**
* Returns {@code true} if this heap's table cannot accommodate a node with
* priority {@code priority}.
*
* @param priority the priority to query.
*
* @return {@code true} if the table must be expanded.
*/
private boolean mustExpand(final int priority) {
return priority >= table.length;
}
/**
* Expands the internal table {@code table} such that it can accommodate the
* priority key {@code priority}, while being smallest such table.
*
* @param priority the requested priority key.
*/
private void expand(final int priority) {
final int nextCapacity = getNextCapacity(priority);
this.table = Arrays.copyOf(table, nextCapacity);
}
/**
* Returns the capacity that is sufficiently large in order to accommodate
* the heap nodes with priority {@code priority}.
*
* @param priority the requested priority.
*
* @return the next capacity to expand with.
*/
private int getNextCapacity(final int priority) {
int nextCapacity = table.length;
while (nextCapacity <= priority) {
nextCapacity *= 2;
}
return nextCapacity;
}
/**
* Returns the maximum priority key in this heap.
*
* @return the maximum priority key in this heap.
*/
private int getMaximumPriority() {
for (int priority = table.length - 1; priority >= 0; priority--) {
if (table[priority] != null) {
return priority;
}
}
return -1;
}
/**
* Makes sure that the input priority is non-negative.
*
* @param priority the priority to check.
*
* @throws IllegalArgumentException if the input priority is negative.
*/
private void checkPriority(final int priority) {
if (priority < 0) {
throw new IllegalArgumentException(
String.format(
"The input priority is negtive (%d).\n",
priority));
}
}
/**
* Updates the minimum priority.
*/
private void updateMinimumPriority() {
for (int p = minimumPriority + 1; p < table.length; p++) {
if (table[p] != null) {
minimumPriority = p;
return;
}
}
minimumPriority = -1;
}
}
package com.github.coderodde.util.benchmark;
import com.github.coderodde.util.CachedDialsHeap;
import com.github.coderodde.util.DialsHeap;
import com.github.coderodde.util.IntegerMinimumPriorityQueue;
import java.util.Arrays;
import java.util.Random;
/**
* This class implements the benchmark program for the priority queues.
*
* @version 1.0.1 (May 12, 2024)
* @since 1.0.0 (May 11, 2024)
*/
public final class Benchmark {
private/**
static final int UPPER_BOUND =* 1_000_000;The upper bound value for the randomly generated integers.
*/
private static final int ARRAY_LENGTHUPPER_BOUND = 10_000_000;150_000;
/**
* The benchmarking array lengths.
*/
private static final int ARRAY_LENGTH = 1_000_000;
/**
* The entry point of the benchmark.
*
* @param args the command line arguments.
*/
public static void main(String[] args) {
final long seed = System.currentTimeMillis();
System.out.printf("seed = %d.\n", seed);
warmup(seed);
benchmark(seed);
}
/**
* Warms up the benchmark.
*
* @param seed the random number generator seed.
*/
private static void warmup(final long seed) {
runBenchmark(
new DialsHeap<>(),
seed,
false);
runBenchmark(
new CachedDialsHeap<>(),
seed,
false);
}
/**
* Benchmarks the heaps.
*
* @param seed the random number generator seed.
*/
private static void benchmark(final long seed) {
final Integer[] output1 =
runBenchmark(
new DialsHeap<>(),
seed,
true);
System.out.println();
final Integer[] output2 =
runBenchmark(
new CachedDialsHeap<>(),
seed,
true);
System.out.println();
System.out.printf(
"Heaps agree: %b.\n",
Arrays.equals(output1,
output2));
}
/**
* Implements the benchmark/warmup runner.
*
* @param heap the heap to benchmark.
* @param seed the random number generator seed.
* @param print the flag specifying whether to print the intermediate
* results.
*
* @return the processed data.
*/
private static Integer[] runBenchmark(
final IntegerMinimumPriorityQueue<Integer> heap,
final long seed,
final boolean print) {
final Random random = new Random(seed);
final Integer[] array =
getRandomIntegerArray(
random,
ARRAY_LENGTH,
UPPER_BOUND);
long totalDuration = 0L;
long start = System.currentTimeMillis();
for (final Integer i : array) {
heap.insert(i, i);
}
long end = System.currentTimeMillis();
totalDuration += end - start;
if (print) {
System.out.printf("insert() in %d milliseconds.\n", end - start);
}
final int[] priorities =
getRandomIntArray(
random,
ARRAY_LENGTH,
UPPER_BOUND);
start = System.currentTimeMillis();
for (int i = 0; i < heap.size(); i++) {
heap.updatePriority(array[i], priorities[i]);
}
end = System.currentTimeMillis();
totalDuration += end - start;
if (print) {
System.out.printf(
"updatePriority() in %d milliseconds.\n",
end - start);
}
final Integer[] output = new Integer[heap.size()];
int index = 0;
start = System.currentTimeMillis();
while (heap.size() != 0) {
output[index++] = heap.extractMinimum();
}
end = System.currentTimeMillis();
totalDuration += end - start;
if (print) {
System.out.printf(
"extractMinimum() in %d milliseconds.\n",
end - start);
System.out.printf(
"Total duration of %s: %d milliseconds.\n",
heap.getClass().getSimpleName(),
totalDuration);
}
return output;
}
/**
* Returns the random array of {@code Integer}s. Each integer is drawn from
* the range {@code [0, upperBound - 1]}.
*
* @param random the random number generator.
* @param length the length of the generated array.
* @param upperBound the upper bound of the integer values.
*
* @return the random integer array.
*/
private static Integer[]
getRandomIntegerArray(
final Random random,
final int length,
final int upperBound) {
final Integer[] array = new Integer[length];
for (int i = 0; i < length; i++) {
array[i] = random.nextInt(upperBound);
}
return array;
}
/**
* Returns the random array of {@code int}s. Each integer is drawn from
* the range {@code [0, upperBound - 1]}.
*
* @param random the random number generator.
* @param length the length of the generated array.
* @param upperBound the upper bound of the integer values.
*
* @return the random integer array.
*/
private static int[]
getRandomIntArray(
final Random random,
final int length,
final int upperBound) {
final int[] array = new int[length];
for (int i = 0; i < length; i++) {
array[i] = random.nextInt(upperBound);
}
return array;
}
}
seed = 17154006725271715856367754.
insert() in 1508126 milliseconds.
updatePriority() in 23622 milliseconds.
extractMinimum() in 394424 milliseconds.
Total duration of DialsHeap: 17834572 milliseconds.
insert() in 1804195 milliseconds.
updatePriority() in 19648 milliseconds.
extractMinimum() in 465620 milliseconds.
Total duration of CachedDialsHeap: 20465863 milliseconds.
Heaps agree: true.
