ObjectHeapPriorityQueue (HPPC-RT v0.7.5 API Documentation)

java.lang.Object
- com.carrotsearch.hppcrt.AbstractObjectCollection<KType>
- - com.carrotsearch.hppcrt.heaps.ObjectHeapPriorityQueue<KType>

All Implemented Interfaces:

ObjectCollection<KType>, ObjectContainer<KType>, ObjectPriorityQueue<KType>, java.lang.Cloneable, java.lang.Iterable<ObjectCursor<KType>>
```
@Generated(date="2017-07-11T19:16:22+0200",
           value="KTypeHeapPriorityQueue.java")
public class ObjectHeapPriorityQueue<KType>
extends AbstractObjectCollection<KType>
implements ObjectPriorityQueue<KType>, java.lang.Cloneable
```
A Heap-based, min-priority queue of Objects. 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 Comparable * or by a custom comparator provided in constructors, see comparator() .

Nested Class Summary

Nested Classes
Modifier and Type Class and Description

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

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

Field Summary

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

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

Constructor Summary

Constructors
Constructor and Description
`ObjectHeapPriorityQueue()` Default constructor: create with a default numbers of elements (`Containers.DEFAULT_EXPECTED_ELEMENTS`), using the Comparable natural ordering.
`ObjectHeapPriorityQueue(java.util.Comparator<? super KType> comp)` Create with default sizing strategy and initial capacity (`Containers.DEFAULT_EXPECTED_ELEMENTS`) using a specific Comparator.
`ObjectHeapPriorityQueue(java.util.Comparator<? super KType> comp, int initialCapacity)` Create with a given initial capacity, using a Comparator for ordering.
`ObjectHeapPriorityQueue(java.util.Comparator<? super KType> comp, int initialCapacity, ArraySizingStrategy resizer)` Create with a Comparator, an initial capacity, and a custom buffer resizing strategy.
`ObjectHeapPriorityQueue(int initialCapacity)` Create with an initial capacity, using the Comparable natural ordering
`ObjectHeapPriorityQueue(ObjectContainer<? extends KType> 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(KType element)` Insert a Object into the queue.
`int`	`addAll(java.lang.Iterable<? extends ObjectCursor<? extends KType>> iterable)` Adds all elements from another iterable.
`int`	`addAll(ObjectContainer<? extends KType> 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.
`ObjectHeapPriorityQueue<KType>`	`clone()` Clone this object.
`java.util.Comparator<? super KType>`	`comparator()` Get the custom comparator used for comparing elements
`boolean`	`contains(KType 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 ObjectPredicate<? super KType>> T`	`forEach(T predicate)` Applies a `predicate` to container elements, as long as the predicate returns `true`.
`<T extends ObjectProcedure<? super KType>> T`	`forEach(T procedure)` Applies a `procedure` to all container elements.
`static <KType> ObjectHeapPriorityQueue<KType>`	`from(KType... elements)` Create a heap from a variable number of arguments or an array of `Object`.
`static <KType> ObjectHeapPriorityQueue<KType>`	`from(ObjectContainer<KType> container)` Create a heap from elements of another container (constructor shortcut)
`KType`	`getDefaultValue()` Returns the "default value" value used in methods returning "default value"
`int`	`hashCode()`
`ObjectHeapPriorityQueue.ValueIterator`	`iterator()` Returns an iterator to a cursor traversing the collection.
`KType`	`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(KType e1)` Removes all occurrences of `e` from this collection.
`int`	`removeAll(ObjectPredicate<? super KType> predicate)` Removes all elements in this collection for which the given predicate returns `true`.
`void`	`setDefaultValue(KType 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.
`KType[]`	`toArray(KType[] target)` Default implementation for: Copies all elements of this container to an existing array of the same type.
`KType`	`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 `ObjectPriorityQueue.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.AbstractObjectCollection
isEmpty, removeAll, retainAll, retainAll, toArray, toArray, toString

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

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

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

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

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

Class ObjectHeapPriorityQueue<KType>

Nested Class Summary

Field Summary

Fields inherited from class com.carrotsearch.hppcrt.AbstractObjectCollection

Constructor Summary

Method Summary

Methods inherited from class com.carrotsearch.hppcrt.AbstractObjectCollection

Methods inherited from class java.lang.Object

Methods inherited from interface com.carrotsearch.hppcrt.ObjectCollection

Methods inherited from interface com.carrotsearch.hppcrt.ObjectContainer

Methods inherited from interface java.lang.Iterable

Field Detail

buffer

elementsCount

comparator

resizer

valueIteratorPool

currentOccurenceToBeRemoved

removeAllOccurencesPredicate

defaultValue

Constructor Detail

ObjectHeapPriorityQueue

ObjectHeapPriorityQueue

ObjectHeapPriorityQueue

ObjectHeapPriorityQueue

ObjectHeapPriorityQueue

ObjectHeapPriorityQueue

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