1 /*
<lambda>null2  * Copyright 2020 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.ui.util
18 
19 import androidx.collection.MutableScatterSet
20 import kotlin.contracts.ExperimentalContracts
21 import kotlin.contracts.contract
22 
23 /**
24  * Iterates through a [List] using the index and calls [action] for each item. This does not
25  * allocate an iterator like [Iterable.forEach].
26  *
27  * **Do not use for collections that come from public APIs**, since they may not support random
28  * access in an efficient way, and this method may actually be a lot slower. Only use for
29  * collections that are created by code we control and are known to support random access.
30  */
31 @Suppress("BanInlineOptIn")
32 @OptIn(ExperimentalContracts::class)
33 inline fun <T> List<T>.fastForEach(action: (T) -> Unit) {
34     contract { callsInPlace(action) }
35     for (index in indices) {
36         val item = get(index)
37         action(item)
38     }
39 }
40 
41 /**
42  * Iterates through a [List] in reverse order using the index and calls [action] for each item. This
43  * does not allocate an iterator like [Iterable.forEach].
44  *
45  * **Do not use for collections that come from public APIs**, since they may not support random
46  * access in an efficient way, and this method may actually be a lot slower. Only use for
47  * collections that are created by code we control and are known to support random access.
48  */
49 @Suppress("BanInlineOptIn")
50 @OptIn(ExperimentalContracts::class)
fastForEachReversednull51 inline fun <T> List<T>.fastForEachReversed(action: (T) -> Unit) {
52     contract { callsInPlace(action) }
53     for (index in indices.reversed()) {
54         val item = get(index)
55         action(item)
56     }
57 }
58 
59 /**
60  * Iterates through a [List] using the index and calls [action] for each item. This does not
61  * allocate an iterator like [Iterable.forEachIndexed].
62  *
63  * **Do not use for collections that come from public APIs**, since they may not support random
64  * access in an efficient way, and this method may actually be a lot slower. Only use for
65  * collections that are created by code we control and are known to support random access.
66  */
67 @Suppress("BanInlineOptIn")
68 @OptIn(ExperimentalContracts::class)
fastForEachIndexednull69 inline fun <T> List<T>.fastForEachIndexed(action: (Int, T) -> Unit) {
70     contract { callsInPlace(action) }
71     for (index in indices) {
72         val item = get(index)
73         action(index, item)
74     }
75 }
76 
77 /**
78  * Returns `true` if all elements match the given [predicate].
79  *
80  * **Do not use for collections that come from public APIs**, since they may not support random
81  * access in an efficient way, and this method may actually be a lot slower. Only use for
82  * collections that are created by code we control and are known to support random access.
83  */
84 @Suppress("BanInlineOptIn")
85 @OptIn(ExperimentalContracts::class)
fastAllnull86 inline fun <T> List<T>.fastAll(predicate: (T) -> Boolean): Boolean {
87     contract { callsInPlace(predicate) }
88     fastForEach { if (!predicate(it)) return false }
89     return true
90 }
91 
92 /**
93  * Returns `true` if at least one element matches the given [predicate].
94  *
95  * **Do not use for collections that come from public APIs**, since they may not support random
96  * access in an efficient way, and this method may actually be a lot slower. Only use for
97  * collections that are created by code we control and are known to support random access.
98  */
99 @Suppress("BanInlineOptIn")
100 @OptIn(ExperimentalContracts::class)
fastAnynull101 inline fun <T> List<T>.fastAny(predicate: (T) -> Boolean): Boolean {
102     contract { callsInPlace(predicate) }
103     fastForEach { if (predicate(it)) return true }
104     return false
105 }
106 
107 /**
108  * Returns the first value that [predicate] returns `true` for or `null` if nothing matches.
109  *
110  * **Do not use for collections that come from public APIs**, since they may not support random
111  * access in an efficient way, and this method may actually be a lot slower. Only use for
112  * collections that are created by code we control and are known to support random access.
113  */
114 @Suppress("BanInlineOptIn")
115 @OptIn(ExperimentalContracts::class)
fastFirstOrNullnull116 inline fun <T> List<T>.fastFirstOrNull(predicate: (T) -> Boolean): T? {
117     contract { callsInPlace(predicate) }
118     fastForEach { if (predicate(it)) return it }
119     return null
120 }
121 
122 /**
123  * Returns the sum of all values produced by [selector] function applied to each element in the
124  * list.
125  *
126  * **Do not use for collections that come from public APIs**, since they may not support random
127  * access in an efficient way, and this method may actually be a lot slower. Only use for
128  * collections that are created by code we control and are known to support random access.
129  */
130 @Suppress("BanInlineOptIn")
131 @OptIn(ExperimentalContracts::class)
fastSumBynull132 inline fun <T> List<T>.fastSumBy(selector: (T) -> Int): Int {
133     contract { callsInPlace(selector) }
134     var sum = 0
135     fastForEach { element -> sum += selector(element) }
136     return sum
137 }
138 
139 /**
140  * Returns a list containing the results of applying the given [transform] function to each element
141  * in the original collection.
142  *
143  * **Do not use for collections that come from public APIs**, since they may not support random
144  * access in an efficient way, and this method may actually be a lot slower. Only use for
145  * collections that are created by code we control and are known to support random access.
146  */
147 @Suppress("BanInlineOptIn")
148 @OptIn(ExperimentalContracts::class)
fastMapnull149 inline fun <T, R> List<T>.fastMap(transform: (T) -> R): List<R> {
150     contract { callsInPlace(transform) }
151     val target = ArrayList<R>(size)
152     fastForEach { target += transform(it) }
153     return target
154 }
155 
156 // TODO: should be fastMaxByOrNull to match stdlib
157 /**
158  * Returns the first element yielding the largest value of the given function or `null` if there are
159  * no elements.
160  *
161  * **Do not use for collections that come from public APIs**, since they may not support random
162  * access in an efficient way, and this method may actually be a lot slower. Only use for
163  * collections that are created by code we control and are known to support random access.
164  */
165 @Suppress("BanInlineOptIn")
166 @OptIn(ExperimentalContracts::class)
fastMaxBynull167 inline fun <T, R : Comparable<R>> List<T>.fastMaxBy(selector: (T) -> R): T? {
168     contract { callsInPlace(selector) }
169     if (isEmpty()) return null
170     var maxElem = get(0)
171     var maxValue = selector(maxElem)
172     for (i in 1..lastIndex) {
173         val e = get(i)
174         val v = selector(e)
175         if (maxValue < v) {
176             maxElem = e
177             maxValue = v
178         }
179     }
180     return maxElem
181 }
182 
183 /**
184  * Applies the given [transform] function to each element of the original collection and appends the
185  * results to the given [destination].
186  *
187  * **Do not use for collections that come from public APIs**, since they may not support random
188  * access in an efficient way, and this method may actually be a lot slower. Only use for
189  * collections that are created by code we control and are known to support random access.
190  */
191 @Suppress("BanInlineOptIn")
192 @OptIn(ExperimentalContracts::class)
fastMapTonull193 inline fun <T, R, C : MutableCollection<in R>> List<T>.fastMapTo(
194     destination: C,
195     transform: (T) -> R
196 ): C {
197     contract { callsInPlace(transform) }
198     fastForEach { item -> destination.add(transform(item)) }
199     return destination
200 }
201 
202 /**
203  * Returns the last element matching the given [predicate], or `null` if no such element was found.
204  *
205  * **Do not use for collections that come from public APIs**, since they may not support random
206  * access in an efficient way, and this method may actually be a lot slower. Only use for
207  * collections that are created by code we control and are known to support random access.
208  */
209 @Suppress("BanInlineOptIn")
210 @OptIn(ExperimentalContracts::class)
fastLastOrNullnull211 inline fun <T> List<T>.fastLastOrNull(predicate: (T) -> Boolean): T? {
212     contract { callsInPlace(predicate) }
213     for (index in indices.reversed()) {
214         val item = get(index)
215         if (predicate(item)) return item
216     }
217     return null
218 }
219 
220 /**
221  * Returns a list containing only elements matching the given [predicate].
222  *
223  * **Do not use for collections that come from public APIs**, since they may not support random
224  * access in an efficient way, and this method may actually be a lot slower. Only use for
225  * collections that are created by code we control and are known to support random access.
226  */
227 @Suppress("BanInlineOptIn") // Treat Kotlin Contracts as non-experimental.
228 @OptIn(ExperimentalContracts::class)
fastFilternull229 inline fun <T> List<T>.fastFilter(predicate: (T) -> Boolean): List<T> {
230     contract { callsInPlace(predicate) }
231     val target = ArrayList<T>(size)
232     fastForEach { if (predicate(it)) target += (it) }
233     return target
234 }
235 
236 /**
237  * Returns a list containing only elements matching the given [predicate], applying the given
238  * [transform] function to each element.
239  *
240  * **Do not use for collections that come from public APIs**, since they may not support random
241  * access in an efficient way, and this method may actually be a lot slower. Only use for
242  * collections that are created by code we control and are known to support random access.
243  */
244 @Suppress("BanInlineOptIn") // Treat Kotlin Contracts as non-experimental.
245 @OptIn(ExperimentalContracts::class)
fastFilteredMapnull246 inline fun <T, R> List<T>.fastFilteredMap(predicate: (T) -> Boolean, transform: (T) -> R): List<R> {
247     contract {
248         callsInPlace(predicate)
249         callsInPlace(transform)
250     }
251     val target = ArrayList<R>(size)
252     fastForEach { if (predicate(it)) target += transform(it) }
253     return target
254 }
255 
256 /**
257  * Accumulates value starting with [initial] value and applying [operation] from left to right to
258  * current accumulator value and each element.
259  *
260  * Returns the specified [initial] value if the collection is empty.
261  *
262  * **Do not use for collections that come from public APIs**, since they may not support random
263  * access in an efficient way, and this method may actually be a lot slower. Only use for
264  * collections that are created by code we control and are known to support random access.
265  */
266 @Suppress("BanInlineOptIn") // Treat Kotlin Contracts as non-experimental.
267 @OptIn(ExperimentalContracts::class)
fastFoldnull268 inline fun <T, R> List<T>.fastFold(initial: R, operation: (acc: R, T) -> R): R {
269     contract { callsInPlace(operation) }
270     var accumulator = initial
271     fastForEach { e -> accumulator = operation(accumulator, e) }
272     return accumulator
273 }
274 
275 /**
276  * Returns a list containing the results of applying the given [transform] function to each element
277  * in the original collection.
278  *
279  * **Do not use for collections that come from public APIs**, since they may not support random
280  * access in an efficient way, and this method may actually be a lot slower. Only use for
281  * collections that are created by code we control and are known to support random access.
282  */
283 @OptIn(ExperimentalContracts::class)
284 @Suppress("BanInlineOptIn") // Treat Kotlin Contracts as non-experimental.
fastMapIndexednull285 inline fun <T, R> List<T>.fastMapIndexed(transform: (index: Int, T) -> R): List<R> {
286     contract { callsInPlace(transform) }
287     val target = ArrayList<R>(size)
288     fastForEachIndexed { index, e -> target += transform(index, e) }
289     return target
290 }
291 
292 /**
293  * Returns a list containing the results of applying the given [transform] function to each element
294  * in the original collection.
295  *
296  * **Do not use for collections that come from public APIs**, since they may not support random
297  * access in an efficient way, and this method may actually be a lot slower. Only use for
298  * collections that are created by code we control and are known to support random access.
299  */
300 @OptIn(ExperimentalContracts::class)
301 @Suppress("BanInlineOptIn") // Treat Kotlin Contracts as non-experimental.
fastMapIndexedNotNullnull302 inline fun <T, R> List<T>.fastMapIndexedNotNull(transform: (index: Int, T) -> R?): List<R> {
303     contract { callsInPlace(transform) }
304     val target = ArrayList<R>(size)
305     fastForEachIndexed { index, e -> transform(index, e)?.let { target += it } }
306     return target
307 }
308 
309 /**
310  * Returns the largest value among all values produced by selector function applied to each element
311  * in the collection or null if there are no elements.
312  *
313  * **Do not use for collections that come from public APIs**, since they may not support random
314  * access in an efficient way, and this method may actually be a lot slower. Only use for
315  * collections that are created by code we control and are known to support random access.
316  */
317 @Suppress("BanInlineOptIn") // Treat Kotlin Contracts as non-experimental.
318 @OptIn(ExperimentalContracts::class)
fastMaxOfOrNullnull319 inline fun <T, R : Comparable<R>> List<T>.fastMaxOfOrNull(selector: (T) -> R): R? {
320     contract { callsInPlace(selector) }
321     if (isEmpty()) return null
322     var maxValue = selector(get(0))
323     for (i in 1..lastIndex) {
324         val v = selector(get(i))
325         if (v > maxValue) maxValue = v
326     }
327     return maxValue
328 }
329 
330 /**
331  * Returns the largest value among all values produced by selector function applied to each element
332  * in the collection or [defaultValue] if there are no elements.
333  *
334  * **Do not use for collections that come from public APIs**, since they may not support random
335  * access in an efficient way, and this method may actually be a lot slower. Only use for
336  * collections that are created by code we control and are known to support random access.
337  */
338 @Suppress("BanInlineOptIn") // Treat Kotlin Contracts as non-experimental.
339 @OptIn(ExperimentalContracts::class)
fastMaxOfOrDefaultnull340 inline fun <T, R : Comparable<R>> List<T>.fastMaxOfOrDefault(
341     defaultValue: R,
342     selector: (T) -> R
343 ): R {
344     contract { callsInPlace(selector) }
345     if (isEmpty()) return defaultValue
346     var maxValue = selector(get(0))
347     for (i in 1..lastIndex) {
348         val v = selector(get(i))
349         if (v > maxValue) maxValue = v
350     }
351     return maxValue
352 }
353 
354 /**
355  * Returns a list containing the results of applying the given [transform] function to each pair of
356  * two adjacent elements in this collection.
357  *
358  * The returned list is empty if this collection contains less than two elements.
359  *
360  * **Do not use for collections that come from public APIs**, since they may not support random
361  * access in an efficient way, and this method may actually be a lot slower. Only use for
362  * collections that are created by code we control and are known to support random access.
363  */
364 @Suppress("BanInlineOptIn")
365 @OptIn(ExperimentalContracts::class)
fastZipWithNextnull366 inline fun <T, R> List<T>.fastZipWithNext(transform: (T, T) -> R): List<R> {
367     contract { callsInPlace(transform) }
368     if (size <= 1) return emptyList()
369     val result = mutableListOf<R>()
370     var current = get(0)
371     // `until` as we don't want to invoke this for the last element, since that won't have a `next`
372     for (i in 0 until lastIndex) {
373         val next = get(i + 1)
374         result.add(transform(current, next))
375         current = next
376     }
377     return result
378 }
379 
380 /**
381  * Accumulates value starting with the first element and applying [operation] from left to right to
382  * current accumulator value and each element.
383  *
384  * Throws an exception if this collection is empty. If the collection can be empty in an expected
385  * way, please use [reduceOrNull] instead. It returns `null` when its receiver is empty.
386  *
387  * **Do not use for collections that come from public APIs**, since they may not support random
388  * access in an efficient way, and this method may actually be a lot slower. Only use for
389  * collections that are created by code we control and are known to support random access.
390  *
391  * @param [operation] function that takes current accumulator value and an element, and calculates
392  *   the next accumulator value.
393  * @throws UnsupportedOperationException if this collection is empty
394  */
395 @Suppress("BanInlineOptIn")
396 @OptIn(ExperimentalContracts::class)
fastReducenull397 inline fun <S, T : S> List<T>.fastReduce(operation: (acc: S, T) -> S): S {
398     contract { callsInPlace(operation) }
399     if (isEmpty()) throwUnsupportedOperationException("Empty collection can't be reduced.")
400     var accumulator: S = first()
401     for (i in 1..lastIndex) {
402         accumulator = operation(accumulator, get(i))
403     }
404     return accumulator
405 }
406 
407 /**
408  * Returns a list of values built from the elements of `this` collection and the [other] collection
409  * with the same index using the provided [transform] function applied to each pair of elements. The
410  * returned list has length of the shortest collection.
411  *
412  * **Do not use for collections that come from public APIs**, since they may not support random
413  * access in an efficient way, and this method may actually be a lot slower. Only use for
414  * collections that are created by code we control and are known to support random access.
415  */
416 @Suppress("BanInlineOptIn")
417 @OptIn(ExperimentalContracts::class)
fastZipnull418 inline fun <T, R, V> List<T>.fastZip(other: List<R>, transform: (a: T, b: R) -> V): List<V> {
419     contract { callsInPlace(transform) }
420     val minSize = minOf(size, other.size)
421     val target = ArrayList<V>(minSize)
422     for (i in 0 until minSize) {
423         target += (transform(get(i), other[i]))
424     }
425     return target
426 }
427 
428 /**
429  * Returns a list containing the results of applying the given [transform] function to each element
430  * in the original collection.
431  *
432  * **Do not use for collections that come from public APIs**, since they may not support random
433  * access in an efficient way, and this method may actually be a lot slower. Only use for
434  * collections that are created by code we control and are known to support random access.
435  */
436 @Suppress("BanInlineOptIn")
437 @OptIn(ExperimentalContracts::class)
fastMapNotNullnull438 inline fun <T, R> List<T>.fastMapNotNull(transform: (T) -> R?): List<R> {
439     contract { callsInPlace(transform) }
440     val target = ArrayList<R>(size)
441     fastForEach { e -> transform(e)?.let { target += it } }
442     return target
443 }
444 
445 /**
446  * Creates a string from all the elements separated using [separator] and using the given [prefix]
447  * and [postfix] if supplied.
448  *
449  * If the collection could be huge, you can specify a non-negative value of [limit], in which case
450  * only the first [limit] elements will be appended, followed by the [truncated] string (which
451  * defaults to "...").
452  *
453  * **Do not use for collections that come from public APIs**, since they may not support random
454  * access in an efficient way, and this method may actually be a lot slower. Only use for
455  * collections that are created by code we control and are known to support random access.
456  */
fastJoinToStringnull457 fun <T> List<T>.fastJoinToString(
458     separator: CharSequence = ", ",
459     prefix: CharSequence = "",
460     postfix: CharSequence = "",
461     limit: Int = -1,
462     truncated: CharSequence = "...",
463     transform: ((T) -> CharSequence)? = null
464 ): String {
465     return fastJoinTo(StringBuilder(), separator, prefix, postfix, limit, truncated, transform)
466         .toString()
467 }
468 
469 /**
470  * Returns a list containing only elements from the given collection having distinct keys returned
471  * by the given [selector] function.
472  *
473  * The elements in the resulting list are in the same order as they were in the source collection.
474  *
475  * **Do not use for collections that come from public APIs**, since they may not support random
476  * access in an efficient way, and this method may actually be a lot slower. Only use for
477  * collections that are created by code we control and are known to support random access.
478  */
479 @Suppress("BanInlineOptIn") // Treat Kotlin Contracts as non-experimental.
480 @OptIn(ExperimentalContracts::class)
fastDistinctBynull481 inline fun <T, K> List<T>.fastDistinctBy(selector: (T) -> K): List<T> {
482     contract { callsInPlace(selector) }
483     val set = MutableScatterSet<K>(size)
484     val target = ArrayList<T>(size)
485     fastForEach { e ->
486         val key = selector(e)
487         if (set.add(key)) target += e
488     }
489     return target
490 }
491 
492 /**
493  * Returns the first element yielding the largest value of the given function or `null` if there are
494  * no elements.
495  *
496  * **Do not use for collections that come from public APIs**, since they may not support random
497  * access in an efficient way, and this method may actually be a lot slower. Only use for
498  * collections that are created by code we control and are known to support random access.
499  */
500 @Suppress("BanInlineOptIn") // Treat Kotlin Contracts as non-experimental.
501 @OptIn(ExperimentalContracts::class)
fastMinByOrNullnull502 inline fun <T, R : Comparable<R>> List<T>.fastMinByOrNull(selector: (T) -> R): T? {
503     contract { callsInPlace(selector) }
504     if (isEmpty()) return null
505     var minElem = get(0)
506     var minValue = selector(minElem)
507     for (i in 1..lastIndex) {
508         val e = get(i)
509         val v = selector(e)
510         if (minValue > v) {
511             minElem = e
512             minValue = v
513         }
514     }
515     return minElem
516 }
517 
518 /**
519  * Returns a single list of all elements yielded from results of [transform] function being invoked
520  * on each element of original collection.
521  *
522  * **Do not use for collections that come from public APIs**, since they may not support random
523  * access in an efficient way, and this method may actually be a lot slower. Only use for
524  * collections that are created by code we control and are known to support random access.
525  */
526 @Suppress("BanInlineOptIn") // Treat Kotlin Contracts as non-experimental.
527 @OptIn(ExperimentalContracts::class)
fastFlatMapnull528 inline fun <T, R> List<T>.fastFlatMap(transform: (T) -> Iterable<R>): List<R> {
529     contract { callsInPlace(transform) }
530     val target = ArrayList<R>(size)
531     fastForEach { e ->
532         val list = transform(e)
533         target.addAll(list)
534     }
535     return target
536 }
537 
538 /**
539  * Returns a list containing all elements that are not null
540  *
541  * **Do not use for collections that come from public APIs**, since they may not support random
542  * access in an efficient way, and this method may actually be a lot slower. Only use for
543  * collections that are created by code we control and are known to support random access.
544  */
fastFilterNotNullnull545 fun <T : Any> List<T?>.fastFilterNotNull(): List<T> {
546     val target = ArrayList<T>(size)
547     fastForEach { if ((it) != null) target += (it) }
548     return target
549 }
550 
551 /**
552  * Returns the first value that [predicate] returns `true` for
553  *
554  * **Do not use for collections that come from public APIs**, since they may not support random
555  * access in an efficient way, and this method may actually be a lot slower. Only use for
556  * collections that are created by code we control and are known to support random access.
557  *
558  * @throws [NoSuchElementException] if no such element is found
559  */
560 @Suppress("BanInlineOptIn")
561 @OptIn(ExperimentalContracts::class)
fastFirstnull562 inline fun <T> List<T>.fastFirst(predicate: (T) -> Boolean): T {
563     contract { callsInPlace(predicate) }
564     fastForEach { if (predicate(it)) return it }
565     throwNoSuchElementException("Collection contains no element matching the predicate.")
566 }
567 
568 /**
569  * Appends the string from all the elements separated using [separator] and using the given [prefix]
570  * and [postfix] if supplied.
571  *
572  * If the collection could be huge, you can specify a non-negative value of [limit], in which case
573  * only the first [limit] elements will be appended, followed by the [truncated] string (which
574  * defaults to "...").
575  *
576  * **Do not use for collections that come from public APIs**, since they may not support random
577  * access in an efficient way, and this method may actually be a lot slower. Only use for
578  * collections that are created by code we control and are known to support random access.
579  */
fastJoinTonull580 private fun <T, A : Appendable> List<T>.fastJoinTo(
581     buffer: A,
582     separator: CharSequence = ", ",
583     prefix: CharSequence = "",
584     postfix: CharSequence = "",
585     limit: Int = -1,
586     truncated: CharSequence = "...",
587     transform: ((T) -> CharSequence)? = null
588 ): A {
589     buffer.append(prefix)
590     var count = 0
591     for (index in indices) {
592         val element = get(index)
593         if (++count > 1) buffer.append(separator)
594         if (limit < 0 || count <= limit) {
595             buffer.appendElement(element, transform)
596         } else break
597     }
598     if (limit >= 0 && count > limit) buffer.append(truncated)
599     buffer.append(postfix)
600     return buffer
601 }
602 
603 /** Copied from Appendable.kt */
appendElementnull604 private fun <T> Appendable.appendElement(element: T, transform: ((T) -> CharSequence)?) {
605     when {
606         transform != null -> append(transform(element))
607         element is CharSequence? -> append(element)
608         element is Char -> append(element)
609         else -> append(element.toString())
610     }
611 }
612 
613 @PublishedApi
throwNoSuchElementExceptionnull614 internal fun throwNoSuchElementException(message: String): Nothing {
615     throw NoSuchElementException(message)
616 }
617 
618 @PublishedApi
throwUnsupportedOperationExceptionnull619 internal fun throwUnsupportedOperationException(message: String) {
620     throw UnsupportedOperationException(message)
621 }
622