Package com.illumon.util.datastructures.linked

Class IntrusiveDoublyLinkedQueue<VALUE_TYPE>

java.lang.Object
com.illumon.util.datastructures.linked.IntrusiveDoublyLinkedStructureBase<VALUE_TYPE>
com.illumon.util.datastructures.linked.IntrusiveDoublyLinkedQueue<VALUE_TYPE>
All Implemented Interfaces:
Iterable<VALUE_TYPE>
public class IntrusiveDoublyLinkedQueue<VALUE_TYPE>
extends IntrusiveDoublyLinkedStructureBase<VALUE_TYPE>
implements Iterable<VALUE_TYPE>
A simple queue based on circular intrusive doubly linked nodes (for O(1) random removal).

  • Constructor Details

  • Method Details

    • isEmpty

      public final boolean isEmpty()
      Test if the queue is empty.
      Returns:
      Whether the queue is empty

    • size

      public final int size()
      Get the size of this queue.
      Returns:
      The size of the queue

    • transferBeforeHeadFrom

      public final void transferBeforeHeadFrom​(@NotNull IntrusiveDoublyLinkedQueue<VALUE_TYPE> other)
      Move all nodes from other to the front of this queue in O(1) time.
      Parameters:
      other - The queue to transfer from

    • transferAfterTailFrom

      public final void transferAfterTailFrom​(@NotNull IntrusiveDoublyLinkedQueue<VALUE_TYPE> other)
      Move all nodes from other to the back of this queue in O(1) time.
      Parameters:
      other - The queue to transfer from

    • offer

      public final boolean offer​(@NotNull VALUE_TYPE node)
      Add a node at the end of the queue.
      Parameters:
      node - The node to add
      Returns:
      true

    • insert

      public final void insert​(@NotNull VALUE_TYPE node, int offset)
      Add a node at the the specified offset into the queue. This is necessarily an O(n) operation.
      Parameters:
      node - The node to add
      offset - The offset (in [0, size()] to add the node at

    • peek

      @Nullable public final VALUE_TYPE peek()
      Get the node at the front of the queue without modifying the queue.
      Returns:
      The current head of the queue, or null if the queue is empty

    • poll

      @Nullable public final VALUE_TYPE poll()
      Remove and get the node at the front of the queue.
      Returns:
      The node at the head of the queue (now removed)

    • remove

      @NotNull public final VALUE_TYPE remove()
      Remove and get the node at the front of the queue.
      Returns:
      The node at the head of the queue (now removed)
      Throws:
      NoSuchElementException - If the queue is empty

    • remove

      public final boolean remove​(@NotNull VALUE_TYPE node)
      Remove a node from the queue.
      Parameters:
      node - The node to remove
      Returns:
      Whether the node was in the queue (and now removed)

    • clear

      public final void clear()
      Remove and unlink all nodes in the queue.

    • clearFast

      public final void clearFast()
      Remove all nodes in the queue, without unlinking anything. This is suitable for nodes that will be discarded.

    • contains

      public final boolean contains​(@NotNull VALUE_TYPE node)
      Determine if a node is currently in the queue. Assumes that the node's prev/next pointers are only used in this queue.
      Parameters:
      node - The node
      Returns:
      Whether the node is currently in the queue

    • iterator

      @NotNull public Iterator<VALUE_TYPE> iterator()
      Specified by:
      iterator in interface Iterable<VALUE_TYPE>

    • spliterator

      public Spliterator<VALUE_TYPE> spliterator()
      Specified by:
      spliterator in interface Iterable<VALUE_TYPE>

    • stream

      @NotNull public Stream<VALUE_TYPE> stream()