1b9537aff4a6ff5231030799cdaf931c27fb9579bTim Kilbourn/* 2b9537aff4a6ff5231030799cdaf931c27fb9579bTim Kilbourn * Copyright (C) 2014 The Android Open Source Project 3b9537aff4a6ff5231030799cdaf931c27fb9579bTim Kilbourn * 4b9537aff4a6ff5231030799cdaf931c27fb9579bTim Kilbourn * Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except 5b9537aff4a6ff5231030799cdaf931c27fb9579bTim Kilbourn * in compliance with the License. You may obtain a copy of the License at 6b9537aff4a6ff5231030799cdaf931c27fb9579bTim Kilbourn * 7b9537aff4a6ff5231030799cdaf931c27fb9579bTim Kilbourn * http://www.apache.org/licenses/LICENSE-2.0 8b9537aff4a6ff5231030799cdaf931c27fb9579bTim Kilbourn * 9b9537aff4a6ff5231030799cdaf931c27fb9579bTim Kilbourn * Unless required by applicable law or agreed to in writing, software distributed under the License 10b9537aff4a6ff5231030799cdaf931c27fb9579bTim Kilbourn * is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express 11b9537aff4a6ff5231030799cdaf931c27fb9579bTim Kilbourn * or implied. See the License for the specific language governing permissions and limitations under 12b9537aff4a6ff5231030799cdaf931c27fb9579bTim Kilbourn * the License. 13b9537aff4a6ff5231030799cdaf931c27fb9579bTim Kilbourn */ 14b9537aff4a6ff5231030799cdaf931c27fb9579bTim Kilbournpackage android.support.v4.util; 15b9537aff4a6ff5231030799cdaf931c27fb9579bTim Kilbourn 16b9537aff4a6ff5231030799cdaf931c27fb9579bTim Kilbourn/** 17ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu * CircularArray is a generic circular array data structure that provides O(1) random read, O(1) 18ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu * prepend and O(1) append. The CircularArray automatically grows its capacity when number of added 19ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu * items is over its capacity. 20b9537aff4a6ff5231030799cdaf931c27fb9579bTim Kilbourn */ 21ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gupublic final class CircularArray<E> { 22b9537aff4a6ff5231030799cdaf931c27fb9579bTim Kilbourn private E[] mElements; 23b9537aff4a6ff5231030799cdaf931c27fb9579bTim Kilbourn private int mHead; 24b9537aff4a6ff5231030799cdaf931c27fb9579bTim Kilbourn private int mTail; 25b9537aff4a6ff5231030799cdaf931c27fb9579bTim Kilbourn private int mCapacityBitmask; 26b9537aff4a6ff5231030799cdaf931c27fb9579bTim Kilbourn 27b9537aff4a6ff5231030799cdaf931c27fb9579bTim Kilbourn private void doubleCapacity() { 28b9537aff4a6ff5231030799cdaf931c27fb9579bTim Kilbourn int n = mElements.length; 29b9537aff4a6ff5231030799cdaf931c27fb9579bTim Kilbourn int r = n - mHead; 30b9537aff4a6ff5231030799cdaf931c27fb9579bTim Kilbourn int newCapacity = n << 1; 31b9537aff4a6ff5231030799cdaf931c27fb9579bTim Kilbourn if (newCapacity < 0) { 32ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu throw new RuntimeException("Max array capacity exceeded"); 33b9537aff4a6ff5231030799cdaf931c27fb9579bTim Kilbourn } 34b9537aff4a6ff5231030799cdaf931c27fb9579bTim Kilbourn Object[] a = new Object[newCapacity]; 35b9537aff4a6ff5231030799cdaf931c27fb9579bTim Kilbourn System.arraycopy(mElements, mHead, a, 0, r); 36b9537aff4a6ff5231030799cdaf931c27fb9579bTim Kilbourn System.arraycopy(mElements, 0, a, r, mHead); 37ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu mElements = (E[]) a; 38b9537aff4a6ff5231030799cdaf931c27fb9579bTim Kilbourn mHead = 0; 39b9537aff4a6ff5231030799cdaf931c27fb9579bTim Kilbourn mTail = n; 40b9537aff4a6ff5231030799cdaf931c27fb9579bTim Kilbourn mCapacityBitmask = newCapacity - 1; 41b9537aff4a6ff5231030799cdaf931c27fb9579bTim Kilbourn } 42b9537aff4a6ff5231030799cdaf931c27fb9579bTim Kilbourn 43b9537aff4a6ff5231030799cdaf931c27fb9579bTim Kilbourn /** 44b9537aff4a6ff5231030799cdaf931c27fb9579bTim Kilbourn * Create a CircularArray with default capacity. 45b9537aff4a6ff5231030799cdaf931c27fb9579bTim Kilbourn */ 46b9537aff4a6ff5231030799cdaf931c27fb9579bTim Kilbourn public CircularArray() { 47b9537aff4a6ff5231030799cdaf931c27fb9579bTim Kilbourn this(8); 48b9537aff4a6ff5231030799cdaf931c27fb9579bTim Kilbourn } 49b9537aff4a6ff5231030799cdaf931c27fb9579bTim Kilbourn 50b9537aff4a6ff5231030799cdaf931c27fb9579bTim Kilbourn /** 51b9537aff4a6ff5231030799cdaf931c27fb9579bTim Kilbourn * Create a CircularArray with capacity for at least minCapacity elements. 52b9537aff4a6ff5231030799cdaf931c27fb9579bTim Kilbourn * 53ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu * @param minCapacity The minimum capacity required for the CircularArray. 54b9537aff4a6ff5231030799cdaf931c27fb9579bTim Kilbourn */ 55b9537aff4a6ff5231030799cdaf931c27fb9579bTim Kilbourn public CircularArray(int minCapacity) { 56b9537aff4a6ff5231030799cdaf931c27fb9579bTim Kilbourn if (minCapacity <= 0) { 57b9537aff4a6ff5231030799cdaf931c27fb9579bTim Kilbourn throw new IllegalArgumentException("capacity must be positive"); 58b9537aff4a6ff5231030799cdaf931c27fb9579bTim Kilbourn } 59b9537aff4a6ff5231030799cdaf931c27fb9579bTim Kilbourn int arrayCapacity = minCapacity; 60b9537aff4a6ff5231030799cdaf931c27fb9579bTim Kilbourn // If minCapacity isn't a power of 2, round up to the next highest power 61b9537aff4a6ff5231030799cdaf931c27fb9579bTim Kilbourn // of 2. 62b9537aff4a6ff5231030799cdaf931c27fb9579bTim Kilbourn if (Integer.bitCount(minCapacity) != 1) { 63b9537aff4a6ff5231030799cdaf931c27fb9579bTim Kilbourn arrayCapacity = 1 << (Integer.highestOneBit(minCapacity) + 1); 64b9537aff4a6ff5231030799cdaf931c27fb9579bTim Kilbourn } 65b9537aff4a6ff5231030799cdaf931c27fb9579bTim Kilbourn mCapacityBitmask = arrayCapacity - 1; 66b9537aff4a6ff5231030799cdaf931c27fb9579bTim Kilbourn mElements = (E[]) new Object[arrayCapacity]; 67b9537aff4a6ff5231030799cdaf931c27fb9579bTim Kilbourn } 68b9537aff4a6ff5231030799cdaf931c27fb9579bTim Kilbourn 69ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu /** 70ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu * Add an element in front of the CircularArray. 71ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu * @param e Element to add. 72ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu */ 73ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu public void addFirst(E e) { 74b9537aff4a6ff5231030799cdaf931c27fb9579bTim Kilbourn mHead = (mHead - 1) & mCapacityBitmask; 75b9537aff4a6ff5231030799cdaf931c27fb9579bTim Kilbourn mElements[mHead] = e; 76b9537aff4a6ff5231030799cdaf931c27fb9579bTim Kilbourn if (mHead == mTail) { 77b9537aff4a6ff5231030799cdaf931c27fb9579bTim Kilbourn doubleCapacity(); 78b9537aff4a6ff5231030799cdaf931c27fb9579bTim Kilbourn } 79b9537aff4a6ff5231030799cdaf931c27fb9579bTim Kilbourn } 80b9537aff4a6ff5231030799cdaf931c27fb9579bTim Kilbourn 81ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu /** 82ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu * Add an element at end of the CircularArray. 83ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu * @param e Element to add. 84ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu */ 85ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu public void addLast(E e) { 86b9537aff4a6ff5231030799cdaf931c27fb9579bTim Kilbourn mElements[mTail] = e; 87b9537aff4a6ff5231030799cdaf931c27fb9579bTim Kilbourn mTail = (mTail + 1) & mCapacityBitmask; 88b9537aff4a6ff5231030799cdaf931c27fb9579bTim Kilbourn if (mTail == mHead) { 89b9537aff4a6ff5231030799cdaf931c27fb9579bTim Kilbourn doubleCapacity(); 90b9537aff4a6ff5231030799cdaf931c27fb9579bTim Kilbourn } 91b9537aff4a6ff5231030799cdaf931c27fb9579bTim Kilbourn } 92b9537aff4a6ff5231030799cdaf931c27fb9579bTim Kilbourn 93ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu /** 94ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu * Remove first element from front of the CircularArray and return it. 95ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu * @return The element removed. 962182cce575fb80fe8d19ae4d2605c5f4b495305cNarayan Kamath * @throws ArrayIndexOutOfBoundsException if CircularArray is empty. 97ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu */ 98ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu public E popFirst() { 99ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu if (mHead == mTail) { 100ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu throw new ArrayIndexOutOfBoundsException(); 101ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu } 102b9537aff4a6ff5231030799cdaf931c27fb9579bTim Kilbourn E result = mElements[mHead]; 103b9537aff4a6ff5231030799cdaf931c27fb9579bTim Kilbourn mElements[mHead] = null; 104b9537aff4a6ff5231030799cdaf931c27fb9579bTim Kilbourn mHead = (mHead + 1) & mCapacityBitmask; 105b9537aff4a6ff5231030799cdaf931c27fb9579bTim Kilbourn return result; 106b9537aff4a6ff5231030799cdaf931c27fb9579bTim Kilbourn } 107b9537aff4a6ff5231030799cdaf931c27fb9579bTim Kilbourn 108ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu /** 109ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu * Remove last element from end of the CircularArray and return it. 110ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu * @return The element removed. 1112182cce575fb80fe8d19ae4d2605c5f4b495305cNarayan Kamath * @throws ArrayIndexOutOfBoundsException if CircularArray is empty. 112ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu */ 113ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu public E popLast() { 114ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu if (mHead == mTail) { 115ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu throw new ArrayIndexOutOfBoundsException(); 116ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu } 117b9537aff4a6ff5231030799cdaf931c27fb9579bTim Kilbourn int t = (mTail - 1) & mCapacityBitmask; 118b9537aff4a6ff5231030799cdaf931c27fb9579bTim Kilbourn E result = mElements[t]; 119b9537aff4a6ff5231030799cdaf931c27fb9579bTim Kilbourn mElements[t] = null; 120b9537aff4a6ff5231030799cdaf931c27fb9579bTim Kilbourn mTail = t; 121b9537aff4a6ff5231030799cdaf931c27fb9579bTim Kilbourn return result; 122b9537aff4a6ff5231030799cdaf931c27fb9579bTim Kilbourn } 123b9537aff4a6ff5231030799cdaf931c27fb9579bTim Kilbourn 124ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu /** 125ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu * Remove all elements from the CircularArray. 126ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu */ 127ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu public void clear() { 128ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu removeFromStart(size()); 129ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu } 130ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu 131ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu /** 132ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu * Remove multiple elements from front of the CircularArray, ignore when numOfElements 133ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu * is less than or equals to 0. 134ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu * @param numOfElements Number of elements to remove. 1352182cce575fb80fe8d19ae4d2605c5f4b495305cNarayan Kamath * @throws ArrayIndexOutOfBoundsException if numOfElements is larger than 136ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu * {@link #size()} 137ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu */ 138ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu public void removeFromStart(int numOfElements) { 139ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu if (numOfElements <= 0) { 140ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu return; 141ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu } 142ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu if (numOfElements > size()) { 143ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu throw new ArrayIndexOutOfBoundsException(); 144ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu } 145ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu int end = mElements.length; 146ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu if (numOfElements < end - mHead) { 147ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu end = mHead + numOfElements; 148ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu } 149ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu for (int i = mHead; i < end; i++) { 150ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu mElements[i] = null; 151ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu } 152ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu int removed = (end - mHead); 153ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu numOfElements -= removed; 154ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu mHead = (mHead + removed) & mCapacityBitmask; 155ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu if (numOfElements > 0) { 156ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu // mHead wrapped to 0 157ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu for (int i = 0; i < numOfElements; i++) { 158ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu mElements[i] = null; 159ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu } 160ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu mHead = numOfElements; 161ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu } 162ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu } 163ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu 164ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu /** 165ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu * Remove multiple elements from end of the CircularArray, ignore when numOfElements 166ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu * is less than or equals to 0. 167ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu * @param numOfElements Number of elements to remove. 1682182cce575fb80fe8d19ae4d2605c5f4b495305cNarayan Kamath * @throws ArrayIndexOutOfBoundsException if numOfElements is larger than 169ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu * {@link #size()} 170ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu */ 171ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu public void removeFromEnd(int numOfElements) { 172ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu if (numOfElements <= 0) { 173ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu return; 174ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu } 175ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu if (numOfElements > size()) { 176ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu throw new ArrayIndexOutOfBoundsException(); 177ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu } 178ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu int start = 0; 179ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu if (numOfElements < mTail) { 180ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu start = mTail - numOfElements; 181ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu } 182ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu for (int i = start; i < mTail; i++) { 183ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu mElements[i] = null; 184ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu } 185ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu int removed = (mTail - start); 186ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu numOfElements -= removed; 187ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu mTail = mTail - removed; 188ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu if (numOfElements > 0) { 189ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu // mTail wrapped to mElements.length 190ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu mTail = mElements.length; 191ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu int newTail = mTail - numOfElements; 192ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu for (int i = newTail; i < mTail; i++) { 193ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu mElements[i] = null; 194ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu } 195ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu mTail = newTail; 196ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu } 197ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu } 198ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu 199ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu /** 200ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu * Get first element of the CircularArray. 201ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu * @return The first element. 2023b26e1a1412a8c3b6e7b520b4472d929e7e1e7f4Dake Gu * @throws {@link ArrayIndexOutOfBoundsException} if CircularArray is empty. 203ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu */ 204ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu public E getFirst() { 205ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu if (mHead == mTail) { 206ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu throw new ArrayIndexOutOfBoundsException(); 207ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu } 208b9537aff4a6ff5231030799cdaf931c27fb9579bTim Kilbourn return mElements[mHead]; 209b9537aff4a6ff5231030799cdaf931c27fb9579bTim Kilbourn } 210b9537aff4a6ff5231030799cdaf931c27fb9579bTim Kilbourn 211ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu /** 212ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu * Get last element of the CircularArray. 213ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu * @return The last element. 2143b26e1a1412a8c3b6e7b520b4472d929e7e1e7f4Dake Gu * @throws {@link ArrayIndexOutOfBoundsException} if CircularArray is empty. 215ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu */ 216ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu public E getLast() { 217ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu if (mHead == mTail) { 218ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu throw new ArrayIndexOutOfBoundsException(); 219ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu } 220b9537aff4a6ff5231030799cdaf931c27fb9579bTim Kilbourn return mElements[(mTail - 1) & mCapacityBitmask]; 221b9537aff4a6ff5231030799cdaf931c27fb9579bTim Kilbourn } 222b9537aff4a6ff5231030799cdaf931c27fb9579bTim Kilbourn 223ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu /** 224ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu * Get nth (0 <= n <= size()-1) element of the CircularArray. 225ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu * @param n The zero based element index in the CircularArray. 226ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu * @return The nth element. 2273b26e1a1412a8c3b6e7b520b4472d929e7e1e7f4Dake Gu * @throws {@link ArrayIndexOutOfBoundsException} if n < 0 or n >= size(). 228ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu */ 229ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu public E get(int n) { 230ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu if (n < 0 || n >= size()) { 231ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu throw new ArrayIndexOutOfBoundsException(); 232ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu } 233ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu return mElements[(mHead + n) & mCapacityBitmask]; 234b9537aff4a6ff5231030799cdaf931c27fb9579bTim Kilbourn } 235b9537aff4a6ff5231030799cdaf931c27fb9579bTim Kilbourn 236ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu /** 237ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu * Get number of elements in the CircularArray. 238ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu * @return Number of elements in the CircularArray. 239ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu */ 240ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu public int size() { 241b9537aff4a6ff5231030799cdaf931c27fb9579bTim Kilbourn return (mTail - mHead) & mCapacityBitmask; 242b9537aff4a6ff5231030799cdaf931c27fb9579bTim Kilbourn } 243b9537aff4a6ff5231030799cdaf931c27fb9579bTim Kilbourn 244ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu /** 245ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu * Return true if size() is 0. 246ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu * @return true if size() is 0. 247ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu */ 248ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu public boolean isEmpty() { 249b9537aff4a6ff5231030799cdaf931c27fb9579bTim Kilbourn return mHead == mTail; 250b9537aff4a6ff5231030799cdaf931c27fb9579bTim Kilbourn } 251b9537aff4a6ff5231030799cdaf931c27fb9579bTim Kilbourn 252b9537aff4a6ff5231030799cdaf931c27fb9579bTim Kilbourn} 253