Class TrackedDeque<E extends TrackedDeque.Element>

java.lang.Object
de.tomatengames.util.data.TrackedDeque<E>
Type Parameters:
E - The type of the elements in the deque. Must extend TrackedDeque.Element.
All Implemented Interfaces:
Iterable<E>
public class TrackedDeque<E extends TrackedDeque.Element> extends Object implements Iterable<E>
A deque that allows efficient random-access removal.

This deque is implemented as a doubly-linked list. The links between elements are stored inside the elements themselves, allowing for efficient node searching. Therefore, the elements must extend TrackedDeque.Element and can only be present in one TrackedDeque at a time. An element cannot be present in one TrackedDeque multiple times.

This implementation does not support null elements. This implementation is not thread-safe.

Since:
1.9

  • Constructor Details

    • TrackedDeque

      public TrackedDeque()
      Creates a new and empty TrackedDeque.

  • Method Details

    • addFirst

      public void addFirst(E e)
      Inserts the specified element at the front of this deque.
      Parameters:
      e - The element to insert. Not null.
      Throws:
      IllegalArgumentException - If the element already belongs to a TrackedDeque.
      NullPointerException - If the element is null.
      Implementation Note:
      O(1)

    • addLast

      public void addLast(E e)
      Inserts the specified element at the end of this deque.
      Parameters:
      e - The element to insert. Not null.
      Throws:
      IllegalArgumentException - If the element already belongs to a TrackedDeque.
      NullPointerException - If the element is null.
      Implementation Note:
      O(1)

    • removeFirst

      public E removeFirst()
      Removes the first element of this deque and returns it.
      Returns:
      The removed element. If this deque is empty, returns null.
      Implementation Note:
      O(1)

    • removeLast

      public E removeLast()
      Removes the last element of this deque and returns it.
      Returns:
      The removed element. If this deque is empty, returns null.
      Implementation Note:
      O(1)

    • remove

      public boolean remove(TrackedDeque.Element e)
      Removes the specified element from this deque.
      Parameters:
      e - The element to remove.
      Returns:
      If the element was removed. Returns false, if the element is null or not found in this deque.
      Implementation Note:
      O(1)

    • peekFirst

      public E peekFirst()
      Returns the first element of the deque without removing it.
      Returns:
      The first element of the deque. If the deque is empty, returns null.
      Implementation Note:
      O(1)

    • peekLast

      public E peekLast()
      Returns the last element of the deque without removing it.
      Returns:
      The last element of the deque. If the deque is empty, returns null.
      Implementation Note:
      O(1)

    • contains

      public boolean contains(TrackedDeque.Element e)
      Returns if the deque contains the specified element.
      Parameters:
      e - The element to check for.
      Returns:
      true if the deque contains the specified element, false otherwise.
      Implementation Note:
      O(1)

    • clear

      public void clear()
      Removes all elements from this deque.
      Implementation Note:
      O(n)

    • size

      public long size()
      Returns the number of elements in this deque.
      Returns:
      The number of elements in this deque.

    • isEmpty

      public boolean isEmpty()
      Returns true if this deque contains no elements.
      Returns:
      If this deque contains no elements.
      Implementation Note:
      O(1)

    • forEach

      public void forEach(Consumer<? super E> action)
      Calls the provided action for each element in the deque, starting from the first element. If an action throws an exception, the iteration is immediately terminated and the exception is thrown.
      Specified by:
      forEach in interface Iterable<E extends TrackedDeque.Element>
      Parameters:
      action - The action to be performed on each element. Not null.
      Throws:
      ConcurrentModificationException - If the deque has been modified during the iteration.

    • iterator

      public Iterator<E> iterator()
      Returns an iterator over the elements of this deque in order from first to last.

      The iterator supports removal. The iterator supports late-binding.

      This method is identical to firstToLastIterator().

      Specified by:
      iterator in interface Iterable<E extends TrackedDeque.Element>
      Returns:
      The iterator. Not null.

    • firstToLastIterator

      public Iterator<E> firstToLastIterator()
      Returns an iterator over the elements of this deque in order from first to last.

      The iterator supports removal. The iterator supports late-binding.

      Returns:
      The iterator. Not null.

    • elementToLastIterator

      public Iterator<E> elementToLastIterator(E startElement)
      Returns an iterator over the elements of this deque in order from first to last, starting at the specified element. All elements before the specified element are excluded from the iteration.

      The iterator supports removal.

      Parameters:
      startElement - The starting element. Not null.
      Returns:
      The iterator. Not null.
      Throws:
      IllegalArgumentException - If the startElement is not contained in this deque.

    • lastToFirstIterator

      public Iterator<E> lastToFirstIterator()
      Returns an iterator over the elements of this deque in order from last to first.

      The iterator supports removal. The iterator supports late-binding.

      Returns:
      The iterator. Not null.

    • elementToFirstIterator

      public Iterator<E> elementToFirstIterator(E startElement)
      Returns an iterator over the elements of this deque in order from last to first, starting at the specified element. All elements after the specified element are excluded from the iteration.

      The iterator supports removal.

      Parameters:
      startElement - The starting element. Not null.
      Returns:
      The iterator. Not null.
      Throws:
      IllegalArgumentException - If the startElement is not contained in this deque.

    • stream

      public Stream<E> stream()
      Returns a stream of the elements in this deque. The stream is ordered from the first to the last element.
      Returns:
      The stream. Not null.

    • streamLastToFirst

      public Stream<E> streamLastToFirst()
      Returns a stream of the elements in this deque. The stream is ordered from the last to the first element.
      Returns:
      The stream. Not null.

    • toString

      public String toString()
      Overrides:
      toString in class Object