1 /*
2 * Copyright 2024 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
17 @file:Suppress("NOTHING_TO_INLINE", "KotlinRedundantDiagnosticSuppress")
18
19 package androidx.compose.ui.spatial
20
21 import kotlin.jvm.JvmField
22 import kotlin.math.max
23 import kotlin.math.min
24
25 /**
26 * This is a fairly straight-forward data structure. It stores an Int value and a corresponding
27 * rectangle, and allows for efficient querying based on the spatial relationships between the
28 * objects contained in it, but it does so just by storing all of the information packed into a
29 * single LongArray. Because of the simplicity and tight loops / locality of information, this ends
30 * up being faster than most other data structures in most things for the size data sets that we
31 * will be using this for. For O(10**2) items, this outperforms other data structures. Each
32 * meta/rect pair is stored contiguously as 3 Longs in an LongArray. This makes insert and update
33 * extremely cheap. Query operations require scanning the entire array, but due to cache locality
34 * and fairly efficient math, it is competitive with data structures which use mechanisms to prune
35 * the size of the data set to query less.
36 *
37 * This data structure comes with some assumptions:
38 * 1. the "identifier" values for this data structure are positive Ints. For performance reasons, we
39 * only store 26 bits of precision here, so practically speaking the item id is limited to 26
40 * bits (~67,000,000).
41 * 2. The coordinate system used for this data structure has the positive "x" axis pointing to the
42 * "right", and the positive "y" axis pointing "down". As a result, a rectangle will always have
43 * top <= bottom, and left <= right.
44 */
45 @Suppress("NAME_SHADOWING")
46 internal class RectList {
47 /**
48 * This is the primary data storage. We store items linearly, with each "item" taking up three
49 * longs (192 bits) of space. The partitioning generally looks like:
50 *
51 * Long 1 (64 bits): the "top left" long
52 * 32 bits: left
53 * 32 bits: top
54 * Long 2 (64 bits): the "bottom right" long
55 * 32 bits: right
56 * 32 bits: bottom
57 * Long 3 (64 bits): the "meta" long
58 * 26 bits: item id
59 * 26 bits: parent id
60 * 9 bits: last child offset
61 * 1 bits: updated
62 * 1 bits: focusable
63 * 1 bits: gesturable
64 */
65 @JvmField internal var items: LongArray = LongArray(LongsPerItem * InitialSize)
66
67 /**
68 * We allocate a 2nd LongArray. This is always going to be sized identical to [items], and
69 * during [defragment] we will swap the two in order to have a cheap defragment algorithm that
70 * preserves order.
71 *
72 * Additionally, this "double buffering" ends up having a side benefit where we can use this
73 * array during [updateSubhierarchy] as a local stack which will never have to grow since it
74 * cannot exceed the size of the items array itself. This allows for RectList to have as few
75 * allocations as possible, however this does double the memory footprint.
76 *
77 * @see [defragment]
78 * @see [updateSubhierarchy]
79 */
80 @JvmField internal var stack: LongArray = LongArray(LongsPerItem * InitialSize)
81
82 /**
83 * The size of the items array that is filled with actual data. This is different from
84 * `items.size` since the array is larger than the data it contains so that inserts can be
85 * cheap.
86 */
87 @JvmField internal var itemsSize: Int = 0
88
89 /** The number of items */
90 val size: Int
91 get() = itemsSize / LongsPerItem
92
93 /**
94 * Returns the 0th index of which 3 contiguous Longs can be stored in the items array. If space
95 * is available at the end of the array, it will use that. If not, this will grow the items
96 * array.This method will return an Int index that you can use, BUT, this method has side
97 * effects and may mutate the [items] and [itemsSize] fields on this class. It is important to
98 * keep this in mind if you call this method and have cached any of those values in a local
99 * variable, you may need to refresh them.
100 */
allocateItemsIndexnull101 private inline fun allocateItemsIndex(): Int {
102 val currentItems = items
103 val currentSize = itemsSize
104 itemsSize = currentSize + LongsPerItem
105 val actualSize = currentItems.size
106 if (actualSize <= currentSize + LongsPerItem) {
107 resizeStorage(actualSize, currentSize, currentItems)
108 }
109 return currentSize
110 }
111
resizeStoragenull112 private fun resizeStorage(actualSize: Int, currentSize: Int, currentItems: LongArray) {
113 val newSize = max(actualSize * 2, currentSize + LongsPerItem)
114 items = currentItems.copyOf(newSize)
115 stack = stack.copyOf(newSize)
116 }
117
118 /**
119 * Insert a value and corresponding bounding rectangle into the RectList. This method does not
120 * check to see that [value] doesn't already exist somewhere in the list.
121 *
122 * NOTE: -1 is NOT a valid value for this collection since it is used as a tombstone value.
123 *
124 * @param value The value to be stored. Intended to be a layout node id. Must be a positive
125 * integer of 28 bits or less
126 * @param l the left coordinate of the rectangle
127 * @param t the top coordinate of the rectangle
128 * @param r the right coordinate of the rectangle
129 * @param b the bottom coordinate of the rectangle
130 * @param parentId If this element is inside of a "scrollable" container which we want to update
131 * with the [updateSubhierarchy] API, then this is the id of that scroll container.
132 * @param focusable true if this element is focusable. This is a flag which we can use to limit
133 * the results of certain queries for
134 * @param gesturable true if this element is a pointer input gesture detector. This is a flag
135 * which we can use to limit the results of certain queries for
136 */
insertnull137 fun insert(
138 value: Int,
139 l: Int,
140 t: Int,
141 r: Int,
142 b: Int,
143 parentId: Int = -1,
144 focusable: Boolean = false,
145 gesturable: Boolean = false,
146 ) {
147 val value = value and Lower26Bits
148 val index = allocateItemsIndex()
149 val items = items
150
151 items[index + 0] = packXY(l, t)
152 items[index + 1] = packXY(r, b)
153 items[index + 2] =
154 packMeta(
155 value,
156 parentId,
157 lastChildOffset = 0,
158 // TODO: consider the fact that we will be updating every rect on insert, and that
159 // will probably impact insert times somewhat negatively. We could potentially
160 // try and check whether or not a node has a "global rect listener" on it before
161 // insert, or alternatively "mark" the updated array when we add a listener so
162 // that we could avoid the "fire" for every rect in the collection. This might not
163 // be a big deal though so let's wait until we can measure and find out if it is
164 // a problem
165 updated = true,
166 focusable,
167 gesturable
168 )
169
170 if (parentId < 0) return
171 val parentId = parentId and Lower26Bits
172 // After inserting, find the item with id = parentId and update it's "last child offset".
173 var i = index - LongsPerItem
174 while (i >= 0) {
175 val meta = items[i + 2]
176 if (unpackMetaValue(meta) == parentId) {
177 // TODO: right now this number will always be a multiple of 3. Since the last child
178 // offset only has 10 bits of precision, we probably want to encode this more
179 // efficiently. It doesn't have to be exact, it just can't be too small. We could
180 // obviously divide by LongsPerItem, but we may also want to do something cheaper
181 // like dividing by 2 or 4
182 val lastChildOffset = index - i
183 items[i + 2] = metaWithLastChildOffset(meta, lastChildOffset)
184 return
185 }
186 i -= LongsPerItem
187 }
188 }
189
190 /**
191 * Remove a value from this collection.
192 *
193 * @return Whether or not a value was found and removed from this list successfully.
194 * @see defragment
195 */
removenull196 fun remove(value: Int): Boolean {
197 val value = value and Lower26Bits
198 val items = items
199 val size = itemsSize
200 var i = 0
201 while (i < items.size - 2) {
202 if (i >= size) break
203 // NOTE: We are assuming that the value can only be here once.
204 val meta = items[i + 2]
205 if (unpackMetaValue(meta) == value) {
206 // To "remove" an item, we make the rectangle [max, max, max, max] so that it won't
207 // match any queries, and we mark meta as tombStone so we can detect it later
208 // in the defragment method
209 items[i + 0] = 0xffff_ffff_ffff_ffffUL.toLong()
210 items[i + 1] = 0xffff_ffff_ffff_ffffUL.toLong()
211 items[i + 2] = TombStone
212 return true
213 }
214 i += LongsPerItem
215 }
216 return false
217 }
218
219 /**
220 * Updates the rectangle associated with this value.
221 *
222 * @return true if the value was found and updated, false if this value is not currently in the
223 * collection
224 */
updatenull225 fun update(value: Int, l: Int, t: Int, r: Int, b: Int): Boolean {
226 val value = value and Lower26Bits
227 val items = items
228 val size = itemsSize
229 var i = 0
230 while (i < items.size - 2) {
231 if (i >= size) break
232 val meta = items[i + 2]
233 // NOTE: We are assuming that the value can only be here once.
234 if (unpackMetaValue(meta) == value) {
235 items[i + 0] = packXY(l, t)
236 items[i + 1] = packXY(r, b)
237 items[i + 2] = metaMarkUpdated(meta)
238 return true
239 }
240 i += LongsPerItem
241 }
242 return false
243 }
244
245 /**
246 * Updates the focusable and/or gesturable flags associated with this value (item id).
247 *
248 * @return true if the value was found and updated, false if this value is not currently in the
249 * collection
250 */
updateFlagsFornull251 fun updateFlagsFor(value: Int, focusable: Boolean, gesturable: Boolean): Boolean {
252 val value = value and Lower26Bits
253 val items = items
254 val size = itemsSize
255 var i = 0
256 while (i < items.size - 2) {
257 if (i >= size) break
258 val meta = items[i + 2]
259 // NOTE: We are assuming that the value can only be here once.
260 if (unpackMetaValue(meta) == value) {
261 items[i + 2] = metaMarkFlags(meta, focusable, gesturable)
262 return true
263 }
264 i += LongsPerItem
265 }
266 return false
267 }
268
269 /**
270 * Moves the rectangle associated with this value to the specified rectangle, and updates every
271 * item that is "below" the specified rectangle by the associated offset. move() is generally
272 * more efficient than calling update() for all of the rectangles included in the subhierarchy
273 * of the item.
274 */
movenull275 fun move(value: Int, l: Int, t: Int, r: Int, b: Int): Boolean {
276 val value = value and Lower26Bits
277 val items = items
278 val size = itemsSize
279 var i = 0
280 while (i < items.size - 2) {
281 if (i >= size) break
282 val meta = items[i + 2]
283 // NOTE: We are assuming that the value can only be here once.
284 if (unpackMetaValue(meta) == value) {
285 val prevLT = items[i + 0]
286 items[i + 0] = packXY(l, t)
287 items[i + 1] = packXY(r, b)
288 items[i + 2] = metaMarkUpdated(meta)
289 val deltaX = l - unpackX(prevLT)
290 val deltaY = t - unpackY(prevLT)
291 if ((deltaX != 0) or (deltaY != 0)) {
292 updateSubhierarchy(metaWithParentId(meta, i + LongsPerItem), deltaX, deltaY)
293 }
294 return true
295 }
296 i += LongsPerItem
297 }
298 return false
299 }
300
updateSubhierarchynull301 fun updateSubhierarchy(id: Int, deltaX: Int, deltaY: Int) {
302 updateSubhierarchy(
303 //
304 stackMeta =
305 packMeta(
306 itemId = id,
307 parentId = 0,
308 lastChildOffset = itemsSize,
309 updated = false,
310 focusable = false,
311 gesturable = false,
312 ),
313 deltaX = deltaX,
314 deltaY = deltaY
315 )
316 }
317
318 /**
319 * Updates a subhierarchy of items by the specified delta. For efficiency, the [stackMeta]
320 * provided is a Long encoded with the same scheme of the "meta" long of each item, where the
321 * encoding has the following semantic specific to this method:
322 *
323 * Long (64 bits): the "stack meta" encoding
324 * 26 bits: the "parent id" that we are matching on (normally item id)
325 * 26 bits: the minimum index that a child can have (normally parent id)
326 * 10 bits: max offset from start index a child can have (normally last child offset)
327 * 1 bits: unused (normally focusable)
328 * 1 bits: unused (normally gesturable)
329 *
330 * We use this essentially as a way to encode three integers into a long, which includes all of
331 * the data needed to efficiently iterate through the below algorithm. It is effectively an id
332 * and a range. The range isn't strictly needed, but it helps turn this O(n^2) algorithm into
333 * something that is ~O(n) in the average case (still O(n^2) worst case though). By using the
334 * same encoding as "meta" longs, we only need to update the start index when we
335 */
updateSubhierarchynull336 private fun updateSubhierarchy(stackMeta: Long, deltaX: Int, deltaY: Int) {
337 val items = items
338 val stack = stack
339 val size = size
340 stack[0] = stackMeta
341 var stackSize = 1
342 while (stackSize > 0) {
343 val idAndStartAndOffset = stack[--stackSize]
344 val parentId = unpackMetaValue(idAndStartAndOffset) // parent id is in the id slot
345 var i = unpackMetaParentId(idAndStartAndOffset) // start index is in the parent id slot
346 val offset = unpackMetaLastChildOffset(idAndStartAndOffset)
347 val endIndex = if (offset == Lower9Bits) size else offset + i
348 if (i < 0) break
349 while (i < items.size - 2) {
350 if (i >= endIndex) break
351 val meta = items[i + 2]
352 if (unpackMetaParentId(meta) == parentId) {
353 val topLeft = items[i + 0]
354 val bottomRight = items[i + 1]
355 items[i + 0] = packXY(unpackX(topLeft) + deltaX, unpackY(topLeft) + deltaY)
356 items[i + 1] =
357 packXY(unpackX(bottomRight) + deltaX, unpackY(bottomRight) + deltaY)
358 items[i + 2] = metaMarkUpdated(meta)
359 if (unpackMetaLastChildOffset(meta) > 0) {
360 // we need to store itemId, lastChildOffset, and a "start index".
361 // For convenience, we just use `meta` which already encodes two of those
362 // values, and we add `i` into the slot for "parentId"
363 stack[stackSize++] = metaWithParentId(meta, i + LongsPerItem)
364 }
365 }
366 i += LongsPerItem
367 }
368 }
369 }
370
markUpdatednull371 fun markUpdated(value: Int) {
372 val value = value and Lower26Bits
373 val items = items
374 val size = itemsSize
375 var i = 0
376 while (i < items.size - 2) {
377 if (i >= size) break
378 val meta = items[i + 2]
379 if (unpackMetaValue(meta) == value) {
380 items[i + 2] = metaMarkUpdated(meta)
381 return
382 }
383 i += LongsPerItem
384 }
385 }
386
withRectnull387 fun withRect(value: Int, block: (Int, Int, Int, Int) -> Unit): Boolean {
388 val value = value and Lower26Bits
389 val items = items
390 val size = itemsSize
391 var i = 0
392 while (i < items.size - 2) {
393 if (i >= size) break
394 val meta = items[i + 2]
395 // NOTE: We are assuming that the value can only be here once.
396 if (unpackMetaValue(meta) == value) {
397 val topLeft = items[i + 0]
398 val bottomRight = items[i + 1]
399 block(
400 unpackX(topLeft),
401 unpackY(topLeft),
402 unpackX(bottomRight),
403 unpackY(bottomRight),
404 )
405 return true
406 }
407 i += LongsPerItem
408 }
409 return false
410 }
411
containsnull412 operator fun contains(value: Int): Boolean {
413 val value = value and Lower26Bits
414 val items = items
415 val size = itemsSize
416 var i = 0
417 while (i < items.size - 2) {
418 if (i >= size) break
419 val meta = items[i + 2]
420 if (unpackMetaValue(meta) == value) {
421 return true
422 }
423 i += LongsPerItem
424 }
425 return false
426 }
427
428 /**
429 * Returns the first index for the item that matches the metadata value of [value], returns -1
430 * if the item wasn't found.
431 *
432 * Note that returned index corresponds to the Long that contains the topLeft data of the item.
433 */
indexOfnull434 fun indexOf(value: Int): Int {
435 val value = value and Lower26Bits
436 val items = items
437 val size = itemsSize
438 var i = 0
439 while (i < items.size - 2) {
440 if (i >= size) break
441 val meta = items[i + 2]
442 if (unpackMetaValue(meta) == value) {
443 return i
444 }
445 i += LongsPerItem
446 }
447 return -1
448 }
449
metaFornull450 fun metaFor(value: Int): Long {
451 val value = value and Lower26Bits
452 val items = items
453 val size = itemsSize
454 var i = 0
455 while (i < items.size - 2) {
456 if (i >= size) break
457 val meta = items[i + 2]
458 // NOTE: We are assuming that the value can only be here once.
459 if (unpackMetaValue(meta) == value) {
460 return meta
461 }
462 i += LongsPerItem
463 }
464 return TombStone
465 }
466
467 /**
468 * For a provided rectangle, executes [block] for each value in the collection whose associated
469 * rectangle intersects the provided one. The argument passed into [block] will be the value.
470 */
forEachIntersectionnull471 inline fun forEachIntersection(
472 l: Int,
473 t: Int,
474 r: Int,
475 b: Int,
476 block: (Int) -> Unit,
477 ) {
478 val destTopLeft = packXY(l, t)
479 val destTopRight = packXY(r, b)
480 val items = items
481 val size = itemsSize
482 var i = 0
483 while (i < items.size - 2) {
484 if (i >= size) break
485 val topLeft = items[i + 0]
486 val bottomRight = items[i + 1]
487 if (rectIntersectsRect(topLeft, bottomRight, destTopLeft, destTopRight)) {
488 // TODO: it might make sense to include the rectangle in the block since calling
489 // code may want to filter this list using that geometry, and it would be
490 // beneficial to not have to look up the layout node in order to do so.
491 block(unpackMetaValue(items[i + 2]))
492 }
493 i += LongsPerItem
494 }
495 }
496
497 /**
498 * For each value in the collection, checks first if it is gesturable. If it is and it
499 * intersects with the provided rectangle, the function executes [block]. The argument passed
500 * into [block] will be the value (item id).
501 */
forEachGesturableIntersectionnull502 inline fun forEachGesturableIntersection(
503 l: Int,
504 t: Int,
505 r: Int,
506 b: Int,
507 block: (Int) -> Unit,
508 ) {
509 val destTopLeft = packXY(l, t)
510 val destTopRight = packXY(r, b)
511 val items = items
512 val size = itemsSize
513
514 var i = 0
515 while (i < items.size - 2) {
516 if (i >= size) break
517 if (unpackMetaGesturable(items[i + 2]) != 0) { // Checks gesturable is true
518 val topLeft = items[i + 0]
519 val bottomRight = items[i + 1]
520
521 if (rectIntersectsRect(topLeft, bottomRight, destTopLeft, destTopRight)) {
522 // TODO: it might make sense to include the rectangle in the block since calling
523 // code may want to filter this list using that geometry, and it would be
524 // beneficial to not have to look up the layout node in order to do so.
525 block(unpackMetaValue(items[i + 2]))
526 }
527 }
528 i += LongsPerItem
529 }
530 }
531
forEachRectnull532 inline fun forEachRect(
533 block: (Int, Int, Int, Int, Int) -> Unit,
534 ) {
535 val items = items
536 val size = itemsSize
537 var i = 0
538 while (i < items.size - 2) {
539 if (i >= size) break
540 val topLeft = items[i + 0]
541 val bottomRight = items[i + 1]
542 val meta = items[i + 2]
543 block(
544 unpackMetaValue(meta),
545 unpackX(topLeft),
546 unpackY(topLeft),
547 unpackX(bottomRight),
548 unpackY(bottomRight),
549 )
550 i += LongsPerItem
551 }
552 }
553
554 // TODO: add ability to filter to just gesture detectors (the main use case for this function)
555 /**
556 * For a provided point, executes [block] for each value in the collection whose associated
557 * rectangle contains the provided point. The argument passed into [block] will be the value.
558 */
forEachIntersectionnull559 inline fun forEachIntersection(
560 x: Int,
561 y: Int,
562 block: (Int) -> Unit,
563 ) {
564 val destXY = packXY(x, y)
565 val items = items
566 val size = itemsSize
567 var i = 0
568 while (i < items.size - 2) {
569 if (i >= size) break
570 val topLeft = items[i + 0]
571 val bottomRight = items[i + 1]
572 if (rectIntersectsRect(topLeft, bottomRight, destXY, destXY)) {
573 val meta = items[i + 2]
574 block(unpackMetaValue(meta))
575 }
576 i += LongsPerItem
577 }
578 }
579
580 /**
581 * For the rectangle at the given [index], calls [block] for each other rectangles that
582 * intersects with it. The parameters in [block] are the intersecting rect and its 'value'.
583 */
forEachIntersectingRectWithValueAtnull584 inline fun forEachIntersectingRectWithValueAt(
585 index: Int,
586 block: (Int, Int, Int, Int, Int) -> Unit
587 ) {
588 val items = items
589 val size = itemsSize
590
591 val destTopLeft = items[index]
592 val destBottomRight = items[index + 1]
593
594 var i = 0
595 while (i < items.size - 2) {
596 if (i >= size) break
597 if (i == index) {
598 i += LongsPerItem
599 continue
600 }
601 val topLeft = items[i + 0]
602 val bottomRight = items[i + 1]
603 if (rectIntersectsRect(topLeft, bottomRight, destTopLeft, destBottomRight)) {
604 block(
605 unpackX(topLeft),
606 unpackY(topLeft),
607 unpackX(bottomRight),
608 unpackY(bottomRight),
609 unpackMetaValue(items[i + 2])
610 )
611 }
612 i += LongsPerItem
613 }
614 }
615
neighborsScoredByDistancenull616 internal fun neighborsScoredByDistance(
617 searchAxis: Int,
618 l: Int,
619 t: Int,
620 r: Int,
621 b: Int,
622 ): IntArray {
623 val items = items
624 val size = itemsSize / LongsPerItem
625 var i = 0
626 // build up an array of size N with each element being the score for the item at that index
627 val results = IntArray(size)
628
629 while (i < results.size) {
630 val itemsIndex = i * LongsPerItem
631 if (itemsIndex < 0 || itemsIndex >= items.size - 1) break
632 val topLeft = items[itemsIndex + 0]
633 val bottomRight = items[itemsIndex + 1]
634 val score =
635 distanceScore(
636 searchAxis,
637 l,
638 t,
639 r,
640 b,
641 unpackX(topLeft),
642 unpackY(topLeft),
643 unpackX(bottomRight),
644 unpackY(bottomRight),
645 )
646 results[i] = score
647 i++
648 }
649 return results
650 }
651
652 // TODO: add ability to filter to just focusable (the main use case for this function)
653 // TODO: add an overload which just takes in searchAxis, k, and item id
findKNearestNeighborsnull654 inline fun findKNearestNeighbors(
655 searchAxis: Int,
656 k: Int,
657 l: Int,
658 t: Int,
659 r: Int,
660 b: Int,
661 block: (score: Int, id: Int, l: Int, t: Int, r: Int, b: Int) -> Unit,
662 ) {
663 // this list is 1:1 with items and holds the score for each item
664 val list =
665 neighborsScoredByDistance(
666 searchAxis,
667 l,
668 t,
669 r,
670 b,
671 )
672 val items = items
673
674 var sent = 0
675 var min = 1
676 var nextMin = Int.MAX_VALUE
677 var loops = 0
678 var i = 0
679 while (loops <= k) {
680 while (i < list.size) {
681 val score = list[i]
682 // update nextmin if score is smaller than nextMin but larger than min
683 if (score > min) {
684 nextMin = min(nextMin, score)
685 }
686 if (score == min) {
687 val itemIndex = i * LongsPerItem
688 val topLeft = items[itemIndex + 0]
689 val bottomRight = items[itemIndex + 1]
690 val meta = items[itemIndex + 2]
691 block(
692 score,
693 unpackMetaValue(meta),
694 unpackX(topLeft),
695 unpackY(topLeft),
696 unpackX(bottomRight),
697 unpackY(bottomRight),
698 )
699 sent++
700 if (sent == k) return
701 }
702 i++
703 }
704 min = nextMin
705 nextMin = Int.MAX_VALUE
706 loops++
707 i = 0
708 }
709 }
710
findNearestNeighbornull711 inline fun findNearestNeighbor(searchAxis: Int, l: Int, t: Int, r: Int, b: Int): Int {
712 val items = items
713 val size = itemsSize
714 var minScore = Int.MAX_VALUE
715 var minIndex = -1
716 var i = 0
717 while (i < items.size - 2) {
718 if (i >= size) break
719 val topLeft = items[i + 0]
720 val bottomRight = items[i + 1]
721 val score =
722 distanceScore(
723 searchAxis,
724 l,
725 t,
726 r,
727 b,
728 unpackX(topLeft),
729 unpackY(topLeft),
730 unpackX(bottomRight),
731 unpackY(bottomRight),
732 )
733 val isNewMin = (score > 0) and (score < minScore)
734 minScore = if (isNewMin) score else minScore
735 minIndex = if (isNewMin) i + 1 else minIndex
736 i += LongsPerItem
737 }
738 return if (minIndex < 0 || minIndex >= items.size) {
739 -1
740 } else {
741 unpackMetaValue(items[minIndex])
742 }
743 }
744
745 /** */
defragmentnull746 fun defragment() {
747 val from = items
748 val size = itemsSize
749 val to = stack
750 var i = 0
751 var j = 0
752 while (i < from.size - 2) {
753 if (j >= to.size - 2) break
754 if (i >= size) break
755 if (from[i + 2] != TombStone) {
756 to[j + 0] = from[i + 0]
757 to[j + 1] = from[i + 1]
758 to[j + 2] = from[i + 2]
759 j += LongsPerItem
760 }
761 i += LongsPerItem
762 }
763 itemsSize = j
764 // NOTE: this could be a reasonable time to shrink items/stack to a smaller array if for
765 // some reason they have gotten very large. I'm choosing NOT to do this because I think
766 // if the arrays have gotten to a large size it is very likely that they will get to that
767 // size again, and avoiding the thrash here is probably desirable
768 items = to
769 stack = from
770 }
771
clearUpdatednull772 fun clearUpdated() {
773 val items = items
774 val size = itemsSize
775 var i = 0
776 while (i < items.size - 2) {
777 if (i >= size) break
778 items[i + 2] = metaUnMarkUpdated(items[i + 2])
779 i += LongsPerItem
780 }
781 }
782
forEachUpdatedRectnull783 inline fun forEachUpdatedRect(block: (Int, Long, Long) -> Unit) {
784 val items = items
785 val size = itemsSize
786 var i = 0
787 while (i < items.size - 2) {
788 if (i >= size) break
789 val meta = items[i + 2]
790 if (unpackMetaUpdated(meta) != 0) {
791 val topLeft = items[i + 0]
792 val bottomRight = items[i + 1]
793 block(
794 unpackMetaValue(meta),
795 topLeft,
796 bottomRight,
797 )
798 }
799 i += LongsPerItem
800 }
801 }
802
<lambda>null803 fun debugString(): String = buildString {
804 val items = items
805 val size = itemsSize
806 var i = 0
807 while (i < items.size - 2) {
808 if (i >= size) break
809 val topLeft = items[i + 0]
810 val bottomRight = items[i + 1]
811 val meta = items[i + 2]
812 val id = unpackMetaValue(meta)
813 val parentId = unpackMetaParentId(meta)
814 val l = unpackX(topLeft)
815 val t = unpackY(topLeft)
816 val r = unpackX(bottomRight)
817 val b = unpackY(bottomRight)
818 appendLine("id=$id, rect=[$l,$t,$r,$b], parent=$parentId")
819 i += LongsPerItem
820 }
821 }
822 }
823
824 internal const val LongsPerItem = 3
825 internal const val InitialSize = 64
826 internal const val Lower26Bits = 0b0000_0011_1111_1111_1111_1111_1111_1111
827 internal const val Lower9Bits = 0b0000_0000_0000_0000_0000_0001_1111_1111
828 internal const val EverythingButParentId = 0xfff0_0000_03ff_ffffUL
829 internal const val EverythingButLastChildOffset = 0xe00fffffffffffffUL
830 private const val PackedIntsLowestBit = 0x000_0001_0000_0001L
831 private const val PackedIntsHighestBit = -0x7FFF_FFFF_8000_0000L // 0x8000_0000_8000_0000UL
832
833 /**
834 * This is the "meta" value that we assign to every removed value.
835 *
836 * @see RectList.remove
837 * @see packMeta
838 */
839 internal const val TombStone = 0x1fff_ffff_ffff_ffffL // packMeta(-1, -1, -1, false, false, false)
840
841 internal const val AxisNorth: Int = 0
842 internal const val AxisSouth: Int = 1
843 internal const val AxisWest: Int = 2
844 internal const val AxisEast: Int = 3
845
packXYnull846 internal inline fun packXY(x: Int, y: Int) = (x.toLong() shl 32) or (y.toLong() and 0xffff_ffff)
847
848 internal inline fun packMeta(
849 itemId: Int,
850 parentId: Int,
851 lastChildOffset: Int,
852 updated: Boolean,
853 focusable: Boolean,
854 gesturable: Boolean,
855 ): Long =
856 // 26 bits: item id
857 // 26 bits: parent id
858 // 9 bits: last child offset
859 // 1 bits: updated - means the bounds have been updated
860 // 1 bits: focusable
861 // 1 bits: gesturable
862 (gesturable.toLong() shl 63) or
863 (focusable.toLong() shl 62) or
864 (updated.toLong() shl 61) or
865 ((lastChildOffset and Lower9Bits).toLong() shl 52) or
866 ((parentId and Lower26Bits).toLong() shl 26) or
867 ((itemId and Lower26Bits).toLong() shl 0)
868
869 internal inline fun unpackMetaValue(meta: Long): Int = meta.toInt() and Lower26Bits
870
871 internal inline fun unpackMetaParentId(meta: Long): Int = (meta shr 26).toInt() and Lower26Bits
872
873 internal inline fun unpackMetaLastChildOffset(meta: Long): Int =
874 (meta shr 52).toInt() and Lower9Bits
875
876 internal inline fun metaWithParentId(meta: Long, parentId: Int): Long =
877 (meta and EverythingButParentId.toLong()) or ((parentId and Lower26Bits).toLong() shl 26)
878
879 internal inline fun metaWithUpdated(meta: Long, updated: Boolean): Long =
880 (meta and (0b1L shl 61).inv()) or (updated.toLong() shl 61)
881
882 internal inline fun metaMarkUpdated(meta: Long): Long = meta or (1L shl 61)
883
884 internal inline fun metaUnMarkUpdated(meta: Long): Long = meta and (1L shl 61).inv()
885
886 internal inline fun metaMarkFlags(meta: Long, focusable: Boolean, gesturable: Boolean): Long {
887 return (meta and (1L shl 62).inv() and (1L shl 63).inv()) or
888 ((1L shl 62) * focusable.toInt()) or
889 ((1L shl 63) * gesturable.toInt())
890 }
891
metaWithLastChildOffsetnull892 internal inline fun metaWithLastChildOffset(meta: Long, lastChildOffset: Int): Long =
893 (meta and EverythingButLastChildOffset.toLong()) or
894 ((lastChildOffset and Lower9Bits).toLong() shl 52)
895
896 internal inline fun unpackMetaFocusable(meta: Long): Int = (meta shr 62).toInt() and 0b1
897
898 internal inline fun unpackMetaGesturable(meta: Long): Int = (meta shr 63).toInt() and 0b1
899
900 internal inline fun unpackMetaUpdated(meta: Long): Int = (meta shr 61).toInt() and 0b1
901
902 internal inline fun unpackX(xy: Long): Int = (xy shr 32).toInt()
903
904 internal inline fun unpackY(xy: Long): Int = (xy).toInt()
905
906 /** */
907 internal inline fun rectIntersectsRect(
908 srcLT: Long,
909 srcRB: Long,
910 destLT: Long,
911 destRB: Long
912 ): Boolean {
913 // destRB - srcLT = [r2 - l1, b2 - t1]
914 // srcRB - destLT = [r1 - l2, b1 - t2]
915
916 // Both of the above expressions represent two long subtractions which are effectively each two
917 // int subtractions. If any of the individual subtractions would have resulted in a negative
918 // value, then the rectangle has no intersection. If this is true, then there will be
919 // "underflow" from one 32bit component to the next, which we can detect by isolating the top
920 // bits of each component using 0x8000_0000_8000_0000UL.toLong()
921
922 // Since an intersection happens when both right/bottom corners are **larger** than the left/top
923 // of the other (only top/left edges are inclusive in a Rect), we subtract a 1 to underflow in
924 // the case they are the same.
925 val a = (destRB - srcLT - PackedIntsLowestBit) or (srcRB - destLT - PackedIntsLowestBit)
926 return a and PackedIntsHighestBit == 0L
927 }
928
929 /**
930 * Turns a boolean into a long of 1L/0L for true/false. It is written precisely this way as this
931 * results in a single ARM instruction where as other approaches are more expensive. For example,
932 * `if (this) 1L else 0L` is several instructions instead of just one. DO NOT change this without
933 * looking at the corresponding arm code and verifying that it is better.
934 */
toLongnull935 internal inline fun Boolean.toLong(): Long = (if (this) 1 else 0).toLong()
936
937 /**
938 * This function will return a "score" of a rectangle relative to a query. A negative score means
939 * that the rectangle should be ignored, and a lower (but non-negative) score means that the
940 * rectangle is close and overlapping in the direction of the axis in question.
941 *
942 * @param axis the direction/axis along which we are scoring
943 * @param queryL the left of the rect we are finding the nearest neighbors of
944 * @param queryT the top of the rect we are finding the nearest neighbors of
945 * @param queryR the right of the rect we are finding the nearest neighbors of
946 * @param queryB the bottom of the rect we are finding the nearest neighbors of
947 * @param l the left of the rect which is the "neighbor" we are scoring
948 * @param t the top of the rect which is the "neighbor" we are scoring
949 * @param r the right of the rect which is the "neighbor" we are scoring
950 * @param b the bottom of the rect which is the "neighbor" we are scoring
951 * @see AxisNorth
952 * @see AxisWest
953 * @see AxisEast
954 * @see AxisSouth
955 */
956 // TODO: consider just passing in TopLeft/BottomRight longs in order to reduce the number of
957 // parameters here.
958 internal fun distanceScore(
959 axis: Int,
960 queryL: Int,
961 queryT: Int,
962 queryR: Int,
963 queryB: Int,
964 l: Int,
965 t: Int,
966 r: Int,
967 b: Int,
968 ): Int {
969 return when (axis) {
970 AxisNorth ->
971 distanceScoreAlongAxis(
972 distanceMin = queryT,
973 distanceMax = b,
974 queryCrossAxisMax = queryR,
975 queryCrossAxisMin = queryL,
976 crossAxisMax = r,
977 crossAxisMin = l,
978 )
979 AxisEast ->
980 distanceScoreAlongAxis(
981 distanceMin = l,
982 distanceMax = queryR,
983 queryCrossAxisMax = queryB,
984 queryCrossAxisMin = queryT,
985 crossAxisMax = b,
986 crossAxisMin = t,
987 )
988 AxisSouth ->
989 distanceScoreAlongAxis(
990 distanceMin = t,
991 distanceMax = queryB,
992 queryCrossAxisMax = queryR,
993 queryCrossAxisMin = queryL,
994 crossAxisMax = r,
995 crossAxisMin = l,
996 )
997 AxisWest ->
998 distanceScoreAlongAxis(
999 distanceMin = queryL,
1000 distanceMax = r,
1001 queryCrossAxisMax = queryB,
1002 queryCrossAxisMin = queryT,
1003 crossAxisMax = b,
1004 crossAxisMin = t,
1005 )
1006 else -> Int.MAX_VALUE
1007 }
1008 }
1009
1010 /**
1011 * This function will return a "score" of a rectangle relative to a query. A negative score means
1012 * that the rectangle should be ignored, and a low score means that
1013 */
distanceScoreAlongAxisnull1014 internal fun distanceScoreAlongAxis(
1015 distanceMin: Int,
1016 distanceMax: Int,
1017 queryCrossAxisMax: Int,
1018 queryCrossAxisMin: Int,
1019 crossAxisMax: Int,
1020 crossAxisMin: Int,
1021 ): Int {
1022 // small positive means it is close to the right, negative means there is overlap or it is to
1023 // the left, which we will reject. We want small and positive.
1024 val distanceAlongAxis = distanceMin - distanceMax
1025 val maxOverlapPossible = queryCrossAxisMax - queryCrossAxisMin
1026 // 0 with full overlap, increasingly large negative numbers without
1027 val overlap =
1028 maxOverlapPossible + max(queryCrossAxisMin, crossAxisMin) -
1029 min(queryCrossAxisMax, crossAxisMax)
1030
1031 return (distanceAlongAxis + 1) * (overlap + 1)
1032 }
1033