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