Package arc.struct

Class LongQueue

java.lang.Object

arc.struct.LongQueue

public class LongQueue
extends Object

Queue for longs.

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.
long[]	values	Contains the values in the queue.

Constructor Summary

Constructors

Constructor	Description
LongQueue()	Creates a new Queue which can hold 16 values without needing to resize backing array.
LongQueue(int initialSize)	Creates a new Queue which can hold the specified number of values without needing to resize backing array.
LongQueue(long[] array)

Method Summary

Modifier and Type	Method	Description
void	addFirst(long object)	Prepend given object to the head.
void	addLast(long object)	Append given object to the tail.
void	clear()	Removes all values from this queue; O(1).
void	ensureCapacity(int additional)	Increases the size of the backing array to accommodate the specified number of additional items.
long	first()	Returns the first (head) item in the queue (without removing it).
long	get(int index)	Retrieves the value in queue without removing it.
int	indexOf(long 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.
long	last()	Returns the last (tail) item in the queue (without removing it).
long	removeFirst()	Remove the first item from the queue.
long	removeIndex(int index)	Removes and returns the item at the specified index.
long	removeLast()	Remove the last item from the queue.
boolean	removeValue(long value, boolean identity)	Removes the first instance of the specified value in the queue.
protected void	resize(int newSize)	Resize backing array.
void	set(int index, long value)
long[]	shrink()	Reduces the size of the backing array to the size of the actual items.
long[]	toArray()
String	toString()

Methods inherited from class java.lang.Object

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

Field Details

size

public int size

Number of elements in the queue.

values

public long[] 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

LongQueue

public LongQueue()

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

LongQueue

public LongQueue(int initialSize)

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

LongQueue

public LongQueue(long[] array)

Method Details

addLast

public void addLast(long 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

addFirst

public void addFirst(long 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(long)

shrink

public long[] 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 long 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 long 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()

indexOf

public int indexOf(long 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

removeValue

public boolean removeValue(long 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 long 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 long first()

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

Throws:

NoSuchElementException - when queue is empty

See Also:

• addFirst(long)
• removeFirst()

last

public long last()

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

Throws:

NoSuchElementException - when queue is empty

See Also:

• addLast(long)
• removeLast()

get

public long 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

set

public void set(int index,
 long value)

clear

public void clear()

Removes all values from this queue; O(1).

toArray

public long[] toArray()

toString

public String toString()

Overrides:

toString in class Object