ShortHeapPriorityQueue (HPPC-RT v0.7.5 API Documentation)

java.lang.Object
- com.carrotsearch.hppcrt.AbstractShortCollection
- - com.carrotsearch.hppcrt.heaps.ShortHeapPriorityQueue

All Implemented Interfaces:

ShortCollection, ShortContainer, ShortPriorityQueue, java.lang.Cloneable, java.lang.Iterable<ShortCursor>
```
@Generated(date="2017-07-11T19:16:22+0200",
           value="KTypeHeapPriorityQueue.java")
public class ShortHeapPriorityQueue
extends AbstractShortCollection
implements ShortPriorityQueue, java.lang.Cloneable
```
A Heap-based, min-priority queue of shorts. 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 ShortHeapPriorityQueue.ValueIterator
An iterator implementation for iterator().

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

Field Summary

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

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

Constructor Summary

Constructors
Constructor and Description
`ShortHeapPriorityQueue()` Default constructor: create with a default numbers of elements (`Containers.DEFAULT_EXPECTED_ELEMENTS`), using the natural ordering of `short`s.
`ShortHeapPriorityQueue(int initialCapacity)` Create with an initial capacity, using the natural ordering of `short`s
`ShortHeapPriorityQueue(ShortComparator comp)` Create with default sizing strategy and initial capacity (`Containers.DEFAULT_EXPECTED_ELEMENTS`) using a specific Comparator.
`ShortHeapPriorityQueue(ShortComparator comp, int initialCapacity)` Create with a given initial capacity, using a Comparator for ordering.
`ShortHeapPriorityQueue(ShortComparator comp, int initialCapacity, ArraySizingStrategy resizer)` Create with a Comparator, an initial capacity, and a custom buffer resizing strategy.
`ShortHeapPriorityQueue(ShortContainer 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(short element)` Insert a short into the queue.
`int`	`addAll(java.lang.Iterable<? extends ShortCursor> iterable)` Adds all elements from another iterable.
`int`	`addAll(ShortContainer container)` Adds all elements from another container.
`int`	`capacity()` Return the maximum number of elements this container is guaranteed to hold without reallocating.
`void`	`clear()` Removes all elements from this collection.
`ShortHeapPriorityQueue`	`clone()` Clone this object.
`ShortComparator`	`comparator()` Get the custom comparator used for comparing elements
`boolean`	`contains(short 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 ShortPredicate> T`	`forEach(T predicate)` Applies a `predicate` to container elements, as long as the predicate returns `true`.
`<T extends ShortProcedure> T`	`forEach(T procedure)` Applies a `procedure` to all container elements.
`static ShortHeapPriorityQueue`	`from(short... elements)` Create a heap from a variable number of arguments or an array of `short`.
`static ShortHeapPriorityQueue`	`from(ShortContainer container)` Create a heap from elements of another container (constructor shortcut)
`short`	`getDefaultValue()` Returns the "default value" value used in methods returning "default value"
`int`	`hashCode()`
`ShortHeapPriorityQueue.ValueIterator`	`iterator()` Returns an iterator to a cursor traversing the collection.
`short`	`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(short e1)` Removes all occurrences of `e` from this collection.
`int`	`removeAll(ShortPredicate predicate)` Removes all elements in this collection for which the given predicate returns `true`.
`void`	`setDefaultValue(short 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.
`short[]`	`toArray(short[] target)` Default implementation for: Copies all elements of this container to an existing array of the same type.
`short`	`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 `ShortPriorityQueue.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.AbstractShortCollection
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.ShortCollection
removeAll, retainAll, retainAll

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

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

- Field Detail
  - buffer
```
public short[] 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 ShortComparator 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<ShortCursor,ShortHeapPriorityQueue.ValueIterator> valueIteratorPool
```
    internal pool of ValueIterator (must be created in constructor)
  - currentOccurenceToBeRemoved
```
protected short currentOccurenceToBeRemoved
```
    The current value set for removeAll
  - removeAllOccurencesPredicate
```
protected ShortPredicate removeAllOccurencesPredicate
```
    Internal predicate for removeAll
  - defaultValue
```
protected short defaultValue
```
    Default value returned when specified in methods.
    
    See Also:
    
    top()
- Constructor Detail
  - ShortHeapPriorityQueue
```
public ShortHeapPriorityQueue(ShortComparator comp,
                              int initialCapacity,
                              ArraySizingStrategy resizer)
```
    Create with a Comparator, an initial capacity, and a custom buffer resizing strategy.
  - ShortHeapPriorityQueue
```
public ShortHeapPriorityQueue(ShortComparator comp)
```
    Create with default sizing strategy and initial capacity (Containers.DEFAULT_EXPECTED_ELEMENTS) using a specific Comparator.
    
    See Also:
    
    BoundedProportionalArraySizingStrategy
  - ShortHeapPriorityQueue
```
public ShortHeapPriorityQueue()
```
    Default constructor: create with a default numbers of elements (Containers.DEFAULT_EXPECTED_ELEMENTS), using the natural ordering of shorts.
  - ShortHeapPriorityQueue
```
public ShortHeapPriorityQueue(int initialCapacity)
```
    Create with an initial capacity, using the natural ordering of shorts
  - ShortHeapPriorityQueue
```
public ShortHeapPriorityQueue(ShortComparator comp,
                              int initialCapacity)
