Adding APIs to enable reporting virtual view hierarchies to accessibility serivces.

Added an interface that is the contract for a client to expose a virtual
view hierarchy to accessibility services. Clients impement this interface
and set it in the View that is the root of the virtual sub-tree. Adding
this finctionality via compostion as opposed to inheritance enables apps
to maintain backwards compatibility by setting the accessibility virtual
hierarchy provider on the View only if the API version is high enough.

bug:5382859

Change-Id: I7e3927b71a5517943c6cb071be2e87fba23132bf

1 files changed, 247 insertions, 0 deletions

diff --git a/core/java/android/util/SparseLongArray.java b/core/java/android/util/SparseLongArray.java
new file mode 100644
index 0000000..a08d5cb
--- /dev/null
+++ b/core/java/android/util/SparseLongArray.java
@@ -0,0 +1,247 @@
+/*
+ * Copyright (C) 2011 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 android.util;
+
+import com.android.internal.util.ArrayUtils;
+
+/**
+ * SparseLongArrays map integers to longs.  Unlike a normal array of longs,
+ * there can be gaps in the indices.  It is intended to be more efficient
+ * than using a HashMap to map Integers to Longs.
+ *
+ * @hide
+ */
+public class SparseLongArray implements Cloneable {
+
+    private int[] mKeys;
+    private long[] mValues;
+    private int mSize;
+
+    /**
+     * Creates a new SparseLongArray containing no mappings.
+     */
+    public SparseLongArray() {
+        this(10);
+    }
+
+    /**
+     * Creates a new SparseLongArray containing no mappings that will not
+     * require any additional memory allocation to store the specified
+     * number of mappings.
+     */
+    public SparseLongArray(int initialCapacity) {
+        initialCapacity = ArrayUtils.idealLongArraySize(initialCapacity);
+
+        mKeys = new int[initialCapacity];
+        mValues = new long[initialCapacity];
+        mSize = 0;
+    }
+
+    @Override
+    public SparseLongArray clone() {
+        SparseLongArray clone = null;
+        try {
+            clone = (SparseLongArray) super.clone();
+            clone.mKeys = mKeys.clone();
+            clone.mValues = mValues.clone();
+        } catch (CloneNotSupportedException cnse) {
+            /* ignore */
+        }
+        return clone;
+    }
+
+    /**
+     * Gets the long mapped from the specified key, or <code>0</code>
+     * if no such mapping has been made.
+     */
+    public long get(int key) {
+        return get(key, 0);
+    }
+
+    /**
+     * Gets the long mapped from the specified key, or the specified value
+     * if no such mapping has been made.
+     */
+    public long get(int key, long valueIfKeyNotFound) {
+        int i = binarySearch(mKeys, 0, mSize, key);
+
+        if (i < 0) {
+            return valueIfKeyNotFound;
+        } else {
+            return mValues[i];
+        }
+    }
+
+    /**
+     * Removes the mapping from the specified key, if there was any.
+     */
+    public void delete(int key) {
+        int i = binarySearch(mKeys, 0, mSize, key);
+
+        if (i >= 0) {
+            removeAt(i);
+        }
+    }
+
+    /**
+     * Removes the mapping at the given index.
+     */
+    public void removeAt(int index) {
+        System.arraycopy(mKeys, index + 1, mKeys, index, mSize - (index + 1));
+        System.arraycopy(mValues, index + 1, mValues, index, mSize - (index + 1));
+        mSize--;
+    }
+
+    /**
+     * Adds a mapping from the specified key to the specified value,
+     * replacing the previous mapping from the specified key if there
+     * was one.
+     */
+    public void put(int key, long value) {
+        int i = binarySearch(mKeys, 0, mSize, key);
+
+        if (i >= 0) {
+            mValues[i] = value;
+        } else {
+            i = ~i;
+
+            if (mSize >= mKeys.length) {
+                growKeyAndValueArrays(mSize + 1);
+            }
+
+            if (mSize - i != 0) {
+                System.arraycopy(mKeys, i, mKeys, i + 1, mSize - i);
+                System.arraycopy(mValues, i, mValues, i + 1, mSize - i);
+            }
+
+            mKeys[i] = key;
+            mValues[i] = value;
+            mSize++;
+        }
+    }
+
+    /**
+     * Returns the number of key-value mappings that this SparseIntArray
+     * currently stores.
+     */
+    public int size() {
+        return mSize;
+    }
+
+    /**
+     * Given an index in the range <code>0...size()-1</code>, returns
+     * the key from the <code>index</code>th key-value mapping that this
+     * SparseLongArray stores.
+     */
+    public int keyAt(int index) {
+        return mKeys[index];
+    }
+
+    /**
+     * Given an index in the range <code>0...size()-1</code>, returns
+     * the value from the <code>index</code>th key-value mapping that this
+     * SparseLongArray stores.
+     */
+    public long valueAt(int index) {
+        return mValues[index];
+    }
+
+    /**
+     * Returns the index for which {@link #keyAt} would return the
+     * specified key, or a negative number if the specified
+     * key is not mapped.
+     */
+    public int indexOfKey(int key) {
+        return binarySearch(mKeys, 0, mSize, key);
+    }
+
+    /**
+     * Returns an index for which {@link #valueAt} would return the
+     * specified key, or a negative number if no keys map to the
+     * specified value.
+     * Beware that this is a linear search, unlike lookups by key,
+     * and that multiple keys can map to the same value and this will
+     * find only one of them.
+     */
+    public int indexOfValue(long value) {
+        for (int i = 0; i < mSize; i++)
+            if (mValues[i] == value)
+                return i;
+
+        return -1;
+    }
+
+    /**
+     * Removes all key-value mappings from this SparseIntArray.
+     */
+    public void clear() {
+        mSize = 0;
+    }
+
+    /**
+     * Puts a key/value pair into the array, optimizing for the case where
+     * the key is greater than all existing keys in the array.
+     */
+    public void append(int key, long value) {
+        if (mSize != 0 && key <= mKeys[mSize - 1]) {
+            put(key, value);
+            return;
+        }
+
+        int pos = mSize;
+        if (pos >= mKeys.length) {
+            growKeyAndValueArrays(pos + 1);
+        }
+
+        mKeys[pos] = key;
+        mValues[pos] = value;
+        mSize = pos + 1;
+    }
+
+    private void growKeyAndValueArrays(int minNeededSize) {
+        int n = ArrayUtils.idealLongArraySize(minNeededSize);
+
+        int[] nkeys = new int[n];
+        long[] nvalues = new long[n];
+
+        System.arraycopy(mKeys, 0, nkeys, 0, mKeys.length);
+        System.arraycopy(mValues, 0, nvalues, 0, mValues.length);
+
+        mKeys = nkeys;
+        mValues = nvalues;
+    }
+
+    private static int binarySearch(int[] a, int start, int len, long key) {
+        int high = start + len, low = start - 1, guess;
+
+        while (high - low > 1) {
+            guess = (high + low) / 2;
+
+            if (a[guess] < key)
+                low = guess;
+            else
+                high = guess;
+        }
+
+        if (high == start + len)
+            return ~(start + len);
+        else if (a[high] == key)
+            return high;
+        else
+            return ~high;
+    }
+}