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 */ 14 package android.support.v4.util; 15 16 /** 17 * CircularIntArray is a circular integer array data structure that provides O(1) random read, O(1) 18 * prepend and O(1) append. The CircularIntArray automatically grows its capacity when number of 19 * added integers is over its capacity. 20 */ 21 public final class CircularIntArray 22 { 23 private int[] mElements; 24 private int mHead; 25 private int mTail; 26 private int mCapacityBitmask; 27 doubleCapacity()28 private void doubleCapacity() { 29 int n = mElements.length; 30 int r = n - mHead; 31 int newCapacity = n << 1; 32 if (newCapacity < 0) { 33 throw new RuntimeException("Max array capacity exceeded"); 34 } 35 int[] a = new int[newCapacity]; 36 System.arraycopy(mElements, mHead, a, 0, r); 37 System.arraycopy(mElements, 0, a, r, mHead); 38 mElements = a; 39 mHead = 0; 40 mTail = n; 41 mCapacityBitmask = newCapacity - 1; 42 } 43 44 /** 45 * Create a CircularIntArray with default capacity. 46 */ CircularIntArray()47 public CircularIntArray() { 48 this(8); 49 } 50 51 /** 52 * Create a CircularIntArray with capacity for at least minCapacity elements. 53 * 54 * @param minCapacity The minimum capacity required for the CircularIntArray. 55 */ CircularIntArray(int minCapacity)56 public CircularIntArray(int minCapacity) { 57 if (minCapacity <= 0) { 58 throw new IllegalArgumentException("capacity must be positive"); 59 } 60 int arrayCapacity = minCapacity; 61 // If minCapacity isn't a power of 2, round up to the next highest power 62 // of 2. 63 if (Integer.bitCount(minCapacity) != 1) { 64 arrayCapacity = 1 << (Integer.highestOneBit(minCapacity) + 1); 65 } 66 mCapacityBitmask = arrayCapacity - 1; 67 mElements = new int[arrayCapacity]; 68 } 69 70 /** 71 * Add an integer in front of the CircularIntArray. 72 * @param e Integer to add. 73 */ addFirst(int e)74 public void addFirst(int e) { 75 mHead = (mHead - 1) & mCapacityBitmask; 76 mElements[mHead] = e; 77 if (mHead == mTail) { 78 doubleCapacity(); 79 } 80 } 81 82 /** 83 * Add an integer at end of the CircularIntArray. 84 * @param e Integer to add. 85 */ addLast(int e)86 public void addLast(int e) { 87 mElements[mTail] = e; 88 mTail = (mTail + 1) & mCapacityBitmask; 89 if (mTail == mHead) { 90 doubleCapacity(); 91 } 92 } 93 94 /** 95 * Remove first integer from front of the CircularIntArray and return it. 96 * @return The integer removed. 97 * @throws ArrayIndexOutOfBoundsException if CircularIntArray is empty. 98 */ popFirst()99 public int popFirst() { 100 if (mHead == mTail) throw new ArrayIndexOutOfBoundsException(); 101 int result = mElements[mHead]; 102 mHead = (mHead + 1) & mCapacityBitmask; 103 return result; 104 } 105 106 /** 107 * Remove last integer from end of the CircularIntArray and return it. 108 * @return The integer removed. 109 * @throws ArrayIndexOutOfBoundsException if CircularIntArray is empty. 110 */ popLast()111 public int popLast() { 112 if (mHead == mTail) throw new ArrayIndexOutOfBoundsException(); 113 int t = (mTail - 1) & mCapacityBitmask; 114 int result = mElements[t]; 115 mTail = t; 116 return result; 117 } 118 119 /** 120 * Remove all integers from the CircularIntArray. 121 */ clear()122 public void clear() { 123 mTail = mHead; 124 } 125 126 /** 127 * Remove multiple integers from front of the CircularIntArray, ignore when numOfElements 128 * is less than or equals to 0. 129 * @param numOfElements Number of integers to remove. 130 * @throws ArrayIndexOutOfBoundsException if numOfElements is larger than 131 * {@link #size()} 132 */ removeFromStart(int numOfElements)133 public void removeFromStart(int numOfElements) { 134 if (numOfElements <= 0) { 135 return; 136 } 137 if (numOfElements > size()) { 138 throw new ArrayIndexOutOfBoundsException(); 139 } 140 mHead = (mHead + numOfElements) & mCapacityBitmask; 141 } 142 143 /** 144 * Remove multiple elements from end of the CircularIntArray, ignore when numOfElements 145 * is less than or equals to 0. 146 * @param numOfElements Number of integers to remove. 147 * @throws ArrayIndexOutOfBoundsException if numOfElements is larger than 148 * {@link #size()} 149 */ removeFromEnd(int numOfElements)150 public void removeFromEnd(int numOfElements) { 151 if (numOfElements <= 0) { 152 return; 153 } 154 if (numOfElements > size()) { 155 throw new ArrayIndexOutOfBoundsException(); 156 } 157 mTail = (mTail - numOfElements) & mCapacityBitmask; 158 } 159 160 /** 161 * Get first integer of the CircularIntArray. 162 * @return The first integer. 163 * @throws {@link ArrayIndexOutOfBoundsException} if CircularIntArray is empty. 164 */ getFirst()165 public int getFirst() { 166 if (mHead == mTail) throw new ArrayIndexOutOfBoundsException(); 167 return mElements[mHead]; 168 } 169 170 /** 171 * Get last integer of the CircularIntArray. 172 * @return The last integer. 173 * @throws {@link ArrayIndexOutOfBoundsException} if CircularIntArray is empty. 174 */ getLast()175 public int getLast() { 176 if (mHead == mTail) throw new ArrayIndexOutOfBoundsException(); 177 return mElements[(mTail - 1) & mCapacityBitmask]; 178 } 179 180 /** 181 * Get nth (0 <= n <= size()-1) integer of the CircularIntArray. 182 * @param n The zero based element index in the CircularIntArray. 183 * @return The nth integer. 184 * @throws {@link ArrayIndexOutOfBoundsException} if n < 0 or n >= size(). 185 */ get(int n)186 public int get(int n) { 187 if (n < 0 || n >= size()) throw new ArrayIndexOutOfBoundsException(); 188 return mElements[(mHead + n) & mCapacityBitmask]; 189 } 190 191 /** 192 * Get number of integers in the CircularIntArray. 193 * @return Number of integers in the CircularIntArray. 194 */ size()195 public int size() { 196 return (mTail - mHead) & mCapacityBitmask; 197 } 198 199 /** 200 * Return true if size() is 0. 201 * @return true if size() is 0. 202 */ isEmpty()203 public boolean isEmpty() { 204 return mHead == mTail; 205 } 206 207 } 208