IntHeapPriorityQueue (HPPC-RT v0.7.5 API Documentation)

java.lang.Object
- com.carrotsearch.hppcrt.AbstractIntCollection
- - com.carrotsearch.hppcrt.heaps.IntHeapPriorityQueue

All Implemented Interfaces:

IntCollection, IntContainer, IntPriorityQueue, java.lang.Cloneable, java.lang.Iterable<IntCursor>
```
@Generated(date="2017-07-11T19:16:22+0200",
           value="KTypeHeapPriorityQueue.java")
public class IntHeapPriorityQueue
extends AbstractIntCollection
implements IntPriorityQueue, java.lang.Cloneable
```
A Heap-based, min-priority queue of ints. i.e. top() is the smallest element, as defined by Sedgewick: Algorithms 4th Edition (2011). It assure O(log(N)) complexity for insertion, deletion and update priority of the min element, and constant time to examine the min element by top().
Important: Ordering of elements must be defined either * by natural ordering * or by a custom comparator provided in constructors, see comparator() .

Nested Class Summary

Nested Classes
Modifier and Type Class and Description

class IntHeapPriorityQueue.ValueIterator
An iterator implementation for iterator().

Nested Classes
Modifier and Type	Class and Description
`class`	`IntHeapPriorityQueue.ValueIterator` An iterator implementation for `iterator()`.

Field Summary

Fields
Modifier and Type	Field and Description
`int[]`	`buffer` Internal array for storing the priority queue.
`protected IntComparator`	`comparator` Defines the Comparator ordering of the queue, If null, natural ordering is used.
`protected int`	`currentOccurenceToBeRemoved` The current value set for removeAll
`protected int`	`defaultValue` Default value returned when specified in methods.
`protected int`	`elementsCount` Number of elements in the queue.
`protected IntPredicate`	`removeAllOccurencesPredicate` Internal predicate for removeAll
`protected ArraySizingStrategy`	`resizer` Buffer resizing strategy.
`protected IteratorPool<IntCursor,IntHeapPriorityQueue.ValueIterator>`	`valueIteratorPool` internal pool of ValueIterator (must be created in constructor)

Fields inherited from class com.carrotsearch.hppcrt.AbstractIntCollection
containsNegateTestPredicate, containsTestPredicate, negatePredicate, testContainer, testPredicate

Constructor Summary

Constructors
Constructor and Description
`IntHeapPriorityQueue()` Default constructor: create with a default numbers of elements (`Containers.DEFAULT_EXPECTED_ELEMENTS`), using the natural ordering of `int`s.
`IntHeapPriorityQueue(int initialCapacity)` Create with an initial capacity, using the natural ordering of `int`s
`IntHeapPriorityQueue(IntComparator comp)` Create with default sizing strategy and initial capacity (`Containers.DEFAULT_EXPECTED_ELEMENTS`) using a specific Comparator.
`IntHeapPriorityQueue(IntComparator comp, int initialCapacity)` Create with a given initial capacity, using a Comparator for ordering.
`IntHeapPriorityQueue(IntComparator comp, int initialCapacity, ArraySizingStrategy resizer)` Create with a Comparator, an initial capacity, and a custom buffer resizing strategy.
`IntHeapPriorityQueue(IntContainer container)` Creates a new heap from elements of another container.

Method Summary

