src/com/replica/replicaisland/FixedSizeArray.java

/*
 * Copyright (C) 2010 The Android Open Source Project
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

package com.replica.replicaisland;

import java.util.Arrays;
import java.util.Comparator;

/**
 * FixedSizeArray is an alternative to a standard Java collection like ArrayList.  It is designed
 * to provide a contiguous array of fixed length which can be accessed, sorted, and searched without
 * requiring any runtime allocation.  This implementation makes a distinction between the "capacity"
 * of an array (the maximum number of objects it can contain) and the "count" of an array
 * (the current number of objects inserted into the array).  Operations such as set() and remove()
 * can only operate on objects that have been explicitly add()-ed to the array; that is, indexes
 * larger than getCount() but smaller than getCapacity() can't be used on their own.
 * @param <T> The type of object that this array contains.
 */
public class FixedSizeArray<T> extends AllocationGuard {
    private final static int LINEAR_SEARCH_CUTOFF = 16;
    private final T[] mContents;
    private int mCount;
    private Comparator<T> mComparator;
    private boolean mSorted;
    private Sorter<T> mSorter;
    
    public FixedSizeArray(int size) {
        super();
        assert size > 0;
        // Ugh!  No generic array construction in Java.
        mContents = (T[])new Object[size];
        mCount = 0;
        mSorted = false;
        
        mSorter = new StandardSorter<T>();        
    }
    
    public FixedSizeArray(int size, Comparator<T> comparator) {
        super();
        assert size > 0;
        mContents = (T[])new Object[size];
        mCount = 0;
        mComparator = comparator;
        mSorted = false;
        
        mSorter = new StandardSorter<T>();
    }
    
    /** 
     * Inserts a new object into the array.  If the array is full, an assert is thrown and the
     * object is ignored.
     */
    public final void add(T object) {
        assert mCount < mContents.length : "Array exhausted!";
        if (mCount < mContents.length) {
            mContents[mCount] = object;
            mSorted = false;
            mCount++;
        }
    }
    
    /** 
     * Searches for an object and removes it from the array if it is found.  Other indexes in the
     * array are shifted up to fill the space left by the removed object.  Note that if
     * ignoreComparator is set to true, a linear search of object references will be performed.
     * Otherwise, the comparator set on this array (if any) will be used to find the object.
     */
    public void remove(T object, boolean ignoreComparator) {
        final int index = find(object, ignoreComparator);
        if (index != -1) {
            remove(index);
        }
    }
    
    /** 
     * Removes the specified index from the array.  Subsequent entries in the array are shifted up
     * to fill the space.
     */
    public void remove(int index) {
        assert index < mCount;
        // ugh
        if (index < mCount) {
            for (int x = index; x < mCount; x++) {
                if (x + 1 < mContents.length && x + 1 < mCount) {
                    mContents[x] = mContents[x + 1];
                } else {
                    mContents[x]  = null;
                }
            }
            mCount--;
        }
    }
    
    /**
     * Removes the last element in the array and returns it.  This method is faster than calling
     * remove(count -1);
     * @return The contents of the last element in the array.
     */
    public T removeLast() {
        T object = null;
        if (mCount > 0) {
            object = mContents[mCount - 1];
            mContents[mCount - 1] = null;
            mCount--;
        }
        return object;
    }
    
    /**
     * Swaps the element at the passed index with the element at the end of the array.  When
     * followed by removeLast(), this is useful for quickly removing array elements.
     */
    public void swapWithLast(int index) {
        if (mCount > 0 && index < mCount - 1) {
            T object = mContents[mCount - 1];
            mContents[mCount - 1] = mContents[index];
            mContents[index] = object;
            mSorted = false;
        }
    }
    
    /**
     * Sets the value of a specific index in the array.  An object must have already been added to
     * the array at that index for this command to complete.
     */
    public void set(int index, T object) {
        assert index < mCount;
        if (index < mCount) {
            mContents[index] = object; 
        }
    }
    
