it.unimi.dsi.fastutil.shorts
Class ShortHeapIndirectDoublePriorityQueue

java.lang.Object
  extended by it.unimi.dsi.fastutil.AbstractIndirectPriorityQueue<Short>
      extended by it.unimi.dsi.fastutil.shorts.ShortHeapSemiIndirectPriorityQueue
          extended by it.unimi.dsi.fastutil.shorts.ShortHeapIndirectPriorityQueue
              extended by it.unimi.dsi.fastutil.shorts.ShortHeapIndirectDoublePriorityQueue
All Implemented Interfaces:
IndirectDoublePriorityQueue<Short>, IndirectPriorityQueue<Short>, ShortIndirectDoublePriorityQueue, ShortIndirectPriorityQueue

public class ShortHeapIndirectDoublePriorityQueue
extends ShortHeapIndirectPriorityQueue
implements ShortIndirectDoublePriorityQueue

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
ShortHeapIndirectDoublePriorityQueue(short[] refArray)
          Creates a new empty queue with capacity equal to the length of the reference array and natural order as primary comparator.
ShortHeapIndirectDoublePriorityQueue(short[] refArray, int capacity)
          Creates a new empty queue with a given capacity and natural order as primary comparator.
ShortHeapIndirectDoublePriorityQueue(short[] refArray, int[] a)
          Wraps a given array in a queue using the natural order.
ShortHeapIndirectDoublePriorityQueue(short[] refArray, int[] a, int size)
          Wraps a given array in a queue using the natural order.
ShortHeapIndirectDoublePriorityQueue(short[] refArray, int[] a, int size, ShortComparator c)
          Wraps a given array in a queue using a given comparator.
ShortHeapIndirectDoublePriorityQueue(short[] refArray, int[] a, int size, ShortComparator c, ShortComparator d)
          Wraps a given array in a queue using the given comparators.
ShortHeapIndirectDoublePriorityQueue(short[] refArray, int[] a, ShortComparator c)
          Wraps a given array in a queue using a given comparator.
ShortHeapIndirectDoublePriorityQueue(short[] refArray, int[] a, ShortComparator c, ShortComparator d)
          Wraps a given array in a queue using the given comparators.
ShortHeapIndirectDoublePriorityQueue(short[] refArray, int capacity, ShortComparator c)
          Creates a new empty queue with a given capacity.
ShortHeapIndirectDoublePriorityQueue(short[] refArray, int capacity, ShortComparator c, ShortComparator d)
          Creates a new empty queue with a given capacity.
ShortHeapIndirectDoublePriorityQueue(short[] refArray, ShortComparator c)
          Creates a new empty queue with capacity equal to the length of the reference array.
ShortHeapIndirectDoublePriorityQueue(short[] refArray, ShortComparator c, ShortComparator d)
          Creates a new empty queue with capacity equal to the length of the reference array.
 
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).
 ShortComparator 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 ShortHeapSemiIndirectPriorityQueue.size() elements.
 
Methods inherited from class it.unimi.dsi.fastutil.shorts.ShortHeapSemiIndirectPriorityQueue
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.shorts.ShortIndirectPriorityQueue
comparator
 
Methods inherited from interface it.unimi.dsi.fastutil.IndirectPriorityQueue
first, front, isEmpty, last, size
 
Methods inherited from interface it.unimi.dsi.fastutil.IndirectPriorityQueue
first, front, isEmpty, last, size
 

Constructor Detail

ShortHeapIndirectDoublePriorityQueue

public ShortHeapIndirectDoublePriorityQueue(short[] refArray,
                                            int capacity,
                                            ShortComparator c,
                                            ShortComparator d)
Creates a new empty queue with a given capacity.

Parameters:
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.

ShortHeapIndirectDoublePriorityQueue

public ShortHeapIndirectDoublePriorityQueue(short[] refArray,
                                            int capacity,
                                            ShortComparator c)
Creates a new empty queue with a given capacity.

This constructor uses as secondary comparator the opposite order of c.

Parameters:
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.

ShortHeapIndirectDoublePriorityQueue

public ShortHeapIndirectDoublePriorityQueue(short[] refArray,
                                            int capacity)
Creates a new empty queue with a given capacity and natural order as primary comparator.

This constructor uses as secondary comparator the opposite of the natural order.

Parameters:
refArray - the reference array.
capacity - the initial capacity of this queue.

ShortHeapIndirectDoublePriorityQueue

public ShortHeapIndirectDoublePriorityQueue(short[] refArray,
                                            ShortComparator c,
                                            ShortComparator d)
Creates a new empty queue with capacity equal to the length of the reference array.

Parameters:
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.

ShortHeapIndirectDoublePriorityQueue

public ShortHeapIndirectDoublePriorityQueue(short[] refArray,
                                            ShortComparator c)
Creates a new empty queue with capacity equal to the length of the reference array.

This constructor uses as secondary comparator the opposite order of c.

Parameters:
refArray - the reference array.
c - the primary comparator used in this queue, or null for the natural order.

ShortHeapIndirectDoublePriorityQueue

public ShortHeapIndirectDoublePriorityQueue(short[] refArray)
Creates a new empty queue with capacity equal to the length of the reference array and natural order as primary comparator.

This constructor uses as secondary comparator the opposite of the natural order.

Parameters:
refArray - the reference array.

ShortHeapIndirectDoublePriorityQueue

