FileDocCategorySizeDatePackage
CircularArray.javaAPI DocAndroid 5.1 API3803Thu Mar 12 22:22:56 GMT 2015android.support.v4.util

CircularArray

public class CircularArray extends Object
A circular array implementation that provides O(1) random read and O(1) prepend and O(1) append.

Fields Summary
private E[]
mElements
private int
mHead
private int
mTail
private int
mCapacityBitmask
Constructors Summary
public CircularArray()
Create a CircularArray with default capacity.

        this(8);
public CircularArray(int minCapacity)
Create a CircularArray with capacity for at least minCapacity elements.

param
minCapacity The minimum capacity required for the circular array.

        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];
Methods Summary
public final voidaddFirst(E e)

        mHead = (mHead - 1) & mCapacityBitmask;
        mElements[mHead] = e;
        if (mHead == mTail) {
            doubleCapacity();
        }
public final voidaddLast(E e)

        mElements[mTail] = e;
        mTail = (mTail + 1) & mCapacityBitmask;
        if (mTail == mHead) {
            doubleCapacity();
        }
private voiddoubleCapacity()

        int n = mElements.length;
        int r = n - mHead;
        int newCapacity = n << 1;
        if (newCapacity < 0) {
            throw new RuntimeException("Too big");
        }
        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;
public final Eget(int i)

        if (i < 0 || i >= size()) throw new ArrayIndexOutOfBoundsException();
        int p = (mHead + i) & mCapacityBitmask;
        return mElements[p];
public final EgetFirst()

        if (mHead == mTail) throw new ArrayIndexOutOfBoundsException();
        return mElements[mHead];
public final EgetLast()

        if (mHead == mTail) throw new ArrayIndexOutOfBoundsException();
        return mElements[(mTail - 1) & mCapacityBitmask];
public final booleanisEmpty()

        return mHead == mTail;
public final EpopFirst()

        if (mHead == mTail) throw new ArrayIndexOutOfBoundsException();
        E result = mElements[mHead];
        mElements[mHead] = null;
        mHead = (mHead + 1) & mCapacityBitmask;
        return result;
public final EpopLast()

        if (mHead == mTail) throw new ArrayIndexOutOfBoundsException();
        int t = (mTail - 1) & mCapacityBitmask;
        E result = mElements[t];
        mElements[t] = null;
        mTail = t;
        return result;
public final intsize()

        return (mTail - mHead) & mCapacityBitmask;