19d5f84f33353a42e837c6b465412d1a6f2fc6eaaChris Banes/* 29d5f84f33353a42e837c6b465412d1a6f2fc6eaaChris Banes * Copyright (C) 2015 The Android Open Source Project 39d5f84f33353a42e837c6b465412d1a6f2fc6eaaChris Banes * 49d5f84f33353a42e837c6b465412d1a6f2fc6eaaChris Banes * Licensed under the Apache License, Version 2.0 (the "License"); 59d5f84f33353a42e837c6b465412d1a6f2fc6eaaChris Banes * you may not use this file except in compliance with the License. 69d5f84f33353a42e837c6b465412d1a6f2fc6eaaChris Banes * You may obtain a copy of the License at 79d5f84f33353a42e837c6b465412d1a6f2fc6eaaChris Banes * 89d5f84f33353a42e837c6b465412d1a6f2fc6eaaChris Banes * http://www.apache.org/licenses/LICENSE-2.0 99d5f84f33353a42e837c6b465412d1a6f2fc6eaaChris Banes * 109d5f84f33353a42e837c6b465412d1a6f2fc6eaaChris Banes * Unless required by applicable law or agreed to in writing, software 119d5f84f33353a42e837c6b465412d1a6f2fc6eaaChris Banes * distributed under the License is distributed on an "AS IS" BASIS, 129d5f84f33353a42e837c6b465412d1a6f2fc6eaaChris Banes * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 139d5f84f33353a42e837c6b465412d1a6f2fc6eaaChris Banes * See the License for the specific language governing permissions and 149d5f84f33353a42e837c6b465412d1a6f2fc6eaaChris Banes * limitations under the License. 159d5f84f33353a42e837c6b465412d1a6f2fc6eaaChris Banes */ 169d5f84f33353a42e837c6b465412d1a6f2fc6eaaChris Banes 1715aeaf26caa61ed5f3cd367044801d03c1a0a2b5Chris Banespackage android.support.v7.content.res; 189d5f84f33353a42e837c6b465412d1a6f2fc6eaaChris Banes 199d5f84f33353a42e837c6b465412d1a6f2fc6eaaChris Banesimport java.lang.reflect.Array; 209d5f84f33353a42e837c6b465412d1a6f2fc6eaaChris Banes 219d5f84f33353a42e837c6b465412d1a6f2fc6eaaChris Banes/** 229d5f84f33353a42e837c6b465412d1a6f2fc6eaaChris Banes * A helper class that aims to provide comparable growth performance to ArrayList, but on primitive 239d5f84f33353a42e837c6b465412d1a6f2fc6eaaChris Banes * arrays. Common array operations are implemented for efficient use in dynamic containers. 249d5f84f33353a42e837c6b465412d1a6f2fc6eaaChris Banes * 259d5f84f33353a42e837c6b465412d1a6f2fc6eaaChris Banes * All methods in this class assume that the length of an array is equivalent to its capacity and 269d5f84f33353a42e837c6b465412d1a6f2fc6eaaChris Banes * NOT the number of elements in the array. The current size of the array is always passed in as a 279d5f84f33353a42e837c6b465412d1a6f2fc6eaaChris Banes * parameter. 289d5f84f33353a42e837c6b465412d1a6f2fc6eaaChris Banes */ 2915aeaf26caa61ed5f3cd367044801d03c1a0a2b5Chris Banesfinal class GrowingArrayUtils { 309d5f84f33353a42e837c6b465412d1a6f2fc6eaaChris Banes 319d5f84f33353a42e837c6b465412d1a6f2fc6eaaChris Banes /** 329d5f84f33353a42e837c6b465412d1a6f2fc6eaaChris Banes * Appends an element to the end of the array, growing the array if there is no more room. 339d5f84f33353a42e837c6b465412d1a6f2fc6eaaChris Banes * @param array The array to which to append the element. This must NOT be null. 349d5f84f33353a42e837c6b465412d1a6f2fc6eaaChris Banes * @param currentSize The number of elements in the array. Must be less than or equal to 359d5f84f33353a42e837c6b465412d1a6f2fc6eaaChris Banes * array.length. 369d5f84f33353a42e837c6b465412d1a6f2fc6eaaChris Banes * @param element The element to append. 379d5f84f33353a42e837c6b465412d1a6f2fc6eaaChris Banes * @return the array to which the element was appended. This may be different than the given 389d5f84f33353a42e837c6b465412d1a6f2fc6eaaChris Banes * array. 399d5f84f33353a42e837c6b465412d1a6f2fc6eaaChris Banes */ 409d5f84f33353a42e837c6b465412d1a6f2fc6eaaChris Banes public static <T> T[] append(T[] array, int currentSize, T element) { 419d5f84f33353a42e837c6b465412d1a6f2fc6eaaChris Banes assert currentSize <= array.length; 429d5f84f33353a42e837c6b465412d1a6f2fc6eaaChris Banes 439d5f84f33353a42e837c6b465412d1a6f2fc6eaaChris Banes if (currentSize + 1 > array.length) { 449d5f84f33353a42e837c6b465412d1a6f2fc6eaaChris Banes T[] newArray = (T[]) Array.newInstance(array.getClass().getComponentType(), 459d5f84f33353a42e837c6b465412d1a6f2fc6eaaChris Banes growSize(currentSize)); 469d5f84f33353a42e837c6b465412d1a6f2fc6eaaChris Banes System.arraycopy(array, 0, newArray, 0, currentSize); 479d5f84f33353a42e837c6b465412d1a6f2fc6eaaChris Banes array = newArray; 489d5f84f33353a42e837c6b465412d1a6f2fc6eaaChris Banes } 499d5f84f33353a42e837c6b465412d1a6f2fc6eaaChris Banes array[currentSize] = element; 509d5f84f33353a42e837c6b465412d1a6f2fc6eaaChris Banes return array; 519d5f84f33353a42e837c6b465412d1a6f2fc6eaaChris Banes } 529d5f84f33353a42e837c6b465412d1a6f2fc6eaaChris Banes 539d5f84f33353a42e837c6b465412d1a6f2fc6eaaChris Banes /** 549d5f84f33353a42e837c6b465412d1a6f2fc6eaaChris Banes * Primitive int version of {@link #append(Object[], int, Object)}. 559d5f84f33353a42e837c6b465412d1a6f2fc6eaaChris Banes */ 569d5f84f33353a42e837c6b465412d1a6f2fc6eaaChris Banes public static int[] append(int[] array, int currentSize, int element) { 579d5f84f33353a42e837c6b465412d1a6f2fc6eaaChris Banes assert currentSize <= array.length; 589d5f84f33353a42e837c6b465412d1a6f2fc6eaaChris Banes 599d5f84f33353a42e837c6b465412d1a6f2fc6eaaChris Banes if (currentSize + 1 > array.length) { 609d5f84f33353a42e837c6b465412d1a6f2fc6eaaChris Banes int[] newArray = new int[growSize(currentSize)]; 619d5f84f33353a42e837c6b465412d1a6f2fc6eaaChris Banes System.arraycopy(array, 0, newArray, 0, currentSize); 629d5f84f33353a42e837c6b465412d1a6f2fc6eaaChris Banes array = newArray; 639d5f84f33353a42e837c6b465412d1a6f2fc6eaaChris Banes } 649d5f84f33353a42e837c6b465412d1a6f2fc6eaaChris Banes array[currentSize] = element; 659d5f84f33353a42e837c6b465412d1a6f2fc6eaaChris Banes return array; 669d5f84f33353a42e837c6b465412d1a6f2fc6eaaChris Banes } 679d5f84f33353a42e837c6b465412d1a6f2fc6eaaChris Banes 689d5f84f33353a42e837c6b465412d1a6f2fc6eaaChris Banes /** 699d5f84f33353a42e837c6b465412d1a6f2fc6eaaChris Banes * Primitive long version of {@link #append(Object[], int, Object)}. 709d5f84f33353a42e837c6b465412d1a6f2fc6eaaChris Banes */ 719d5f84f33353a42e837c6b465412d1a6f2fc6eaaChris Banes public static long[] append(long[] array, int currentSize, long element) { 729d5f84f33353a42e837c6b465412d1a6f2fc6eaaChris Banes assert currentSize <= array.length; 739d5f84f33353a42e837c6b465412d1a6f2fc6eaaChris Banes 749d5f84f33353a42e837c6b465412d1a6f2fc6eaaChris Banes if (currentSize + 1 > array.length) { 759d5f84f33353a42e837c6b465412d1a6f2fc6eaaChris Banes long[] newArray = new long[growSize(currentSize)]; 769d5f84f33353a42e837c6b465412d1a6f2fc6eaaChris Banes System.arraycopy(array, 0, newArray, 0, currentSize); 779d5f84f33353a42e837c6b465412d1a6f2fc6eaaChris Banes array = newArray; 789d5f84f33353a42e837c6b465412d1a6f2fc6eaaChris Banes } 799d5f84f33353a42e837c6b465412d1a6f2fc6eaaChris Banes array[currentSize] = element; 809d5f84f33353a42e837c6b465412d1a6f2fc6eaaChris Banes return array; 819d5f84f33353a42e837c6b465412d1a6f2fc6eaaChris Banes } 829d5f84f33353a42e837c6b465412d1a6f2fc6eaaChris Banes 839d5f84f33353a42e837c6b465412d1a6f2fc6eaaChris Banes /** 849d5f84f33353a42e837c6b465412d1a6f2fc6eaaChris Banes * Primitive boolean version of {@link #append(Object[], int, Object)}. 859d5f84f33353a42e837c6b465412d1a6f2fc6eaaChris Banes */ 869d5f84f33353a42e837c6b465412d1a6f2fc6eaaChris Banes public static boolean[] append(boolean[] array, int currentSize, boolean element) { 879d5f84f33353a42e837c6b465412d1a6f2fc6eaaChris Banes assert currentSize <= array.length; 889d5f84f33353a42e837c6b465412d1a6f2fc6eaaChris Banes 899d5f84f33353a42e837c6b465412d1a6f2fc6eaaChris Banes if (currentSize + 1 > array.length) { 909d5f84f33353a42e837c6b465412d1a6f2fc6eaaChris Banes boolean[] newArray = new boolean[growSize(currentSize)]; 919d5f84f33353a42e837c6b465412d1a6f2fc6eaaChris Banes System.arraycopy(array, 0, newArray, 0, currentSize); 929d5f84f33353a42e837c6b465412d1a6f2fc6eaaChris Banes array = newArray; 939d5f84f33353a42e837c6b465412d1a6f2fc6eaaChris Banes } 949d5f84f33353a42e837c6b465412d1a6f2fc6eaaChris Banes array[currentSize] = element; 959d5f84f33353a42e837c6b465412d1a6f2fc6eaaChris Banes return array; 969d5f84f33353a42e837c6b465412d1a6f2fc6eaaChris Banes } 979d5f84f33353a42e837c6b465412d1a6f2fc6eaaChris Banes 989d5f84f33353a42e837c6b465412d1a6f2fc6eaaChris Banes /** 999d5f84f33353a42e837c6b465412d1a6f2fc6eaaChris Banes * Inserts an element into the array at the specified index, growing the array if there is no 1009d5f84f33353a42e837c6b465412d1a6f2fc6eaaChris Banes * more room. 1019d5f84f33353a42e837c6b465412d1a6f2fc6eaaChris Banes * 1029d5f84f33353a42e837c6b465412d1a6f2fc6eaaChris Banes * @param array The array to which to append the element. Must NOT be null. 1039d5f84f33353a42e837c6b465412d1a6f2fc6eaaChris Banes * @param currentSize The number of elements in the array. Must be less than or equal to 1049d5f84f33353a42e837c6b465412d1a6f2fc6eaaChris Banes * array.length. 1059d5f84f33353a42e837c6b465412d1a6f2fc6eaaChris Banes * @param element The element to insert. 1069d5f84f33353a42e837c6b465412d1a6f2fc6eaaChris Banes * @return the array to which the element was appended. This may be different than the given 1079d5f84f33353a42e837c6b465412d1a6f2fc6eaaChris Banes * array. 1089d5f84f33353a42e837c6b465412d1a6f2fc6eaaChris Banes */ 1099d5f84f33353a42e837c6b465412d1a6f2fc6eaaChris Banes public static <T> T[] insert(T[] array, int currentSize, int index, T element) { 1109d5f84f33353a42e837c6b465412d1a6f2fc6eaaChris Banes assert currentSize <= array.length; 1119d5f84f33353a42e837c6b465412d1a6f2fc6eaaChris Banes 1129d5f84f33353a42e837c6b465412d1a6f2fc6eaaChris Banes if (currentSize + 1 <= array.length) { 1139d5f84f33353a42e837c6b465412d1a6f2fc6eaaChris Banes System.arraycopy(array, index, array, index + 1, currentSize - index); 1149d5f84f33353a42e837c6b465412d1a6f2fc6eaaChris Banes array[index] = element; 1159d5f84f33353a42e837c6b465412d1a6f2fc6eaaChris Banes return array; 1169d5f84f33353a42e837c6b465412d1a6f2fc6eaaChris Banes } 1179d5f84f33353a42e837c6b465412d1a6f2fc6eaaChris Banes 1189d5f84f33353a42e837c6b465412d1a6f2fc6eaaChris Banes T[] newArray = (T[]) Array.newInstance(array.getClass().getComponentType(), 1199d5f84f33353a42e837c6b465412d1a6f2fc6eaaChris Banes growSize(currentSize)); 1209d5f84f33353a42e837c6b465412d1a6f2fc6eaaChris Banes System.arraycopy(array, 0, newArray, 0, index); 1219d5f84f33353a42e837c6b465412d1a6f2fc6eaaChris Banes newArray[index] = element; 1229d5f84f33353a42e837c6b465412d1a6f2fc6eaaChris Banes System.arraycopy(array, index, newArray, index + 1, array.length - index); 1239d5f84f33353a42e837c6b465412d1a6f2fc6eaaChris Banes return newArray; 1249d5f84f33353a42e837c6b465412d1a6f2fc6eaaChris Banes } 1259d5f84f33353a42e837c6b465412d1a6f2fc6eaaChris Banes 1269d5f84f33353a42e837c6b465412d1a6f2fc6eaaChris Banes /** 1279d5f84f33353a42e837c6b465412d1a6f2fc6eaaChris Banes * Primitive int version of {@link #insert(Object[], int, int, Object)}. 1289d5f84f33353a42e837c6b465412d1a6f2fc6eaaChris Banes */ 1299d5f84f33353a42e837c6b465412d1a6f2fc6eaaChris Banes public static int[] insert(int[] array, int currentSize, int index, int element) { 1309d5f84f33353a42e837c6b465412d1a6f2fc6eaaChris Banes assert currentSize <= array.length; 1319d5f84f33353a42e837c6b465412d1a6f2fc6eaaChris Banes 1329d5f84f33353a42e837c6b465412d1a6f2fc6eaaChris Banes if (currentSize + 1 <= array.length) { 1339d5f84f33353a42e837c6b465412d1a6f2fc6eaaChris Banes System.arraycopy(array, index, array, index + 1, currentSize - index); 1349d5f84f33353a42e837c6b465412d1a6f2fc6eaaChris Banes array[index] = element; 1359d5f84f33353a42e837c6b465412d1a6f2fc6eaaChris Banes return array; 1369d5f84f33353a42e837c6b465412d1a6f2fc6eaaChris Banes } 1379d5f84f33353a42e837c6b465412d1a6f2fc6eaaChris Banes 1389d5f84f33353a42e837c6b465412d1a6f2fc6eaaChris Banes int[] newArray = new int[growSize(currentSize)]; 1399d5f84f33353a42e837c6b465412d1a6f2fc6eaaChris Banes System.arraycopy(array, 0, newArray, 0, index); 1409d5f84f33353a42e837c6b465412d1a6f2fc6eaaChris Banes newArray[index] = element; 1419d5f84f33353a42e837c6b465412d1a6f2fc6eaaChris Banes System.arraycopy(array, index, newArray, index + 1, array.length - index); 1429d5f84f33353a42e837c6b465412d1a6f2fc6eaaChris Banes return newArray; 1439d5f84f33353a42e837c6b465412d1a6f2fc6eaaChris Banes } 1449d5f84f33353a42e837c6b465412d1a6f2fc6eaaChris Banes 1459d5f84f33353a42e837c6b465412d1a6f2fc6eaaChris Banes /** 1469d5f84f33353a42e837c6b465412d1a6f2fc6eaaChris Banes * Primitive long version of {@link #insert(Object[], int, int, Object)}. 1479d5f84f33353a42e837c6b465412d1a6f2fc6eaaChris Banes */ 1489d5f84f33353a42e837c6b465412d1a6f2fc6eaaChris Banes public static long[] insert(long[] array, int currentSize, int index, long element) { 1499d5f84f33353a42e837c6b465412d1a6f2fc6eaaChris Banes assert currentSize <= array.length; 1509d5f84f33353a42e837c6b465412d1a6f2fc6eaaChris Banes 1519d5f84f33353a42e837c6b465412d1a6f2fc6eaaChris Banes if (currentSize + 1 <= array.length) { 1529d5f84f33353a42e837c6b465412d1a6f2fc6eaaChris Banes System.arraycopy(array, index, array, index + 1, currentSize - index); 1539d5f84f33353a42e837c6b465412d1a6f2fc6eaaChris Banes array[index] = element; 1549d5f84f33353a42e837c6b465412d1a6f2fc6eaaChris Banes return array; 1559d5f84f33353a42e837c6b465412d1a6f2fc6eaaChris Banes } 1569d5f84f33353a42e837c6b465412d1a6f2fc6eaaChris Banes 1579d5f84f33353a42e837c6b465412d1a6f2fc6eaaChris Banes long[] newArray = new long[growSize(currentSize)]; 1589d5f84f33353a42e837c6b465412d1a6f2fc6eaaChris Banes System.arraycopy(array, 0, newArray, 0, index); 1599d5f84f33353a42e837c6b465412d1a6f2fc6eaaChris Banes newArray[index] = element; 1609d5f84f33353a42e837c6b465412d1a6f2fc6eaaChris Banes System.arraycopy(array, index, newArray, index + 1, array.length - index); 1619d5f84f33353a42e837c6b465412d1a6f2fc6eaaChris Banes return newArray; 1629d5f84f33353a42e837c6b465412d1a6f2fc6eaaChris Banes } 1639d5f84f33353a42e837c6b465412d1a6f2fc6eaaChris Banes 1649d5f84f33353a42e837c6b465412d1a6f2fc6eaaChris Banes /** 1659d5f84f33353a42e837c6b465412d1a6f2fc6eaaChris Banes * Primitive boolean version of {@link #insert(Object[], int, int, Object)}. 1669d5f84f33353a42e837c6b465412d1a6f2fc6eaaChris Banes */ 1679d5f84f33353a42e837c6b465412d1a6f2fc6eaaChris Banes public static boolean[] insert(boolean[] array, int currentSize, int index, boolean element) { 1689d5f84f33353a42e837c6b465412d1a6f2fc6eaaChris Banes assert currentSize <= array.length; 1699d5f84f33353a42e837c6b465412d1a6f2fc6eaaChris Banes 1709d5f84f33353a42e837c6b465412d1a6f2fc6eaaChris Banes if (currentSize + 1 <= array.length) { 1719d5f84f33353a42e837c6b465412d1a6f2fc6eaaChris Banes System.arraycopy(array, index, array, index + 1, currentSize - index); 1729d5f84f33353a42e837c6b465412d1a6f2fc6eaaChris Banes array[index] = element; 1739d5f84f33353a42e837c6b465412d1a6f2fc6eaaChris Banes return array; 1749d5f84f33353a42e837c6b465412d1a6f2fc6eaaChris Banes } 1759d5f84f33353a42e837c6b465412d1a6f2fc6eaaChris Banes 1769d5f84f33353a42e837c6b465412d1a6f2fc6eaaChris Banes boolean[] newArray = new boolean[growSize(currentSize)]; 1779d5f84f33353a42e837c6b465412d1a6f2fc6eaaChris Banes System.arraycopy(array, 0, newArray, 0, index); 1789d5f84f33353a42e837c6b465412d1a6f2fc6eaaChris Banes newArray[index] = element; 1799d5f84f33353a42e837c6b465412d1a6f2fc6eaaChris Banes System.arraycopy(array, index, newArray, index + 1, array.length - index); 1809d5f84f33353a42e837c6b465412d1a6f2fc6eaaChris Banes return newArray; 1819d5f84f33353a42e837c6b465412d1a6f2fc6eaaChris Banes } 1829d5f84f33353a42e837c6b465412d1a6f2fc6eaaChris Banes 1839d5f84f33353a42e837c6b465412d1a6f2fc6eaaChris Banes /** 1849d5f84f33353a42e837c6b465412d1a6f2fc6eaaChris Banes * Given the current size of an array, returns an ideal size to which the array should grow. 1859d5f84f33353a42e837c6b465412d1a6f2fc6eaaChris Banes * This is typically double the given size, but should not be relied upon to do so in the 1869d5f84f33353a42e837c6b465412d1a6f2fc6eaaChris Banes * future. 1879d5f84f33353a42e837c6b465412d1a6f2fc6eaaChris Banes */ 1889d5f84f33353a42e837c6b465412d1a6f2fc6eaaChris Banes public static int growSize(int currentSize) { 1899d5f84f33353a42e837c6b465412d1a6f2fc6eaaChris Banes return currentSize <= 4 ? 8 : currentSize * 2; 1909d5f84f33353a42e837c6b465412d1a6f2fc6eaaChris Banes } 1919d5f84f33353a42e837c6b465412d1a6f2fc6eaaChris Banes 1929d5f84f33353a42e837c6b465412d1a6f2fc6eaaChris Banes // Uninstantiable 1939d5f84f33353a42e837c6b465412d1a6f2fc6eaaChris Banes private GrowingArrayUtils() {} 1949d5f84f33353a42e837c6b465412d1a6f2fc6eaaChris Banes}