Package icyllis.arc3d.engine

# Class PriorityQueue<E>

java.lang.Object
java.util.AbstractCollection<E>
java.util.AbstractQueue<E>
icyllis.arc3d.engine.PriorityQueue<E>

Type Parameters:
  `E` - the type of elements held in this queue

All Implemented Interfaces:
  `Iterable<E>`, `Collection<E>`, `Queue<E>`

public class PriorityQueue<E> extends AbstractQueue<E>
Similar to `PriorityQueue`, but supports `PriorityQueue.Access`.

- ## Nested Class Summary

  Nested Classes
  Modifier and Type
  Class
  Description
  `static interface`
  `PriorityQueue.Access<E>`
  This allows us to store the index into the element itself to improve the performance of inserting or removing elements.

- ## Field Summary

  Fields
  Modifier and Type
  Field
  Description
  `protected PriorityQueue.Access<? super E>`
  `mAccess`
  The type-specific index accessor used in this queue.
  `protected Comparator<? super E>`
  `mComparator`
  The type-specific comparator used in this queue.
  `protected E[]`
  `mHeap`
  The heap array.
  `protected int`
  `mSize`
  The number of elements in this queue.

- ## Constructor Summary

  Constructors
  Constructor
  Description
  `PriorityQueue()`
  `PriorityQueue(int priority)`
  `PriorityQueue(int capacity, PriorityQueue.Access<? super E> access)`
  `PriorityQueue(int capacity, Comparator<? super E> comparator, PriorityQueue.Access<? super E> access)`
  Creates a `PriorityQueue` with a given capacity, comparator and index accessor.
  `PriorityQueue(PriorityQueue.Access<? super E> access)`
  `PriorityQueue(Comparator<? super E> comparator, PriorityQueue.Access<? super E> access)`

- ## Method Summary

  Modifier and Type
  Method
  Description
  `PriorityQueue.Access<? super E>`
  `access()`
  `boolean`
  `add(E e)`
  Inserts the specified element into this priority queue.
  `void`
  `clear()`
  Removes all of the elements from this priority queue.
  `Comparator<? super E>`
  `comparator()`
  Returns the comparator used to order the elements in this queue, or `null` if this queue is sorted according to the natural ordering of its elements.
  `boolean`
  `contains(Object o)`
  Returns `true` if this queue contains the specified element.
  `E`
  `elementAt(int i)`
  Gets the ith element in priority queue.
  `void`
  `heap()`
  Makes the current array into a heap.
  `Iterator<E>`
  `iterator()`
  Returns an iterator over the elements in this queue.
  `boolean`
  `offer(E e)`
  Inserts the specified element into this priority queue.
  `E`
  `peek()`
  `E`
  `poll()`
  `boolean`
  `remove(Object o)`
  Removes a single instance of the specified element from this queue, if it is present.
  `void`
  `removeAt(int i)`
  Removes the ith element from queue.
  `int`
  `size()`
  `void`
  `sort()`
  Sorts the queue into priority order.
  `Object[]`
  `toArray()`
  Returns an array containing all of the elements in this queue.
  `<T> T[]`
  `toArray(T[] a)`
  Returns an array containing all of the elements in this queue; the runtime type of the returned array is that of the specified array.
  `void`
  `trim()`
  Trims the underlying heap array so that it has exactly `size()` elements.

  ### Methods inherited from class java.util.AbstractQueue

  `addAll, element, remove`

  ### Methods inherited from class java.util.AbstractCollection

  `containsAll, isEmpty, removeAll, retainAll, toString`

  ### Methods inherited from class java.lang.Object

  `clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait`

  ### Methods inherited from interface java.util.Collection

  `containsAll, equals, hashCode, isEmpty, parallelStream, removeAll, removeIf, retainAll, spliterator, stream, toArray`

  ### Methods inherited from interface java.lang.Iterable

  `forEach`

- ## Field Details

  - ### mHeap

    protected transient E[] mHeap
    The heap array.

  - ### mSize

    protected int mSize
    The number of elements in this queue.

  - ### mComparator

    protected Comparator<? super E> mComparator
    The type-specific comparator used in this queue.

  - ### mAccess

    protected PriorityQueue.Access<? super E> mAccess
    The type-specific index accessor used in this queue.

- ## Constructor Details

  - ### PriorityQueue

    public PriorityQueue()

  - ### PriorityQueue

    public PriorityQueue(int priority)

  - ### PriorityQueue

    public PriorityQueue(PriorityQueue.Access<? super E> access)

  - ### PriorityQueue

    public PriorityQueue(int capacity, PriorityQueue.Access<? super E> access)

  - ### PriorityQueue

    public PriorityQueue(Comparator<? super E> comparator, PriorityQueue.Access<? super E> access)

  - ### PriorityQueue

    public PriorityQueue(int capacity, Comparator<? super E> comparator, PriorityQueue.Access<? super E> access)
    Creates a `PriorityQueue` with a given capacity, comparator and index accessor.
    Parameters:
      `capacity` - the initial capacity of this queue.
      `comparator` - the comparator used in this queue, or `null` for the natural order.
      `access` - the index accessor used in this queue, or `null`.

