CircularArrayList

gistfile1.java

/*
Copyright (c) 2015 Frode Carlsen

Permission is hereby granted, free of charge, to any person obtaining a copy of this software 
and associated documentation files (the "Software"), to deal in the Software without restriction,
including without limitation the rights to use, copy, modify, merge, publish, distribute, 
sublicense, and/or sell copies of the Software, and to permit persons to whom the Software 
is furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in all copies
or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, 
INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR 
A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS
OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, 
WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, 
OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
*/

/**
 * Circular list with silent overwrite of 'oldest' entries making it suitable for sliding window implementations.  
 * Items by default added to 'tail'.  
 * NOTE: Once 'end' passes size of buffer, it silently overwrites entries beginning at 'head'.
*/
public class CircularBuffer<E> extends AbstractList<E> implements RandomAccess {

    private long head = 0L;
    private long tail = 0L;
    private final Object[] buf;
    
    public CircularBuffer(int size) {
        buf = new Object[size];
    }

    public int capacity() {
        return buf.length;
    }

    private void rightShiftBlock(int startIndex, int endIndex) {
        assert (endIndex > startIndex);
        for (int i = endIndex - 1; i >= startIndex; i--) {
            set(i + 1, get(i));
        }
    }

    private void leftShiftBlock(int startIndex, int endIndex) {
        assert (endIndex > startIndex);
        for (int i = startIndex + 1; i < endIndex; i++) {
            set(i - 1, get(i));
        }
    }

    @Override
    public int size() {
        return (int) (tail - head);
    }

    @SuppressWarnings("unchecked")
    @Override
    public E get(int i) {
        int s = size();
        if (i < 0 || i >= s) {
            throw new IndexOutOfBoundsException();
        }
        return (E) buf[index(i)];
    }

    private int index(int i) {
        return (int) ((head + i) % (buf.length));
    }

    @SuppressWarnings("unchecked")
    @Override
    public E set(int i, E e) {
        if (i < 0 || i > size()) {
            throw new IndexOutOfBoundsException();
        }
        int index = index(i);
        E current = (E) buf[index];
        buf[index] = e;
        return current;
    }

    @Override
    public void add(int i, E e) {
        int s = size();
        if (i < 0 || i > s) {
            throw new IndexOutOfBoundsException();
        }

        if (i < s) {

            if (tail < buf.length) {
                rightShiftBlock(i, Math.max(buf.length, s) - 1);
                set(i, e);
            } else if (tail >= buf.length) {
                leftShiftBlock(0, i + 1);
                set(Math.max(i - 1, 0), e);
                return;
            }
        } else {
            set(i, e);
        }

        tail++;
        if (tail > buf.length) {
            head++;
        }
    }

    @Override
    public Iterator<E> iterator() {
        return new Itr();
    }

    @Override
    public E remove(int i) {
        int s = size();
        if (i < 0 || i >= s) {
            throw new IndexOutOfBoundsException();
        }
        E e = get(i);
        set(i, null);
        if (i > 0) {
            rightShiftBlock(0, i);
        }
        head++;
        return e;
    }

    /** from java.util.ArrayList . */
    public class Itr implements Iterator<E> {
        /**
         * Index of element to be returned by subsequent call to next.
         */
        int cursor = 0;

        /**
         * Index of element returned by most recent call to next or
         * previous. Reset to -1 if this element is deleted by a call
         * to remove.
         */
        int lastRet = -1;

        /**
         * The modCount value that the iterator believes that the backing
         * List should have. If this expectation is violated, the iterator
         * has detected concurrent modification.
         */
        int expectedModCount = modCount;

        @Override
        public boolean hasNext() {
            return cursor != size();
        }

        @Override
        public E next() {
            checkForComodification();
            try {
                int i = cursor;
                E next = get(i);
                lastRet = i;
                cursor = i + 1;
                return next;
            } catch (IndexOutOfBoundsException e) {
                checkForComodification();
                throw new NoSuchElementException();
            }
        }

        @Override
        public void remove() {
            if (lastRet < 0)
                throw new IllegalStateException();
            checkForComodification();

            try {
                CircularArrayList.this.remove(lastRet);
                if (lastRet < cursor)
                    cursor--;
                lastRet = -1;
                expectedModCount = modCount;
            } catch (IndexOutOfBoundsException e) {
                throw new ConcurrentModificationException();
            }
        }

        final void checkForComodification() {
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
        }
    }
}

// -- UNIT TESTS
import static org.fest.assertions.Assertions.assertThat;

import org.junit.Test;

public class CircularBufferTest {

    CircularBuffer<String> list = new CircularBuffer<>(3);

    @Test
    public void insert_some_data() throws Exception {
        list.add("1");
        assertThat(list).hasSize(1);
        list.add("2");
        assertThat(list).hasSize(2);
    }

