http://fastutil.di.unimi.it/: fastutil extends the Java Collections Framework by providing type-specific maps, sets, lists and priority queues with a small memory footprint and fast access and insertion; provides also big (64-bit) arrays, sets and lists, and fast, practical I/O classes for binary and text files.
  • Sebastiano Vigna 
package it.unimi.dsi.fastutil;

/*
 * Copyright (C) 2003-2019 Paolo Boldi and Sebastiano Vigna
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */


import java.util.Comparator;
import java.util.NoSuchElementException;


An indirect priority queue.

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.

/** An indirect priority queue.
 *
 * <p>An indirect priority queue provides a way to {@linkplain #enqueue(int)
 * enqueue} by index elements taken from a given <em>reference list</em>,
 * and to {@linkplain #dequeue() dequeue} them in some specified order.
 * Elements that are <em>smaller</em> in the specified order are
 * dequeued first. It
 * is also possible to get the {@linkplain #first() index of the first element}, that
 * is, the index that would be dequeued next.
 *
 * <p>Additionally, the queue may provide a method to peek at the index of the
 * element that would be dequeued {@linkplain #last() last}.
 *
 * <p>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 {@linkplain #changed() first element has changed its
 * relative position in the order}.
 *
 * <p>Optionally, an indirect priority queue may even provide methods to notify
 * {@linkplain #changed(int) the change of <em>any</em> element of the
 * reference list}, to check {@linkplain #contains(int) the presence of
 * an index in the queue}, and to {@linkplain #remove(int) remove an index from the queue}.
 * It may even allow to notify that {@linkplain #allChanged() all elements have changed}.
 *
 * <p>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.
 *
 * <p>Note that <em>all element manipulation happens via indices</em>.
 */

public interface IndirectPriorityQueue<K> {

	
Enqueues a new element.

Params:
  • index – the element to enqueue.
/** Enqueues a new element.
	 *
	 * @param index the element to enqueue.
	 */

	void enqueue(int index);

	
Dequeues the first element from this queue. 
Throws:
Returns:the dequeued element.
/** Dequeues the {@linkplain #first() first} element from this queue.
	 *
	 * @return the dequeued element.
	 * @throws NoSuchElementException if this queue is empty.
	 */

	int dequeue();

	
Checks whether this queue is empty.

This default implementation checks whether size() is zero. 
Returns:true if this queue is empty.
/** Checks whether this queue is empty.
	 *
	 * <P>This default implementation checks whether {@link #size()} is zero.
	 * @return true if this queue is empty.
	 */

	default boolean isEmpty() { return size() == 0; }

	
Returns the number of elements in this queue.

Returns:the number of elements in this queue.
/** Returns the number of elements in this queue.
	 *
	 * @return the number of elements in this queue.
	 */

	int size();

	
Removes all elements from this queue.

/** Removes all elements from this queue.
	 */

	void clear();

	
Returns the first element of this queue.

Throws:
Returns:the first element.
/** Returns the first element of this queue.
	 *
	 * @return the first element.
	 * @throws NoSuchElementException if this queue is empty.
	 */

	int first();

	
Returns the last element of this queue, that is, the element the would be dequeued last (optional operation).

This default implementation just throws an UnsupportedOperationException. 
Throws:
Returns:the last element.
/** Returns the last element of this queue, that is, the element the would be dequeued last (optional operation).
	 *
	 * <p>This default implementation just throws an {@link UnsupportedOperationException}.
	 *
	 * @return the last element.
	 * @throws NoSuchElementException if this queue is empty.
	 */

	default int last() { throw new UnsupportedOperationException(); }

	
Notifies this queue that the first element has changed (optional operation). 
This default implementation just calls changed(int) with argument first(). 
/** Notifies this queue that the {@linkplain #first() first element} has changed (optional operation).
	 *
	 * <p>This default implementation just calls {@link #changed(int)} with argument {@link #first()}.
	 */

	default void changed() {
		changed(first());
	}

	
Returns the comparator associated with this queue, or null if it uses its elements' natural ordering. 
Returns:the comparator associated with this sorted set, or null if it uses its elements' natural ordering.
/** Returns the comparator associated with this queue, or {@code null} if it uses its elements' natural ordering.
	 *
	 * @return the comparator associated with this sorted set, or {@code null} if it uses its elements' natural ordering.
	 */
	Comparator <? super K> comparator();

	
Notifies this queue that the specified element has changed (optional operation).

Note that the specified element must belong to this queue.

This default implementation just throws an UnsupportedOperationException. 
Params:
  • index – the element that has changed.
Throws:
/** Notifies this queue that the specified element has changed (optional operation).
	 *
	 * <p>Note that the specified element must belong to this queue.
	 *
	 * <p>This default implementation just throws an {@link UnsupportedOperationException}.
	 *
	 * @param index the element that has changed.
	 * @throws NoSuchElementException if the specified element is not in this queue.
	 */

	default void changed(int index) { throw new UnsupportedOperationException(); }


	
Notifies this queue that the all elements have changed (optional operation).

This default implementation just throws an UnsupportedOperationException. 
/** Notifies this queue that the all elements have changed (optional operation).
	 *
	 * <p>This default implementation just throws an {@link UnsupportedOperationException}.
	 */

	default void allChanged() { throw new UnsupportedOperationException(); }

	
Checks whether a given index belongs to this queue (optional operation).

This default implementation just throws an UnsupportedOperationException. 
Params:
  • index – an index possibly in the queue.
Returns:true if the specified index belongs to this queue.
/** Checks whether a given index belongs to this queue (optional operation).
	 *
	 * <p>This default implementation just throws an {@link UnsupportedOperationException}.
	 * @param index an index possibly in the queue.
	 * @return true if the specified index belongs to this queue.
	 */
	default boolean contains(int index) { throw new UnsupportedOperationException(); }

	
Removes the specified element from this queue (optional operation).

This default implementation just throws an UnsupportedOperationException. 
Params:
  • index – the element to be removed.
Returns:true if the index was in the queue.
/** Removes the specified element from this queue (optional operation).
	 *
	 * <p>This default implementation just throws an {@link UnsupportedOperationException}.
	 * @param index the element to be removed.
	 * @return true if the index was in the queue.
	 */

	default boolean remove(int index) { throw new UnsupportedOperationException(); }

	
Retrieves the front of this queue in a given array (optional operation).

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. 
Params:
  • a – an array large enough to hold the front (e.g., at least long as the reference array).
Returns:the number of elements actually written (starting from the first position of a).
/** Retrieves the front of this queue in a given array (optional operation).
	 *
	 * <p>The <em>front</em> of an indirect queue is the set of indices whose associated elements in the reference array
	 * are equal to the element associated to the {@linkplain #first() 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.
	 *
	 * <p>This default implementation just throws an {@link UnsupportedOperationException}.
	 *
	 * @param a an array large enough to hold the front (e.g., at least long as the reference array).
	 * @return the number of elements actually written (starting from the first position of {@code a}).
	 */

	default int front(final int[] a) { throw new UnsupportedOperationException(); }
}