//E對應HashMap的Value
public class SparseArray<E> implements Cloneable {
    // 用來優化刪除性能（當有元素被remove delete時），標記已經刪除的對象為DELETE
    private static final Object DELETED = new Object();
    // 用來優化刪除性能，標記是否需要垃圾回收
    private boolean mGarbage = false;
    // 存儲索引，整數索引（key為整數）從小到大被映射在該數組
    private int[] mKeys;
    // 存儲對象（Value）
    private Object[] mValues;
    // SparseArray實際大小
    private int mSize;

    public SparseArray() {
        //默認容量是10個元素
        this(10);
    }

    public SparseArray(int initialCapacity) {
        if (initialCapacity == 0) {
             //mKeys的初值等于new int[0],mValues的初值等于new Object[0]
            mKeys = EmptyArray.INT;
            mValues = EmptyArray.OBJECT;
        } else {
            //newUnpaddedObjectArray最后指向了VMRuntime的一個native方法,返回一個至少長initialCapacity的數組，
            mValues = ArrayUtils.newUnpaddedObjectArray(initialCapacity);
            mKeys = new int[mValues.length];
        }
        mSize = 0;
    }

    /**
     * 獲得指定key的映射對象，或者null如果沒有該映射。
     */
    public E get(int key) {
        return get(key, null);
    }

    @SuppressWarnings("unchecked")
    public E get(int key, E valueIfKeyNotFound) {
        //二分查找
        int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
        // 如果沒找到或者該value已經被標記刪除,則返回默認值
        if (i < 0 || mValues[i] == DELETED) {
            return valueIfKeyNotFound;
        } else {
             // i>0 且該位置的元素未被標記為待刪除，返回該值mValues[i]
            return (E) mValues[i];
        }
    }

    public void remove(int key) {
        //調用delete執行刪除操作
        delete(key);
    }

    /**
     * Removes the mapping from the specified key, if there was any.
     */
    /**
     * 刪除指定key的映射對象。
     */
    public void delete(int key) {
        //二分查找
        int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
        //找到了
        if (i >= 0) {
             //若未被標記delete，標記為delete，回收mGarbage=true
            if (mValues[i] != DELETED) {
                mValues[i] = DELETED;
                mGarbage = true;
            }
        }
    }

    //目的只有一個壓縮空間（壓縮數組，把無效的值刪除）
    private void gc() {
        // Log.e("SparseArray", "gc start with " + mSize);
        int n = mSize;
        int o = 0;
        int[] keys = mKeys;
        Object[] values = mValues;
        //循環整個元素區間，刪除值為DELETED的數，這里比較巧妙，直接對同一個keys和values操作，完成元素的刪除和移動！
        for (int i = 0; i < n; i++) {
            Object val = values[i];

            if (val != DELETED) {
                if (i != o) {
                    keys[o] = keys[i];
                    values[o] = val;
                    values[i] = null;
                }
                o++;
            }
        }
        mGarbage = false;
        mSize = o;//實際大小

        // Log.e("SparseArray", "gc end with " + mSize);
    }

    /**
     * 添加一個指定key到指定object的映射，如果之前有一個指定key的映射則直接替換掉原映射object。注意gc。
     */
    public void put(int key, E value) {
        //先二分查找，確定插入位置，保證了key數組的有序性
        int i = ContainerHelpers.binarySearch(mKeys, mSize, key);

        if (i >= 0) {
            //找到了，直接替換
            mValues[i] = value;
        } else {
            // 做一個取反運算，獲得應該插入的index
            //沒找到的情況下： i = -insertPoint -1，對他取反剛好得insertPoint。
            i = ~i;
            //若i在size范圍內，且剛好對應位置標記為delete了，直接放入
            if (i < mSize && mValues[i] == DELETED) {
                mKeys[i] = key;
                mValues[i] = value;
                return;
            }
            //若前面if不成立，即i超出了size范圍，或者對應的位置的元素是有效的
            // 如果被標記為需要垃圾回收且SparseArray大小不小于keys數組長度
            if (mGarbage && mSize >= mKeys.length) {
                // 壓縮空間，會壓縮數組，把無效的值都去掉，保證連續有效值
                gc();
                // Search again because indices may have changed.
                // 再次查找插入點因為索引可能改變
                i = ~ContainerHelpers.binarySearch(mKeys, mSize, key);
            }
            // 插入，如果size不夠則會重新分配更大的數組，然后拷貝過去并插入；size足夠則用System.arraycopy把插入位置開始的value都后移然后插入
            mKeys = GrowingArrayUtils.insert(mKeys, mSize, i, key);
            mValues = GrowingArrayUtils.insert(mValues, mSize, i, value);
            // 實際大小加1
            mSize++;
        }
    }

    /**
     * Returns the number of key-value mappings that this SparseArray
     * currently stores.
     */
    //返回mSize，注意gc。
    public int size() {
        if (mGarbage) {
            gc();
        }
        return mSize;
    }

}