import org.jetbrains.annotations.NotNull;
import java.lang.reflect.Array;
import java.util.AbstractList;
import java.util.Collection;
import java.util.RandomAccess;
import java.util.Objects;
import java.util.Iterator;
import java.util.ConcurrentModificationException;
import java.util.NoSuchElementException;
import java.util.function.Consumer;
* A size-limited, circular array-backed list that automatically evicts the oldest elements
* when new elements are added and the list is at full capacity. This list dynamically
* grows up to its maximum capacity, making it ideal for scenarios requiring a fixed-size
* "rolling buffer" or "history log" where elements are primarily added and iterated.
* <p>This implementation provides constant-time {@code add}, {@code get}, and {@code set} operations.
* When the list reaches its specified max capacity, adding a new element will automatically
* evict the element at the head of the list.
* <p>The capacity of the list is always rounded up to the next power of two to optimize
* index calculations using bitwise operations. It starts with an initial capacity (default 16)
* and dynamically doubles its size until it hits the max capacity.
@SuppressWarnings({"unchecked", "unused"})
public final class EvictingRingList<E> extends AbstractList<E> implements RandomAccess {
private static final int DEFAULT_INITIAL_CAPACITY = 16;
private Object[] elements;
private final int maxCapacity;
public EvictingRingList(int requestedMaxCapacity) {
if (requestedMaxCapacity <= 0) {
throw new IllegalArgumentException("Capacity must be positive");
this.maxCapacity = tableSizeFor(requestedMaxCapacity);
int initialCapacity = Math.min(DEFAULT_INITIAL_CAPACITY, this.maxCapacity);
this.elements = new Object[initialCapacity];
this.mask = initialCapacity - 1;
private static int tableSizeFor(int cap) {
return (n < 0) ? 1 : n + 1;
public EvictingRingList(Collection<? extends E> c) {
this(Math.max(1, c.size()));
int oldCapacity = elements.length;
int newCapacity = oldCapacity << 1;
Object[] newElements = new Object[newCapacity];
int firstPart = oldCapacity - head;
System.arraycopy(elements, head, newElements, 0, firstPart);
System.arraycopy(elements, 0, newElements, firstPart, head);
this.elements = newElements;
this.mask = newCapacity - 1;
public boolean add(E e) {
if (size == elements.length) {
if (elements.length < maxCapacity) {
head = (head + 1) & mask;
size--; // for the size++ call below
tail = (tail + 1) & mask;
public E get(int index) {
Objects.checkIndex(index, size);
return (E) elements[(head + index) & mask];
public E set(int index, E element) {
Objects.checkIndex(index, size);
int realIndex = (head + index) & mask;
E oldValue = (E) elements[realIndex];
elements[realIndex] = element;
public E remove(int index) {
Objects.checkIndex(index, size);
int realIndex = (head + index) & mask;
E oldValue = (E) elements[realIndex];
for (int i = index; i < size - 1; i++) {
int current = (head + i) & mask;
int next = (head + i + 1) & mask;
elements[current] = elements[next];
int lastIndex = (head + size - 1) & mask;
elements[lastIndex] = null;
tail = (tail - 1) & mask;
public int indexOf(Object o) {
for (int i = 0; i < size; i++) {
if (Objects.equals(o, get(i))) {
public int lastIndexOf(Object o) {
for (int i = size - 1; i >= 0; i--) {
if (Objects.equals(o, get(i))) {
public boolean contains(Object o) {
public boolean isEmpty() {
Arrays.fill(elements, head, tail, null);
Arrays.fill(elements, head, elements.length, null);
Arrays.fill(elements, 0, tail, null);
public void forEach(Consumer<? super E> action) {
Objects.requireNonNull(action);
final int expectedModCount = modCount;
final int currentSize = this.size;
for (int count = 0; count < currentSize; count++) {
action.accept((E) elements[i]);
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
public Object @NotNull[] toArray() {
Object[] result = new Object[size];
System.arraycopy(elements, head, result, 0, size);
int firstPart = elements.length - head;
System.arraycopy(elements, head, result, 0, firstPart);
System.arraycopy(elements, 0, result, firstPart, tail);
public <T> T @NotNull [] toArray(T[] a) {
a = (T[]) Array.newInstance(a.getClass().getComponentType(), size);
System.arraycopy(elements, head, a, 0, size);
int firstPart = elements.length - head;
System.arraycopy(elements, head, a, 0, firstPart);
System.arraycopy(elements, 0, a, firstPart, tail);
public @NotNull Iterator<E> iterator() {
return new RingIterator();
private class RingIterator implements Iterator<E> {
private int lastRet = -1;
private int expectedModCount;
this.expectedModCount = modCount;
public boolean hasNext() {
checkForComodification();
throw new NoSuchElementException();
E e = (E) elements[cursor];
cursor = (cursor + 1) & mask;
throw new IllegalStateException();
checkForComodification();
int logicalIndex = (lastRet - head) & mask;
EvictingRingList.this.remove(logicalIndex);
expectedModCount = modCount;
} catch (IndexOutOfBoundsException e) {
throw new ConcurrentModificationException();
final void checkForComodification() {
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();