All Methods Static Methods Instance Methods Concrete Methods
Modifier and Type	Method and Description
`void`	`add(int element)` Insert a int into the queue.
`int`	`addAll(IntContainer container)` Adds all elements from another container.
`int`	`addAll(java.lang.Iterable<? extends IntCursor> iterable)` Adds all elements from another iterable.
`int`	`capacity()` Return the maximum number of elements this container is guaranteed to hold without reallocating.
`void`	`clear()` Removes all elements from this collection.
`IntHeapPriorityQueue`	`clone()` Clone this object.
`IntComparator`	`comparator()` Get the custom comparator used for comparing elements
`boolean`	`contains(int element)` Lookup a given element in the container.
`protected void`	`ensureBufferSpace(int expectedAdditions)` Ensures the internal buffer has enough free slots to store `expectedAdditions`.
`boolean`	`equals(java.lang.Object obj)` this instance and obj can only be equal to this if either: (both don't have set comparators) or (both have equal comparators defined by `comparator()`.equals(obj.comparator)) then, both heap elements are compared with `equals(Object)` iterating their `buffer`.
`<T extends IntPredicate> T`	`forEach(T predicate)` Applies a `predicate` to container elements, as long as the predicate returns `true`.
`<T extends IntProcedure> T`	`forEach(T procedure)` Applies a `procedure` to all container elements.
`static IntHeapPriorityQueue`	`from(int... elements)` Create a heap from a variable number of arguments or an array of `int`.
`static IntHeapPriorityQueue`	`from(IntContainer container)` Create a heap from elements of another container (constructor shortcut)
`int`	`getDefaultValue()` Returns the "default value" value used in methods returning "default value"
`int`	`hashCode()`
`IntHeapPriorityQueue.ValueIterator`	`iterator()` Returns an iterator to a cursor traversing the collection.
`int`	`popTop()` Retrieve, and remove the top element of the queue, i.e. the min element with respect to the comparison criteria (implementation defined) Returns the default value if empty.
`int`	`removeAll(int e1)` Removes all occurrences of `e` from this collection.
`int`	`removeAll(IntPredicate predicate)` Removes all elements in this collection for which the given predicate returns `true`.
`void`	`setDefaultValue(int defaultValue)` Set the "default value" value to be used in methods returning "default value"
`int`	`size()` Return the current number of elements in this container.
`int[]`	`toArray(int[] target)` Default implementation for: Copies all elements of this container to an existing array of the same type.
`int`	`top()` Retrieve, but not remove, the top element of the queue, i.e. the min element with respect to the comparison criteria (implementation defined) of the queue.
`void`	`updatePriorities()` Update priorities of all the elements of the queue, to re-establish the correct priorities towards the comparison criteria.
`void`	`updateTopPriority()` Update the priority of the `IntPriorityQueue.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.

Methods inherited from class com.carrotsearch.hppcrt.AbstractIntCollection
isEmpty, removeAll, retainAll, retainAll, toArray, toString

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

Methods inherited from interface com.carrotsearch.hppcrt.IntCollection
removeAll, retainAll, retainAll

Methods inherited from interface com.carrotsearch.hppcrt.IntContainer
isEmpty, toArray

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

- Field Detail
  - buffer
```
public int[] buffer
```
    Internal array for storing the priority queue.
    Direct priority queue iteration: iterate buffer[i] for i in [1; size()] (included) but is out-of-order w.r.t popTop()
  - elementsCount
```
protected int elementsCount
```
    Number of elements in the queue.
  - comparator
```
protected IntComparator comparator
```
    Defines the Comparator ordering of the queue, If null, natural ordering is used.
  - resizer
```
protected final ArraySizingStrategy resizer
```
    Buffer resizing strategy.
  - valueIteratorPool
```
protected final IteratorPool<IntCursor,IntHeapPriorityQueue.ValueIterator> valueIteratorPool
```
    internal pool of ValueIterator (must be created in constructor)
  - currentOccurenceToBeRemoved
```
protected int currentOccurenceToBeRemoved
```
    The current value set for removeAll
  - removeAllOccurencesPredicate
```
protected IntPredicate removeAllOccurencesPredicate
```
    Internal predicate for removeAll
  - defaultValue
```
protected int defaultValue
```
    Default value returned when specified in methods.
    
    See Also:
    
    top()
- Constructor Detail
  - IntHeapPriorityQueue
```
public IntHeapPriorityQueue(IntComparator comp,
                            int initialCapacity,
                            ArraySizingStrategy resizer)
```
    Create with a Comparator, an initial capacity, and a custom buffer resizing strategy.
  - IntHeapPriorityQueue
```
public IntHeapPriorityQueue(IntComparator comp)
```
    Create with default sizing strategy and initial capacity (Containers.DEFAULT_EXPECTED_ELEMENTS) using a specific Comparator.
    
    See Also:
    
    BoundedProportionalArraySizingStrategy
  - IntHeapPriorityQueue
```
public IntHeapPriorityQueue()
```
    Default constructor: create with a default numbers of elements (Containers.DEFAULT_EXPECTED_ELEMENTS), using the natural ordering of ints.
  - IntHeapPriorityQueue
```
public IntHeapPriorityQueue(int initialCapacity)
```
    Create with an initial capacity, using the natural ordering of ints
  - IntHeapPriorityQueue
```
public IntHeapPriorityQueue(IntComparator comp,
                            int initialCapacity)
```
    Create with a given initial capacity, using a Comparator for ordering.
    
    See Also:
    
    BoundedProportionalArraySizingStrategy
  - IntHeapPriorityQueue
```
public IntHeapPriorityQueue(IntContainer container)
```
    Creates a new heap from elements of another container.
- Method Detail
  - from
```
public static IntHeapPriorityQueue from(IntContainer container)
```
    Create a heap from elements of another container (constructor shortcut)
  - from
```
public static IntHeapPriorityQueue from(int... elements)
```
    Create a heap from a variable number of arguments or an array of int.
  - removeAll
```
public int removeAll(int e1)
```
    Removes all occurrences of e from this collection.
    
    Specified by:
    
    removeAll in interface IntCollection
    
    Parameters:
    
    e1 - Element to be removed from this collection, if present.
    
    Returns:
    
    The number of removed elements as a result of this call.
  - removeAll
```
public int removeAll(IntPredicate predicate)
```
    Removes all elements in this collection for which the given predicate returns true.
    
    Specified by:
    
    removeAll in interface IntCollection
    
    Returns:
    
    Returns the number of removed elements.
  - clear
```
public void clear()
```
    Removes all elements from this collection.
    
    Specified by:
    
    clear in interface IntCollection
  - iterator
```
public IntHeapPriorityQueue.ValueIterator iterator()
```
    Returns an iterator to a cursor traversing the collection. The order of traversal is not defined. More than one cursor may be active at a time. The behavior of iterators is undefined if structural changes are made to the underlying collection.
    The iterator is implemented as a cursor and it returns the same cursor instance on every call to Iterator.next() (to avoid boxing of primitive types). To read the current list's value (or index in the list) use the cursor's public fields. An example is shown below.
```
 for (IntCursor<int> c : container) {
   System.out.println("index=" + c.index + " value=" + c.value);
 }
 
```
    Specified by:
    
    iterator in interface IntContainer
    
    Specified by:
    
    iterator in interface java.lang.Iterable<IntCursor>
  - contains
```
public boolean contains(int element)
```
    Lookup a given element in the container. This operation has no speed guarantees (may be linear with respect to the size of this container).
    
    Specified by:
    
    contains in interface IntContainer
    
    Returns:
    
    Returns true if this container has an element equal to e.
  - size
```
public int size()
```
    Return the current number of elements in this container. The time for calculating the container's size may take O(n) time, although implementing classes should try to maintain the current size and return in constant time.
    
    Specified by:
    
    size in interface IntContainer
  - capacity
```
public int capacity()
```
    Return the maximum number of elements 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 IntContainer
  - forEach
```
public <T extends IntProcedure> T forEach(T procedure)
```
    Applies a procedure to all container elements. Returns the argument (any subclass of IntProcedure. 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 (IntContainer):
```
 int count = container.forEach(new IntProcedure() {
      int count; // this is a field declaration in an anonymous class.
      public void apply(int value) { count++; }}).count;
 
```
    Specified by:
    
    forEach in interface IntContainer
  - forEach
```
public <T extends IntPredicate> T forEach(T predicate)
```
    Applies a predicate to container elements, as long as the predicate returns true. The iteration is interrupted otherwise.
    
    Specified by:
    
    forEach in interface IntContainer
  - add
```
public void add(int element)
```
    Insert a int into the queue. cost: O(log(N)) for a N sized queue
    
    Specified by:
    
    add in interface IntPriorityQueue
  - top
```
public int top()
```
    Retrieve, but not remove, the top element of the queue, i.e. the min element with respect to the comparison criteria (implementation defined) of the queue. Returns the default value if empty. cost: O(1)
    
    Specified by:
    
    top in interface IntPriorityQueue
  - popTop
```
public int popTop()
```
    Retrieve, and remove the top element of the queue, i.e. the min element with respect to the comparison criteria (implementation defined) Returns the default value if empty. cost: O(log(N)) for a N sized queue
    
    Specified by:
    
    popTop in interface IntPriorityQueue
  - addAll
```
public int addAll(IntContainer container)
```
    Adds all elements from another container. cost: O(N*log(N)) for N elements
  - addAll
```
public int addAll(java.lang.Iterable<? extends IntCursor> iterable)
```
    Adds all elements from another iterable. cost: O(N*log(N)) for N elements
  - hashCode
```
public int hashCode()
```
    Overrides:
    
    hashCode 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))
    
    Specified by:
    
    updatePriorities in interface IntPriorityQueue
  - updateTopPriority
```
public void updateTopPriority()
```
    Update the priority of the IntPriorityQueue.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))
    
    Specified by:
    
    updateTopPriority in interface IntPriorityQueue
  - clone
```
public IntHeapPriorityQueue clone()
```
    Clone this object. The returned clone will use the same resizing strategy and comparator.
    
    Overrides:
    
    clone in class java.lang.Object
  - equals
```
public boolean equals(java.lang.Object obj)
```
    this instance and obj can only be equal to this if either:
```
 (both don't have set comparators)
 or
 (both have equal comparators defined by comparator().equals(obj.comparator))
```
    then, both heap elements are compared with equals(Object) iterating their buffer.
    Overrides:
    
    equals in class java.lang.Object
  - ensureBufferSpace
```
protected void ensureBufferSpace(int expectedAdditions)
```
    Ensures the internal buffer has enough free slots to store expectedAdditions. Increases internal buffer size if needed.
  - toArray
```
public int[] toArray(int[] target)
```
    Default implementation for: Copies all elements of this container to an existing array of the same type.
    
    Specified by:
    
    toArray in interface IntContainer
    
    Overrides:
    
    toArray in class AbstractIntCollection
    
    Parameters:
    
    target - The target array must be large enough to hold all elements, i.e >= IntContainer.size().
    
    Returns:
    
    Returns the target argument for chaining.
  - comparator
```
public IntComparator comparator()
```
    Get the custom comparator used for comparing elements
    
    Returns:
    
    null if no custom comparator was set, i.e natural ordering of ints is used instead
  - getDefaultValue
```
public int getDefaultValue()
```
    Returns the "default value" value used in methods returning "default value"
    
    Specified by:
    
    getDefaultValue in interface IntPriorityQueue
  - setDefaultValue
```
public void setDefaultValue(int defaultValue)
```
    Set the "default value" value to be used in methods returning "default value"
    
    Specified by:
    
    setDefaultValue in interface IntPriorityQueue

Class IntHeapPriorityQueue

Nested Class Summary

Field Summary

Fields inherited from class com.carrotsearch.hppcrt.AbstractIntCollection

Constructor Summary

Method Summary

Methods inherited from class com.carrotsearch.hppcrt.AbstractIntCollection

Methods inherited from class java.lang.Object

Methods inherited from interface com.carrotsearch.hppcrt.IntCollection

Methods inherited from interface com.carrotsearch.hppcrt.IntContainer

Methods inherited from interface java.lang.Iterable

Field Detail

buffer

elementsCount

comparator

resizer

valueIteratorPool

currentOccurenceToBeRemoved

removeAllOccurencesPredicate

defaultValue

Constructor Detail

IntHeapPriorityQueue

IntHeapPriorityQueue

IntHeapPriorityQueue

IntHeapPriorityQueue

IntHeapPriorityQueue

IntHeapPriorityQueue

Method Detail

from

from

removeAll

removeAll

clear

iterator

contains

size

capacity

forEach

forEach

add

top

popTop

addAll

addAll

hashCode

updatePriorities

updateTopPriority

clone

equals

ensureBufferSpace

toArray

comparator

getDefaultValue

setDefaultValue