    /**
     * Clears the contents of the array, releasing all references to objects it contains and 
     * setting its count to zero.
     */
    public void clear() {
        for (int x = 0; x < mCount; x++) {
            mContents[x] = null;
        }
        mCount = 0;
        mSorted = false;
    }
       
    /**
     * Returns an entry from the array at the specified index.
     */
    public T get(int index) {
        assert index < mCount;
        T result = null;
        if (index < mCount && index >= 0) {
            result = mContents[index];
        }
        return result;
    }
    
    /** 
     * Returns the raw internal array.  Exposed here so that tight loops can cache this array
     * and walk it without the overhead of repeated function calls.  Beware that changing this array
     * can leave FixedSizeArray in an undefined state, so this function is potentially dangerous
     * and should be used in read-only cases.
     * @return The internal storage array.
     */
    public final Object[] getArray() {
        return mContents;
    }
    
    
    /**
     * Searches the array for the specified object.  If the array has been sorted with sort(),
     * and if no other order-changing events have occurred since the sort (e.g. add()), a
     * binary search will be performed.  If a comparator has been specified with setComparator(),
     * it will be used to perform the search.  If not, the default comparator for the object type
     * will be used.  If the array is unsorted, a linear search is performed.
     * Note that if ignoreComparator is set to true, a linear search of object references will be 
     * performed. Otherwise, the comparator set on this array (if any) will be used to find the
     * object.
     * @param object  The object to search for.
     * @return  The index of the object in the array, or -1 if the object is not found.
     */
    public int find(T object, boolean ignoreComparator) {
        int index = -1;
        final int count = mCount;
    	final boolean sorted = mSorted;
    	final Comparator comparator = mComparator;
    	final T[] contents = mContents;
        if (sorted && !ignoreComparator && count > LINEAR_SEARCH_CUTOFF) {
            if (comparator != null) {
                index = Arrays.binarySearch(contents, object, comparator);
            } else {
                index = Arrays.binarySearch(contents, object);
            }
            // Arrays.binarySearch() returns a negative insertion index if the object isn't found,
            // but we just want a boolean.
            if (index < 0) {
                index = -1;
            }
        } else {
            // unsorted, linear search
        	
            if (comparator != null && !ignoreComparator) {
                for (int x = 0; x < count; x++) {
                	final int result = comparator.compare(contents[x], object);
                    if (result == 0) {
                        index = x;
                        break;
                    } else if (result > 0 && sorted) {
                    	// we've passed the object, early out
                    	break;
                    }
                }
            } else {
                for (int x = 0; x < count; x++) {
                    if (contents[x] == object) {
                        index = x;
                        break;
                    } 
                }  
            }
        }
        return index;
    }
    
    /**
     * Sorts the array.  If the array is already sorted, no work will be performed unless
     * the forceResort parameter is set to true.  If a comparator has been specified with
     * setComparator(), it will be used for the sort; otherwise the object's natural ordering will
     * be used.
     * @param forceResort  If set to true, the array will be resorted even if the order of the
     * objects in the array has not changed since the last sort.
     */
    public void sort(boolean forceResort) {
        if (!mSorted || forceResort) {
           if (mComparator != null) {
               mSorter.sort(mContents, mCount, mComparator);
           } else {
               DebugLog.d("FixedSizeArray", "No comparator specified for this type, using Arrays.sort().");
               
               Arrays.sort(mContents, 0, mCount);
           }
           mSorted = true;
        }
    }
    
    /** Returns the number of objects in the array. */
    public int getCount() {
        return mCount;
    }
    
    /** Returns the maximum number of objects that can be inserted inot this array. */
    public int getCapacity() {
        return mContents.length;
    }
    
    /** Sets a comparator to use for sorting and searching. */
    public void setComparator(Comparator<T> comparator) {
        mComparator = comparator;
        mSorted = false;
    }
    
    public void setSorter(Sorter<T> sorter) {
        mSorter = sorter;
    }
}