package jsat.utils;
import java.io.Serializable;
import java.util.*;
/**
* This class represents a priority queue specifically designed to contain
* integer keys, and uses less memory then a {@link PriorityQueue} filled with
* integers. This queue can optionally support log(n) removal of key
* values at increased memory cost.
* @author Edward Raff
*/
public class IntPriorityQueue extends AbstractQueue implements Serializable
{
private static final long serialVersionUID = -310756323843109562L;
public static final Comparator naturalComparator = new Comparator() {
@Override
public int compare(Integer o1, Integer o2)
{
return o1.compareTo(o2);
}
};
/**
* Sets the mode used for the priority queue.
*/
public static enum Mode
{
/**
* Sets the priority queue to use the standard queue implementation with
* the standard complexity for the following operations
*
* O(1) time for {@link #peek() }
* O(log n) time for {@link #poll() }, {@link #add(java.lang.Object) }
* O(n) time for {@link #remove(java.lang.Object) } and {@link #contains(java.lang.Object) }
* And calling {@link Iterator#remove() } is O(log n), but the iteration is in no particular order
*
*/
STANDARD,
/**
* Sets the priority queue to use a backing hashtable to map values to
* their position in the heap. This changes the complexity to
*
* O(1) time for {@link #peek() } and {@link #contains(java.lang.Object) }
* O(log n) time for {@link #poll() }, {@link #add(java.lang.Object) },
* and {@link #remove(java.lang.Object) }
* And calling {@link Iterator#remove() } is O(log n), but the iteration
* is in no particular order
*/
HASH,
/**
* Sets the priority queue to use a backing array that indexes into the
* heap. This provides the fastest version if fast
* {@link #remove(java.lang.Object) } and {@link #contains(java.lang.Object) }
* are needed. However, it must create an array as large as the largest
* int value put into the queue, and negative values will not be accepted.
* This method is best when the size of the queue is known to be bounded
* and all values are in the range [0, N].
*
* O(1) time for {@link #peek() } and {@link #contains(java.lang.Object) }
* O(log n) time for {@link #poll() }, {@link #add(java.lang.Object) },
* and {@link #remove(java.lang.Object) }
* And calling {@link Iterator#remove() } is O(log n), but the iteration
* is in no particular order
*/
BOUNDED
}
private int[] heap;
private int size;
private Comparator comparator;
private final HashMap valueIndexMap;
private int[] valueIndexStore;
private final Mode fastValueRemove;
/**
* Creates a new integer priority queue using {@link Mode#STANDARD}
*/
public IntPriorityQueue()
{
this(8, naturalComparator);
}
/**
* Creates a new integer priority queue using the specified comparison and {@link Mode#STANDARD}
* @param initialSize the initial storage size of the queue
* @param comparator the comparator to determine the order of elements in the queue
*/
public IntPriorityQueue(int initialSize, Comparator comparator)
{
this(initialSize, comparator, Mode.STANDARD);
}
/**
* Creates a new integer priority queue
* @param initialSize the initial storage size of the queue
* @param fastValueRemove the mode that whether or not, and how, fast
* arbitrary object removal from the queue will be done.
*/
public IntPriorityQueue(int initialSize, Mode fastValueRemove)
{
this(initialSize, naturalComparator, fastValueRemove);
}
/**
* Creates a new integer priority queue
* @param initialSize the initial storage size of the queue
* @param comparator the comparator to determine the order of elements in the queue
* @param fastValueRemove the mode that whether or not, and how, fast
* arbitrary object removal from the queue will be done.
*/
public IntPriorityQueue( int initialSize, Comparator comparator, Mode fastValueRemove)
{
this.heap = new int[initialSize];
this.comparator = comparator;
this.size = 0;
this.fastValueRemove = fastValueRemove;
valueIndexStore = null;
if(fastValueRemove == Mode.HASH)
valueIndexMap = new HashMap(initialSize);
else if(fastValueRemove == Mode.BOUNDED)
{
valueIndexStore = new int[initialSize];
Arrays.fill(valueIndexStore, -1);
valueIndexMap = null;
}
else
valueIndexMap = null;
}
@Override
public Iterator iterator()
{
//Return a itterator that itterats the heap array in reverse. This is
//slower (against cache line), but allows for simple implementaiton of
//remove(). Becase removing an item is done by pulling the last element
//in the heap and then pushing down, all changes for removing node i
//will occur after index i
return new Iterator()
{
int pos = size-1;
boolean canRemove = false;
@Override
public boolean hasNext()
{
return pos >= 0;
}
@Override
public Integer next()
{
canRemove = true;
return heap[pos--];
}
@Override
public void remove()
{
if(!canRemove)
throw new IllegalStateException("An element can not currently be removed");
else
{
canRemove = false;
removeHeapNode(pos+1);
}
}
};
}
@Override
public int size()
{
return size;
}
@Override
public boolean offer(Integer e)
{
if(e == null)
return false;
return offer((int)e);
}
public boolean offer(int e)
{
int i = size++;
if(heap.length < size)
heap = Arrays.copyOf(heap, heap.length*2);
heap[i] = e;
if(fastValueRemove == Mode.HASH)
valueIndexMap.put(e, i);
else if (fastValueRemove == Mode.BOUNDED )
if(e >= 0)
indexArrayStore(e, i);
else
{
heap[i] = 0;
size--;
return false;
}
heapifyUp(i);
return true;
}
/**
* Sets the given index to use the specific value
* @param e the value to store the index of
* @param i the index of the value
*/
private void indexArrayStore(int e, int i)
{
if (valueIndexStore.length < e)
{
int oldLength = valueIndexStore.length;
valueIndexStore = Arrays.copyOf(valueIndexStore, e + 2);
Arrays.fill(valueIndexStore, oldLength, valueIndexStore.length, -1);
}
valueIndexStore[e] = i;
}
@SuppressWarnings("unused")
private int getRightMostChild(int i)
{
int rightMostChild = i;
//Get the right most child in this tree
while(rightChild(rightMostChild) < size)
rightMostChild = rightChild(rightMostChild);
//Could be at a level with a left but no right
while(leftChild(rightMostChild) < size)
rightMostChild = leftChild(rightMostChild);
return rightMostChild;
}
private int cmp(int i, int j)
{
return comparator.compare(heap[i], heap[j]);
}
private void heapDown(int i)
{
int iL = leftChild(i);
int iR = rightChild(i);
//While we have two children, make sure we are smaller
while (childIsSmallerAndValid(i, iL) || childIsSmallerAndValid(i, iR))
{
//we are larger then one of ours children, so swap with the smallest of the two
if ( iR < size && cmp(iL, iR) > 0 )//Right is the smallest
{
swapHeapValues(i, iR);
i = iR;
}
else//Left is smallest or lef tis only option
{
swapHeapValues(i, iL);
i = iL;
}
iL = leftChild(i);
iR = rightChild(i);
}
}
/**
* Heapify up from the given index in the heap and make sure everything is
* correct. Stops when the child value is in correct order with its parent.
* @param i the index in the heap to start checking from.
*/
private void heapifyUp(int i)
{
int iP = parent(i);
while(i != 0 && cmp(i, iP) < 0)//Should not be greater then our parent
{
swapHeapValues(iP, i);
i = iP;
iP = parent(i);
}
}
/**
* Swaps the values stored in the heap for the given indices
* @param i the first index to be swapped
* @param j the second index to be swapped
*/
private void swapHeapValues(int i, int j)
{
if(fastValueRemove == Mode.HASH)
{
valueIndexMap.put(heap[i], j);
valueIndexMap.put(heap[j], i);
}
else if(fastValueRemove == Mode.BOUNDED)
{
//Already in the array, so just need to set
valueIndexStore[heap[i]] = j;
valueIndexStore[heap[j]] = i;
}
int tmp = heap[i];
heap[i] = heap[j];
heap[j] = tmp;
}
private int parent(int i)
{
return (i-1)/2;
}
private int leftChild(int i)
{
return 2*i+1;
}
/**
* Removes the node specified from the heap
* @param i the valid heap node index to remove from the heap
* @return the value that was stored in the heap node
*/
protected int removeHeapNode(int i)
{
int val = heap[i];
int rightMost = --size;
heap[i] = heap[rightMost];
heap[rightMost] = 0;
if(fastValueRemove == Mode.HASH)
{
valueIndexMap.remove(val);
if(size != 0)
valueIndexMap.put(heap[i], i);
}
else if(fastValueRemove == Mode.BOUNDED)
{
valueIndexStore[val] = -1;
}
heapDown(i);
return val;
}
private int rightChild(int i)
{
return 2*i+2;
}
private boolean childIsSmallerAndValid(int i, int child)
{
return child < size && cmp(i, child) > 0;
}
@Override
public Integer poll()
{
if(isEmpty())
return null;
return removeHeapNode(0);
}
@Override
public Integer peek()
{
if(isEmpty())
return null;
return heap[0];
}
@Override
public boolean contains(Object o)
{
if(fastValueRemove == Mode.HASH)
return valueIndexMap.containsKey(o);
else if(fastValueRemove == Mode.BOUNDED)
{
if( o instanceof Integer)
{
int val = ((Integer) o).intValue();
return val >= 0 && valueIndexStore[val] >= 0;
}
return false;
}
return super.contains(o);
}
@Override
public void clear()
{
Arrays.fill(heap, 0, size, 0);
size = 0;
if(fastValueRemove == Mode.HASH)
valueIndexMap.clear();
else if(fastValueRemove == Mode.BOUNDED)
Arrays.fill(valueIndexStore, -1);
}
@Override
public boolean remove(Object o)
{
if(fastValueRemove == Mode.HASH)
{
Integer index = valueIndexMap.get(o);
if(index == null)
return false;
removeHeapNode(index);
return true;
}
else if(fastValueRemove == Mode.BOUNDED)
{
if(o instanceof Integer)
{
int val = ((Integer) o).intValue();
if(val <0 || val >= valueIndexStore.length)
return false;
int index = valueIndexStore[val];
if(index == -1)
return false;
removeHeapNode(index);
return true;
}
return false;
}
return super.remove(o);
}
}
Ads help maintain this website.