Package arc.struct

Class IntQueue

java.lang.Object
arc.struct.IntQueue
public class IntQueue extends Object
Queue for ints.

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

  • Constructor Summary

    Constructors
    Constructor
    Description
    IntQueue()
    Creates a new Queue which can hold 16 values without needing to resize backing array.
    IntQueue(int initialSize)
    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
    addFirst(int object)
    Prepend given object to the head.
    void
    addLast(int 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.
    int
    first()
    Returns the first (head) item in the queue (without removing it).
    int
    get(int index)
    Retrieves the value in queue without removing it.
    int
    indexOf(int 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.
    int
    last()
    Returns the last (tail) item in the queue (without removing it).
    int
    removeFirst()
    Remove the first item from the queue.
    int
    removeIndex(int index)
    Removes and returns the item at the specified index.
    int
    removeLast()
    Remove the last item from the queue.
    boolean
    removeValue(int 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, int value)
     
    int[]
    shrink()
    Reduces the size of the backing array to the size of the actual items.
    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 int[] values
      Contains the values in the queue. Head and tail indices go in a circle around this array, wrapping at the end.

    • 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

    • IntQueue

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

    • IntQueue

      public IntQueue(int initialSize)
      Creates a new Queue which can hold the specified number of values without needing to resize backing array.

  • Method Details

    • addLast

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

    • shrink

      public int[] 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 int 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 int 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:

    • indexOf

      public int indexOf(int 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(int 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 int 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 int first()
      Returns the first (head) item in the queue (without removing it).
      Throws:
      NoSuchElementException - when queue is empty
      See Also:

    • last

      public int last()
      Returns the last (tail) item in the queue (without removing it).
      Throws:
      NoSuchElementException - when queue is empty
      See Also:

    • get

      public int 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, int value)

    • clear

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

    • toString

      public String toString()
      Overrides:
      toString in class Object