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 is ideal for
* scenarios requiring a fixed-size "rolling buffer" or "history log" where elements
* are primarily added and iterated, and the oldest elements are implicitly removed
* to make space for new ones.
* <p>This implementation provides constant-time {@code add}, {@code get}, and {@code set} operations.
* When the list reaches its specified capacity, adding a new element will automatically
* evict the element at the head of the list, ensuring the list's size never exceeds its capacity.
* <p>The {@code remove(int index)}, {@code indexOf(Object o)}, and {@code lastIndexOf(Object o)}
* operations run in linear time (O(n)). Iteration over the elements also takes time proportional
* to the number of elements in 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.
@SuppressWarnings({"unchecked", "unused"})
public final class EvictingRingList<E> extends AbstractList<E> implements RandomAccess {
private final Object[] elements;
private final int capacity;
public EvictingRingList(int requestedCapacity) {
if (requestedCapacity <= 0) {
throw new IllegalArgumentException("Capacity must be positive");
this.capacity = tableSizeFor(requestedCapacity);
this.mask = this.capacity - 1;
this.elements = new Object[this.capacity];
private static int tableSizeFor(int cap) {
return (n < 0) ? 1 : n + 1;
public EvictingRingList(Collection<? extends E> c) {
this(Math.max(1, c.size()));
public boolean add(E e) {
tail = (tail + 1) & mask;
head = (head + 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, capacity, null);
Arrays.fill(elements, 0, tail, null);
public void forEach(Consumer<? super E> action) {
Objects.requireNonNull(action);
final int expectedModCount = modCount;
final int size = this.size;
for (int count = 0; count < size; 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 = capacity - 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 = capacity - head;
System.arraycopy(elements, head, a, 0, firstPart);
System.arraycopy(elements, 0, a, firstPart, tail);
private void rangeCheck(int index) {
Objects.checkIndex(index, size);
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();