DoubleIndexedHeapPriorityQueue (HPPC-RT v0.7.5 API Documentation)

java.lang.Object
- com.carrotsearch.hppcrt.heaps.DoubleIndexedHeapPriorityQueue

All Implemented Interfaces:

IntDoubleAssociativeContainer, IntDoubleMap, java.lang.Cloneable, java.lang.Iterable<IntDoubleCursor>
```
@Generated(date="2017-07-11T19:16:23+0200",
           value="KTypeIndexedHeapPriorityQueue.java")
public class DoubleIndexedHeapPriorityQueue
extends java.lang.Object
implements IntDoubleMap, java.lang.Cloneable
```
A Heap-based, indexed min-priority queue of doubles, i.e. top() is the smallest element of the queue. as defined by Sedgewick: Algorithms 4th Edition (2011). This class is also a IntDoubleMap, and acts like a (K,V) = (int, double) map with >= 0 keys. It assures O(log(N)) complexity for insertion, deletion, updating priorities, and constant time to examine the min element by top() and for containsKey(int).
Important: Ordering of elements must be defined either * by natural ordering * or by a custom comparator provided in constructors, see comparator() .
Warning : This implementation uses direct indexing, meaning that a map at any given time is only able to have int keys in the [0 ; capacity()[ range. So when a put(int, double) occurs, the map may be resized to be able hold a key exceeding the current capacity.

Nested Class Summary

Nested Classes
Modifier and Type	Class and Description
`class`	`DoubleIndexedHeapPriorityQueue.EntryIterator` An iterator implementation for `iterator()` entries.
`class`	`DoubleIndexedHeapPriorityQueue.KeysCollection` A view of the keys inside this Indexed heap.
`class`	`DoubleIndexedHeapPriorityQueue.KeysIterator` An iterator over the set of assigned keys.
`class`	`DoubleIndexedHeapPriorityQueue.ValuesCollection` A view over the set of values of this map.
`class`	`DoubleIndexedHeapPriorityQueue.ValuesIterator` An iterator over the set of assigned values.

Field Summary

Fields
Modifier and Type	Field and Description
`double[]`	`buffer` Internal array for storing the priority queue.
`protected DoubleComparator`	`comparator` Defines the Comparator ordering of the queue, If null, natural ordering is used.
`protected double`	`defaultValue`
`protected int`	`elementsCount` Number of elements in the queue.
`protected IteratorPool<IntDoubleCursor,DoubleIndexedHeapPriorityQueue.EntryIterator>`	`entryIteratorPool` internal pool of EntryIterator (must be created in constructor)
`int[]`	`pq` Internal array for storing index to buffer position matching i.e for an index i, pq[i] is the position of element in priority queue buffer.
`protected int[]`	`qp` Internal array pq inversing : i.e for a priority buffer position pos, qp[pos] is the index of the value., ie qp[pq\|i]] = i

Constructor Summary

Constructors
Constructor and Description
`DoubleIndexedHeapPriorityQueue()` Default constructor: create with a default numbers of elements (`Containers.DEFAULT_EXPECTED_ELEMENTS`), using the natural ordering of `double`s.
`DoubleIndexedHeapPriorityQueue(DoubleComparator comp)` Create with default sizing strategy and initial capacity for storing `Containers.DEFAULT_EXPECTED_ELEMENTS` elements.
`DoubleIndexedHeapPriorityQueue(DoubleComparator comp, int initialCapacity)` Create with a given initial capacity, using a Comparator for ordering.
`DoubleIndexedHeapPriorityQueue(int initialCapacity)` Create with an initial capacity, using the natural ordering of `double`s
`DoubleIndexedHeapPriorityQueue(IntDoubleAssociativeContainer container)` Create a indexed heap from all key-value pairs of another container.

Method Summary

All Methods Static Methods Instance Methods Concrete Methods
Modifier and Type	Method and Description
`double`	`addTo(int key, double incrementValue)` Adds `incrementValue` to any existing value for the given `key` or inserts `incrementValue` if `key` did not previously exist.
`int`	`capacity()` Return the maximum number of keys this container is guaranteed to hold without reallocating.
`void`	`clear()` Clear all keys and values in the container.
`DoubleIndexedHeapPriorityQueue`	`clone()` Clone this object.
`DoubleComparator`	`comparator()` Get the custom comparator used for comparing elements
`boolean`	`containsKey(int key)` Returns `true` if this container has an association to a value for the given key.
`protected void`	`ensureBufferSpace(int index)` Ensures the internal buffer has enough free slots to accommodate the index `index`.
`boolean`	`equals(java.lang.Object obj)` this instance and obj can only be equal if either: (both don't have set comparators) or (both have equal comparators defined by `comparator()`.equals(obj.comparator)) then the indexed heaps are considered equal as IntDoubleMap are.
`<T extends IntDoublePredicate> T`	`forEach(T predicate)` Applies a `predicate` to container elements, as long as the predicate returns `true`.
`<T extends IntDoubleProcedure> T`	`forEach(T procedure)` Applies a given procedure to all keys-value pairs in this container.
`static DoubleIndexedHeapPriorityQueue`	`from(int[] keys, double[] values)` Creates a Indexed heap from two index-aligned arrays of key-value pairs.
`static DoubleIndexedHeapPriorityQueue`	`from(IntDoubleAssociativeContainer container)` Create a indexed heap from all key-value pairs of another container..
`double`	`get(int key)` cost: O(1)
`double`	`getDefaultValue()` Returns the "default value" value used in methods returning "default value"
`int`	`hashCode()`
`boolean`	`isEmpty()`
`DoubleIndexedHeapPriorityQueue.EntryIterator`	`iterator()` Returns a cursor over the entries (key-value pairs) in this map.
`DoubleIndexedHeapPriorityQueue.KeysCollection`	`keys()` Returns a collection view of keys of this container.
`double`	`popTop()` Retrieve, and remove the top element of the queue, i.e. the min/max element with respect to the comparison criteria (implementation defined) Returns the default value if empty.
`double`	`put(int key, double element)` Place a given key and value in the container.
`int`	`putAll(IntDoubleAssociativeContainer container)` Puts all keys from another container to this map, replacing the values of existing keys, if such keys are present.
`int`	`putAll(java.lang.Iterable<? extends IntDoubleCursor> iterable)` Puts all keys from an iterable cursor to this map, replacing the values of existing keys, if such keys are present.
`boolean`	`putIfAbsent(int key, double value)` Trove-inspired API method.
`double`	`putOrAdd(int key, double putValue, double incrementValue)` If `key` exists, `putValue` is inserted into the map, otherwise any existing value is incremented by `additionValue`.
`double`	`remove(int key)` Remove the (key, value) pair associated with the given key, and returns the assocaited value.
`int`	`removeAll(IntContainer container)` Removes all keys (and associated values) present in a given container.
`int`	`removeAll(IntDoublePredicate predicate)` Removes all keys (and associated values) for which the predicate on (key, value) pairs returns `true`.
`int`	`removeAll(IntPredicate predicate)` Removes all keys (and associated values) for which the predicate on keys returns `true`.
`void`	`setDefaultValue(double defaultValue)` Set the "default value" value to be used in methods returning the "default value"
`int`	`size()`
`double`	`top()` Retrieve, but not remove, the top element of the queue, i.e. the min. element with respect to the comparison criteria of the queue.
`int`	`topKey()` Retrieve the key corresponding to the top element of the queue, i.e. the min element with respect to the comparison criteria of the queue.
`java.lang.String`	`toString()`
`void`	`updatePriorities()` Update priorities of all the elements of the queue, to re-establish the correct priorities towards the comparison criteria. cost: O(n*log(N))
`void`	`updatePriority(int key)` Update the priority of the value associated with key, to re-establish the value correct priority towards the comparison criteria.
`void`	`updateTopPriority()` Update the priority of the `top()` element, to re-establish its actual priority towards the comparison criteria when it may have changed such that it is no longer the min element with respect to the comparison criteria.
`DoubleIndexedHeapPriorityQueue.ValuesCollection`	`values()` Returns a collection view of all values present in this container.

Methods inherited from class java.lang.Object
finalize, getClass, notify, notifyAll, wait, wait, wait

Methods inherited from interface java.lang.Iterable
forEach, spliterator

- Field Detail
  - buffer
```
public double[] buffer
```
    Internal array for storing the priority queue.
    Direct indexed priority queue iteration: iterate pq[i] for i in [0; pq.length[ and buffer[pq[i]] to get value where pq[i] > 0
  - pq
```
public int[] pq
```
    Internal array for storing index to buffer position matching i.e for an index i, pq[i] is the position of element in priority queue buffer.
    Direct iteration: iterate pq[i] for indices i in [0; pq.length[ where pq[i] > 0, then buffer[pq[i]] is the value associated with index i.
  - qp
```
protected int[] qp
```
    Internal array pq inversing : i.e for a priority buffer position pos, qp[pos] is the index of the value., ie qp[pq|i]] = i
  - elementsCount
```
protected int elementsCount
```
    Number of elements in the queue.
  - comparator
```
protected DoubleComparator comparator
```
    Defines the Comparator ordering of the queue, If null, natural ordering is used.
  - defaultValue
```
protected double defaultValue
```
  - entryIteratorPool
```
protected final IteratorPool<IntDoubleCursor,DoubleIndexedHeapPriorityQueue.EntryIterator> entryIteratorPool
```
    internal pool of EntryIterator (must be created in constructor)
- Constructor Detail
  - DoubleIndexedHeapPriorityQueue
```
public DoubleIndexedHeapPriorityQueue(DoubleComparator comp,
                                      int initialCapacity)
```
    Create with a given initial capacity, using a Comparator for ordering.
  - DoubleIndexedHeapPriorityQueue
```
public DoubleIndexedHeapPriorityQueue(DoubleComparator comp)
```
    Create with default sizing strategy and initial capacity for storing Containers.DEFAULT_EXPECTED_ELEMENTS elements.
    
    See Also:
    
    BoundedProportionalArraySizingStrategy
  - DoubleIndexedHeapPriorityQueue
```
public DoubleIndexedHeapPriorityQueue()
```
    Default constructor: create with a default numbers of elements (Containers.DEFAULT_EXPECTED_ELEMENTS), using the natural ordering of doubles.
  - DoubleIndexedHeapPriorityQueue
```
public DoubleIndexedHeapPriorityQueue(int initialCapacity)
```
    Create with an initial capacity, using the natural ordering of doubles
  - DoubleIndexedHeapPriorityQueue
```
public DoubleIndexedHeapPriorityQueue(IntDoubleAssociativeContainer container)
```
    Create a indexed heap from all key-value pairs of another container.
- Method Detail
  - from
```
public static DoubleIndexedHeapPriorityQueue from(IntDoubleAssociativeContainer container)
```
    Create a indexed heap from all key-value pairs of another container.. (constructor shortcut)
  - from
```
public static DoubleIndexedHeapPriorityQueue from(int[] keys,
                                                  double[] values)
```
    Creates a Indexed heap from two index-aligned arrays of key-value pairs.
  - clear
```
public void clear()
```
    Clear all keys and values in the container.
    
    Specified by:
    
    clear in interface IntDoubleMap
  - iterator
```
public DoubleIndexedHeapPriorityQueue.EntryIterator iterator()
```
    Returns a cursor over the entries (key-value pairs) in this map. The iterator is implemented as a cursor and it returns the same cursor instance on every call to Iterator.next(). To read the current key and value use the cursor's public fields. An example is shown below.
```
 for (IntShortCursor c : intShortMap)
 {
     System.out.println("index=" + c.index
       + " key=" + c.key
       + " value=" + c.value);
 }
 
```
    The index field inside the cursor gives the internal index inside the container's implementation. The interpretation of this index depends on to the container.
    Specified by:
    
    iterator in interface IntDoubleAssociativeContainer
    
    Specified by:
    
    iterator in interface java.lang.Iterable<IntDoubleCursor>
  - size
```
public int size()
```
    Specified by:
    
    size in interface IntDoubleAssociativeContainer
    
    Returns:
    
    Returns the current size (number of assigned keys) in the container.
  - capacity
```
public int capacity()
```
    Return the maximum number of keys this container is guaranteed to hold without reallocating. The time for calculating the container's capacity may take O(n) time.
    
    Specified by:
    
    capacity in interface IntDoubleAssociativeContainer
  - forEach
```
public <T extends IntDoubleProcedure> T forEach(T procedure)
```
    Applies a given procedure to all keys-value pairs in this container. Returns the argument (any subclass of IntDoubleProcedure. This lets the caller to call methods of the argument by chaining the call (even if the argument is an anonymous type) to retrieve computed values, for example.
    
    Specified by:
    
    forEach in interface IntDoubleAssociativeContainer
  - forEach
```
public <T extends IntDoublePredicate> T forEach(T predicate)
```
    Applies a predicate to container elements, as long as the predicate returns true. The iteration is interrupted otherwise. Returns the argument (any subclass of IntDoublePredicate. This lets the caller to call methods of the argument by chaining the call (even if the argument is an anonymous type) to retrieve computed values, for example. The iteration is continued as long as the predicate returns true.
    
    Specified by:
    
    forEach in interface IntDoubleAssociativeContainer
  - isEmpty
```
public boolean isEmpty()
```
    Specified by:
    
    isEmpty in interface IntDoubleAssociativeContainer
    
    Returns:
    
    Return true if this hash map contains no assigned keys.
  - removeAll
```
public int removeAll(IntContainer container)
```
    Removes all keys (and associated values) present in a given container.
    
    Specified by:
    
    removeAll in interface IntDoubleAssociativeContainer
    
    Returns:
    
    Returns the number of elements actually removed as a result of this call.
  - removeAll
```
public int removeAll(IntPredicate predicate)
```
    Removes all keys (and associated values) for which the predicate on keys returns true.
    
    Specified by:
    
    removeAll in interface IntDoubleAssociativeContainer
    
    Returns:
    
    Returns the number of elements actually removed as a result of this call.
  - removeAll
```
public int removeAll(IntDoublePredicate predicate)
```
    Removes all keys (and associated values) for which the predicate on (key, value) pairs returns true.
    
    Specified by:
    
    removeAll in interface IntDoubleAssociativeContainer
    
    Returns:
    
    Returns the number of elements actually removed as a result of this call.
  - putIfAbsent
```
public boolean putIfAbsent(int key,
                           double value)
```
    Trove-inspired API method. An equivalent of the following code:
```
 if (!map.containsKey(key))
      map.put(key, value);
 
```
    Specified by:
    
    putIfAbsent in interface IntDoubleMap
    
    Parameters:
    
    key - The key of the value to check.
    
    value - The value to put if key does not exist.
    
    Returns:
    
    true if key did not exist and value was placed in the map.
  - putAll
```
public int putAll(IntDoubleAssociativeContainer container)
```
    Puts all keys from another container to this map, replacing the values of existing keys, if such keys are present.
    
    Specified by:
    
    putAll in interface IntDoubleMap
    
    Returns:
    
    Returns the number of keys added to the map as a result of this call (not previously present in the map). Values of existing keys are overwritten.
  - putAll
```
public int putAll(java.lang.Iterable<? extends IntDoubleCursor> iterable)
```
    Puts all keys from an iterable cursor to this map, replacing the values of existing keys, if such keys are present.
    
    Specified by:
    
    putAll in interface IntDoubleMap
    
    Returns:
    
    Returns the number of keys added to the map as a result of this call (not previously present in the map). Values of existing keys are overwritten.
  - put
```
public double put(int key,
                  double element)
```
    Place a given key and value in the container. cost: O(log(N)) for a N sized queue
    Important: Whenever a new (key, value) pair is inserted, or a value is updated with an already present key as specified by the IntDoubleMap.put(int, double) contract, the inserted value priority is always consistent towards the comparison criteria. In other words, there is no need to call updatePriority(int) after a put(int, double).
    
    Specified by:
    
    put in interface IntDoubleMap
    
    Parameters:
    
    key - the integer key, must be >= 0
    
    element - the associated value
    
    Returns:
    
    Returns the value previously stored under the given key, if an equal key is already in the map and replaces the existing value only with the argument value. If the given key was not already in the map, the given (key, value) pair is inserted in the map and the default value is returned.
  - putOrAdd
```
public double putOrAdd(int key,
                       double putValue,
                       double incrementValue)
```
    If key exists, putValue is inserted into the map, otherwise any existing value is incremented by additionValue.
    
    Specified by:
    
    putOrAdd in interface IntDoubleMap
    
    Parameters:
    
    key - The key of the value to adjust.
    
    putValue - The value to put if key does not exist.
    
    incrementValue - The value to add to the existing value if key exists.
    
    Returns:
    
    Returns the current value associated with key (after changes).
  - addTo
```
public double addTo(int key,
                    double incrementValue)
```
    Adds incrementValue to any existing value for the given key or inserts incrementValue if key did not previously exist.
    
    Specified by:
    
    addTo in interface IntDoubleMap
    
    Parameters:
    
    key - The key of the value to adjust.
    
    incrementValue - The value to put or add to the existing value if key exists.
    
    Returns:
    
    Returns the current value associated with key (after changes).
  - top
```
public double top()
```
    Retrieve, but not remove, the top element of the queue, i.e. the min. element with respect to the comparison criteria of the queue. Returns the default value if empty. cost: O(1)
  - topKey
```
public int topKey()
```
    Retrieve the key corresponding to the top element of the queue, i.e. the min element with respect to the comparison criteria of the queue. Returns -1 if empty. cost: O(1)
  - popTop
```
public double popTop()
```
    Retrieve, and remove the top element of the queue, i.e. the min/max element with respect to the comparison criteria (implementation defined) Returns the default value if empty. cost: O(log(N)) for a N sized queue
  - get
```
public double get(int key)
```
    cost: O(1)
    
    Specified by:
    
    get in interface IntDoubleMap
    
    Returns:
    
    Returns the value associated with the given key, or the default value if the key is not associated with any value.
  - remove
```
public double remove(int key)
```
    Remove the (key, value) pair associated with the given key, and returns the assocaited value. The default value is returned if the key did not exist in the map. cost: O(log(N))
    
    Specified by:
    
    remove in interface IntDoubleMap
  - updatePriority
```
public void updatePriority(int key)
```
    Update the priority of the value associated with key, to re-establish the value correct priority towards the comparison criteria. cost: O(log(N))
  - updateTopPriority
```
public void updateTopPriority()
```
    Update the priority of the top() element, to re-establish its actual priority towards the comparison criteria when it may have changed such that it is no longer the min element with respect to the comparison criteria. cost: O(log(N))
  - containsKey
```
public boolean containsKey(int key)
```
    Returns true if this container has an association to a value for the given key. cost: O(1)
    
    Specified by:
    
    containsKey in interface IntDoubleAssociativeContainer
  - hashCode
```
public int hashCode()
```
    Overrides:
    
    hashCode in class java.lang.Object
  - equals
```
public boolean equals(java.lang.Object obj)
```
    this instance and obj can only be equal if either:
```
 (both don't have set comparators)
 or
 (both have equal comparators defined by comparator().equals(obj.comparator))
```
    then the indexed heaps are considered equal as IntDoubleMap are.
    Overrides:
    
    equals in class java.lang.Object
  - clone
```
public DoubleIndexedHeapPriorityQueue clone()
```
    Clone this object. The returned clone will use the same comparator.
    
    Overrides:
    
    clone in class java.lang.Object
  - updatePriorities
```
public void updatePriorities()
```
    Update priorities of all the elements of the queue, to re-establish the correct priorities towards the comparison criteria. cost: O(n*log(N))
  - keys
```
public DoubleIndexedHeapPriorityQueue.KeysCollection keys()
```
    Description copied from interface: IntDoubleAssociativeContainer
    
    Returns a collection view of keys of this container. The returned collection is a view over the key set and any modifications (if allowed) introduced to the collection will propagate to the associative container immediately.
    
    Specified by:
    
    keys in interface IntDoubleAssociativeContainer
    
    Returns:
    
    a new KeysCollection view of the keys of this associated container. This view then reflects all changes from the heap.
  - values
```
public DoubleIndexedHeapPriorityQueue.ValuesCollection values()
```
    Description copied from interface: IntDoubleAssociativeContainer
    
    Returns a collection view of all values present in this container. The returned collection is a view over the value set and any modifications (if allowed) introduced to the collection will propagate to the associative container immediately.
    
    Specified by:
    
    values in interface IntDoubleAssociativeContainer
    
    Returns:
    
    a new ValuesCollection, view of the values of this indexed heap. This view then reflects all changes from the heap.
  - toString
```
public java.lang.String toString()
```
    Overrides:
    
    toString in class java.lang.Object
  - getDefaultValue
```
public double getDefaultValue()
```
    Returns the "default value" value used in methods returning "default value"
    
    Specified by:
    
    getDefaultValue in interface IntDoubleMap
  - setDefaultValue
```
public void setDefaultValue(double defaultValue)
```
    Set the "default value" value to be used in methods returning the "default value"
    
    Specified by:
    
    setDefaultValue in interface IntDoubleMap
  - comparator
```
public DoubleComparator comparator()
```
    Get the custom comparator used for comparing elements
    
    Returns:
    
    null if no custom comparator was set, i.e natural ordering of doubles is used instead
  - ensureBufferSpace
```
protected void ensureBufferSpace(int index)
```
    Ensures the internal buffer has enough free slots to accommodate the index index. Increases internal buffer size if needed.

Class DoubleIndexedHeapPriorityQueue

Nested Class Summary

Field Summary

Constructor Summary

Method Summary

Methods inherited from class java.lang.Object

Methods inherited from interface java.lang.Iterable

Field Detail

buffer

pq

qp

elementsCount

comparator

defaultValue

entryIteratorPool

Constructor Detail

DoubleIndexedHeapPriorityQueue

DoubleIndexedHeapPriorityQueue

DoubleIndexedHeapPriorityQueue

DoubleIndexedHeapPriorityQueue

DoubleIndexedHeapPriorityQueue

Method Detail

from

from

clear

iterator

size

capacity

forEach

forEach

isEmpty

removeAll

removeAll

removeAll

putIfAbsent

putAll

putAll

put

putOrAdd

addTo

top

topKey

popTop

get

remove

updatePriority

updateTopPriority

containsKey

hashCode

equals

clone

updatePriorities

keys

values

toString

getDefaultValue

setDefaultValue

comparator

ensureBufferSpace