Package arc.struct

Class IntQueue

java.lang.Object
arc.struct.IntQueue
All Implemented Interfaces:
Iterable<Integer>
public class IntQueue extends Object implements Iterable<Integer>
Queue for ints.

  • Nested Class Summary

    Nested Classes
    Modifier and Type
    Class
    Description
    static class 
    IntQueue.IntQueueIterator
     

  • 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
    each(Intc consumer)
     
    void
    ensureCapacity(int additional)
    Increases the size of the backing array to accommodate the specified number of additional items.
    boolean
    equals(Object o)
     
    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
    hashCode()
     
    int
    indexOf(int value)
    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.
    IntQueue.IntQueueIterator
    iterator()
    Returns an iterator for the items in this queue.
    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)
    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, 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 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

    • each

      public void each(Intc consumer)

    • 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)
      Returns the index of first occurrence of value in the queue, or -1 if no such value exists.
      Returns:
      An index of first occurrence of value in queue or -1 if no such value exists

    • removeValue

      public boolean removeValue(int value)
      Removes the first instance of the specified value in the queue.
      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).

    • hashCode

      public int hashCode()
      Overrides:
      hashCode in class Object

    • equals

      public boolean equals(Object o)
      Overrides:
      equals in class Object

    • toString

      public String toString()
      Overrides:
      toString in class Object

    • iterator

      public IntQueue.IntQueueIterator iterator()
      Returns an iterator for the items in this queue. Remove is supported. Note that the same iterator instance is returned each time this method is called. Use the IntQueue.IntQueueIterator constructor for nested or multithreaded iteration.
      Specified by:
      iterator in interface Iterable<Integer>