Circular Buffers: A data structure for O(1) random-indexing, append, prepend, clear, dropFirst and dropLast

Revision en3, by wrick, 2017-01-31 23:27:13

Circular buffers are simple data structures that provide O(1) get, set, append, prepend, clear, dropFirst and dropLast operations. It can be implemented using 2 pointers (start and end) and an array and using modular arithmetics for indexing.

Here is a simple implementation in Java:

class CircularBuffer<T> {
private T[] array = (T[]) new Object[1<<4];
private int start = 0, end = 0;

public T get(int i) {
assert(0 <= i && i < size());
return array[mod(start + i)];
}

public void set(int i, T elem) {
assert(0 <= i && i < size());
array[mod(start + i)] = elem;
}

public void append(T elem) {
if (size() == array.length - 1) resize();
array[mod(end++)] = elem;
}

public void prepend(T elem) {
if (size() == array.length - 1) resize();
array[mod(--start)] = elem;
}

public void dropFirst(int count) {
assert(0 <= count && count <= size());
start += count;
}

public void dropLast(int count) {
assert(0 <= count && count <= size());
end -= count;
}

public int size() {
return mod(mod(end) - mod(start));
}

public void clear() {
start = end;
}

private int mod(int x) {
return Math.floorMod(x, array.length);
}

private void resize() {
T[] array2 = (T[]) new Object[2*array.length];
for(int i = 0; i < size(); i++) {
array2[i] = get(i);
}
end = size();
start = 0;
array = array2;
}
}


#### History

Revisions

Rev. Lang. By When Δ Comment
en3 wrick 2017-01-31 23:27:13 29
en2 wrick 2017-01-30 19:48:38 112
en1 wrick 2017-01-30 18:23:10 1625 Initial revision (published)