```
    Create with a given initial capacity, using a Comparator for ordering.
    
    See Also:
    
    BoundedProportionalArraySizingStrategy
  - ShortHeapPriorityQueue
```
public ShortHeapPriorityQueue(ShortContainer container)
```
    Creates a new heap from elements of another container.
- Method Detail
  - from
```
public static ShortHeapPriorityQueue from(ShortContainer container)
```
    Create a heap from elements of another container (constructor shortcut)
  - from
```
public static ShortHeapPriorityQueue from(short... elements)
```
    Create a heap from a variable number of arguments or an array of short.
  - removeAll
```
public int removeAll(short e1)
```
    Removes all occurrences of e from this collection.
    
    Specified by:
    
    removeAll in interface ShortCollection
    
    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(ShortPredicate predicate)
```
    Removes all elements in this collection for which the given predicate returns true.
    
    Specified by:
    
    removeAll in interface ShortCollection
    
    Returns:
    
    Returns the number of removed elements.
  - clear
```
public void clear()
```
    Removes all elements from this collection.
    
    Specified by:
    
    clear in interface ShortCollection
  - iterator
```
public ShortHeapPriorityQueue.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 (ShortCursor<short> c : container) {
   System.out.println("index=" + c.index + " value=" + c.value);
 }
 
```
    Specified by:
    
    iterator in interface ShortContainer
    
    Specified by:
    
    iterator in interface java.lang.Iterable<ShortCursor>
  - contains
```
public boolean contains(short 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 ShortContainer
    
    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 ShortContainer
  - 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 ShortContainer
  - forEach
```
public <T extends ShortProcedure> T forEach(T procedure)
```
    Applies a procedure to all container elements. Returns the argument (any subclass of ShortProcedure. 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 ShortContainer
  - forEach
```
public <T extends ShortPredicate> 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 ShortContainer
  - add
```
public void add(short element)
```
    Insert a short into the queue. cost: O(log(N)) for a N sized queue
    
    Specified by:
    
    add in interface ShortPriorityQueue
  - top
```
public short 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 ShortPriorityQueue
  - popTop
```
public short 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 ShortPriorityQueue
  - addAll
```
public int addAll(ShortContainer container)
```
    Adds all elements from another container. cost: O(N*log(N)) for N elements
  - addAll
```
public int addAll(java.lang.Iterable<? extends ShortCursor> 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 ShortPriorityQueue
  - updateTopPriority
```
public void updateTopPriority()
```
    Update the priority of the ShortPriorityQueue.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 ShortPriorityQueue
  - clone
```
public ShortHeapPriorityQueue 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 short[] toArray(short[] target)
```
    Default implementation for: Copies all elements of this container to an existing array of the same type.
    
    Specified by:
    
    toArray in interface ShortContainer
    
    Overrides:
    
    toArray in class AbstractShortCollection
    
    Parameters:
    
    target - The target array must be large enough to hold all elements, i.e >= ShortContainer.size().
    
    Returns:
    
    Returns the target argument for chaining.
  - comparator
```
public ShortComparator comparator()
```
    Get the custom comparator used for comparing elements
    
    Returns:
    
    null if no custom comparator was set, i.e natural ordering of shorts is used instead
  - getDefaultValue
```
public short getDefaultValue()
```
    Returns the "default value" value used in methods returning "default value"
    
    Specified by:
    
    getDefaultValue in interface ShortPriorityQueue
  - setDefaultValue
```
public void setDefaultValue(short defaultValue)
```
    Set the "default value" value to be used in methods returning "default value"
    
    Specified by:
    
    setDefaultValue in interface ShortPriorityQueue

Class ShortHeapPriorityQueue

Nested Class Summary

Field Summary

Fields inherited from class com.carrotsearch.hppcrt.AbstractShortCollection

Constructor Summary

Method Summary

Methods inherited from class com.carrotsearch.hppcrt.AbstractShortCollection

Methods inherited from class java.lang.Object

Methods inherited from interface com.carrotsearch.hppcrt.ShortCollection

Methods inherited from interface com.carrotsearch.hppcrt.ShortContainer

Methods inherited from interface java.lang.Iterable

Field Detail

buffer

elementsCount

comparator

resizer

valueIteratorPool

currentOccurenceToBeRemoved

removeAllOccurencesPredicate

defaultValue

Constructor Detail

ShortHeapPriorityQueue

ShortHeapPriorityQueue

ShortHeapPriorityQueue

ShortHeapPriorityQueue

ShortHeapPriorityQueue

ShortHeapPriorityQueue

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