public interface IndirectPriorityQueue<K>
An indirect priority queue provides a way to enqueue by index elements taken from a given reference list, and to dequeue them in some specified order. Elements that are smaller in the specified order are dequeued first. It is also possible to get the index of the first element, that is, the index that would be dequeued next.
Additionally, the queue may provide a method to peek at the index of the element that would be dequeued last.
The reference list should not change during queue operations (or, more precisely, the relative order of the elements corresponding to indices in the queue should not change). Nonetheless, some implementations may give the caller a way to notify the queue that the first element has changed its relative position in the order.
Optionally, an indirect priority queue may even provide methods to notify the change of any element of the reference list, to check the presence of an index in the queue, and to remove an index from the queue. It may even allow to notify that all elements have changed.
It is always possible to enqueue two distinct indices corresponding to equal elements of the reference list. However, depending on the implementation, it may or may not be possible to enqueue twice the same index.
Note that all element manipulation happens via indices.
Modifier and Type | Method and Description |
---|---|
default void |
allChanged()
Notifies this queue that the all elements have changed (optional operation).
|
default void |
changed()
Notifies this queue that the first element has changed (optional operation).
|
default void |
changed(int index)
Notifies this queue that the specified element has changed (optional operation).
|
void |
clear()
Removes all elements from this queue.
|
java.util.Comparator<? super K> |
comparator()
Returns the comparator associated with this queue, or
null if it uses its elements' natural ordering. |
default boolean |
contains(int index)
Checks whether a given index belongs to this queue (optional operation).
|
int |
dequeue()
Dequeues the first element from this queue.
|
void |
enqueue(int index)
Enqueues a new element.
|
int |
first()
Returns the first element of this queue.
|
default int |
front(int[] a)
Retrieves the front of this queue in a given array (optional operation).
|
default boolean |
isEmpty()
Checks whether this queue is empty.
|
default int |
last()
Returns the last element of this queue, that is, the element the would be dequeued last (optional operation).
|
default boolean |
remove(int index)
Removes the specified element from this queue (optional operation).
|
int |
size()
Returns the number of elements in this queue.
|
void enqueue(int index)
index
- the element to enqueue.int dequeue()
java.util.NoSuchElementException
- if this queue is empty.default boolean isEmpty()
This default implementation checks whether size()
is zero.
int size()
void clear()
int first()
java.util.NoSuchElementException
- if this queue is empty.default int last()
This default implementation just throws an UnsupportedOperationException
.
java.util.NoSuchElementException
- if this queue is empty.default void changed()
This default implementation just calls changed(int)
with argument first()
.
java.util.Comparator<? super K> comparator()
null
if it uses its elements' natural ordering.null
if it uses its elements' natural ordering.default void changed(int index)
Note that the specified element must belong to this queue.
This default implementation just throws an UnsupportedOperationException
.
index
- the element that has changed.java.util.NoSuchElementException
- if the specified element is not in this queue.default void allChanged()
This default implementation just throws an UnsupportedOperationException
.
default boolean contains(int index)
This default implementation just throws an UnsupportedOperationException
.
index
- an index possibly in the queue.default boolean remove(int index)
This default implementation just throws an UnsupportedOperationException
.
index
- the element to be removed.default int front(int[] a)
The front of an indirect queue is the set of indices whose associated elements in the reference array are equal to the element associated to the first index. These indices can be always obtain by dequeueing, but this method should retrieve efficiently such indices in the given array without modifying the state of this queue.
This default implementation just throws an UnsupportedOperationException
.
a
- an array large enough to hold the front (e.g., at least long as the reference array).a
).