wrick's blog

By wrick, history, 5 years ago, In English

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;
  }
}

Source: https://gist.github.com/pathikrit/eac29538af53abf7e827a74e110fb0ac

 
 
 
 
  • Vote: I like it
  • +22
  • Vote: I do not like it

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In the function mod , why are you using Math.floorMod

»
5 years ago, # |
  Vote: I like it +13 Vote: I do not like it

In c++ you can just use deque.

»
5 years ago, # |
  Vote: I like it +5 Vote: I do not like it
  • »
    »
    5 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Ah there was a bug in the "resize" check. Fixed now. Thanks for pointing it out!