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
    Index of first element.
    int
    Number of elements in the queue.
    protected int
    Index of last element.
    long[]
    Contains the values in the queue.
  • Constructor Summary

    Constructors
    Constructor
    Description
    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
    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
    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
    Returns true if the queue is empty.
    long
    Returns the last (tail) item in the queue (without removing it).
    long
    Remove the first item from the queue.
    long
    removeIndex(int index)
    Removes and returns the item at the specified index.
    long
    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[]
    Reduces the size of the backing array to the size of the actual items.
    long[]
     
     

    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.
    • 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:
    • 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:
    • 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:
    • last

      public long last()
      Returns the last (tail) item in the queue (without removing it).
      Throws:
      NoSuchElementException - when queue is empty
      See Also:
    • 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