CircularArray

CircularArray.java

package com.kiwiwearables.kiwilib;
/*
 * Copyright (C) 2014 The Android Open Source Project
 *
 * Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except
 * in compliance with the License. You may obtain a copy of the License at
 *
 * http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software distributed under the License
 * is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express
 * or implied. See the License for the specific language governing permissions and limitations under
 * the License.
 */

import java.util.Arrays;

/**
 * A circular array implementation that provides O(1) random read, O(1)
 * prepend, O(1) append and O(1) set in an existing index.
 */
public class CircularArray<E> {
    private E[] mElements;
    private int mHead;
    private int mTail;
    private int mCapacityBitmask;

    private void doubleCapacity() {
        int n = mElements.length;
        int r = n - mHead;
        int newCapacity = n << 1;
        if (newCapacity < 0) {
            throw new RuntimeException("Max array capacity exceeded");
        }
        Object[] a = new Object[newCapacity];
        System.arraycopy(mElements, mHead, a, 0, r);
        System.arraycopy(mElements, 0, a, r, mHead);
        mElements = (E[]) a;
        mHead = 0;
        mTail = n;
        mCapacityBitmask = newCapacity - 1;
    }

    /**
     * Create a CircularArray with default capacity.
     */
    public CircularArray() {
        this(8);
    }

    /**
     * Create a CircularArray with capacity for at least minCapacity elements.
     *
     * @param minCapacity The minimum capacity required for the CircularArray.
     */
    public CircularArray(int minCapacity) {
        if (minCapacity <= 0) {
            throw new IllegalArgumentException("capacity must be positive");
        }
        int arrayCapacity = minCapacity;
        // If minCapacity isn't a power of 2, round up to the next highest power
        // of 2.
        if (Integer.bitCount(minCapacity) != 1) {
            arrayCapacity = 1 << (Integer.highestOneBit(minCapacity) + 1);
        }
        mCapacityBitmask = arrayCapacity - 1;
        mElements = (E[]) new Object[arrayCapacity];
    }

    /**
     * Add an element in front of the CircularArray.
     * @param e  Element to add.
     */
    public void addFirst(E e) {
        if (e == null) {
            throw new NullPointerException();
        }
        mHead = (mHead - 1) & mCapacityBitmask;
        mElements[mHead] = e;
        if (mHead == mTail) {
            doubleCapacity();
        }
    }

    /**
     * Add an element at end of the CircularArray.
     * @param e  Element to add.
     */
    public void addLast(E e) {
        if (e == null) {
            throw new NullPointerException();
        }
        mElements[mTail] = e;
        mTail = (mTail + 1) & mCapacityBitmask;
        if (mTail == mHead) {
            doubleCapacity();
        }
    }

    /**
     * Remove first element from front of the CircularArray and return it.
     * @return  The element removed.
     * @throws {@link ArrayIndexOutOfBoundsException} if CircularArray is empty.
     */
    public E popFirst() {
        if (mHead == mTail) {
            throw new ArrayIndexOutOfBoundsException();
        }
        E result = mElements[mHead];
        mElements[mHead] = null;
        mHead = (mHead + 1) & mCapacityBitmask;
        return result;
    }

    /**
     * Remove last element from end of the CircularArray and return it.
     * @return  The element removed.
     * @throws {@link ArrayIndexOutOfBoundsException} if CircularArray is empty.
     */
    public E popLast() {
        if (mHead == mTail) {
            throw new ArrayIndexOutOfBoundsException();
        }
        int t = (mTail - 1) & mCapacityBitmask;
        E result = mElements[t];
        mElements[t] = null;
        mTail = t;
        return result;
    }

    /**
     * Remove all elements from the CircularArray.
     */
    public void clear() {
        removeFromStart(size());
    }

    /**
     * Remove multiple elements from front of the CircularArray, ignore when numOfElements
     * is less than or equals to 0.
     * @param numOfElements  Number of elements to remove.
     * @throws {@link ArrayIndexOutOfBoundsException} if numOfElements is larger than
     *         {@link #size()}
     */
    public void removeFromStart(int numOfElements) {
        if (numOfElements <= 0) {
            return;
        }
        if (numOfElements > size()) {
            throw new ArrayIndexOutOfBoundsException();
        }
        int end = mElements.length;
        if (numOfElements < end - mHead) {
            end = mHead + numOfElements;
        }
        for (int i = mHead; i < end; i++) {
            mElements[i] = null;
        }
        int removed = (end - mHead);
        numOfElements -= removed;
        mHead = (mHead + removed) & mCapacityBitmask;
        if (numOfElements > 0) {
            // mHead wrapped to 0
            for (int i = 0; i < numOfElements; i++) {
                mElements[i] = null;
            }
            mHead = numOfElements;
        }
    }

