1 /* 2 * Copyright (C) 2019 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 */ 16 17 package android.util; 18 19 import com.android.internal.util.ArrayUtils; 20 import com.android.internal.util.GrowingArrayUtils; 21 22 import libcore.util.EmptyArray; 23 24 import java.util.NoSuchElementException; 25 26 /** 27 * A lightweight implementation for a queue with long values. 28 * Additionally supports getting an element with a specified position from the head of the queue. 29 * The queue grows in size if needed to accommodate new elements. 30 * 31 * @hide 32 */ 33 public class LongArrayQueue { 34 35 private long[] mValues; 36 private int mSize; 37 private int mHead; 38 private int mTail; 39 40 /** 41 * Initializes a queue with the given starting capacity. 42 * 43 * @param initialCapacity the capacity. 44 */ LongArrayQueue(int initialCapacity)45 public LongArrayQueue(int initialCapacity) { 46 if (initialCapacity == 0) { 47 mValues = EmptyArray.LONG; 48 } else { 49 mValues = ArrayUtils.newUnpaddedLongArray(initialCapacity); 50 } 51 mSize = 0; 52 mHead = mTail = 0; 53 } 54 55 /** 56 * Initializes a queue with default starting capacity. 57 */ LongArrayQueue()58 public LongArrayQueue() { 59 this(16); 60 } 61 grow()62 private void grow() { 63 if (mSize < mValues.length) { 64 throw new IllegalStateException("Queue not full yet!"); 65 } 66 final int newSize = GrowingArrayUtils.growSize(mSize); 67 final long[] newArray = ArrayUtils.newUnpaddedLongArray(newSize); 68 final int r = mValues.length - mHead; // Number of elements on and to the right of head. 69 System.arraycopy(mValues, mHead, newArray, 0, r); 70 System.arraycopy(mValues, 0, newArray, r, mHead); 71 mValues = newArray; 72 mHead = 0; 73 mTail = mSize; 74 } 75 76 /** 77 * Returns the number of elements in the queue. 78 */ size()79 public int size() { 80 return mSize; 81 } 82 83 /** 84 * Removes all elements from this queue. 85 */ clear()86 public void clear() { 87 mSize = 0; 88 mHead = mTail = 0; 89 } 90 91 /** 92 * Adds a value to the tail of the queue. 93 * 94 * @param value the value to be added. 95 */ addLast(long value)96 public void addLast(long value) { 97 if (mSize == mValues.length) { 98 grow(); 99 } 100 mValues[mTail] = value; 101 mTail = (mTail + 1) % mValues.length; 102 mSize++; 103 } 104 105 /** 106 * Removes an element from the head of the queue. 107 * 108 * @return the element at the head of the queue. 109 * @throws NoSuchElementException if the queue is empty. 110 */ removeFirst()111 public long removeFirst() { 112 if (mSize == 0) { 113 throw new NoSuchElementException("Queue is empty!"); 114 } 115 final long ret = mValues[mHead]; 116 mHead = (mHead + 1) % mValues.length; 117 mSize--; 118 return ret; 119 } 120 121 /** 122 * Returns the element at the given position from the head of the queue, where 0 represents the 123 * head of the queue. 124 * 125 * @param position the position from the head of the queue. 126 * @return the element found at the given position. 127 * @throws IndexOutOfBoundsException if {@code position} < {@code 0} or 128 * {@code position} >= {@link #size()} 129 */ get(int position)130 public long get(int position) { 131 if (position < 0 || position >= mSize) { 132 throw new IndexOutOfBoundsException("Index " + position 133 + " not valid for a queue of size " + mSize); 134 } 135 final int index = (mHead + position) % mValues.length; 136 return mValues[index]; 137 } 138 139 /** 140 * Returns the element at the head of the queue, without removing it. 141 * 142 * @return the element at the head of the queue. 143 * @throws NoSuchElementException if the queue is empty 144 */ peekFirst()145 public long peekFirst() { 146 if (mSize == 0) { 147 throw new NoSuchElementException("Queue is empty!"); 148 } 149 return mValues[mHead]; 150 } 151 152 /** 153 * Returns the element at the tail of the queue. 154 * 155 * @return the element at the tail of the queue. 156 * @throws NoSuchElementException if the queue is empty. 157 */ peekLast()158 public long peekLast() { 159 if (mSize == 0) { 160 throw new NoSuchElementException("Queue is empty!"); 161 } 162 final int index = (mTail == 0) ? mValues.length - 1 : mTail - 1; 163 return mValues[index]; 164 } 165 166 /** 167 * {@inheritDoc} 168 */ 169 @Override toString()170 public String toString() { 171 if (mSize <= 0) { 172 return "{}"; 173 } 174 175 final StringBuilder buffer = new StringBuilder(mSize * 64); 176 buffer.append('{'); 177 buffer.append(get(0)); 178 for (int i = 1; i < mSize; i++) { 179 buffer.append(", "); 180 buffer.append(get(i)); 181 } 182 buffer.append('}'); 183 return buffer.toString(); 184 } 185 } 186