it.unimi.dsi.fastutil.bytes
Class ByteHeapIndirectDoublePriorityQueue

java.lang.Object
  it.unimi.dsi.fastutil.AbstractIndirectPriorityQueue
      it.unimi.dsi.fastutil.bytes.ByteHeapSemiIndirectPriorityQueue
          it.unimi.dsi.fastutil.bytes.ByteHeapIndirectPriorityQueue
              it.unimi.dsi.fastutil.bytes.ByteHeapIndirectDoublePriorityQueue

All Implemented Interfaces:

IndirectDoublePriorityQueue, IndirectPriorityQueue

public class ByteHeapIndirectDoublePriorityQueue

extends ByteHeapIndirectPriorityQueue

implements IndirectDoublePriorityQueue

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

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

ByteHeapIndirectDoublePriorityQueue(byte[] refArray, ByteComparator c)
Creates a new empty queue with capacity equal to the length of the reference array.

ByteHeapIndirectDoublePriorityQueue(byte[] refArray, ByteComparator c, ByteComparator d)
Creates a new empty queue with capacity equal to the length of the reference array.

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

ByteHeapIndirectDoublePriorityQueue(byte[] refArray, int[] a)
Wraps a given array in a queue using the natural order.

ByteHeapIndirectDoublePriorityQueue(byte[] refArray, int[] a, ByteComparator c)
Wraps a given array in a queue using a given comparator.

ByteHeapIndirectDoublePriorityQueue(byte[] refArray, int[] a, ByteComparator c, ByteComparator d)
Wraps a given array in a queue using the given comparators.

ByteHeapIndirectDoublePriorityQueue(byte[] refArray, int[] a, int size)
Wraps a given array in a queue using the natural order.

ByteHeapIndirectDoublePriorityQueue(byte[] refArray, int[] a, int size, ByteComparator c)
Wraps a given array in a queue using a given comparator.

ByteHeapIndirectDoublePriorityQueue(byte[] refArray, int[] a, int size, ByteComparator c, ByteComparator d)
Wraps a given array in a queue using the given comparators.

ByteHeapIndirectDoublePriorityQueue(byte[] refArray, int capacity, ByteComparator c)
Creates a new empty queue with a given capacity.

ByteHeapIndirectDoublePriorityQueue(byte[] refArray, int capacity, ByteComparator c, ByteComparator d)
Creates a new empty queue with a given capacity.

Method Summary

void	allChanged() Notifies the queue that the all elements have changed (optional operation).
void	changed() Notifies the queue that the first element has changed (optional operation).
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).
Comparator	secondaryComparator() Returns the secondary comparator of this queue.
int	secondaryFirst() Returns the first element of this queue with respect to the secondary comparator.
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 ByteHeapSemiIndirectPriorityQueue.size() elements.

Methods inherited from class it.unimi.dsi.fastutil.bytes.ByteHeapSemiIndirectPriorityQueue

comparator, first, 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, isEmpty, last, size

Constructor Detail

ByteHeapIndirectDoublePriorityQueue

public ByteHeapIndirectDoublePriorityQueue(byte[] refArray,
                                           int capacity,
                                           ByteComparator c,
                                           ByteComparator 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.

ByteHeapIndirectDoublePriorityQueue

public ByteHeapIndirectDoublePriorityQueue(byte[] refArray,
                                           int capacity,
                                           ByteComparator 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.

ByteHeapIndirectDoublePriorityQueue

public ByteHeapIndirectDoublePriorityQueue(byte[] 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.

ByteHeapIndirectDoublePriorityQueue

public ByteHeapIndirectDoublePriorityQueue(byte[] refArray,
                                           ByteComparator c,
                                           ByteComparator 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.

ByteHeapIndirectDoublePriorityQueue

public ByteHeapIndirectDoublePriorityQueue(byte[] refArray,
                                           ByteComparator 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.

ByteHeapIndirectDoublePriorityQueue

public ByteHeapIndirectDoublePriorityQueue(byte[] 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.

ByteHeapIndirectDoublePriorityQueue

public ByteHeapIndirectDoublePriorityQueue(byte[] refArray,
                                           int[] a,
                                           int size,
                                           ByteComparator c,
                                           ByteComparator 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.

ByteHeapIndirectDoublePriorityQueue

public ByteHeapIndirectDoublePriorityQueue(byte[] refArray,
                                           int[] a,
                                           ByteComparator c,
                                           ByteComparator 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.

ByteHeapIndirectDoublePriorityQueue

public ByteHeapIndirectDoublePriorityQueue(byte[] refArray,
                                           int[] a,
                                           int size,
                                           ByteComparator 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.

ByteHeapIndirectDoublePriorityQueue

public ByteHeapIndirectDoublePriorityQueue(byte[] refArray,
                                           int[] a,
                                           ByteComparator 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.

ByteHeapIndirectDoublePriorityQueue

public ByteHeapIndirectDoublePriorityQueue(byte[] 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.

ByteHeapIndirectDoublePriorityQueue

public ByteHeapIndirectDoublePriorityQueue(byte[] 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

Overrides:

enqueue in class ByteHeapIndirectPriorityQueue

dequeue

public int dequeue()

Description copied from interface: IndirectPriorityQueue

Dequeues the first element from the queue.

Specified by:

dequeue in interface IndirectPriorityQueue

Overrides:

dequeue in class ByteHeapIndirectPriorityQueue

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

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

Returns:

the last element of this queue w.r.t. the secondary comparator.

changed

public void changed()

Description copied from interface: IndirectPriorityQueue

Notifies the queue that the first element has changed (optional operation).

Specified by:

changed in interface IndirectPriorityQueue

Overrides:

changed in class ByteHeapIndirectPriorityQueue

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

Overrides:

changed in class ByteHeapIndirectPriorityQueue

allChanged

public void allChanged()

Description copied from interface: IndirectPriorityQueue

Notifies the queue that the all elements have changed (optional operation).

Specified by:

allChanged in interface IndirectPriorityQueue

Overrides:

allChanged in class ByteHeapIndirectPriorityQueue

clear

public void clear()

Description copied from interface: IndirectPriorityQueue

Removes all elements from this queue.

Specified by:

clear in interface IndirectPriorityQueue

Overrides:

clear in class ByteHeapIndirectPriorityQueue

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

Overrides:

remove in class ByteHeapIndirectPriorityQueue

trim

public void trim()

Trims the underlying queues so they have exactly ByteHeapSemiIndirectPriorityQueue.size() elements.

Overrides:

trim in class ByteHeapSemiIndirectPriorityQueue

secondaryComparator

public Comparator secondaryComparator()

Returns the secondary comparator of this queue.

Specified by:

secondaryComparator in interface IndirectDoublePriorityQueue

Returns:

the secondary comparator of this queue.

See Also:

secondaryFirst()