1/*
2 * Copyright (C) 2011 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.android.mail.utils;
18
19/**
20 * SparseLongArrays map integers to longs.  Unlike a normal array of longs,
21 * there can be gaps in the indices.  It is intended to be more efficient
22 * than using a HashMap to map Integers to Longs.
23 *
24 * TODO: Remove this when there's an equivalent in the support library. This was changed slightly
25 * to remove the dependency on com.android.internal.util.ArrayUtils.
26 */
27public class SparseLongArray implements Cloneable {
28
29    private int[] mKeys;
30    private long[] mValues;
31    private int mSize;
32
33    /**
34     * Creates a new SparseLongArray containing no mappings.
35     */
36    public SparseLongArray() {
37        this(10);
38    }
39
40    /**
41     * Creates a new SparseLongArray containing no mappings that will not
42     * require any additional memory allocation to store the specified
43     * number of mappings.
44     */
45    public SparseLongArray(int initialCapacity) {
46        mKeys = new int[initialCapacity];
47        mValues = new long[initialCapacity];
48        mSize = 0;
49    }
50
51    @Override
52    public SparseLongArray clone() {
53        SparseLongArray clone = null;
54        try {
55            clone = (SparseLongArray) super.clone();
56            clone.mKeys = mKeys.clone();
57            clone.mValues = mValues.clone();
58        } catch (CloneNotSupportedException cnse) {
59            /* ignore */
60        }
61        return clone;
62    }
63
64    /**
65     * Gets the long mapped from the specified key, or <code>0</code>
66     * if no such mapping has been made.
67     */
68    public long get(int key) {
69        return get(key, 0);
70    }
71
72    /**
73     * Gets the long mapped from the specified key, or the specified value
74     * if no such mapping has been made.
75     */
76    public long get(int key, long valueIfKeyNotFound) {
77        int i = binarySearch(mKeys, 0, mSize, key);
78
79        if (i < 0) {
80            return valueIfKeyNotFound;
81        } else {
82            return mValues[i];
83        }
84    }
85
86    /**
87     * Removes the mapping from the specified key, if there was any.
88     */
89    public void delete(int key) {
90        int i = binarySearch(mKeys, 0, mSize, key);
91
92        if (i >= 0) {
93            removeAt(i);
94        }
95    }
96
97    /**
98     * Removes the mapping at the given index.
99     */
100    public void removeAt(int index) {
101        System.arraycopy(mKeys, index + 1, mKeys, index, mSize - (index + 1));
102        System.arraycopy(mValues, index + 1, mValues, index, mSize - (index + 1));
103        mSize--;
104    }
105
106    /**
107     * Adds a mapping from the specified key to the specified value,
108     * replacing the previous mapping from the specified key if there
109     * was one.
110     */
111    public void put(int key, long value) {
112        int i = binarySearch(mKeys, 0, mSize, key);
113
114        if (i >= 0) {
115            mValues[i] = value;
116        } else {
117            i = ~i;
118
119            if (mSize >= mKeys.length) {
120                growKeyAndValueArrays(mSize + 1);
121            }
122
123            if (mSize - i != 0) {
124                System.arraycopy(mKeys, i, mKeys, i + 1, mSize - i);
125                System.arraycopy(mValues, i, mValues, i + 1, mSize - i);
126            }
127
128            mKeys[i] = key;
129            mValues[i] = value;
130            mSize++;
131        }
132    }
133
134    /**
135     * Returns the number of key-value mappings that this SparseIntArray
136     * currently stores.
137     */
138    public int size() {
139        return mSize;
140    }
141
142    /**
143     * Given an index in the range <code>0...size()-1</code>, returns
144     * the key from the <code>index</code>th key-value mapping that this
145     * SparseLongArray stores.
146     */
147    public int keyAt(int index) {
148        return mKeys[index];
149    }
150
151    /**
152     * Given an index in the range <code>0...size()-1</code>, returns
153     * the value from the <code>index</code>th key-value mapping that this
154     * SparseLongArray stores.
155     */
156    public long valueAt(int index) {
157        return mValues[index];
158    }
159
160    /**
161     * Returns the index for which {@link #keyAt} would return the
162     * specified key, or a negative number if the specified
163     * key is not mapped.
164     */
165    public int indexOfKey(int key) {
166        return binarySearch(mKeys, 0, mSize, key);
167    }
168
169    /**
170     * Returns an index for which {@link #valueAt} would return the
171     * specified key, or a negative number if no keys map to the
172     * specified value.
173     * Beware that this is a linear search, unlike lookups by key,
174     * and that multiple keys can map to the same value and this will
175     * find only one of them.
176     */
177    public int indexOfValue(long value) {
178        for (int i = 0; i < mSize; i++)
179            if (mValues[i] == value)
180                return i;
181
182        return -1;
183    }
184
185    /**
186     * Removes all key-value mappings from this SparseIntArray.
187     */
188    public void clear() {
189        mSize = 0;
190    }
191
192    /**
193     * Puts a key/value pair into the array, optimizing for the case where
194     * the key is greater than all existing keys in the array.
195     */
196    public void append(int key, long value) {
197        if (mSize != 0 && key <= mKeys[mSize - 1]) {
198            put(key, value);
199            return;
200        }
201
202        int pos = mSize;
203        if (pos >= mKeys.length) {
204            growKeyAndValueArrays(pos + 1);
205        }
206
207        mKeys[pos] = key;
208        mValues[pos] = value;
209        mSize = pos + 1;
210    }
211
212    private void growKeyAndValueArrays(int minNeededSize) {
213        int n = minNeededSize;
214
215        int[] nkeys = new int[n];
216        long[] nvalues = new long[n];
217
218        System.arraycopy(mKeys, 0, nkeys, 0, mKeys.length);
219        System.arraycopy(mValues, 0, nvalues, 0, mValues.length);
220
221        mKeys = nkeys;
222        mValues = nvalues;
223    }
224
225    private static int binarySearch(int[] a, int start, int len, long key) {
226        int high = start + len, low = start - 1, guess;
227
228        while (high - low > 1) {
229            guess = (high + low) / 2;
230
231            if (a[guess] < key)
232                low = guess;
233            else
234                high = guess;
235        }
236
237        if (high == start + len)
238            return ~(start + len);
239        else if (a[high] == key)
240            return high;
241        else
242            return ~high;
243    }
244}
245