    /**
     * Remove multiple elements from end of the CircularArray, ignore when numOfElements
     * is less than or equals to 0.
     * @param numOfElements  Number of elements to remove.
     * @throws {@link ArrayIndexOutOfBoundsException} if numOfElements is larger than
     *         {@link #size()}
     */
    public void removeFromEnd(int numOfElements) {
        if (numOfElements <= 0) {
            return;
        }
        if (numOfElements > size()) {
            throw new ArrayIndexOutOfBoundsException();
        }
        int start = 0;
        if (numOfElements < mTail) {
            start = mTail - numOfElements;
        }
        for (int i = start; i < mTail; i++) {
            mElements[i] = null;
        }
        int removed = (mTail - start);
        numOfElements -= removed;
        mTail = mTail - removed;
        if (numOfElements > 0) {
            // mTail wrapped to mElements.length
            mTail = mElements.length;
            int newTail = mTail - numOfElements;
            for (int i = newTail; i < mTail; i++) {
                mElements[i] = null;
            }
            mTail = newTail;
        }
    }

    /**
     * Get first element of the CircularArray.
     * @return The first element.
     * @throws {@link ArrayIndexOutOfBoundsException} if CircularArray is empty.
     */
    public E getFirst() {
        if (mHead == mTail) {
            throw new ArrayIndexOutOfBoundsException();
        }
        return mElements[mHead];
    }

    /**
     * Get last element of the CircularArray.
     * @return The last element.
     * @throws {@link ArrayIndexOutOfBoundsException} if CircularArray is empty.
     */
    public E getLast() {
        if (mHead == mTail) {
            throw new ArrayIndexOutOfBoundsException();
        }
        return mElements[(mTail - 1) & mCapacityBitmask];
    }

    /**
     * Get nth (0 <= n <= size()-1) element of the CircularArray.
     * @param n  The zero based element index in the CircularArray.
     * @return The nth element.
     * @throws {@link ArrayIndexOutOfBoundsException} if n < 0 or n >= size().
     */
    public E get(int n) {
        int size = size();
        if (n < 0 || n >= size) {
            throw new ArrayIndexOutOfBoundsException();
        }
        return mElements[(mHead + n) & mCapacityBitmask];
    }

    /**
     * Set the nth (0 <= n <= size()-1) element of the CircularArray.
     * @param n  The zero based element index in the CircularArray.
     * @param e  The
     * @throws {@link ArrayIndexOutOfBoundsException} if n < 0 or n >= size().
     */
    public void set(int n, E e) {
        int size = size();
        if (e == null) {
            throw new NullPointerException();
        }
        if (n < 0 || n >= size) {
            throw new ArrayIndexOutOfBoundsException();
        }
        mElements[(mHead + n) & mCapacityBitmask] = e;
    }

    /**
     * Get number of elements in the CircularArray.
     * @return Number of elements in the CircularArray.
     */
    public int size() {
        return (mTail - mHead) & mCapacityBitmask;
    }

    /**
     * Return true if size() is 0.
     * @return true if size() is 0.
     */
    public boolean isEmpty() {
        return mHead == mTail;
    }

    public synchronized Object[] toArray() {
        return copyElements(new Object[size()]);
    }

    public synchronized <T> T[] toArray(T[] a) {
        int size = size();
        if (a.length < size) {
            a = (T[]) java.lang.reflect.Array.newInstance(a.getClass().getComponentType(), size);
        }
        copyElements(a);
        if (a.length > size) {
            a[size] = null;
        }
        return a;
    }

    public String toString() {
        return Arrays.toString(toArray());
    }

    private <T> T[] copyElements(T[] a) {
        if (mHead < mTail) {
            System.arraycopy(mElements, mHead, a, 0, size());
        } else if (mHead > mTail) {
            int headPortionLen = mElements.length - mHead;
            System.arraycopy(mElements, mHead, a, 0, headPortionLen);
            System.arraycopy(mElements, 0, a, headPortionLen, mTail);
        }
        return a;
    }
}

CircularArrayTest.java

package com.kiwiwearables.kiwilib;

/*
 * Written by Doug Lea with assistance from members of JCP JSR-166
 * Expert Group and released to the public domain, as explained at
 * http://creativecommons.org/publicdomain/zero/1.0/
 *
 *
 * Modified for CircularArray by afzal on 15-04-17.
 */

