Last active
October 28, 2018 05:02
-
-
Save pathikrit/eac29538af53abf7e827a74e110fb0ac to your computer and use it in GitHub Desktop.
A circular (or ring) buffer: O(1) random-indexing (get/set), append, prepend, dropFirst, dropLast, clear
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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; | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment