Package arc.struct

Class Queue<T>

java.lang.Object

arc.struct.Queue<T>

All Implemented Interfaces:

Eachable<T>, Iterable<T>

public class Queue<T>
extends Object
implements Iterable<T>, Eachable<T>

A resizable, ordered array of objects with efficient add and remove at the beginning and end. Values in the backing array may wrap back to the beginning, making add and remove at the beginning and end O(1) (unless the backing array needs to resize when adding). Deque functionality is provided via removeLast() and addFirst(Object).

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
static class	Queue.QueueIterable<T>

Field Summary

Fields

Modifier and Type	Field	Description
protected int	head	Index of first element.
int	size	Number of elements in the queue.
protected int	tail	Index of last element.
T[]	values	Contains the values in the queue.

Constructor Summary

Constructors

Constructor	Description
Queue()	Creates a new Queue which can hold 16 values without needing to resize backing array.
Queue(int initialSize)	Creates a new Queue which can hold the specified number of values without needing to resize backing array.
Queue(int initialSize, Class<T> type)	Creates a new Queue which can hold the specified number of values without needing to resize backing array.

Method Summary

Modifier and Type	Method	Description
void	add(T object)	Adds an object to the tail.
void	addFirst(T object)	Prepend given object to the head.
void	addLast(T object)	Append given object to the tail.
void	clear()	Removes all values from this queue.
boolean	contains(T value)
boolean	contains(T value, boolean identity)
void	each(Cons<? super T> c)
void	ensureCapacity(int additional)	Increases the size of the backing array to accommodate the specified number of additional items.
boolean	equals(Object o)
T	first()	Returns the first (head) item in the queue (without removing it).
T	get(int index)	Retrieves the value in queue without removing it.
int	hashCode()
int	indexOf(Boolf<T> value)
int	indexOf(T value, boolean identity)	Returns the index of first occurrence of value in the queue, or -1 if no such value exists.
boolean	isEmpty()	Returns true if the queue is empty.
Iterator<T>	iterator()	Returns an iterator for the items in the queue.
T	last()	Returns the last (tail) item in the queue (without removing it).
boolean	remove(Boolf<T> value)
boolean	remove(T value)
boolean	remove(T value, boolean identity)	Removes the first instance of the specified value in the queue.
T	removeFirst()	Remove the first item from the queue.
T	removeIndex(int index)	Removes and returns the item at the specified index.
T	removeLast()	Remove the last item from the queue.
protected void	resize(int newSize)	Resize backing array.
T[]	shrink()	Reduces the size of the backing array to the size of the actual items.
T[]	toArray(Class<T> type)
String	toString()

Methods inherited from class java.lang.Object

clone, finalize, getClass, notify, notifyAll, wait, wait, wait

Methods inherited from interface java.lang.Iterable

forEach, spliterator

Field Details

size

public int size

Number of elements in the queue.

values

public T[] values

Contains the values in the queue. Head and tail indices go in a circle around this array, wrapping at the end.

head

protected int head

Index of first element. Logically smaller than tail. Unless empty, it points to a valid element inside queue.

tail

protected int tail

Index of last element. Logically bigger than head. Usually points to an empty position, but points to the head when full (size == values.length).

Constructor Details

Queue

public Queue()

Creates a new Queue which can hold 16 values without needing to resize backing array.

Queue

public Queue(int initialSize)

Creates a new Queue which can hold the specified number of values without needing to resize backing array.

Queue

public Queue(int initialSize,
 Class<T> type)

Creates a new Queue which can hold the specified number of values without needing to resize backing array. This creates backing array of the specified type via reflection, which is necessary only when accessing the backing array directly.

Method Details

toArray

public T[] toArray(Class<T> type)

addLast

public void addLast(T object)

Append given object to the tail. (enqueue to tail) Unless backing array needs resizing, operates in O(1) time.

Parameters:

object - can be null

add

public void add(T object)

Adds an object to the tail.

addFirst

public void addFirst(T object)

Prepend given object to the head. (enqueue to head) Unless backing array needs resizing, operates in O(1) time.

Parameters:

object - can be null

See Also:

• addLast(Object)

shrink

public T[] shrink()

Reduces the size of the backing array to the size of the actual items. This is useful to release memory when many items have been removed, or if it is known that more items will not be added.

Returns:

values

ensureCapacity

public void ensureCapacity(int additional)

Increases the size of the backing array to accommodate the specified number of additional items. Useful before adding many items to avoid multiple backing array resizes.

resize

protected void resize(int newSize)

Resize backing array. newSize must be bigger than current size.

removeFirst

public T removeFirst()

Remove the first item from the queue. (dequeue from head) Always O(1).

Returns:

removed object

Throws:

NoSuchElementException - when queue is empty

removeLast

public T removeLast()

Remove the last item from the queue. (dequeue from tail) Always O(1).

Returns:

removed object

Throws:

NoSuchElementException - when queue is empty

See Also:

• removeFirst()

contains

public boolean contains(T value)

contains

public boolean contains(T value,
 boolean identity)

indexOf

public int indexOf(T value,
 boolean identity)

Returns the index of first occurrence of value in the queue, or -1 if no such value exists.

Parameters:

identity - If true, == comparison will be used. If false, .equals() comparison will be used.

Returns:

An index of first occurrence of value in queue or -1 if no such value exists

indexOf

public int indexOf(Boolf<T> value)

remove

public boolean remove(Boolf<T> value)

remove

public boolean remove(T value)

remove

public boolean remove(T value,
 boolean identity)

Removes the first instance of the specified value in the queue.

Parameters:

identity - If true, == comparison will be used. If false, .equals() comparison will be used.

Returns:

true if value was found and removed, false otherwise

removeIndex

public T removeIndex(int index)

Removes and returns the item at the specified index.

isEmpty

public boolean isEmpty()

Returns true if the queue is empty.

first

public T first()

Returns the first (head) item in the queue (without removing it).

Throws:

NoSuchElementException - when queue is empty

See Also:

• addFirst(Object)
• removeFirst()

last

public T last()

Returns the last (tail) item in the queue (without removing it).

Throws:

NoSuchElementException - when queue is empty

See Also:

• addLast(Object)
• removeLast()

get

public T get(int index)

Retrieves the value in queue without removing it. Indexing is from the front to back, zero based. Therefore get(0) is the same as first().

Throws:

IndexOutOfBoundsException - when the index is negative or >= size

clear

public void clear()

Removes all values from this queue. Values in backing array are set to null to prevent memory leak, so this operates in O(n).

iterator

public Iterator<T> iterator()

Returns an iterator for the items in the queue. Remove is supported. Note that the same iterator instance is returned each time this method is called. Use the constructor for nested or multithreaded iteration.

Specified by:

iterator in interface Iterable<T>

each

public void each(Cons<? super T> c)

Specified by:

each in interface Eachable<T>

toString

public String toString()

Overrides:

toString in class Object

hashCode

public int hashCode()

Overrides:

hashCode in class Object

equals

public boolean equals(Object o)

Overrides:

equals in class Object