import java.util.Arrays;

import junit.framework.Test;
import junit.framework.TestCase;
import junit.framework.TestSuite;

import static org.assertj.core.api.Assertions.assertThat;
import static org.assertj.core.api.Assertions.failBecauseExceptionWasNotThrown;

public class CircularArrayTest extends TestCase {

    private static final int SIZE = 12;

    public static void main(String[] args) {
        junit.textui.TestRunner.run(suite());
    }

    public static Test suite() {
        return new TestSuite(CircularArrayTest.class);
    }

    /**
     * Returns a new CircularArray of given size containing consecutive
     * Integers 0 ... n.
     */
    private CircularArray<Integer> populatedCircularArray(int n) {
        CircularArray<Integer> q = new CircularArray<>();
        assertTrue(q.isEmpty());
        for (int i = 0; i < n; ++i) {
            q.addLast(i);
        }
        assertFalse(q.isEmpty());
        assertEquals(n, q.size());
        return q;
    }

    /**
     * new CircularArray is empty
     */
    public void testConstructor1() {
        assertEquals(0, new CircularArray().size());
    }

    public void testConstructor2() {
        assertEquals(0, new CircularArray(SIZE).size());
    }

    /**
     * isEmpty is true before add, false after
     */
    public void testEmpty() {
        CircularArray q = new CircularArray();
        assertTrue(q.isEmpty());
        q.addLast(1);
        assertFalse(q.isEmpty());
        q.addLast(2);
        q.popFirst();
        q.popFirst();
        assertTrue(q.isEmpty());
    }

    /**
     * size changes when elements added and removed
     */
    public void testSize() {
        CircularArray q = populatedCircularArray(SIZE);
        for (int i = 0; i < SIZE; ++i) {
            assertEquals(SIZE - i, q.size());
            q.popFirst();
        }
        for (int i = 0; i < SIZE; ++i) {
            assertEquals(i, q.size());
            q.addLast(i);
        }
    }

    /**
     * getFirst() returns element inserted with push
     */
    public void testPush() {
        CircularArray q = populatedCircularArray(3);
        q.addFirst(2);
        assertSame(2, q.getFirst());
    }

    /**
     * pop() removes next element, or throws NSEE if empty
     */
    public void testPop() {
        CircularArray q = populatedCircularArray(SIZE);
        for (int i = 0; i < SIZE; ++i) {
            assertEquals(i, q.popFirst());
        }
        try {
            q.popFirst();
            failBecauseExceptionWasNotThrown(ArrayIndexOutOfBoundsException.class);
        } catch (ArrayIndexOutOfBoundsException success) {}

    }

    /**
     * addFirst(null) throws NPE
     */
    public void testAddFirstNull() {
        CircularArray q = new CircularArray();
        try {
            q.addFirst(null);
            failBecauseExceptionWasNotThrown(NullPointerException.class);
        } catch (NullPointerException success) {}
    }

    /**
     * addLast(null) throws NPE
     */
    public void testAddLastNull() {
        CircularArray q = new CircularArray();
        try {
            q.addLast(null);
            failBecauseExceptionWasNotThrown(NullPointerException.class);
        } catch (NullPointerException success) {}
    }

    /**
     * addFirst(x) succeeds
     */
    public void testAddFirst() {
        CircularArray q = new CircularArray();
        q.addFirst(0);
        q.addFirst(1);
        assertSame(1, q.getFirst());
        assertSame(0, q.getLast());
    }

    /**
     * addLast(x) succeeds
     */
    public void testAddLast() {
        CircularArray q = new CircularArray();
        q.addLast(0);
        q.addLast(1);
        assertSame(0, q.getFirst());
        assertSame(1, q.getLast());
    }

    /**
     * popFirst() succeeds unless empty
     */
    public void testPopFirst() {
        CircularArray q = populatedCircularArray(SIZE);
        for (int i = 0; i < SIZE; ++i) {
            assertEquals(i, q.popFirst());
        }

        try {
            q.popFirst();
            failBecauseExceptionWasNotThrown(ArrayIndexOutOfBoundsException.class);
        } catch (ArrayIndexOutOfBoundsException success) {}
    }

    /**
     * popLast() succeeds unless empty
     */
    public void testPopLast() {
        CircularArray q = populatedCircularArray(SIZE);
        for (int i = SIZE - 1; i >= 0; --i) {
            assertEquals(i, q.popLast());
        }

        try {
            q.popLast();
            failBecauseExceptionWasNotThrown(ArrayIndexOutOfBoundsException.class);
        } catch (ArrayIndexOutOfBoundsException success) {}
    }

