|
|||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Objectit.unimi.dsi.fastutil.AbstractIndirectPriorityQueue<K>
it.unimi.dsi.fastutil.objects.ObjectHeapSemiIndirectPriorityQueue<K>
it.unimi.dsi.fastutil.objects.ObjectHeapIndirectPriorityQueue<K>
it.unimi.dsi.fastutil.objects.ObjectHeapIndirectDoublePriorityQueue<K>
public class ObjectHeapIndirectDoublePriorityQueue<K>
A type-specific heap-based indirect double priority queue.
Instances of this class are based on two indirect
heap-based queues. The queues are enlarged as needed, but they are never
shrunk. Use the trim()
method to reduce their size, if necessary.
Either comparator may be null
, indicating that natural comparison should take place. Of course,
it makes little sense having them equal.
Constructor Summary | |
---|---|
ObjectHeapIndirectDoublePriorityQueue(K[] refArray)
Creates a new empty queue with capacity equal to the length of the reference array and natural order as primary comparator. |
|
ObjectHeapIndirectDoublePriorityQueue(K[] refArray,
java.util.Comparator<? super K> c)
Creates a new empty queue with capacity equal to the length of the reference array. |
|
ObjectHeapIndirectDoublePriorityQueue(K[] refArray,
java.util.Comparator<? super K> c,
java.util.Comparator<? super K> d)
Creates a new empty queue with capacity equal to the length of the reference array. |
|
ObjectHeapIndirectDoublePriorityQueue(K[] refArray,
int capacity)
Creates a new empty queue with a given capacity and natural order as primary comparator. |
|
ObjectHeapIndirectDoublePriorityQueue(K[] refArray,
int[] a)
Wraps a given array in a queue using the natural order. |
|
ObjectHeapIndirectDoublePriorityQueue(K[] refArray,
int[] a,
java.util.Comparator<? super K> c)
Wraps a given array in a queue using a given comparator. |
|
ObjectHeapIndirectDoublePriorityQueue(K[] refArray,
int[] a,
java.util.Comparator<? super K> c,
java.util.Comparator<? super K> d)
Wraps a given array in a queue using the given comparators. |
|
ObjectHeapIndirectDoublePriorityQueue(K[] refArray,
int[] a,
int size)
Wraps a given array in a queue using the natural order. |
|
ObjectHeapIndirectDoublePriorityQueue(K[] refArray,
int[] a,
int size,
java.util.Comparator<? super K> c)
Wraps a given array in a queue using a given comparator. |
|
ObjectHeapIndirectDoublePriorityQueue(K[] refArray,
int[] a,
int size,
java.util.Comparator<? super K> c,
java.util.Comparator<? super K> d)
Wraps a given array in a queue using the given comparators. |
|
ObjectHeapIndirectDoublePriorityQueue(K[] refArray,
int capacity,
java.util.Comparator<? super K> c)
Creates a new empty queue with a given capacity. |
|
ObjectHeapIndirectDoublePriorityQueue(K[] refArray,
int capacity,
java.util.Comparator<? super K> c,
java.util.Comparator<? super K> d)
Creates a new empty queue with a given capacity. |
Method Summary | |
---|---|
void |
allChanged()
Rebuilds this heap in a bottom-up fashion. |
void |
changed()
Notifies the queue that the first element has changed (optional operation). The caller must guarantee that when this method is called the index of the first element appears just once in the queue. |
void |
changed(int index)
Notifies the queue that the specified element has changed (optional operation). |
void |
clear()
Removes all elements from this queue. |
int |
dequeue()
Dequeues the first element from the queue. |
void |
enqueue(int x)
Enqueues a new element. |
void |
remove(int index)
Removes the specified element from the queue (optional operation). |
java.util.Comparator<? super K> |
secondaryComparator()
Returns the secondary comparator of this queue. |
int |
secondaryFirst()
Returns the first element of this queue with respect to the secondary comparator. |
int |
secondaryFront(int[] a)
Retrieves the secondary front of the queue in a given array (optional operation). |
int |
secondaryLast()
Returns the last element of this queue with respect to the secondary comparator (optional operation). |
void |
trim()
Trims the underlying queues so they have exactly ObjectHeapSemiIndirectPriorityQueue.size() elements. |
Methods inherited from class it.unimi.dsi.fastutil.objects.ObjectHeapSemiIndirectPriorityQueue |
---|
comparator, first, front, size, toString |
Methods inherited from class it.unimi.dsi.fastutil.AbstractIndirectPriorityQueue |
---|
isEmpty, last |
Methods inherited from class java.lang.Object |
---|
equals, getClass, hashCode, notify, notifyAll, wait, wait, wait |
Methods inherited from interface it.unimi.dsi.fastutil.IndirectPriorityQueue |
---|
comparator, first, front, isEmpty, last, size |
Constructor Detail |
---|
public ObjectHeapIndirectDoublePriorityQueue(K[] refArray, int capacity, java.util.Comparator<? super K> c, java.util.Comparator<? super K> d)
refArray
- the reference array.capacity
- the initial capacity of this queue.c
- the primary comparator used in this queue, or null
for the natural order.d
- the secondary comparator used in this queue, or null
for the natural order.public ObjectHeapIndirectDoublePriorityQueue(K[] refArray, int capacity, java.util.Comparator<? super K> c)
This constructor uses as secondary comparator the opposite order of c
.
refArray
- the reference array.capacity
- the initial capacity of this queue.c
- the primary comparator used in this queue, or null
for the natural order.public ObjectHeapIndirectDoublePriorityQueue(K[] refArray, int capacity)
This constructor uses as secondary comparator the opposite of the natural order.
refArray
- the reference array.capacity
- the initial capacity of this queue.public ObjectHeapIndirectDoublePriorityQueue(K[] refArray, java.util.Comparator<? super K> c, java.util.Comparator<? super K> d)
refArray
- the reference array.c
- the primary comparator used in this queue, or null
for the natural order.d
- the secondary comparator used in this queue, or null
for the natural order.public ObjectHeapIndirectDoublePriorityQueue(K[] refArray, java.util.Comparator<? super K> c)
This constructor uses as secondary comparator the opposite order of c
.
refArray
- the reference array.c
- the primary comparator used in this queue, or null
for the natural order.public ObjectHeapIndirectDoublePriorityQueue(K[] refArray)
This constructor uses as secondary comparator the opposite of the natural order.
refArray
- the reference array.public ObjectHeapIndirectDoublePriorityQueue(K[] refArray, int[] a, int size, java.util.Comparator<? super K> c, java.util.Comparator<? super K> d)
The queue returned by this method will be backed by the given array.
The first size
element of the array will be rearranged so to form a heap, and
moreover the array will be cloned and wrapped in a secondary queue (this is
more efficient than enqueing the elements of a
one by one).
refArray
- the reference array.a
- an array of indices into refArray
.size
- the number of elements to be included in the queue.c
- the primary comparator used in this queue, or null
for the natural order.d
- the secondary comparator used in this queue, or null
for the natural order.public ObjectHeapIndirectDoublePriorityQueue(K[] refArray, int[] a, java.util.Comparator<? super K> c, java.util.Comparator<? super K> d)
The queue returned by this method will be backed by the given array.
The first elements of the array will be rearranged so to form a heap, and
moreover the array will be cloned and wrapped in a secondary queue (this is
more efficient than enqueing the elements of a
one by one).
refArray
- the reference array.a
- an array of indices into refArray
.c
- the primary comparator used in this queue, or null
for the natural order.d
- the secondary comparator used in this queue, or null
for the natural order.public ObjectHeapIndirectDoublePriorityQueue(K[] refArray, int[] a, int size, java.util.Comparator<? super K> c)
The queue returned by this method will be backed by the given array.
The first size
element of the array will be rearranged so to form a heap, and
moreover the array will be cloned and wrapped in a secondary queue (this is
more efficient than enqueing the elements of a
one by one).
This constructor uses as secondary comparator the opposite order of c
.
refArray
- the reference array.a
- an array of indices into refArray
.size
- the number of elements to be included in the queue.c
- the primary comparator used in this queue, or null
for the natural order.public ObjectHeapIndirectDoublePriorityQueue(K[] refArray, int[] a, java.util.Comparator<? super K> c)
The queue returned by this method will be backed by the given array.
The elements of the array will be rearranged so to form a heap, and
moreover the array will be cloned and wrapped in a secondary queue (this is
more efficient than enqueing the elements of a
one by one).
This constructor uses as secondary comparator the opposite order of c
.
refArray
- the reference array.a
- an array of indices into refArray
.c
- the primary comparator used in this queue, or null
for the natural order.public ObjectHeapIndirectDoublePriorityQueue(K[] refArray, int[] a, int size)
The queue returned by this method will be backed by the given array.
The first size
element of the array will be rearranged so to form a heap, and
moreover the array will be cloned and wrapped in a secondary queue (this is
more efficient than enqueing the elements of a
one by one).
This constructor uses as secondary comparator the opposite of the natural order.
refArray
- the reference array.a
- an array of indices into refArray
.size
- the number of elements to be included in the queue.public ObjectHeapIndirectDoublePriorityQueue(K[] refArray, int[] a)
The queue returned by this method will be backed by the given array.
The elements of the array will be rearranged so to form a heap, and
moreover the array will be cloned and wrapped in a secondary queue (this is
more efficient than enqueing the elements of a
one by one).
This constructor uses as secondary comparator the opposite of the natural order.
refArray
- the reference array.a
- an array of indices into refArray
.Method Detail |
---|
public void enqueue(int x)
IndirectPriorityQueue
enqueue
in interface IndirectPriorityQueue<K>
enqueue
in class ObjectHeapIndirectPriorityQueue<K>
x
- the element to enqueue..public int dequeue()
IndirectPriorityQueue
dequeue
in interface IndirectPriorityQueue<K>
dequeue
in class ObjectHeapIndirectPriorityQueue<K>
public int secondaryFirst()
IndirectDoublePriorityQueue
secondaryFirst
in interface IndirectDoublePriorityQueue<K>
public int secondaryLast()
IndirectDoublePriorityQueue
secondaryLast
in interface IndirectDoublePriorityQueue<K>
public void changed()
ObjectHeapSemiIndirectPriorityQueue
The caller must guarantee that when this method is called the index of the first element appears just once in the queue. Failure to do so will bring the queue in an inconsistent state, and will cause unpredictable behaviour.
changed
in interface IndirectPriorityQueue<K>
changed
in class ObjectHeapIndirectPriorityQueue<K>
public void changed(int index)
IndirectPriorityQueue
Note that the specified element must belong to the queue.
changed
in interface IndirectPriorityQueue<K>
changed
in class ObjectHeapIndirectPriorityQueue<K>
index
- the element that has changed.public void allChanged()
ObjectHeapIndirectPriorityQueue
allChanged
in interface IndirectPriorityQueue<K>
allChanged
in class ObjectHeapIndirectPriorityQueue<K>
public void clear()
IndirectPriorityQueue
clear
in interface IndirectPriorityQueue<K>
clear
in class ObjectHeapIndirectPriorityQueue<K>
public void remove(int index)
IndirectPriorityQueue
Note that the specified element must belong to the queue.
remove
in interface IndirectPriorityQueue<K>
remove
in class ObjectHeapIndirectPriorityQueue<K>
index
- the element to be removed.public int secondaryFront(int[] a)
IndirectDoublePriorityQueue
secondaryFront
in interface IndirectDoublePriorityQueue<K>
a
- an array large enough to hold the secondary front (e.g., at least long as the reference array).
a
).IndirectPriorityQueue.front(int[])
public void trim()
ObjectHeapSemiIndirectPriorityQueue.size()
elements.
trim
in class ObjectHeapSemiIndirectPriorityQueue<K>
public java.util.Comparator<? super K> secondaryComparator()
secondaryComparator
in interface IndirectDoublePriorityQueue<K>
secondaryFirst()
|
|||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |