Package net.sherst.util

Class FastRingBuffer<E>

java.lang.Object
net.sherst.util.FastRingBuffer<E>
Type Parameters:
E - the type of elements in the buffer
Direct Known Subclasses:
SafeRingBuffer
public class FastRingBuffer<E> extends Object
A simple fast ring buffer (circular buffer) implementation for Java.

A ring buffer is a fixed-size first in - first out buffer typically backed by an array with head and tail pointers. Elements are added to the tail of the buffer and removed from the head. When the end of the array is reached, the pointers wrap around to the beginning. When the buffer is full, adding new elements overwrites the oldest elements (but see the offer(E) and offer(E[]) methods in this implementation).

Pros: Fast, simple.

Cons: Size fixed at creation time, adding new elements overwrites the oldest ones if the buffer is full, elements can only be added or removed in FIFO order.

There are some useful look-ahead methods, peek(), peek(int), at(E), at(E[]), atSkip(E) and atSkip(E[]).

These are simple, hopefully fast, implementations. They deliberately do not implement Java's Collection or Queue interfaces, although the API is similar.

Variants:

remove() sets the underlying array slot to null to avoid memory leaks. All other remove and poll methods call remove().

clear() discards the underlying array to avoid memory leaks. removeAll() calls clear().

Elements can be null, but this means that, if peek(), poll() or remove() return null, this could be because an element was null or because the buffer was empty. Consider using isEmpty() or size() to disambiguate.

poll() might seem redundant, but is overridden in BlockingRingBuffer.

