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.layout
18 
19 import androidx.compose.foundation.internal.requirePrecondition
20 import androidx.compose.foundation.internal.throwIndexOutOfBoundsException
21 import androidx.compose.runtime.collection.MutableVector
22 import androidx.compose.runtime.collection.mutableVectorOf
23 
24 /**
25  * The list consisting of multiple intervals.
26  *
27  * It is useful when you want to define your own dsl similar to the one used by LazyColumn where
28  * list items can be defined via multiple item/items calls.
29  *
30  * This interface is read only, in order to create a list you need to use [MutableIntervalList].
31  *
32  * @param T type of values each interval contains in [Interval.value].
33  *
34  * Note: this class is a part of [LazyLayout] harness that allows for building custom lazy layouts.
35  * LazyLayout and all corresponding APIs are still under development and are subject to change.
36  */
37 sealed interface IntervalList<out T> {
38 
39     /**
40      * The total amount of items in all the intervals.
41      *
42      * Note that it is not the amount of intervals, but the sum of [Interval.size] for all the
43      * intervals added into this list.
44      */
45     val size: Int
46 
47     /**
48      * Returns the interval containing the given [index].
49      *
50      * @throws IndexOutOfBoundsException if the index is not within 0..[size] - 1 range.
51      */
getnull52     operator fun get(index: Int): Interval<T>
53 
54     /**
55      * Iterates through all the intervals starting from the one containing [fromIndex] until the one
56      * containing [toIndex].
57      *
58      * @param fromIndex we will start iterating from the interval containing this index.
59      * @param toIndex the last interval we iterate through will contain this index. This index
60      *   should be not smaller than [fromIndex].
61      * @param block will be invoked on each interval within the defined indexes
62      * @throws IndexOutOfBoundsException if the indexes are not within 0..[size] - 1 range.
63      */
64     fun forEach(fromIndex: Int = 0, toIndex: Int = size - 1, block: (Interval<T>) -> Unit)
65 
66     /**
67      * The interval holder.
68      *
69      * @see get
70      */
71     class Interval<out T>
72     internal constructor(
73         /** The index of the first item in the interval. */
74         val startIndex: Int,
75         /** The amount of items in the interval. */
76         val size: Int,
77         /** The value representing this interval. */
78         val value: T
79     ) {
80         init {
81             requirePrecondition(startIndex >= 0) { "startIndex should be >= 0" }
82             requirePrecondition(size > 0) { "size should be > 0" }
83         }
84     }
85 }
86 
87 /**
88  * Mutable version of [IntervalList]. It allows you to add new intervals via [addInterval].
89  *
90  * Note: this class is a part of [LazyLayout] harness that allows for building custom lazy layouts.
91  * LazyLayout and all corresponding APIs are still under development and are subject to change.
92  */
93 class MutableIntervalList<T> : IntervalList<T> {
94     private val intervals = mutableVectorOf<IntervalList.Interval<T>>()
95 
96     override var size = 0
97         private set
98 
99     /**
100      * Caches the last interval we binary searched for. We might not need to recalculate for
101      * subsequent queries, as they tend to be localised.
102      */
103     private var lastInterval: IntervalList.Interval<T>? = null
104 
105     /**
106      * Adds a new interval into this list.
107      *
108      * @param size the amount of items in the new interval.
109      * @param value the value representing this interval.
110      */
addIntervalnull111     fun addInterval(size: Int, value: T) {
112         requirePrecondition(size >= 0) { "size should be >=0" }
113         if (size == 0) {
114             return
115         }
116 
117         val interval = IntervalList.Interval(startIndex = this.size, size = size, value = value)
118         this.size += size
119         intervals.add(interval)
120     }
121 
122     /**
123      * Allows to iterate through all the intervals starting from the one containing [fromIndex]
124      * until the one containing [toIndex].
125      *
126      * @param fromIndex we will start iterating from the interval containing this index.
127      * @param toIndex the last interval we iterate through will contain this index. This index
128      *   should be not smaller than [fromIndex].
129      * @param block will be invoked on each interval within the defined indexes
130      * @throws IndexOutOfBoundsException if the indexes are not within 0..[size] - 1 range.
131      */
forEachnull132     override fun forEach(fromIndex: Int, toIndex: Int, block: (IntervalList.Interval<T>) -> Unit) {
133         checkIndexBounds(fromIndex)
134         checkIndexBounds(toIndex)
135         requirePrecondition(toIndex >= fromIndex) {
136             "toIndex ($toIndex) should be not smaller than fromIndex ($fromIndex)"
137         }
138 
139         var intervalIndex = intervals.binarySearch(fromIndex)
140         var itemIndex = intervals[intervalIndex].startIndex
141         while (itemIndex <= toIndex) {
142             val interval = intervals[intervalIndex]
143             block(interval)
144             itemIndex += interval.size
145             intervalIndex++
146         }
147     }
148 
getnull149     override fun get(index: Int): IntervalList.Interval<T> {
150         checkIndexBounds(index)
151         return getIntervalForIndex(index)
152     }
153 
getIntervalForIndexnull154     private fun getIntervalForIndex(itemIndex: Int): IntervalList.Interval<T> {
155         val lastInterval = lastInterval
156         return if (lastInterval != null && lastInterval.contains(itemIndex)) {
157             lastInterval
158         } else {
159             intervals[intervals.binarySearch(itemIndex)].also { this.lastInterval = it }
160         }
161     }
162 
163     @Suppress("NOTHING_TO_INLINE")
checkIndexBoundsnull164     private inline fun checkIndexBounds(index: Int) {
165         if (index !in 0 until size) {
166             throwIndexOutOfBoundsException("Index $index, size $size")
167         }
168     }
169 
containsnull170     private fun IntervalList.Interval<T>.contains(index: Int) =
171         index in startIndex until startIndex + size
172 }
173 
174 /**
175  * Finds the index of the interval which contains the highest value of
176  * [IntervalList.Interval.startIndex] that is less than or equal to the given [itemIndex].
177  */
178 private fun <T> MutableVector<IntervalList.Interval<T>>.binarySearch(itemIndex: Int): Int {
179     var left = 0
180     var right = lastIndex
181 
182     while (left < right) {
183         val middle = left + (right - left) / 2
184 
185         val middleValue = get(middle).startIndex
186         if (middleValue == itemIndex) {
187             return middle
188         }
189 
190         if (middleValue < itemIndex) {
191             left = middle + 1
192 
193             // Verify that the left will not be bigger than our value
194             if (itemIndex < get(left).startIndex) {
195                 return middle
196             }
197         } else {
198             right = middle - 1
199         }
200     }
201 
202     return left
203 }
204