1 /*
2  * Copyright 2022 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 package androidx.compose.foundation.lazy.staggeredgrid
18 
19 import androidx.compose.foundation.internal.requirePrecondition
20 
21 /**
22  * Utility class to remember grid lane assignments in a sliding window relative to requested item
23  * position (usually reflected by scroll position). Remembers the maximum range of remembered items
24  * is reflected by [MaxCapacity], if index is beyond the bounds, [anchor] moves to reflect new
25  * position.
26  */
27 internal class LazyStaggeredGridLaneInfo {
28     private var anchor = 0
29     private var lanes = IntArray(16)
30     private val spannedItems = ArrayDeque<SpannedItem>()
31 
32     private class SpannedItem(val index: Int, var gaps: IntArray)
33 
34     /** Sets given lane for given item index. */
setLanenull35     fun setLane(itemIndex: Int, lane: Int) {
36         requirePrecondition(itemIndex >= 0) { "Negative lanes are not supported" }
37         ensureValidIndex(itemIndex)
38         lanes[itemIndex - anchor] = lane + 1
39     }
40 
41     /**
42      * Get lane for given item index.
43      *
44      * @return lane previously recorded for given item or [Unset] if it doesn't exist.
45      */
getLanenull46     fun getLane(itemIndex: Int): Int {
47         if (itemIndex < lowerBound() || itemIndex >= upperBound()) {
48             return Unset
49         }
50         return lanes[itemIndex - anchor] - 1
51     }
52 
53     /**
54      * Checks whether item can be in the target lane
55      *
56      * @param itemIndex item to check lane for
57      * @param targetLane lane it should belong to
58      */
assignedToLanenull59     fun assignedToLane(itemIndex: Int, targetLane: Int): Boolean {
60         val lane = getLane(itemIndex)
61         return lane == targetLane || lane == Unset || lane == FullSpan
62     }
63 
64     /** @return upper bound of currently valid item range */
65     /* @VisibleForTests */
upperBoundnull66     fun upperBound(): Int = anchor + lanes.size
67 
68     /** @return lower bound of currently valid item range */
69     /* @VisibleForTests */
70     fun lowerBound(): Int = anchor
71 
72     /** Delete remembered lane assignments. */
73     fun reset() {
74         lanes.fill(0)
75         spannedItems.clear()
76     }
77 
78     /**
79      * Find the previous item relative to [itemIndex] set to target lane
80      *
81      * @return found item index or -1 if it doesn't exist.
82      */
findPreviousItemIndexnull83     fun findPreviousItemIndex(itemIndex: Int, targetLane: Int): Int {
84         for (i in (itemIndex - 1) downTo 0) {
85             if (assignedToLane(i, targetLane)) {
86                 return i
87             }
88         }
89         return -1
90     }
91 
92     /**
93      * Find the next item relative to [itemIndex] set to target lane
94      *
95      * @return found item index or [upperBound] if it doesn't exist.
96      */
findNextItemIndexnull97     fun findNextItemIndex(itemIndex: Int, targetLane: Int): Int {
98         for (i in itemIndex + 1 until upperBound()) {
99             if (assignedToLane(i, targetLane)) {
100                 return i
101             }
102         }
103         return upperBound()
104     }
105 
ensureValidIndexnull106     fun ensureValidIndex(requestedIndex: Int) {
107         val requestedCapacity = requestedIndex - anchor
108 
109         if (requestedCapacity in 0 until MaxCapacity) {
110             // simplest path - just grow array to given capacity
111             ensureCapacity(requestedCapacity + 1)
112         } else {
113             // requested index is beyond current span bounds
114             // rebase anchor so that requested index is in the middle of span array
115             val oldAnchor = anchor
116             anchor = maxOf(requestedIndex - (lanes.size / 2), 0)
117             var delta = anchor - oldAnchor
118 
119             if (delta >= 0) {
120                 // copy previous span data if delta is smaller than span size
121                 if (delta < lanes.size) {
122                     lanes.copyInto(
123                         lanes,
124                         destinationOffset = 0,
125                         startIndex = delta,
126                         endIndex = lanes.size
127                     )
128                 }
129                 // fill the rest of the spans with default values
130                 lanes.fill(0, maxOf(0, lanes.size - delta), lanes.size)
131             } else {
132                 delta = -delta
133                 // check if we can grow spans to match delta
134                 if (lanes.size + delta < MaxCapacity) {
135                     // grow spans and leave space in the start
136                     ensureCapacity(lanes.size + delta + 1, delta)
137                 } else {
138                     // otherwise, just move data that fits
139                     if (delta < lanes.size) {
140                         lanes.copyInto(
141                             lanes,
142                             destinationOffset = delta,
143                             startIndex = 0,
144                             endIndex = lanes.size - delta
145                         )
146                     }
147                     // fill the rest of the spans with default values
148                     lanes.fill(0, 0, minOf(lanes.size, delta))
149                 }
150             }
151         }
152 
153         // ensure full item spans beyond saved index are forgotten to save memory
154 
155         while (spannedItems.isNotEmpty() && spannedItems.first().index < lowerBound()) {
156             spannedItems.removeFirst()
157         }
158 
159         while (spannedItems.isNotEmpty() && spannedItems.last().index > upperBound()) {
160             spannedItems.removeLast()
161         }
162     }
163 
setGapsnull164     fun setGaps(itemIndex: Int, gaps: IntArray?) {
165         val foundIndex = spannedItems.binarySearchBy(itemIndex) { it.index }
166         if (foundIndex < 0) {
167             if (gaps == null) {
168                 return
169             }
170             // not found, insert new element
171             val insertionIndex = -(foundIndex + 1)
172             spannedItems.add(insertionIndex, SpannedItem(itemIndex, gaps))
173         } else {
174             if (gaps == null) {
175                 // found, but gaps are reset, remove item
176                 spannedItems.removeAt(foundIndex)
177             } else {
178                 // found, update gaps
179                 spannedItems[foundIndex].gaps = gaps
180             }
181         }
182     }
183 
getGapsnull184     fun getGaps(itemIndex: Int): IntArray? {
185         val foundIndex = spannedItems.binarySearchBy(itemIndex) { it.index }
186         return spannedItems.getOrNull(foundIndex)?.gaps
187     }
188 
ensureCapacitynull189     private fun ensureCapacity(capacity: Int, newOffset: Int = 0) {
190         requirePrecondition(capacity <= MaxCapacity) {
191             "Requested item capacity $capacity is larger than max supported: $MaxCapacity!"
192         }
193         if (lanes.size < capacity) {
194             var newSize = lanes.size
195             while (newSize < capacity) newSize *= 2
196             lanes = lanes.copyInto(IntArray(newSize), destinationOffset = newOffset)
197         }
198     }
199 
200     companion object {
201         private const val MaxCapacity = 131_072 // Closest to 100_000, 2 ^ 17
202         internal const val Unset = -1
203         internal const val FullSpan = -2
204     }
205 }
206