Author:
sherstDotNet@yahoo.com

  • Field Summary

    Fields
    Modifier and Type
    Field
    Description
    protected int
    capacity
     
    protected int
    count
     

  • Constructor Summary

    Constructors
    Constructor
    Description
    FastRingBuffer​(int capacity)
    Creates a new buffer.

  • Method Summary

    Modifier and Type
    Method
    Description
    boolean
    add​(E e)
    Adds an element to the buffer.
    boolean
    addAll​(E[] a)
    Adds elements to the buffer, preserving their ordering in the array.
    boolean
    addAll​(Collection<E> c)
    Adds elements to the buffer, preserving their ordering in the collection.
    boolean
    at​(E o)
    Returns true if the head of the buffer (the next element that will be removed) is equal to o, compared using Objects.equals(java.lang.Object, java.lang.Object).
    boolean
    at​(E[] a)
    Returns true if the elements at the head of the buffer (the next elements that will be removed) are equal to the contents of a, compared using Objects.equals(java.lang.Object, java.lang.Object).
    boolean
    atSkip​(E o)
    Compares the head of the buffer (the next element that will be removed) to o using Objects.equals(java.lang.Object, java.lang.Object) and removes it from the buffer if there is a match.
    boolean
    atSkip​(E[] a)
    Compares the head of the buffer (the next elements that will be removed) to a using Objects.equals(java.lang.Object, java.lang.Object) and removes them from the buffer if there is a match.
    void
    clear()
    Empties the buffer.
    boolean
    contains​(E e)
    Returns true if the buffer contains e, tested using Objects.equals(java.lang.Object, java.lang.Object).
    int
    getCapacity()
    Returns the maximum capacity of this buffer.
    boolean
    isEmpty()
    Returns true if the buffer is empty.
    boolean
    offer​(E e)
    Adds an element to the buffer if there is space for it.
    boolean
    offer​(E[] a)
    Adds elements to the buffer if there is space for them.
    boolean
    offer​(Collection<E> c)
    Adds elements to the buffer if there is space for them.
    E
    peek()
    Returns the head of the buffer (the next element that will be removed) without actually removing it.
    E
    peek​(int n)
    Returns the nth element that will be removed from the buffer, counting from 0 (peek(0) returns the first element that will be removed), or null if the buffer does not contain that many elements.
    E
    poll()
    Removes and returns the element at the head of the buffer, or null if the buffer is empty.
    E[]
    poll​(int n, Class<E> cls)
    Removes and returns n consecutive elements from the head of the buffer in the order they were added, or null if the buffer does not contain n elements.
    E
    remove()
    Removes and returns the element at the head of the buffer, or null if the buffer is empty.
    E[]
    remove​(int n, Class<E> cls)
    Removes and returns up to n consecutive elements from the head of the buffer in the order they were added.
    boolean
    removeAll()
    Empties the buffer.
    int
    size()
    Returns the number of elements in the buffer.
    int
    skip​(int n)
    Removes n elements from the head of the buffer (and discards them).
    List<E>
    toList()
     

    Methods inherited from class java.lang.Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

  • Field Details

  • Constructor Details

    • FastRingBuffer

      public FastRingBuffer​(int capacity)
      Creates a new buffer.
      Parameters:
      capacity - Maximum capacity of the buffer

  • Method Details

    • add

      public boolean add​(E e)
      Adds an element to the buffer. If the buffer is full, silently overwrites the oldest element.
      Parameters:
      e - the element to add
      Returns:
      true

    • addAll

      public boolean addAll​(E[] a)
      Adds elements to the buffer, preserving their ordering in the array. If the buffer is full, silently overwrites the oldest elements.
      Parameters:
      a - the elements to add
      Returns:
      true

    • addAll

      public boolean addAll​(Collection<E> c)
      Adds elements to the buffer, preserving their ordering in the collection. If the buffer is full, silently overwrites the oldest elements.
      Parameters:
      c - the elements to add
      Returns:
      true

    • at

      public boolean at​(E o)
      Returns true if the head of the buffer (the next element that will be removed) is equal to o, compared using Objects.equals(java.lang.Object, java.lang.Object).
      Parameters:
      o - the value to be compared
      Returns:
      true if the head of the buffer equals o; false if the buffer is empty

    • at

      public boolean at​(E[] a)
      Returns true if the elements at the head of the buffer (the next elements that will be removed) are equal to the contents of a, compared using Objects.equals(java.lang.Object, java.lang.Object).
      Parameters:
      a - the values to be compared
      Returns:
      true if the elements at head of the buffer are equal to the elements of a; false if the buffer doesn't contain enough elements to match.

    • atSkip

      public boolean atSkip​(E o)
      Compares the head of the buffer (the next element that will be removed) to o using Objects.equals(java.lang.Object, java.lang.Object) and removes it from the buffer if there is a match.
      Parameters:
      o - the value to be compared
      Returns:
      true if the head of the buffer equals o and is removed; false if the buffer is empty

    • atSkip

      public boolean atSkip​(E[] a)
      Compares the head of the buffer (the next elements that will be removed) to a using Objects.equals(java.lang.Object, java.lang.Object) and removes them from the buffer if there is a match.
      Parameters:
      a - the values to be compared
      Returns:
      true if the elements at head of the buffer are equal to the elements of a; false if the buffer doesn't contain enough elements to match.

    • clear

      public void clear()
      Empties the buffer.

    • contains

      public boolean contains​(E e)
      Returns true if the buffer contains e, tested using Objects.equals(java.lang.Object, java.lang.Object).
      Returns:
      true if the buffer contains e; false if not.

    • getCapacity

      public int getCapacity()
      Returns the maximum capacity of this buffer.
      Returns:
      the maximum capacity of this buffer

    • isEmpty

      public boolean isEmpty()
      Returns true if the buffer is empty.
      Returns:
      true if the buffer is empty

    • offer

      public boolean offer​(E e)
      Adds an element to the buffer if there is space for it.
      Parameters:
      e - the element to add.
      Returns:
      true if there was space in the buffer and the element was added

    • offer

      public boolean offer​(E[] a)
      Adds elements to the buffer if there is space for them.
      Parameters:
      e - the element to add.
      Returns:
      true if there was space in the buffer and the elements were added

    • offer

      public boolean offer​(Collection<E> c)
      Adds elements to the buffer if there is space for them.
      Parameters:
      e - the element to add.
      Returns:
      true if there was space in the buffer and the elements were added

    • peek

      public E peek()
      Returns the head of the buffer (the next element that will be removed) without actually removing it.
      Returns:
      the element at the head of the buffer or null if the buffer is empty

    • peek

      public E peek​(int n)
      Returns the nth element that will be removed from the buffer, counting from 0 (peek(0) returns the first element that will be removed), or null if the buffer does not contain that many elements.
      Parameters:
      n -
      Returns:
      the nth element that will be removed from the buffer or null if the buffer does not contain that many elements

    • poll

      public E poll()
      Removes and returns the element at the head of the buffer, or null if the buffer is empty.
      Returns:
      the element that was at the head of the buffer which was removed, or null if the buffer is empty

    • poll

      public E[] poll​(int n, Class<E> cls)
      Removes and returns n consecutive elements from the head of the buffer in the order they were added, or null if the buffer does not contain n elements.
      Parameters:
      n - the number of elements to remove
      cls - the Class of the elements in the buffer (needed to create the array)
      Returns:
      the elements that were at the head of the buffer which were removed, or null if the buffer does not contain n elements

    • remove

      public E remove()
      Removes and returns the element at the head of the buffer, or null if the buffer is empty.
      Returns:
      the element that was at the head of the buffer which was removed, or null if the buffer is empty

    • remove

      public E[] remove​(int n, Class<E> cls)
      Removes and returns up to n consecutive elements from the head of the buffer in the order they were added.
      Parameters:
      n - the number of elements to remove
      cls - the Class of the elements in the buffer (needed to create the array)
      Returns:
      the elements that were at the head of the buffer which were removed; the length of the array reflects the number of elements that were available

    • removeAll

      public boolean removeAll()
      Empties the buffer.
      Returns:
      true

    • size

      public int size()
      Returns the number of elements in the buffer.
      Returns:
      the number of elements in the buffer

    • skip

      public int skip​(int n)
      Removes n elements from the head of the buffer (and discards them). If n>size(), only size() elements are removed. Inspired by and named after similar methods in InputStreams and Readers.
      Parameters:
      n - the number of elements to remove
      Returns:
      the number of elements actually removed

    • toList

      public List<E> toList()