1 /*
2  * Copyright (C) 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  */
16 
17 package com.android.launcher3.util;
18 
19 import java.util.Arrays;
20 import java.util.StringTokenizer;
21 
22 /**
23  * Copy of the platform hidden implementation of android.util.IntArray.
24  * Implements a growing array of int primitives.
25  */
26 public class IntArray implements Cloneable {
27     private static final int MIN_CAPACITY_INCREMENT = 12;
28 
29     private static final int[] EMPTY_INT = new int[0];
30 
31     /* package private */ int[] mValues;
32     /* package private */ int mSize;
33 
IntArray(int[] array, int size)34     private  IntArray(int[] array, int size) {
35         mValues = array;
36         mSize = size;
37     }
38 
39     /**
40      * Creates an empty IntArray with the default initial capacity.
41      */
IntArray()42     public IntArray() {
43         this(10);
44     }
45 
46     /**
47      * Creates an empty IntArray with the specified initial capacity.
48      */
IntArray(int initialCapacity)49     public IntArray(int initialCapacity) {
50         if (initialCapacity == 0) {
51             mValues = EMPTY_INT;
52         } else {
53             mValues = new int[initialCapacity];
54         }
55         mSize = 0;
56     }
57 
58     /**
59      * Creates an IntArray wrapping the given primitive int array.
60      */
wrap(int... array)61     public static IntArray wrap(int... array) {
62         return new IntArray(array, array.length);
63     }
64 
65     /**
66      * Appends the specified value to the end of this array.
67      */
add(int value)68     public void add(int value) {
69         add(mSize, value);
70     }
71 
72     /**
73      * Inserts a value at the specified position in this array. If the specified index is equal to
74      * the length of the array, the value is added at the end.
75      *
76      * @throws IndexOutOfBoundsException when index < 0 || index > size()
77      */
add(int index, int value)78     public void add(int index, int value) {
79         ensureCapacity(1);
80         int rightSegment = mSize - index;
81         mSize++;
82         checkBounds(mSize, index);
83 
84         if (rightSegment != 0) {
85             // Move by 1 all values from the right of 'index'
86             System.arraycopy(mValues, index, mValues, index + 1, rightSegment);
87         }
88 
89         mValues[index] = value;
90     }
91 
92     /**
93      * Adds the values in the specified array to this array.
94      */
addAll(IntArray values)95     public void addAll(IntArray values) {
96         final int count = values.mSize;
97         ensureCapacity(count);
98 
99         System.arraycopy(values.mValues, 0, mValues, mSize, count);
100         mSize += count;
101     }
102 
103     /**
104      * Sets the array to be same as {@param other}
105      */
copyFrom(IntArray other)106     public void copyFrom(IntArray other) {
107         clear();
108         addAll(other);
109     }
110 
111     /**
112      * Ensures capacity to append at least <code>count</code> values.
113      */
ensureCapacity(int count)114     private void ensureCapacity(int count) {
115         final int currentSize = mSize;
116         final int minCapacity = currentSize + count;
117         if (minCapacity >= mValues.length) {
118             final int targetCap = currentSize + (currentSize < (MIN_CAPACITY_INCREMENT / 2) ?
119                     MIN_CAPACITY_INCREMENT : currentSize >> 1);
120             final int newCapacity = targetCap > minCapacity ? targetCap : minCapacity;
121             final int[] newValues = new int[newCapacity];
122             System.arraycopy(mValues, 0, newValues, 0, currentSize);
123             mValues = newValues;
124         }
125     }
126 
127     /**
128      * Removes all values from this array.
129      */
clear()130     public void clear() {
131         mSize = 0;
132     }
133 
134     @Override
clone()135     public IntArray clone() {
136         return wrap(toArray());
137     }
138 
139     @Override
equals(Object obj)140     public boolean equals(Object obj) {
141         if (obj == this) {
142             return true;
143         }
144         if (obj instanceof IntArray) {
145             IntArray arr = (IntArray) obj;
146             if (mSize == arr.mSize) {
147                 for (int i = 0; i < mSize; i++) {
148                     if (arr.mValues[i] != mValues[i]) {
149                         return false;
150                     }
151                 }
152                 return true;
153             }
154         }
155         return false;
156     }
157 
158     /**
159      * Returns the value at the specified position in this array.
160      */
get(int index)161     public int get(int index) {
162         checkBounds(mSize, index);
163         return mValues[index];
164     }
165 
166     /**
167      * Sets the value at the specified position in this array.
168      */
set(int index, int value)169     public void set(int index, int value) {
170         checkBounds(mSize, index);
171         mValues[index] = value;
172     }
173 
174     /**
175      * Returns the index of the first occurrence of the specified value in this
176      * array, or -1 if this array does not contain the value.
177      */
indexOf(int value)178     public int indexOf(int value) {
179         final int n = mSize;
180         for (int i = 0; i < n; i++) {
181             if (mValues[i] == value) {
182                 return i;
183             }
184         }
185         return -1;
186     }
187 
contains(int value)188     public boolean contains(int value) {
189         return indexOf(value) >= 0;
190     }
191 
isEmpty()192     public boolean isEmpty() {
193         return mSize == 0;
194     }
195 
196     /**
197      * Removes the value at the specified index from this array.
198      */
removeIndex(int index)199     public void removeIndex(int index) {
200         checkBounds(mSize, index);
201         System.arraycopy(mValues, index + 1, mValues, index, mSize - index - 1);
202         mSize--;
203     }
204 
205     /**
206      * Removes the values if it exists
207      */
removeValue(int value)208     public void removeValue(int value) {
209         int index = indexOf(value);
210         if (index >= 0) {
211             removeIndex(index);
212         }
213     }
214 
215     /**
216      * Removes the values if it exists
217      */
removeAllValues(IntArray values)218     public void removeAllValues(IntArray values) {
219         for (int i = 0; i < values.mSize; i++) {
220             removeValue(values.mValues[i]);
221         }
222     }
223 
224     /**
225      * Returns the number of values in this array.
226      */
size()227     public int size() {
228         return mSize;
229     }
230 
231     /**
232      * Returns a new array with the contents of this IntArray.
233      */
toArray()234     public int[] toArray() {
235         return mSize == 0 ? EMPTY_INT : Arrays.copyOf(mValues, mSize);
236     }
237 
238     /**
239      * Returns a comma separate list of all values.
240      */
toConcatString()241     public String toConcatString() {
242         StringBuilder b = new StringBuilder();
243         for (int i = 0; i < mSize ; i++) {
244             if (i > 0) {
245                 b.append(", ");
246             }
247             b.append(mValues[i]);
248         }
249         return b.toString();
250     }
251 
fromConcatString(String concatString)252     public static IntArray fromConcatString(String concatString) {
253         StringTokenizer tokenizer = new StringTokenizer(concatString, ",");
254         int[] array = new int[tokenizer.countTokens()];
255         int count = 0;
256         while (tokenizer.hasMoreTokens()) {
257             array[count] = Integer.parseInt(tokenizer.nextToken().trim());
258             count++;
259         }
260         return new IntArray(array, array.length);
261     }
262 
263     /**
264      * Throws {@link ArrayIndexOutOfBoundsException} if the index is out of bounds.
265      *
266      * @param len length of the array. Must be non-negative
267      * @param index the index to check
268      * @throws ArrayIndexOutOfBoundsException if the {@code index} is out of bounds of the array
269      */
checkBounds(int len, int index)270     private static void checkBounds(int len, int index) {
271         if (index < 0 || len <= index) {
272             throw new ArrayIndexOutOfBoundsException("length=" + len + "; index=" + index);
273         }
274     }
275 }