    /**
     * getFirst() returns next element, or null if empty
     */
    public void testGetFirst() {
        CircularArray q = populatedCircularArray(SIZE);
        for (int i = 0; i < SIZE; ++i) {
            assertEquals(i, q.getFirst());
            assertEquals(i, q.popFirst());
        }
        try {
            q.getFirst();
            failBecauseExceptionWasNotThrown(ArrayIndexOutOfBoundsException.class);
        } catch (ArrayIndexOutOfBoundsException success) {}
    }

    /**
     * get() returns the correct element
     */
    public void testGet() {
        CircularArray q = populatedCircularArray(SIZE);
        for (int i = 0; i < SIZE; ++i) {
            assertEquals(i, q.get(i));
        }
    }

    /**
     * get() returns null if empty
     */
    public void testGetNull() {
        CircularArray q = populatedCircularArray(SIZE);
        for (int i = 0; i < SIZE; ++i) {
            q.popFirst();
        }
        try {
            q.get(0);
            failBecauseExceptionWasNotThrown(ArrayIndexOutOfBoundsException.class);
        } catch (ArrayIndexOutOfBoundsException success) {}
    }

    /**
     * getLast() returns next element, or null if empty
     */
    public void testGetLast() {
        CircularArray q = populatedCircularArray(SIZE);
        for (int i = SIZE - 1; i >= 0; --i) {
            assertEquals(i, q.getLast());
            assertEquals(i, q.popLast());
        }
        try {
            q.getLast();
            failBecauseExceptionWasNotThrown(ArrayIndexOutOfBoundsException.class);
        } catch (ArrayIndexOutOfBoundsException success) {}
    }

    /**
     * getFirst() returns first element, or throws NSEE if empty
     */
    public void testFirstElement() {
        CircularArray q = populatedCircularArray(SIZE);
        for (int i = 0; i < SIZE; ++i) {
            assertEquals(i, q.getFirst());
            assertEquals(i, q.popFirst());
        }
        try {
            q.getFirst();
            failBecauseExceptionWasNotThrown(ArrayIndexOutOfBoundsException.class);
        } catch (ArrayIndexOutOfBoundsException success) {}
    }

    /**
     * getLast() returns last element, or throws NSEE if empty
     */
    public void testLastElement() {
        CircularArray q = populatedCircularArray(SIZE);
        for (int i = SIZE - 1; i >= 0; --i) {
            assertEquals(i, q.getLast());
            assertEquals(i, q.popLast());
        }
        try {
            q.getLast();
            failBecauseExceptionWasNotThrown(ArrayIndexOutOfBoundsException.class);
        } catch (ArrayIndexOutOfBoundsException success) {}
    }

    void checkToArray(CircularArray q) {
        int size = q.size();
        Object[] o = q.toArray();
        assertEquals(size, o.length);
        for (int i = 0; i < size; i++) {
            Integer x = (Integer) q.get(i);
            assertEquals((Integer) o[0] + i, (int) x);
            assertSame(o[i], x);
        }
    }

    /**
     * toArray() contains all elements in FIFO order
     */
    public void testToArray() {
        CircularArray q = new CircularArray();
        for (int i = 0; i < SIZE; i++) {
            checkToArray(q);
            q.addLast(i);
        }
        // Provoke wraparound
        for (int i = 0; i < SIZE; i++) {
            checkToArray(q);
            assertEquals(i, q.popFirst());
            q.addLast(SIZE + i);
        }
        for (int i = 0; i < SIZE; i++) {
            checkToArray(q);
            assertEquals(SIZE + i, q.popFirst());
        }
    }

    void checkToArray2(CircularArray q) {
        int size = q.size();
        Integer[] a1 = size == 0 ? null : new Integer[size - 1];
        Integer[] a2 = new Integer[size];
        Integer[] a3 = new Integer[size + 2];
        if (size > 0) Arrays.fill(a1, 42);
        Arrays.fill(a2, 42);
        Arrays.fill(a3, 42);
        Integer[] b1 = size == 0 ? null : (Integer[]) q.toArray(a1);
        Integer[] b2 = (Integer[]) q.toArray(a2);
        Integer[] b3 = (Integer[]) q.toArray(a3);
        assertSame(a2, b2);
        assertSame(a3, b3);
        for (int i = 0; i < size; i++) {
            Integer x = (Integer) q.get(i);
            assertSame(b1[i], x);
            assertEquals(b1[0] + i, (int) x);
            assertSame(b2[i], x);
            assertSame(b3[i], x);
        }
        assertNull(a3[size]);
        assertEquals(42, (int) a3[size + 1]);
        if (size > 0) {
            assertNotSame(a1, b1);
            assertEquals(size, b1.length);
            for (Integer a : a1) {
                assertEquals(42, (int) a);
            }
        }
    }

