1/*
2 * Copyright (C) 2014 The Android Open Source Project
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except
5 * in compliance with the License. You may obtain a copy of the License at
6 *
7 * http://www.apache.org/licenses/LICENSE-2.0
8 *
9 * Unless required by applicable law or agreed to in writing, software distributed under the License
10 * is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express
11 * or implied. See the License for the specific language governing permissions and limitations under
12 * the License.
13 */
14package android.support.v4.util;
15
16/**
17 * A circular array implementation that provides O(1) random read and O(1)
18 * prepend and O(1) append.
19 */
20public class CircularArray<E>
21{
22    private E[] mElements;
23    private int mHead;
24    private int mTail;
25    private int mCapacityBitmask;
26
27    private void doubleCapacity() {
28        int n = mElements.length;
29        int r = n - mHead;
30        int newCapacity = n << 1;
31        if (newCapacity < 0) {
32            throw new RuntimeException("Too big");
33        }
34        Object[] a = new Object[newCapacity];
35        System.arraycopy(mElements, mHead, a, 0, r);
36        System.arraycopy(mElements, 0, a, r, mHead);
37        mElements = (E[])a;
38        mHead = 0;
39        mTail = n;
40        mCapacityBitmask = newCapacity - 1;
41    }
42
43    /**
44     * Create a CircularArray with default capacity.
45     */
46    public CircularArray() {
47        this(8);
48    }
49
50    /**
51     * Create a CircularArray with capacity for at least minCapacity elements.
52     *
53     * @param minCapacity The minimum capacity required for the circular array.
54     */
55    public CircularArray(int minCapacity) {
56        if (minCapacity <= 0) {
57            throw new IllegalArgumentException("capacity must be positive");
58        }
59        int arrayCapacity = minCapacity;
60        // If minCapacity isn't a power of 2, round up to the next highest power
61        // of 2.
62        if (Integer.bitCount(minCapacity) != 1) {
63            arrayCapacity = 1 << (Integer.highestOneBit(minCapacity) + 1);
64        }
65        mCapacityBitmask = arrayCapacity - 1;
66        mElements = (E[]) new Object[arrayCapacity];
67    }
68
69    public final void addFirst(E e) {
70        mHead = (mHead - 1) & mCapacityBitmask;
71        mElements[mHead] = e;
72        if (mHead == mTail) {
73            doubleCapacity();
74        }
75    }
76
77    public final void addLast(E e) {
78        mElements[mTail] = e;
79        mTail = (mTail + 1) & mCapacityBitmask;
80        if (mTail == mHead) {
81            doubleCapacity();
82        }
83    }
84
85    public final E popFirst() {
86        if (mHead == mTail) throw new ArrayIndexOutOfBoundsException();
87        E result = mElements[mHead];
88        mElements[mHead] = null;
89        mHead = (mHead + 1) & mCapacityBitmask;
90        return result;
91    }
92
93    public final E popLast() {
94        if (mHead == mTail) throw new ArrayIndexOutOfBoundsException();
95        int t = (mTail - 1) & mCapacityBitmask;
96        E result = mElements[t];
97        mElements[t] = null;
98        mTail = t;
99        return result;
100    }
101
102    public final E getFirst() {
103        if (mHead == mTail) throw new ArrayIndexOutOfBoundsException();
104        return mElements[mHead];
105    }
106
107    public final E getLast() {
108        if (mHead == mTail) throw new ArrayIndexOutOfBoundsException();
109        return mElements[(mTail - 1) & mCapacityBitmask];
110    }
111
112    public final E get(int i) {
113        if (i < 0 || i >= size()) throw new ArrayIndexOutOfBoundsException();
114        int p = (mHead + i) & mCapacityBitmask;
115        return mElements[p];
116    }
117
118    public final int size() {
119        return (mTail - mHead) & mCapacityBitmask;
120    }
121
122    public final boolean isEmpty() {
123        return mHead == mTail;
124    }
125
126}
127