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