public ShortHeapIndirectDoublePriorityQueue(short[] refArray,
                                            int[] a,
                                            int size,
                                            ShortComparator c,
                                            ShortComparator d)
Wraps a given array in a queue using the given comparators.

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).

Parameters:
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.

ShortHeapIndirectDoublePriorityQueue

public ShortHeapIndirectDoublePriorityQueue(short[] refArray,
                                            int[] a,
                                            ShortComparator c,
                                            ShortComparator d)
Wraps a given array in a queue using the given comparators.

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).

Parameters:
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.

ShortHeapIndirectDoublePriorityQueue

public ShortHeapIndirectDoublePriorityQueue(short[] refArray,
                                            int[] a,
                                            int size,
                                            ShortComparator c)
Wraps a given array in a queue using a given comparator.

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.

Parameters:
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.

ShortHeapIndirectDoublePriorityQueue

public ShortHeapIndirectDoublePriorityQueue(short[] refArray,
                                            int[] a,
                                            ShortComparator c)
Wraps a given array in a queue using a given comparator.

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.

Parameters:
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.

ShortHeapIndirectDoublePriorityQueue

public ShortHeapIndirectDoublePriorityQueue(short[] refArray,
                                            int[] a,
                                            int size)
Wraps a given array in a queue using the natural order.

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.

Parameters:
refArray - the reference array.
a - an array of indices into refArray.
size - the number of elements to be included in the queue.

ShortHeapIndirectDoublePriorityQueue

public ShortHeapIndirectDoublePriorityQueue(short[] refArray,
                                            int[] a)
Wraps a given array in a queue using the natural order.

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.

Parameters:
refArray - the reference array.
a - an array of indices into refArray.
Method Detail

enqueue

public void enqueue(int x)
Description copied from interface: IndirectPriorityQueue
Enqueues a new element.

Specified by:
enqueue in interface IndirectPriorityQueue<Short>
Overrides:
enqueue in class ShortHeapIndirectPriorityQueue
Parameters:
x - the element to enqueue..

dequeue

public int dequeue()
Description copied from interface: IndirectPriorityQueue
Dequeues the first element from the queue.

Specified by:
dequeue in interface IndirectPriorityQueue<Short>
Overrides:
dequeue in class ShortHeapIndirectPriorityQueue
Returns:
the dequeued element.

secondaryFirst

public int secondaryFirst()
Description copied from interface: IndirectDoublePriorityQueue
Returns the first element of this queue with respect to the secondary comparator.

Specified by:
secondaryFirst in interface IndirectDoublePriorityQueue<Short>
Returns:
the first element of this queue w.r.t. the secondary comparator.

secondaryLast

public int secondaryLast()
Description copied from interface: IndirectDoublePriorityQueue
Returns the last element of this queue with respect to the secondary comparator (optional operation).

Specified by:
secondaryLast in interface IndirectDoublePriorityQueue<Short>
Returns:
the last element of this queue w.r.t. the secondary comparator.

changed

public void changed()
Description copied from class: ShortHeapSemiIndirectPriorityQueue
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. Failure to do so will bring the queue in an inconsistent state, and will cause unpredictable behaviour.

Specified by:
changed in interface IndirectPriorityQueue<Short>
Overrides:
changed in class ShortHeapIndirectPriorityQueue

changed

public void changed(int index)
Description copied from interface: IndirectPriorityQueue
Notifies the queue that the specified element has changed (optional operation).

Note that the specified element must belong to the queue.

Specified by:
changed in interface IndirectPriorityQueue<Short>
Overrides:
changed in class ShortHeapIndirectPriorityQueue
Parameters:
index - the element that has changed.

allChanged

public void allChanged()
Description copied from class: ShortHeapIndirectPriorityQueue
Rebuilds this heap in a bottom-up fashion.

Specified by:
allChanged in interface IndirectPriorityQueue<Short>
Overrides:
allChanged in class ShortHeapIndirectPriorityQueue

clear

public void clear()
Description copied from interface: IndirectPriorityQueue
Removes all elements from this queue.

Specified by:
clear in interface IndirectPriorityQueue<Short>
Overrides:
clear in class ShortHeapIndirectPriorityQueue

remove

public void remove(int index)
Description copied from interface: IndirectPriorityQueue
Removes the specified element from the queue (optional operation).

Note that the specified element must belong to the queue.

Specified by:
remove in interface IndirectPriorityQueue<Short>
Overrides:
remove in class ShortHeapIndirectPriorityQueue
Parameters:
index - the element to be removed.

secondaryFront

public int secondaryFront(int[] a)
Description copied from interface: IndirectDoublePriorityQueue
Retrieves the secondary front of the queue in a given array (optional operation).

Specified by:
secondaryFront in interface IndirectDoublePriorityQueue<Short>
Parameters:
a - an array large enough to hold the secondary front (e.g., at least long as the reference array).
Returns:
the number of elements actually written (starting from the first position of a).
See Also:
IndirectPriorityQueue.front(int[])

trim

public void trim()
Trims the underlying queues so they have exactly ShortHeapSemiIndirectPriorityQueue.size() elements.

Overrides:
trim in class ShortHeapSemiIndirectPriorityQueue

secondaryComparator

public ShortComparator secondaryComparator()
Returns the secondary comparator of this queue.

Specified by:
secondaryComparator in interface IndirectDoublePriorityQueue<Short>
Specified by:
secondaryComparator in interface ShortIndirectDoublePriorityQueue
Returns:
the secondary comparator of this queue.
See Also:
secondaryFirst()