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
17package com.replica.replicaisland;
18
19import java.util.Arrays;
20import 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 */
32public 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
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
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     */
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