1 /*
2  * Copyright 2017 Google Inc.
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  *     https://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 
17 package trebuchet.collections
18 
19 @Suppress("UNCHECKED_CAST", "unused")
20 class SparseArray<E> constructor(initialCapacity: Int = 10) {
21     private var mGarbage = false
22 
23     private var mKeys: IntArray
24     private var mValues: Array<Any?>
25     private var mSize: Int = 0
26 
27     init {
28         if (initialCapacity == 0) {
29             mKeys = EMPTY_INTS
30             mValues = EMPTY_OBJECTS
31         } else {
32             val idealSize = idealIntArraySize(initialCapacity)
33             mKeys = IntArray(idealSize)
34             mValues = arrayOfNulls<Any>(idealSize)
35         }
36     }
37 
38     /**
39      * Gets the Object mapped from the specified key, or `null`
40      * if no such mapping has been made.
41      */
getnull42     operator fun get(key: Int): E? {
43         return get(key, null)
44     }
45 
46     /**
47      * Gets the Object mapped from the specified key, or the specified Object
48      * if no such mapping has been made.
49      */
getnull50     operator fun get(key: Int, valueIfKeyNotFound: E?): E? {
51         val i = binarySearch(mKeys, mSize, key)
52 
53         if (i < 0 || mValues[i] === DELETED) {
54             return valueIfKeyNotFound
55         } else {
56             return mValues[i] as E
57         }
58     }
59 
60     /**
61      * Removes the mapping from the specified key, if there was any.
62      */
deletenull63     fun delete(key: Int) {
64         val i = binarySearch(mKeys, mSize, key)
65 
66         if (i >= 0) {
67             if (mValues[i] !== DELETED) {
68                 mValues[i] = DELETED
69                 mGarbage = true
70             }
71         }
72     }
73 
74     /**
75      * Alias for [.delete].
76      */
removenull77     fun remove(key: Int) {
78         delete(key)
79     }
80 
81     /**
82      * Removes the mapping at the specified index.
83      */
removeAtnull84     fun removeAt(index: Int) {
85         if (mValues[index] !== DELETED) {
86             mValues[index] = DELETED
87             mGarbage = true
88         }
89     }
90 
91     /**
92      * Remove a range of mappings as a batch.
93 
94      * @param index Index to begin at
95      * *
96      * @param size Number of mappings to remove
97      */
removeAtRangenull98     fun removeAtRange(index: Int, size: Int) {
99         val end = minOf(mSize, index + size)
100         for (i in index..end - 1) {
101             removeAt(i)
102         }
103     }
104 
gcnull105     private fun gc() {
106         val n = mSize
107         var o = 0
108         val keys = mKeys
109         val values = mValues
110 
111         for (i in 0..n - 1) {
112             val `val` = values[i]
113 
114             if (`val` !== DELETED) {
115                 if (i != o) {
116                     keys[o] = keys[i]
117                     values[o] = `val`
118                     values[i] = null
119                 }
120 
121                 o++
122             }
123         }
124 
125         mGarbage = false
126         mSize = o
127     }
128 
129     /**
130      * Adds a mapping from the specified key to the specified value,
131      * replacing the previous mapping from the specified key if there
132      * was one.
133      */
putnull134     fun put(key: Int, value: E) {
135         var i = binarySearch(mKeys, mSize, key)
136 
137         if (i >= 0) {
138             mValues[i] = value
139         } else {
140             i = i.inv()
141 
142             if (i < mSize && mValues[i] === DELETED) {
143                 mKeys[i] = key
144                 mValues[i] = value
145                 return
146             }
147 
148             if (mGarbage && mSize >= mKeys.size) {
149                 gc()
150 
151                 // Search again because indices may have changed.
152                 i = binarySearch(mKeys, mSize, key).inv()
153             }
154 
155             if (mSize >= mKeys.size) {
156                 val n = idealIntArraySize(mSize + 1)
157 
158                 val nkeys = IntArray(n)
159                 val nvalues = arrayOfNulls<Any>(n)
160 
161                 System.arraycopy(mKeys, 0, nkeys, 0, mKeys.size)
162                 System.arraycopy(mValues, 0, nvalues, 0, mValues.size)
163 
164                 mKeys = nkeys
165                 mValues = nvalues
166             }
167 
168             if (mSize - i != 0) {
169                 System.arraycopy(mKeys, i, mKeys, i + 1, mSize - i)
170                 System.arraycopy(mValues, i, mValues, i + 1, mSize - i)
171             }
172 
173             mKeys[i] = key
174             mValues[i] = value
175             mSize++
176         }
177     }
178 
179     /**
180      * Returns the number of key-value mappings that this SparseArray
181      * currently stores.
182      */
sizenull183     fun size(): Int {
184         if (mGarbage) {
185             gc()
186         }
187 
188         return mSize
189     }
190 
191     /**
192      * Given an index in the range `0...size()-1`, returns
193      * the key from the `index`th key-value mapping that this
194      * SparseArray stores.
195      */
keyAtnull196     fun keyAt(index: Int): Int {
197         if (mGarbage) {
198             gc()
199         }
200 
201         return mKeys[index]
202     }
203 
204     /**
205      * Given an index in the range `0...size()-1`, returns
206      * the value from the `index`th key-value mapping that this
207      * SparseArray stores.
208      */
valueAtnull209     fun valueAt(index: Int): E {
210         if (mGarbage) {
211             gc()
212         }
213 
214         return mValues[index] as E
215     }
216 
217     /**
218      * Given an index in the range `0...size()-1`, sets a new
219      * value for the `index`th key-value mapping that this
220      * SparseArray stores.
221      */
setValueAtnull222     fun setValueAt(index: Int, value: E) {
223         if (mGarbage) {
224             gc()
225         }
226 
227         mValues[index] = value
228     }
229 
230     /**
231      * Returns the index for which [.keyAt] would return the
232      * specified key, or a negative number if the specified
233      * key is not mapped.
234      */
indexOfKeynull235     fun indexOfKey(key: Int): Int {
236         if (mGarbage) {
237             gc()
238         }
239 
240         return binarySearch(mKeys, mSize, key)
241     }
242 
243     /**
244      * Returns an index for which [.valueAt] would return the
245      * specified key, or a negative number if no keys map to the
246      * specified value.
247      *
248      * Beware that this is a linear search, unlike lookups by key,
249      * and that multiple keys can map to the same value and this will
250      * find only one of them.
251      *
252      * Note also that unlike most collections' `indexOf` methods,
253      * this method compares values using `==` rather than `equals`.
254      */
indexOfValuenull255     fun indexOfValue(value: E): Int {
256         if (mGarbage) {
257             gc()
258         }
259 
260         for (i in 0..mSize - 1)
261             if (mValues[i] === value)
262                 return i
263 
264         return -1
265     }
266 
267     /**
268      * Removes all key-value mappings from this SparseArray.
269      */
clearnull270     fun clear() {
271         val n = mSize
272         val values = mValues
273 
274         for (i in 0..n - 1) {
275             values[i] = null
276         }
277 
278         mSize = 0
279         mGarbage = false
280     }
281 
282     /**
283      * Puts a key/value pair into the array, optimizing for the case where
284      * the key is greater than all existing keys in the array.
285      */
appendnull286     fun append(key: Int, value: E) {
287         if (mSize != 0 && key <= mKeys[mSize - 1]) {
288             put(key, value)
289             return
290         }
291 
292         if (mGarbage && mSize >= mKeys.size) {
293             gc()
294         }
295 
296         val pos = mSize
297         if (pos >= mKeys.size) {
298             val n = idealIntArraySize(pos + 1)
299 
300             val nkeys = IntArray(n)
301             val nvalues = arrayOfNulls<Any>(n)
302 
303             System.arraycopy(mKeys, 0, nkeys, 0, mKeys.size)
304             System.arraycopy(mValues, 0, nvalues, 0, mValues.size)
305 
306             mKeys = nkeys
307             mValues = nvalues
308         }
309 
310         mKeys[pos] = key
311         mValues[pos] = value
312         mSize = pos + 1
313     }
314 
315     /**
316      * {@inheritDoc}
317 
318      *
319      * This implementation composes a string by iterating over its mappings. If
320      * this map contains itself as a value, the string "(this Map)"
321      * will appear in its place.
322      */
toStringnull323     override fun toString(): String {
324         if (size() <= 0) {
325             return "{}"
326         }
327 
328         val buffer = StringBuilder(mSize * 28)
329         buffer.append('{')
330         for (i in 0..mSize - 1) {
331             if (i > 0) {
332                 buffer.append(", ")
333             }
334             val key = keyAt(i)
335             buffer.append(key)
336             buffer.append('=')
337             val value = valueAt(i)
338             if (value !== this) {
339                 buffer.append(value)
340             } else {
341                 buffer.append("(this Map)")
342             }
343         }
344         buffer.append('}')
345         return buffer.toString()
346     }
347 
348     companion object {
349         private val DELETED = Any()
350 
351         val EMPTY_INTS = IntArray(0)
352         val EMPTY_OBJECTS = arrayOfNulls<Any>(0)
353 
idealIntArraySizenull354         fun idealIntArraySize(need: Int): Int {
355             return idealByteArraySize(need * 4) / 4
356         }
357 
idealByteArraySizenull358         fun idealByteArraySize(need: Int): Int {
359             for (i in 4..31)
360                 if (need <= (1 shl i) - 12)
361                     return (1 shl i) - 12
362 
363             return need
364         }
365 
366         // This is Arrays.binarySearch(), but doesn't do any argument validation.
binarySearchnull367         fun binarySearch(array: IntArray, size: Int, value: Int): Int {
368             var lo = 0
369             var hi = size - 1
370 
371             while (lo <= hi) {
372                 val mid = (lo + hi).ushr(1)
373                 val midVal = array[mid]
374 
375                 if (midVal < value) {
376                     lo = mid + 1
377                 } else if (midVal > value) {
378                     hi = mid - 1
379                 } else {
380                     return mid  // value found
381                 }
382             }
383             return lo.inv()  // value not present
384         }
385     }
386 }