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 /** 44fa0f278ff6c3ac316e12489a3cf0146766c168ceAlan Viverette * Creates a circular array with default capacity. 45b9537aff4a6ff5231030799cdaf931c27fb9579bTim Kilbourn */ 46b9537aff4a6ff5231030799cdaf931c27fb9579bTim Kilbourn public CircularArray() { 47b9537aff4a6ff5231030799cdaf931c27fb9579bTim Kilbourn this(8); 48b9537aff4a6ff5231030799cdaf931c27fb9579bTim Kilbourn } 49b9537aff4a6ff5231030799cdaf931c27fb9579bTim Kilbourn 50b9537aff4a6ff5231030799cdaf931c27fb9579bTim Kilbourn /** 51fa0f278ff6c3ac316e12489a3cf0146766c168ceAlan Viverette * Creates a circular array with capacity for at least {@code minCapacity} 52fa0f278ff6c3ac316e12489a3cf0146766c168ceAlan Viverette * elements. 53b9537aff4a6ff5231030799cdaf931c27fb9579bTim Kilbourn * 542337b3fa0ca11ddb9121974ca25211e4ae64392fAlan Viverette * @param minCapacity the minimum capacity, between 1 and 2^30 inclusive 55b9537aff4a6ff5231030799cdaf931c27fb9579bTim Kilbourn */ 56b9537aff4a6ff5231030799cdaf931c27fb9579bTim Kilbourn public CircularArray(int minCapacity) { 57fa0f278ff6c3ac316e12489a3cf0146766c168ceAlan Viverette if (minCapacity < 1) { 58fa0f278ff6c3ac316e12489a3cf0146766c168ceAlan Viverette throw new IllegalArgumentException("capacity must be >= 1"); 59b9537aff4a6ff5231030799cdaf931c27fb9579bTim Kilbourn } 60fa0f278ff6c3ac316e12489a3cf0146766c168ceAlan Viverette if (minCapacity > (2 << 29)) { 612337b3fa0ca11ddb9121974ca25211e4ae64392fAlan Viverette throw new IllegalArgumentException("capacity must be <= 2^30"); 62fa0f278ff6c3ac316e12489a3cf0146766c168ceAlan Viverette } 63fa0f278ff6c3ac316e12489a3cf0146766c168ceAlan Viverette 64fa0f278ff6c3ac316e12489a3cf0146766c168ceAlan Viverette // If minCapacity isn't a power of 2, round up to the next highest 65fa0f278ff6c3ac316e12489a3cf0146766c168ceAlan Viverette // power of 2. 66fa0f278ff6c3ac316e12489a3cf0146766c168ceAlan Viverette final int arrayCapacity; 67b9537aff4a6ff5231030799cdaf931c27fb9579bTim Kilbourn if (Integer.bitCount(minCapacity) != 1) { 68fa0f278ff6c3ac316e12489a3cf0146766c168ceAlan Viverette arrayCapacity = Integer.highestOneBit(minCapacity - 1) << 1; 69fa0f278ff6c3ac316e12489a3cf0146766c168ceAlan Viverette } else { 70fa0f278ff6c3ac316e12489a3cf0146766c168ceAlan Viverette arrayCapacity = minCapacity; 71b9537aff4a6ff5231030799cdaf931c27fb9579bTim Kilbourn } 72fa0f278ff6c3ac316e12489a3cf0146766c168ceAlan Viverette 73b9537aff4a6ff5231030799cdaf931c27fb9579bTim Kilbourn mCapacityBitmask = arrayCapacity - 1; 74b9537aff4a6ff5231030799cdaf931c27fb9579bTim Kilbourn mElements = (E[]) new Object[arrayCapacity]; 75b9537aff4a6ff5231030799cdaf931c27fb9579bTim Kilbourn } 76b9537aff4a6ff5231030799cdaf931c27fb9579bTim Kilbourn 77ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu /** 78ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu * Add an element in front of the CircularArray. 79ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu * @param e Element to add. 80ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu */ 81ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu public void addFirst(E e) { 82b9537aff4a6ff5231030799cdaf931c27fb9579bTim Kilbourn mHead = (mHead - 1) & mCapacityBitmask; 83b9537aff4a6ff5231030799cdaf931c27fb9579bTim Kilbourn mElements[mHead] = e; 84b9537aff4a6ff5231030799cdaf931c27fb9579bTim Kilbourn if (mHead == mTail) { 85b9537aff4a6ff5231030799cdaf931c27fb9579bTim Kilbourn doubleCapacity(); 86b9537aff4a6ff5231030799cdaf931c27fb9579bTim Kilbourn } 87b9537aff4a6ff5231030799cdaf931c27fb9579bTim Kilbourn } 88b9537aff4a6ff5231030799cdaf931c27fb9579bTim Kilbourn 89ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu /** 90ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu * Add an element at end of the CircularArray. 91ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu * @param e Element to add. 92ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu */ 93ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu public void addLast(E e) { 94b9537aff4a6ff5231030799cdaf931c27fb9579bTim Kilbourn mElements[mTail] = e; 95b9537aff4a6ff5231030799cdaf931c27fb9579bTim Kilbourn mTail = (mTail + 1) & mCapacityBitmask; 96b9537aff4a6ff5231030799cdaf931c27fb9579bTim Kilbourn if (mTail == mHead) { 97b9537aff4a6ff5231030799cdaf931c27fb9579bTim Kilbourn doubleCapacity(); 98b9537aff4a6ff5231030799cdaf931c27fb9579bTim Kilbourn } 99b9537aff4a6ff5231030799cdaf931c27fb9579bTim Kilbourn } 100b9537aff4a6ff5231030799cdaf931c27fb9579bTim Kilbourn 101ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu /** 102ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu * Remove first element from front of the CircularArray and return it. 103ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu * @return The element removed. 1042182cce575fb80fe8d19ae4d2605c5f4b495305cNarayan Kamath * @throws ArrayIndexOutOfBoundsException if CircularArray is empty. 105ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu */ 106ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu public E popFirst() { 107ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu if (mHead == mTail) { 108ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu throw new ArrayIndexOutOfBoundsException(); 109ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu } 110b9537aff4a6ff5231030799cdaf931c27fb9579bTim Kilbourn E result = mElements[mHead]; 111b9537aff4a6ff5231030799cdaf931c27fb9579bTim Kilbourn mElements[mHead] = null; 112b9537aff4a6ff5231030799cdaf931c27fb9579bTim Kilbourn mHead = (mHead + 1) & mCapacityBitmask; 113b9537aff4a6ff5231030799cdaf931c27fb9579bTim Kilbourn return result; 114b9537aff4a6ff5231030799cdaf931c27fb9579bTim Kilbourn } 115b9537aff4a6ff5231030799cdaf931c27fb9579bTim Kilbourn 116ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu /** 117ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu * Remove last element from end of the CircularArray and return it. 118ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu * @return The element removed. 1192182cce575fb80fe8d19ae4d2605c5f4b495305cNarayan Kamath * @throws ArrayIndexOutOfBoundsException if CircularArray is empty. 120ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu */ 121ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu public E popLast() { 122ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu if (mHead == mTail) { 123ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu throw new ArrayIndexOutOfBoundsException(); 124ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu } 125b9537aff4a6ff5231030799cdaf931c27fb9579bTim Kilbourn int t = (mTail - 1) & mCapacityBitmask; 126b9537aff4a6ff5231030799cdaf931c27fb9579bTim Kilbourn E result = mElements[t]; 127b9537aff4a6ff5231030799cdaf931c27fb9579bTim Kilbourn mElements[t] = null; 128b9537aff4a6ff5231030799cdaf931c27fb9579bTim Kilbourn mTail = t; 129b9537aff4a6ff5231030799cdaf931c27fb9579bTim Kilbourn return result; 130b9537aff4a6ff5231030799cdaf931c27fb9579bTim Kilbourn } 131b9537aff4a6ff5231030799cdaf931c27fb9579bTim Kilbourn 132ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu /** 133ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu * Remove all elements from the CircularArray. 134ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu */ 135ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu public void clear() { 136ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu removeFromStart(size()); 137ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu } 138ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu 139ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu /** 140ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu * Remove multiple elements from front of the CircularArray, ignore when numOfElements 141ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu * is less than or equals to 0. 142ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu * @param numOfElements Number of elements to remove. 1432182cce575fb80fe8d19ae4d2605c5f4b495305cNarayan Kamath * @throws ArrayIndexOutOfBoundsException if numOfElements is larger than 144ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu * {@link #size()} 145ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu */ 146ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu public void removeFromStart(int numOfElements) { 147ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu if (numOfElements <= 0) { 148ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu return; 149ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu } 150ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu if (numOfElements > size()) { 151ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu throw new ArrayIndexOutOfBoundsException(); 152ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu } 153ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu int end = mElements.length; 154ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu if (numOfElements < end - mHead) { 155ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu end = mHead + numOfElements; 156ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu } 157ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu for (int i = mHead; i < end; i++) { 158ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu mElements[i] = null; 159ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu } 160ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu int removed = (end - mHead); 161ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu numOfElements -= removed; 162ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu mHead = (mHead + removed) & mCapacityBitmask; 163ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu if (numOfElements > 0) { 164ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu // mHead wrapped to 0 165ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu for (int i = 0; i < numOfElements; i++) { 166ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu mElements[i] = null; 167ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu } 168ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu mHead = numOfElements; 169ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu } 170ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu } 171ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu 172ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu /** 173ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu * Remove multiple elements from end of the CircularArray, ignore when numOfElements 174ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu * is less than or equals to 0. 175ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu * @param numOfElements Number of elements to remove. 1762182cce575fb80fe8d19ae4d2605c5f4b495305cNarayan Kamath * @throws ArrayIndexOutOfBoundsException if numOfElements is larger than 177ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu * {@link #size()} 178ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu */ 179ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu public void removeFromEnd(int numOfElements) { 180ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu if (numOfElements <= 0) { 181ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu return; 182ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu } 183ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu if (numOfElements > size()) { 184ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu throw new ArrayIndexOutOfBoundsException(); 185ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu } 186ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu int start = 0; 187ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu if (numOfElements < mTail) { 188ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu start = mTail - numOfElements; 189ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu } 190ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu for (int i = start; i < mTail; i++) { 191ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu mElements[i] = null; 192ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu } 193ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu int removed = (mTail - start); 194ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu numOfElements -= removed; 195ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu mTail = mTail - removed; 196ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu if (numOfElements > 0) { 197ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu // mTail wrapped to mElements.length 198ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu mTail = mElements.length; 199ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu int newTail = mTail - numOfElements; 200ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu for (int i = newTail; i < mTail; i++) { 201ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu mElements[i] = null; 202ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu } 203ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu mTail = newTail; 204ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu } 205ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu } 206ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu 207ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu /** 208ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu * Get first element of the CircularArray. 209ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu * @return The first element. 2103b26e1a1412a8c3b6e7b520b4472d929e7e1e7f4Dake Gu * @throws {@link ArrayIndexOutOfBoundsException} if CircularArray is empty. 211ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu */ 212ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu public E getFirst() { 213ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu if (mHead == mTail) { 214ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu throw new ArrayIndexOutOfBoundsException(); 215ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu } 216b9537aff4a6ff5231030799cdaf931c27fb9579bTim Kilbourn return mElements[mHead]; 217b9537aff4a6ff5231030799cdaf931c27fb9579bTim Kilbourn } 218b9537aff4a6ff5231030799cdaf931c27fb9579bTim Kilbourn 219ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu /** 220ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu * Get last element of the CircularArray. 221ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu * @return The last element. 2223b26e1a1412a8c3b6e7b520b4472d929e7e1e7f4Dake Gu * @throws {@link ArrayIndexOutOfBoundsException} if CircularArray is empty. 223ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu */ 224ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu public E getLast() { 225ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu if (mHead == mTail) { 226ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu throw new ArrayIndexOutOfBoundsException(); 227ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu } 228b9537aff4a6ff5231030799cdaf931c27fb9579bTim Kilbourn return mElements[(mTail - 1) & mCapacityBitmask]; 229b9537aff4a6ff5231030799cdaf931c27fb9579bTim Kilbourn } 230b9537aff4a6ff5231030799cdaf931c27fb9579bTim Kilbourn 231ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu /** 232ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu * Get nth (0 <= n <= size()-1) element of the CircularArray. 233ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu * @param n The zero based element index in the CircularArray. 234ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu * @return The nth element. 2353b26e1a1412a8c3b6e7b520b4472d929e7e1e7f4Dake Gu * @throws {@link ArrayIndexOutOfBoundsException} if n < 0 or n >= size(). 236ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu */ 237ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu public E get(int n) { 238ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu if (n < 0 || n >= size()) { 239ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu throw new ArrayIndexOutOfBoundsException(); 240ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu } 241ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu return mElements[(mHead + n) & mCapacityBitmask]; 242b9537aff4a6ff5231030799cdaf931c27fb9579bTim Kilbourn } 243b9537aff4a6ff5231030799cdaf931c27fb9579bTim Kilbourn 244ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu /** 245ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu * Get number of elements in the CircularArray. 246ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu * @return Number of elements in the CircularArray. 247ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu */ 248ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu public int size() { 249b9537aff4a6ff5231030799cdaf931c27fb9579bTim Kilbourn return (mTail - mHead) & mCapacityBitmask; 250b9537aff4a6ff5231030799cdaf931c27fb9579bTim Kilbourn } 251b9537aff4a6ff5231030799cdaf931c27fb9579bTim Kilbourn 252ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu /** 253ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu * Return true if size() is 0. 254ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu * @return true if size() is 0. 255ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu */ 256ae6b4cc8fd0872c64c4e1295e54e109222938d86Dake Gu public boolean isEmpty() { 257b9537aff4a6ff5231030799cdaf931c27fb9579bTim Kilbourn return mHead == mTail; 258b9537aff4a6ff5231030799cdaf931c27fb9579bTim Kilbourn } 259b9537aff4a6ff5231030799cdaf931c27fb9579bTim Kilbourn 260b9537aff4a6ff5231030799cdaf931c27fb9579bTim Kilbourn} 261