Home | History | Annotate | Download | only in util 
      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      */
     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      */
     58     public LongArrayQueue() {
     59         this(16);
     60     }
     61 
     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      */
     79     public int size() {
     80         return mSize;
     81     }
     82 
     83     /**
     84      * Removes all elements from this queue.
     85      */
     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      */
     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      */
    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      */
    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      */
    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      */
    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