1 /* 2 * Copyright (C) 2010 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.replica.replicaisland; 18 19 import java.util.Arrays; 20 import java.util.Comparator; 21 22 /** 23 * FixedSizeArray is an alternative to a standard Java collection like ArrayList. It is designed 24 * to provide a contiguous array of fixed length which can be accessed, sorted, and searched without 25 * requiring any runtime allocation. This implementation makes a distinction between the "capacity" 26 * of an array (the maximum number of objects it can contain) and the "count" of an array 27 * (the current number of objects inserted into the array). Operations such as set() and remove() 28 * can only operate on objects that have been explicitly add()-ed to the array; that is, indexes 29 * larger than getCount() but smaller than getCapacity() can't be used on their own. 30 * @param <T> The type of object that this array contains. 31 */ 32 public class FixedSizeArray<T> extends AllocationGuard { 33 private final static int LINEAR_SEARCH_CUTOFF = 16; 34 private final T[] mContents; 35 private int mCount; 36 private Comparator<T> mComparator; 37 private boolean mSorted; 38 private Sorter<T> mSorter; 39 FixedSizeArray(int size)40 public FixedSizeArray(int size) { 41 super(); 42 assert size > 0; 43 // Ugh! No generic array construction in Java. 44 mContents = (T[])new Object[size]; 45 mCount = 0; 46 mSorted = false; 47 48 mSorter = new StandardSorter<T>(); 49 } 50 FixedSizeArray(int size, Comparator<T> comparator)51 public FixedSizeArray(int size, Comparator<T> comparator) { 52 super(); 53 assert size > 0; 54 mContents = (T[])new Object[size]; 55 mCount = 0; 56 mComparator = comparator; 57 mSorted = false; 58 59 mSorter = new StandardSorter<T>(); 60 } 61 62 /** 63 * Inserts a new object into the array. If the array is full, an assert is thrown and the 64 * object is ignored. 65 */ add(T object)66 public final void add(T object) { 67 assert mCount < mContents.length : "Array exhausted!"; 68 if (mCount < mContents.length) { 69 mContents[mCount] = object; 70 mSorted = false; 71 mCount++; 72 } 73 } 74 75 /** 76 * Searches for an object and removes it from the array if it is found. Other indexes in the 77 * array are shifted up to fill the space left by the removed object. Note that if 78 * ignoreComparator is set to true, a linear search of object references will be performed. 79 * Otherwise, the comparator set on this array (if any) will be used to find the object. 80 */ 81 public void remove(T object, boolean ignoreComparator) { 82 final int index = find(object, ignoreComparator); 83 if (index != -1) { 84 remove(index); 85 } 86 } 87 88 /** 89 * Removes the specified index from the array. Subsequent entries in the array are shifted up 90 * to fill the space. 91 */ 92 public void remove(int index) { 93 assert index < mCount; 94 // ugh 95 if (index < mCount) { 96 for (int x = index; x < mCount; x++) { 97 if (x + 1 < mContents.length && x + 1 < mCount) { 98 mContents[x] = mContents[x + 1]; 99 } else { 100 mContents[x] = null; 101 } 102 } 103 mCount--; 104 } 105 } 106 107 /** 108 * Removes the last element in the array and returns it. This method is faster than calling 109 * remove(count -1); 110 * @return The contents of the last element in the array. 111 */ 112 public T removeLast() { 113 T object = null; 114 if (mCount > 0) { 115 object = mContents[mCount - 1]; 116 mContents[mCount - 1] = null; 117 mCount--; 118 } 119 return object; 120 } 121 122 /** 123 * Swaps the element at the passed index with the element at the end of the array. When 124 * followed by removeLast(), this is useful for quickly removing array elements. 125 */ 126 public void swapWithLast(int index) { 127 if (mCount > 0 && index < mCount - 1) { 128 T object = mContents[mCount - 1]; 129 mContents[mCount - 1] = mContents[index]; 130 mContents[index] = object; 131 mSorted = false; 132 } 133 } 134 135 /** 136 * Sets the value of a specific index in the array. An object must have already been added to 137 * the array at that index for this command to complete. 138 */ 139 public void set(int index, T object) { 140 assert index < mCount; 141 if (index < mCount) { 142 mContents[index] = object; 143 } 144 } 145 146 /** 147 * Clears the contents of the array, releasing all references to objects it contains and 148 * setting its count to zero. 149 */ 150 public void clear() { 151 for (int x = 0; x < mCount; x++) { 152 mContents[x] = null; 153 } 154 mCount = 0; 155 mSorted = false; 156 } 157 158 /** 159 * Returns an entry from the array at the specified index. 160 */ 161 public T get(int index) { 162 assert index < mCount; 163 T result = null; 164 if (index < mCount && index >= 0) { 165 result = mContents[index]; 166 } 167 return result; 168 } 169 170 /** 171 * Returns the raw internal array. Exposed here so that tight loops can cache this array 172 * and walk it without the overhead of repeated function calls. Beware that changing this array 173 * can leave FixedSizeArray in an undefined state, so this function is potentially dangerous 174 * and should be used in read-only cases. 175 * @return The internal storage array. 176 */ 177 public final Object[] getArray() { 178 return mContents; 179 } 180 181 182 /** 183 * Searches the array for the specified object. If the array has been sorted with sort(), 184 * and if no other order-changing events have occurred since the sort (e.g. add()), a 185 * binary search will be performed. If a comparator has been specified with setComparator(), 186 * it will be used to perform the search. If not, the default comparator for the object type 187 * will be used. If the array is unsorted, a linear search is performed. 188 * Note that if ignoreComparator is set to true, a linear search of object references will be 189 * performed. Otherwise, the comparator set on this array (if any) will be used to find the 190 * object. 191 * @param object The object to search for. 192 * @return The index of the object in the array, or -1 if the object is not found. 193 */ 194 public int find(T object, boolean ignoreComparator) { 195 int index = -1; 196 final int count = mCount; 197 final boolean sorted = mSorted; 198 final Comparator comparator = mComparator; 199 final T[] contents = mContents; 200 if (sorted && !ignoreComparator && count > LINEAR_SEARCH_CUTOFF) { 201 if (comparator != null) { 202 index = Arrays.binarySearch(contents, object, comparator); 203 } else { 204 index = Arrays.binarySearch(contents, object); 205 } 206 // Arrays.binarySearch() returns a negative insertion index if the object isn't found, 207 // but we just want a boolean. 208 if (index < 0) { 209 index = -1; 210 } 211 } else { 212 // unsorted, linear search 213 214 if (comparator != null && !ignoreComparator) { 215 for (int x = 0; x < count; x++) { 216 final int result = comparator.compare(contents[x], object); 217 if (result == 0) { 218 index = x; 219 break; 220 } else if (result > 0 && sorted) { 221 // we've passed the object, early out 222 break; 223 } 224 } 225 } else { 226 for (int x = 0; x < count; x++) { 227 if (contents[x] == object) { 228 index = x; 229 break; 230 } 231 } 232 } 233 } 234 return index; 235 } 236 237 /** 238 * Sorts the array. If the array is already sorted, no work will be performed unless 239 * the forceResort parameter is set to true. If a comparator has been specified with 240 * setComparator(), it will be used for the sort; otherwise the object's natural ordering will 241 * be used. 242 * @param forceResort If set to true, the array will be resorted even if the order of the 243 * objects in the array has not changed since the last sort. 244 */ 245 public void sort(boolean forceResort) { 246 if (!mSorted || forceResort) { 247 if (mComparator != null) { 248 mSorter.sort(mContents, mCount, mComparator); 249 } else { 250 DebugLog.d("FixedSizeArray", "No comparator specified for this type, using Arrays.sort()."); 251 252 Arrays.sort(mContents, 0, mCount); 253 } 254 mSorted = true; 255 } 256 } 257 258 /** Returns the number of objects in the array. */ 259 public int getCount() { 260 return mCount; 261 } 262 263 /** Returns the maximum number of objects that can be inserted inot this array. */ 264 public int getCapacity() { 265 return mContents.length; 266 } 267 268 /** Sets a comparator to use for sorting and searching. */ 269 public void setComparator(Comparator<T> comparator) { 270 mComparator = comparator; 271 mSorted = false; 272 } 273 274 public void setSorter(Sorter<T> sorter) { 275 mSorter = sorter; 276 } 277 } 278