    /**
     * toArray(a) contains all elements in FIFO order
     */
    public void testToArray2() {
        CircularArray q = new CircularArray();
        for (int i = 0; i < SIZE; i++) {
            checkToArray2(q);
            q.addLast(i);
        }
        // Provoke wraparound
        for (int i = 0; i < SIZE; i++) {
            checkToArray2(q);
            assertEquals(i, q.popFirst());
            q.addLast(SIZE + i);
        }
        for (int i = 0; i < SIZE; i++) {
            checkToArray2(q);
            assertEquals(SIZE + i, q.popFirst());
        }
    }

    /**
     * toArray(null) throws NullPointerException
     */
    public void testToArray_NullArg() {
        CircularArray l = new CircularArray();
        l.addLast(new Object());
        try {
            l.toArray(null);
            failBecauseExceptionWasNotThrown(NullPointerException.class);
        } catch (NullPointerException success) {}
    }

    /**
     * toArray(incompatible array type) throws ArrayStoreException
     */
    public void testToArray1_BadArg() {
        CircularArray l = new CircularArray();
        l.addFirst(5);
        try {
            l.toArray(new String[10]);
//            shouldThrow();
        } catch (ArrayStoreException success) {}
    }

    /**
     * clear removes all elements
     */
    public void testClear() {
        CircularArray q = populatedCircularArray(SIZE);
        q.clear();
        assertTrue(q.isEmpty());
        assertEquals(0, q.size());
        q.addLast(1);
        assertFalse(q.isEmpty());
        q.clear();
        assertTrue(q.isEmpty());
    }

    public void testRemoveFromStartZero() {
        CircularArray l = populatedCircularArray(5);
        l.removeFromStart(0);
        assertThat(l.size()).isEqualTo(5);
    }

    public void testRemoveFromStartLessThanSize() {
        CircularArray l = populatedCircularArray(5);
        l.removeFromStart(2);
        assertThat(l.size()).isEqualTo(3);
    }

    public void testRemoveFromStartEqualToSize() {
        CircularArray l = populatedCircularArray(5);
        l.removeFromStart(5);
        assertThat(l.size()).isEqualTo(0);
    }

    public void testRemoveFromStartGreaterThanSize() {
        CircularArray l = populatedCircularArray(5);
        try {
            l.removeFromStart(6);
            failBecauseExceptionWasNotThrown(ArrayIndexOutOfBoundsException.class);
        } catch (ArrayIndexOutOfBoundsException success) {}
    }

    public void testRemoveFromEndZero() {
        CircularArray l = populatedCircularArray(5);
        l.removeFromEnd(0);
        assertThat(l.size()).isEqualTo(5);
    }

    public void testRemoveFromEndLessThanSize() {
        CircularArray l = populatedCircularArray(5);
        l.removeFromEnd(2);
        assertThat(l.size()).isEqualTo(3);
    }

    public void testRemoveFromEndEqualToSize() {
        CircularArray l = populatedCircularArray(5);
        l.removeFromEnd(5);
        assertThat(l.size()).isEqualTo(0);
    }

    public void testRemoveFromEndGreaterThanSize() {
        CircularArray l = populatedCircularArray(5);
        try {
            l.removeFromEnd(6);
            failBecauseExceptionWasNotThrown(ArrayIndexOutOfBoundsException.class);
        } catch (ArrayIndexOutOfBoundsException success) {}
    }

    public void testSet() {
        CircularArray l = populatedCircularArray(5);
        assertThat(l.get(0)).isEqualTo(0);
        l.set(0, 20);
        assertThat(l.get(0)).isEqualTo(20);
    }

    public void testSetNull() {
        CircularArray l = populatedCircularArray(5);
        assertThat(l.get(0)).isEqualTo(0);
        try {
            l.set(0, null);
            failBecauseExceptionWasNotThrown(NullPointerException.class);
        } catch (NullPointerException success) {}
    }

    public void testSetOutOfRange() {
        CircularArray l = populatedCircularArray(5);
        assertThat(l.get(0)).isEqualTo(0);
        try {
            l.set(6, 20);
            failBecauseExceptionWasNotThrown(ArrayIndexOutOfBoundsException.class);
        } catch (ArrayIndexOutOfBoundsException success) {}

    }
}