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