it.unimi.dsi.fastutil.doubles
Class DoubleHeapSemiIndirectPriorityQueue

java.lang.Object
  extended by it.unimi.dsi.fastutil.AbstractIndirectPriorityQueue<Double>
      extended by it.unimi.dsi.fastutil.doubles.DoubleHeapSemiIndirectPriorityQueue
All Implemented Interfaces:
IndirectPriorityQueue<Double>
Direct Known Subclasses:
DoubleHeapIndirectPriorityQueue

public class DoubleHeapSemiIndirectPriorityQueue
extends AbstractIndirectPriorityQueue<Double>

A type-specific heap-based semi-indirect priority queue.

Instances of this class use as reference list a reference array, which must be provided to each constructor. The priority queue is represented using a heap. The heap is enlarged as needed, but it is never shrunk. Use the trim() method to reduce its size, if necessary.

This implementation allows one to enqueue several time the same index, but you must be careful when calling changed().


Field Summary
protected  DoubleComparator c
          The type-specific comparator used in this queue.
protected  int[] heap
          The semi-indirect heap.
protected  double[] refArray
          The reference array.
protected  int size
          The number of elements in this queue.
 
Constructor Summary
DoubleHeapSemiIndirectPriorityQueue(double[] refArray)
          Creates a new empty queue with capacity equal to the length of the reference array and using the natural order.
DoubleHeapSemiIndirectPriorityQueue(double[] refArray, DoubleComparator c)
          Creates a new empty queue with capacity equal to the length of the reference array and a given comparator.
DoubleHeapSemiIndirectPriorityQueue(double[] refArray, int capacity)
          Creates a new empty queue with given capacity and using the natural order.
DoubleHeapSemiIndirectPriorityQueue(double[] refArray, int[] a)
          Wraps a given array in a queue using the natural order.
DoubleHeapSemiIndirectPriorityQueue(double[] refArray, int[] a, DoubleComparator c)
          Wraps a given array in a queue using a given comparator.
DoubleHeapSemiIndirectPriorityQueue(double[] refArray, int[] a, int size)
          Wraps a given array in a queue using the natural order.
DoubleHeapSemiIndirectPriorityQueue(double[] refArray, int[] a, int size, DoubleComparator c)
          Wraps a given array in a queue using a given comparator.
DoubleHeapSemiIndirectPriorityQueue(double[] refArray, int capacity, DoubleComparator c)
          Creates a new empty queue without elements with a given capacity and comparator.
 
Method Summary
 void allChanged()
          Rebuilds this heap in a bottom-up fashion.
 void changed()
          Notifies this queue that the first element has changed (optional operation).
 void clear()
          Removes all elements from this queue.
 DoubleComparator comparator()
          Returns the comparator associated with this queue, or null if it uses its elements' natural ordering.
 int dequeue()
          Dequeues the first element from this queue.
 void enqueue(int x)
          Enqueues a new element.
protected  void ensureElement(int index)
          Ensures that the given index is a valid reference.
 int first()
          Returns the first element of this queue.
 int front(int[] a)
          Retrieves the front of this queue in a given array (optional operation).
 int size()
          Returns the number of elements in this queue.
 String toString()
           
 void trim()
          Trims the backing array so that it has exactly size() elements.
 
Methods inherited from class it.unimi.dsi.fastutil.AbstractIndirectPriorityQueue
changed, contains, isEmpty, last, remove
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
 

Field Detail

refArray

protected double[] refArray
The reference array.


heap

protected int[] heap
The semi-indirect heap.


size

protected int size
The number of elements in this queue.


c

protected DoubleComparator c
The type-specific comparator used in this queue.

Constructor Detail

DoubleHeapSemiIndirectPriorityQueue

public DoubleHeapSemiIndirectPriorityQueue(double[] refArray,
                                           int capacity,
                                           DoubleComparator c)
Creates a new empty queue without elements with a given capacity and comparator.

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

DoubleHeapSemiIndirectPriorityQueue

public DoubleHeapSemiIndirectPriorityQueue(double[] refArray,
                                           int capacity)
Creates a new empty queue with given capacity and using the natural order.

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

DoubleHeapSemiIndirectPriorityQueue

public DoubleHeapSemiIndirectPriorityQueue(double[] refArray,
                                           DoubleComparator c)
Creates a new empty queue with capacity equal to the length of the reference array and a given comparator.

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

DoubleHeapSemiIndirectPriorityQueue

public DoubleHeapSemiIndirectPriorityQueue(double[] refArray)
Creates a new empty queue with capacity equal to the length of the reference array and using the natural order.

Parameters:
refArray - the reference array.

DoubleHeapSemiIndirectPriorityQueue

public DoubleHeapSemiIndirectPriorityQueue(double[] refArray,
                                           int[] a,
                                           int size,
                                           DoubleComparator 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 (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 comparator used in this queue, or null for the natural order.

DoubleHeapSemiIndirectPriorityQueue

public DoubleHeapSemiIndirectPriorityQueue(double[] refArray,
                                           int[] a,
                                           DoubleComparator 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 (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 comparator used in this queue, or null for the natural order.

DoubleHeapSemiIndirectPriorityQueue

public DoubleHeapSemiIndirectPriorityQueue(double[] 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 (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.

DoubleHeapSemiIndirectPriorityQueue

public DoubleHeapSemiIndirectPriorityQueue(double[] 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 (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.
Method Detail

ensureElement

protected void ensureElement(int index)
Ensures that the given index is a valid reference.

Parameters:
index - an index in the reference array.
Throws:
IndexOutOfBoundsException - if the given index is negative or larger than the reference array length.

enqueue

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

Parameters:
x - the element to enqueue..

dequeue

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

Returns:
the dequeued element.

first

public int first()
Description copied from interface: IndirectPriorityQueue
Returns the first element of this queue.

Returns:
the first element.

changed

public void changed()
Notifies this 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<Double>
Overrides:
changed in class AbstractIndirectPriorityQueue<Double>

allChanged

public void allChanged()
Rebuilds this heap in a bottom-up fashion.

Specified by:
allChanged in interface IndirectPriorityQueue<Double>
Overrides:
allChanged in class AbstractIndirectPriorityQueue<Double>

size

public int size()
Description copied from interface: IndirectPriorityQueue
Returns the number of elements in this queue.

Returns:
the number of elements in this queue.

clear

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


trim

public void trim()
Trims the backing array so that it has exactly size() elements.


comparator

public DoubleComparator comparator()
Description copied from interface: IndirectPriorityQueue
Returns the comparator associated with this queue, or null if it uses its elements' natural ordering.

Returns:
the comparator associated with this sorted set, or null if it uses its elements' natural ordering.

front

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

The front of an indirect queue is the set of indices whose associated elements in the reference array are equal to the element associated to the first index. These indices can be always obtain by dequeueing, but this method should retrieve efficiently such indices in the given array without modifying the state of this queue.

Parameters:
a - an array large enough to hold the front (e.g., at least long as the reference array).
Returns:
the number of elements actually written (starting from the first position of a).

toString

public String toString()
Overrides:
toString in class Object


Copyright © 2011. All Rights Reserved.