    @Test
    public void insert_and_overwrite_old_data() throws Exception {
        list.add("1");
        assertThat(list).hasSize(1);
        list.add("2");
        assertThat(list).hasSize(2);
        list.add("3");
        assertThat(list).hasSize(3);
        list.add("4");
        assertThat(list).hasSize(3);

        assertThat(list).containsExactly("2", "3", "4");

        list.add("5");
        assertThat(list).hasSize(3);

        assertThat(list).containsExactly("3", "4", "5");

        list.add("6");
        assertThat(list).hasSize(3);

        assertThat(list).containsExactly("4", "5", "6");

        list.add("7");
        assertThat(list).hasSize(3);

        assertThat(list).containsExactly("5", "6", "7");
    }
    
    @Test
    public void insert_in_middle_before_circling() throws Exception {
        list.add("1");
        assertThat(list).hasSize(1);
        list.add("2");
        assertThat(list).hasSize(2);

        assertThat(list).containsExactly("1", "2");
        
        // try add in middle
        list.add(1, "5");
        assertThat(list).hasSize(3);

        assertThat(list).containsExactly("1", "5", "2");
        
        // try again
        list.add(1, "6");
        assertThat(list).hasSize(3);

        assertThat(list).containsExactly("6", "5", "2");
        
        // try again - at start
        list.add(0, "7");
        assertThat(list).hasSize(3);

        assertThat(list).containsExactly("7", "5", "2");
    }
    
    
    @Test
    public void insert_in_middle_when_circling() throws Exception {
        list.add("1");
        assertThat(list).hasSize(1);
        list.add("2");
        assertThat(list).hasSize(2);
        list.add("3");
        assertThat(list).hasSize(3);

        assertThat(list).containsExactly("1", "2", "3");
        
        // try add in middle
        list.add(1, "5");
        assertThat(list).hasSize(3);

        assertThat(list).containsExactly("5", "2", "3");
        
    }
    
    @Test
    public void insert_in_middle_after_circling() throws Exception {
        list.add("1");
        assertThat(list).hasSize(1);
        list.add("2");
        assertThat(list).hasSize(2);
        list.add("3");
        assertThat(list).hasSize(3);
        list.add("4");
        assertThat(list).hasSize(3);

        assertThat(list).containsExactly("2", "3", "4");
        
        // try add in middle
        list.add(1, "5");
        assertThat(list).hasSize(3);

        assertThat(list).containsExactly("5", "3", "4");
        
    }
    
    @Test
    public void remove_oldest_data_before_circling() throws Exception {
        list.add("1");
        assertThat(list).hasSize(1);
        list.add("2");
        assertThat(list).hasSize(2);

        assertThat(list).containsExactly("1", "2");

        list.remove(0);

        assertThat(list).containsExactly("2");
    }

    @Test
    public void remove_oldest_data_after_circling() throws Exception {
        list.add("1");
        assertThat(list).hasSize(1);
        list.add("2");
        assertThat(list).hasSize(2);
        list.add("3");
        assertThat(list).hasSize(3);
        list.add("4");
        assertThat(list).hasSize(3);

        assertThat(list).containsExactly("2", "3", "4");

        list.remove(0);

        assertThat(list).containsExactly("3", "4");
    }
    
    
    @Test
    public void remove_middle_data_before_circling() throws Exception {
        list.add("1");
        assertThat(list).hasSize(1);
        list.add("2");
        assertThat(list).hasSize(2);
        list.add("3");
        assertThat(list).hasSize(3);

        assertThat(list).containsExactly("1", "2", "3");

        list.remove(1);

        assertThat(list).containsExactly("1", "3");
    }
    
    @Test
    public void remove_latest_data_before_circling() throws Exception {
        list.add("1");
        assertThat(list).hasSize(1);
        list.add("2");
        assertThat(list).hasSize(2);
        list.add("3");
        assertThat(list).hasSize(3);

        assertThat(list).containsExactly("1", "2", "3");

        list.remove(2);

        assertThat(list).containsExactly("1", "2");
    }
    
    @Test
    public void remove_latest_data_after_circling() throws Exception {
        list.add("1");
        assertThat(list).hasSize(1);
        list.add("2");
        assertThat(list).hasSize(2);
        list.add("3");
        assertThat(list).hasSize(3);
        list.add("4");
        assertThat(list).hasSize(3);

        assertThat(list).containsExactly("2", "3", "4");

        list.remove(2);

        assertThat(list).containsExactly("2", "3");
    }
    
    @Test
    public void remove_middle_data_after_circling() throws Exception {
        list.add("1");
        assertThat(list).hasSize(1);
        list.add("2");
        assertThat(list).hasSize(2);
        list.add("3");
        assertThat(list).hasSize(3);
        list.add("4");
        assertThat(list).hasSize(3);

        assertThat(list).containsExactly("2", "3", "4");

        list.remove(1);

        assertThat(list).containsExactly("2", "4");
    }
}