- ## Method Details

  - ### add

    public boolean add(E e)
    Inserts the specified element into this priority queue.
    Specified by:
      `add` in interface `Collection<E>`
    Specified by:
      `add` in interface `Queue<E>`
    Overrides:
      `add` in class `AbstractQueue<E>`
    Returns:
      `true` (as specified by `Collection.add(E)`)
    Throws:
      `ClassCastException` - if the specified element cannot be compared with elements currently in this priority queue according to the priority queue's ordering
      `NullPointerException` - if the specified element is null

  - ### offer

    public boolean offer(E e)
    Inserts the specified element into this priority queue.
    Returns:
      `true` (as specified by `Queue.offer(E)`)
    Throws:
      `ClassCastException` - if the specified element cannot be compared with elements currently in this priority queue according to the priority queue's ordering
      `NullPointerException` - if the specified element is null

  - ### peek

    public E peek()

  - ### remove

    public boolean remove(Object o)
    Removes a single instance of the specified element from this queue, if it is present. More formally, removes an element `e` such that `o.equals(e)`, if this queue contains one or more such elements. Returns `true` if and only if this queue contained the specified element (or equivalently, if this queue changed as a result of the call).
    Specified by:
      `remove` in interface `Collection<E>`
    Overrides:
      `remove` in class `AbstractCollection<E>`
    Parameters:
      `o` - element to be removed from this queue, if present
    Returns:
      `true` if this queue changed as a result of the call

  - ### contains

    public boolean contains(Object o)
    Returns `true` if this queue contains the specified element. More formally, returns `true` if and only if this queue contains at least one element `e` such that `o.equals(e)`.
    Specified by:
      `contains` in interface `Collection<E>`
    Overrides:
      `contains` in class `AbstractCollection<E>`
    Parameters:
      `o` - object to be checked for containment in this queue
    Returns:
      `true` if this queue contains the specified element

  - ### toArray

    public Object[] toArray()
    Returns an array containing all of the elements in this queue. The elements are in no particular order.

    The returned array will be "safe" in that no references to it are maintained by this queue. (In other words, this method must allocate a new array). The caller is thus free to modify the returned array.

    This method acts as bridge between array-based and collection-based APIs.

    Specified by:
      `toArray` in interface `Collection<E>`
    Overrides:
      `toArray` in class `AbstractCollection<E>`
    Returns:
      an array containing all of the elements in this queue

  - ### toArray

    public <T> T[] toArray(T[] a)
    Returns an array containing all of the elements in this queue; the runtime type of the returned array is that of the specified array. The returned array elements are in no particular order. If the queue fits in the specified array, it is returned therein. Otherwise, a new array is allocated with the runtime type of the specified array and the size of this queue.

    If the queue fits in the specified array with room to spare (i.e., the array has more elements than the queue), the element in the array immediately following the end of the collection is set to `null`.

    Like the `toArray()` method, this method acts as bridge between array-based and collection-based APIs. Further, this method allows precise control over the runtime type of the output array, and may, under certain circumstances, be used to save allocation costs.

    Suppose `x` is a queue known to contain only strings. The following code can be used to dump the queue into a newly allocated array of `String`:

         String[] y = x.toArray(new String[0]);

    Note that `toArray(new Object[0])` is identical in function to `toArray()`.

    Specified by:
      `toArray` in interface `Collection<E>`
    Overrides:
      `toArray` in class `AbstractCollection<E>`
    Parameters:
      `a` - the array into which the elements of the queue are to be stored, if it is big enough; otherwise, a new array of the same runtime type is allocated for this purpose.
    Returns:
      an array containing all of the elements in this queue
    Throws:
      `ArrayStoreException` - if the runtime type of the specified array is not a supertype of the runtime type of every element in this queue
      `NullPointerException` - if the specified array is null

  - ### iterator

    public Iterator<E> iterator()
    Returns an iterator over the elements in this queue. The iterator does not return the elements in any particular order.
    Specified by:
      `iterator` in interface `Collection<E>`
    Specified by:
      `iterator` in interface `Iterable<E>`
    Specified by:
      `iterator` in class `AbstractCollection<E>`
    Returns:
      an iterator over the elements in this queue

  - ### size

    public int size()
    Specified by:
      `size` in interface `Collection<E>`
    Specified by:
      `size` in class `AbstractCollection<E>`

  - ### clear

    public void clear()
    Removes all of the elements from this priority queue. The queue will be empty after this call returns.
    Specified by:
      `clear` in interface `Collection<E>`
    Overrides:
      `clear` in class `AbstractQueue<E>`

  - ### poll

    public E poll()

  - ### removeAt

    public void removeAt(int i)
    Removes the ith element from queue.

  - ### elementAt

    public E elementAt(int i)
    Gets the ith element in priority queue. `elementAt(0)` is equivalent to `peek()`. Otherwise, there is no guarantee about ordering of elements in the queue.

  - ### sort

    public void sort()
    Sorts the queue into priority order. The queue is only guaranteed to remain in sorted order until any other operation, other than `elementAt(int)`, is performed.

  - ### heap

    public void heap()
    Makes the current array into a heap.

  - ### trim

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

  - ### comparator

    public Comparator<? super E> comparator()
    Returns the comparator used to order the elements in this queue, or `null` if this queue is sorted according to the natural ordering of its elements.
    Returns:
      the comparator used to order this queue, or `null` if this queue is sorted according to the natural ordering of its elements

  - ### access

    public PriorityQueue.Access<? super E> access()