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 @file:Suppress("NOTHING_TO_INLINE", "UNCHECKED_CAST", "KotlinRedundantDiagnosticSuppress")
18
19 package androidx.compose.runtime.collection
20
21 import kotlin.contracts.ExperimentalContracts
22 import kotlin.contracts.contract
23 import kotlin.jvm.JvmField
24 import kotlin.math.max
25
26 /**
27 * A [MutableList]-like structure with a simplified interface that offers faster access than
28 * [ArrayList].
29 */
30 @OptIn(ExperimentalContracts::class)
31 class MutableVector<T>
32 @PublishedApi
33 internal constructor(@PublishedApi @JvmField internal var content: Array<T?>, size: Int) :
34 RandomAccess {
35 /** Stores allocated [MutableList] representation of this vector. */
36 private var list: MutableList<T>? = null
37
38 /** The number of elements in the [MutableVector]. */
39 var size: Int = size
40 private set
41
42 /** Returns the last valid index in the [MutableVector]. */
43 inline val lastIndex: Int
44 get() = size - 1
45
46 /** Returns an [IntRange] of the valid indices for this [MutableVector]. */
47 inline val indices: IntRange
48 get() = 0 until size
49
50 // Added for compatibility with `content` previously defined without @JvmField
51 @PublishedApi internal fun getContent() = content
52
53 /** Adds [element] to the [MutableVector] and returns `true`. */
54 fun add(element: T): Boolean {
55 ensureCapacity(size + 1)
56 content[size] = element
57 size++
58 return true
59 }
60
61 /**
62 * Adds [element] to the [MutableVector] at the given [index], shifting over any elements that
63 * are in the way.
64 */
65 fun add(index: Int, element: T) {
66 ensureCapacity(size + 1)
67 val content = content
68 if (index != size) {
69 content.fastCopyInto(
70 destination = content,
71 destinationOffset = index + 1,
72 startIndex = index,
73 endIndex = size
74 )
75 }
76 content[index] = element
77 size++
78 }
79
80 /**
81 * Adds all [elements] to the [MutableVector] at the given [index], shifting over any elements
82 * that are in the way.
83 */
84 fun addAll(index: Int, elements: List<T>): Boolean {
85 if (elements.isEmpty()) return false
86 val elementsSize = elements.size
87 ensureCapacity(size + elementsSize)
88 val content = content
89 if (index != size) {
90 content.fastCopyInto(
91 destination = content,
92 destinationOffset = index + elementsSize,
93 startIndex = index,
94 endIndex = size
95 )
96 }
97 for (i in elements.indices) {
98 content[index + i] = elements[i]
99 }
100 size += elementsSize
101 return true
102 }
103
104 /**
105 * Adds all [elements] to the [MutableVector] at the given [index], shifting over any elements
106 * that are in the way.
107 */
108 fun addAll(index: Int, elements: MutableVector<T>): Boolean {
109 val elementsSize = elements.size
110 if (elementsSize == 0) return false
111 ensureCapacity(size + elementsSize)
112 val content = content
113 if (index != size) {
114 content.fastCopyInto(
115 destination = content,
116 destinationOffset = index + elementsSize,
117 startIndex = index,
118 endIndex = size
119 )
120 }
121 elements.content.fastCopyInto(
122 destination = content,
123 destinationOffset = index,
124 startIndex = 0,
125 endIndex = elementsSize
126 )
127 size += elementsSize
128 return true
129 }
130
131 /**
132 * Adds all [elements] to the end of the [MutableVector] and returns `true` if the
133 * [MutableVector] was changed.
134 */
135 inline fun addAll(elements: List<T>): Boolean {
136 return addAll(size, elements)
137 }
138
139 /**
140 * Adds all [elements] to the end of the [MutableVector] and returns `true` if the
141 * [MutableVector] was changed.
142 */
143 inline fun addAll(elements: MutableVector<T>): Boolean {
144 return addAll(size, elements)
145 }
146
147 /**
148 * Adds all [elements] to the end of the [MutableVector] and returns `true` if the
149 * [MutableVector] was changed.
150 */
151 fun addAll(@Suppress("ArrayReturn") elements: Array<T>): Boolean {
152 val elementsSize = elements.size
153 if (elementsSize == 0) {
154 return false
155 }
156 ensureCapacity(size + elementsSize)
157 elements.fastCopyInto(destination = content, destinationOffset = size, 0, elementsSize)
158 size += elementsSize
159 return true
160 }
161
162 /**
163 * Adds all [elements] to the [MutableVector] at the given [index], shifting over any elements
164 * that are in the way.
165 */
166 fun addAll(index: Int, elements: Collection<T>): Boolean {
167 if (elements.isEmpty()) return false
168 val elementsSize = elements.size
169 ensureCapacity(size + elementsSize)
170 val content = content
171 if (index != size) {
172 content.fastCopyInto(
173 destination = content,
174 destinationOffset = index + elementsSize,
175 startIndex = index,
176 endIndex = size
177 )
178 }
179 elements.forEachIndexed { i, item -> content[index + i] = item }
180 size += elementsSize
181 return true
182 }
183
184 /**
185 * Adds all [elements] to the end of the [MutableVector] and returns `true` if the
186 * [MutableVector] was changed.
187 */
188 fun addAll(elements: Collection<T>): Boolean {
189 return addAll(size, elements)
190 }
191
192 /** Returns `true` if any of the elements give a `true` return value for [predicate]. */
193 inline fun any(predicate: (T) -> Boolean): Boolean {
194 contract { callsInPlace(predicate) }
195 val content = content as Array<T>
196 val size = size
197 for (i in 0 until size) {
198 if (predicate(content[i])) return true
199 }
200 return false
201 }
202
203 /**
204 * Returns `true` if any of the elements give a `true` return value for [predicate] while
205 * iterating in the reverse order.
206 */
207 inline fun reversedAny(predicate: (T) -> Boolean): Boolean {
208 contract { callsInPlace(predicate) }
209 val content = content as Array<T>
210 var i = size - 1
211 while (i >= 0) {
212 if (predicate(content[i])) return true
213 i--
214 }
215 return false
216 }
217
218 /** Returns [MutableList] interface access to the [MutableVector]. */
219 fun asMutableList(): MutableList<T> {
220 return list ?: MutableVectorList(this).also { list = it }
221 }
222
223 /** Removes all elements in the [MutableVector]. */
224 fun clear() {
225 val content = content
226 for (i in 0 until size) {
227 content[i] = null
228 }
229 size = 0
230 }
231
232 /** Returns `true` if the [MutableVector] contains [element] or `false` otherwise. */
233 operator fun contains(element: T): Boolean {
234 for (i in 0..lastIndex) {
235 if (get(i) == element) return true
236 }
237 return false
238 }
239
240 /**
241 * Returns `true` if the [MutableVector] contains all elements in [elements] or `false` if one
242 * or more are missing.
243 */
244 fun containsAll(elements: List<T>): Boolean {
245 for (i in elements.indices) {
246 if (!contains(elements[i])) return false
247 }
248 return true
249 }
250
251 /**
252 * Returns `true` if the [MutableVector] contains all elements in [elements] or `false` if one
253 * or more are missing.
254 */
255 fun containsAll(elements: Collection<T>): Boolean {
256 elements.forEach { if (!contains(it)) return false }
257 return true
258 }
259
260 /**
261 * Returns `true` if the [MutableVector] contains all elements in [elements] or `false` if one
262 * or more are missing.
263 */
264 fun containsAll(elements: MutableVector<T>): Boolean {
265 for (i in elements.indices) {
266 if (!contains(elements[i])) return false
267 }
268 return true
269 }
270
271 /**
272 * Returns `true` if the contents of the [MutableVector] are the same or `false` if there is any
273 * difference. This uses equality comparisons on each element rather than reference equality.
274 */
275 fun contentEquals(other: MutableVector<T>): Boolean {
276 if (other.size != size) {
277 return false
278 }
279 for (i in 0..lastIndex) {
280 if (other[i] != this[i]) {
281 return false
282 }
283 }
284 return true
285 }
286
287 /** Ensures that there is enough space to store [capacity] elements in the [MutableVector]. */
288 inline fun ensureCapacity(capacity: Int) {
289 if (content.size < capacity) {
290 resizeStorage(capacity)
291 }
292 }
293
294 @PublishedApi
295 internal fun resizeStorage(capacity: Int) {
296 val oldContent = content
297 val oldSize = oldContent.size
298 val newSize = max(capacity, oldSize * 2)
299 val newContent = arrayOfNulls<Any?>(newSize) as Array<T?>
300 oldContent.fastCopyInto(newContent, 0, 0, oldSize)
301 content = newContent
302 }
303
304 /**
305 * Returns the first element in the [MutableVector] or throws a [NoSuchElementException] if it
306 * [isEmpty].
307 */
308 fun first(): T {
309 if (isEmpty()) {
310 throwNoSuchElementException()
311 }
312 return get(0)
313 }
314
315 /**
316 * Returns the first element in the [MutableVector] for which [predicate] returns `true` or
317 * throws [NoSuchElementException] if nothing matches.
318 */
319 inline fun first(predicate: (T) -> Boolean): T {
320 contract { callsInPlace(predicate) }
321 val content = content as Array<T>
322 val size = size
323 for (i in 0 until size) {
324 val item = content[i]
325 if (predicate(item)) return item
326 }
327 throwNoSuchElementException("MutableVector contains no element matching the predicate.")
328 }
329
330 @PublishedApi
331 internal inline fun throwNoSuchElementException(): Nothing =
332 throwNoSuchElementException("MutableVector is empty.")
333
334 @PublishedApi
335 internal fun throwNoSuchElementException(message: String): Nothing {
336 throw NoSuchElementException(message)
337 }
338
339 /** Returns the first element in the [MutableVector] or `null` if it [isEmpty]. */
340 inline fun firstOrNull() = if (isEmpty()) null else get(0)
341
342 /**
343 * Returns the first element in the [MutableVector] for which [predicate] returns `true` or
344 * returns `null` if nothing matches.
345 */
346 inline fun firstOrNull(predicate: (T) -> Boolean): T? {
347 contract { callsInPlace(predicate) }
348 val content = content as Array<T>
349 val size = size
350 for (i in 0 until size) {
351 val item = content[i]
352 if (predicate(item)) return item
353 }
354 return null
355 }
356
357 /**
358 * Accumulates values, starting with [initial], and applying [operation] to each element in the
359 * [MutableVector] in order.
360 */
361 inline fun <R> fold(initial: R, operation: (acc: R, T) -> R): R {
362 contract { callsInPlace(operation) }
363 var acc = initial
364 val content = content as Array<T>
365 val size = size
366 for (i in 0 until size) {
367 acc = operation(acc, content[i])
368 }
369 return acc
370 }
371
372 /**
373 * Accumulates values, starting with [initial], and applying [operation] to each element in the
374 * [MutableVector] in order.
375 */
376 inline fun <R> foldIndexed(initial: R, operation: (index: Int, acc: R, T) -> R): R {
377 contract { callsInPlace(operation) }
378 var acc = initial
379 val content = content as Array<T>
380 val size = size
381 for (i in 0 until size) {
382 acc = operation(i, acc, content[i])
383 }
384 return acc
385 }
386
387 /**
388 * Accumulates values, starting with [initial], and applying [operation] to each element in the
389 * [MutableVector] in reverse order.
390 */
391 inline fun <R> foldRight(initial: R, operation: (T, acc: R) -> R): R {
392 contract { callsInPlace(operation) }
393 var acc = initial
394 var i = size - 1
395 val content = content as Array<T>
396 if (i >= content.size) return acc
397 while (i >= 0) {
398 acc = operation(content[i], acc)
399 i--
400 }
401 return acc
402 }
403
404 /**
405 * Accumulates values, starting with [initial], and applying [operation] to each element in the
406 * [MutableVector] in reverse order.
407 */
408 inline fun <R> foldRightIndexed(initial: R, operation: (index: Int, T, acc: R) -> R): R {
409 contract { callsInPlace(operation) }
410 var acc = initial
411 var i = size - 1
412 val content = content as Array<T>
413 if (i >= content.size) return acc
414 while (i >= 0) {
415 acc = operation(i, content[i], acc)
416 i--
417 }
418 return acc
419 }
420
421 /** Calls [block] for each element in the [MutableVector], in order. */
422 inline fun forEach(block: (T) -> Unit) {
423 contract { callsInPlace(block) }
424 var i = 0
425 val content = content as Array<T>
426 val size = size
427 while (i < size) {
428 block(content[i])
429 i++
430 }
431 }
432
433 /** Calls [block] for each element in the [MutableVector] along with its index, in order. */
434 inline fun forEachIndexed(block: (Int, T) -> Unit) {
435 contract { callsInPlace(block) }
436 var i = 0
437 val content = content as Array<T>
438 val size = size
439 while (i < size) {
440 block(i, content[i])
441 i++
442 }
443 }
444
445 /** Calls [block] for each element in the [MutableVector] in reverse order. */
446 inline fun forEachReversed(block: (T) -> Unit) {
447 contract { callsInPlace(block) }
448 var i = size - 1
449 val content = content as Array<T>
450 if (i >= content.size) return
451 while (i >= 0) {
452 block(content[i])
453 i--
454 }
455 }
456
457 /**
458 * Calls [block] for each element in the [MutableVector] along with its index, in reverse order.
459 */
460 inline fun forEachReversedIndexed(block: (Int, T) -> Unit) {
461 contract { callsInPlace(block) }
462 var i = size - 1
463 val content = content as Array<T>
464 if (i >= content.size) return
465 while (i >= 0) {
466 block(i, content[i])
467 i--
468 }
469 }
470
471 /** Returns the element at the given [index]. */
472 inline operator fun get(index: Int): T = content[index] as T
473
474 /** Returns the index of [element] in the [MutableVector] or `-1` if [element] is not there. */
475 fun indexOf(element: T): Int {
476 val content = content as Array<T>
477 val size = size
478 for (i in 0 until size) {
479 if (element == content[i]) return i
480 }
481 return -1
482 }
483
484 /**
485 * Returns the index if the first element in the [MutableVector] for which [predicate] returns
486 * `true`.
487 */
488 inline fun indexOfFirst(predicate: (T) -> Boolean): Int {
489 contract { callsInPlace(predicate) }
490 val content = content as Array<T>
491 val size = size
492 for (i in 0 until size) {
493 if (predicate(content[i])) return i
494 }
495 return -1
496 }
497
498 /**
499 * Returns the index if the last element in the [MutableVector] for which [predicate] returns
500 * `true`.
501 */
502 inline fun indexOfLast(predicate: (T) -> Boolean): Int {
503 contract { callsInPlace(predicate) }
504 var i = size - 1
505 val content = content as Array<T>
506 if (i < content.size) {
507 while (i >= 0) {
508 if (predicate(content[i])) return i
509 i--
510 }
511 }
512 return -1
513 }
514
515 /** Returns `true` if the [MutableVector] has no elements in it or `false` otherwise. */
516 inline fun isEmpty(): Boolean = size == 0
517
518 /** Returns `true` if there are elements in the [MutableVector] or `false` if it is empty. */
519 inline fun isNotEmpty(): Boolean = size != 0
520
521 /**
522 * Returns the last element in the [MutableVector] or throws a [NoSuchElementException] if it
523 * [isEmpty].
524 */
525 fun last(): T {
526 if (isEmpty()) {
527 throwNoSuchElementException("MutableVector is empty.")
528 }
529 return get(lastIndex)
530 }
531
532 /**
533 * Returns the last element in the [MutableVector] for which [predicate] returns `true` or
534 * throws [NoSuchElementException] if nothing matches.
535 */
536 inline fun last(predicate: (T) -> Boolean): T {
537 contract { callsInPlace(predicate) }
538 var i = size - 1
539 val content = content as Array<T>
540 while (i >= 0) {
541 val item = content[i]
542 if (predicate(item)) return item
543 i--
544 }
545 throwNoSuchElementException("MutableVector contains no element matching the predicate.")
546 }
547
548 /**
549 * Returns the index of the last element in the [MutableVector] that is the same as [element] or
550 * `-1` if no elements match.
551 */
552 fun lastIndexOf(element: T): Int {
553 var i = size - 1
554 val content = content as Array<T>
555 while (i >= 0) {
556 if (element == content[i]) return i
557 i--
558 }
559 return -1
560 }
561
562 /** Returns the last element in the [MutableVector] or `null` if it [isEmpty]. */
563 inline fun lastOrNull() = if (isEmpty()) null else get(lastIndex)
564
565 /**
566 * Returns the last element in the [MutableVector] for which [predicate] returns `true` or
567 * returns `null` if nothing matches.
568 */
569 inline fun lastOrNull(predicate: (T) -> Boolean): T? {
570 contract { callsInPlace(predicate) }
571 var i = size - 1
572 val content = content as Array<T>
573 while (i >= 0) {
574 val item = content[i]
575 if (predicate(item)) return item
576 i--
577 }
578 return null
579 }
580
581 /**
582 * Returns an [Array] of results of transforming each element in the [MutableVector]. The Array
583 * will be the same size as this.
584 */
585 @Suppress("ArrayReturn")
586 inline fun <reified R> map(transform: (T) -> R): Array<R> {
587 contract { callsInPlace(transform) }
588 return Array(size) { transform(get(it)) }
589 }
590
591 /**
592 * Returns an [Array] of results of transforming each element in the [MutableVector]. The Array
593 * will be the same size as this.
594 */
595 @Suppress("ArrayReturn")
596 inline fun <reified R> mapIndexed(transform: (index: Int, T) -> R): Array<R> {
597 contract { callsInPlace(transform) }
598 return Array(size) { transform(it, get(it)) }
599 }
600
601 /**
602 * Returns an [MutableVector] of results of transforming each element in the [MutableVector],
603 * excluding those transformed values that are `null`.
604 */
605 inline fun <reified R> mapIndexedNotNull(transform: (index: Int, T) -> R?): MutableVector<R> {
606 contract { callsInPlace(transform) }
607 val size = size
608 val arr = arrayOfNulls<R>(size)
609 var targetSize = 0
610 val content = content as Array<T>
611 for (i in 0 until size) {
612 val target = transform(i, content[i])
613 if (target != null) {
614 arr[targetSize++] = target
615 }
616 }
617 return MutableVector(arr, targetSize)
618 }
619
620 /**
621 * Returns an [MutableVector] of results of transforming each element in the [MutableVector],
622 * excluding those transformed values that are `null`.
623 */
624 inline fun <reified R> mapNotNull(transform: (T) -> R?): MutableVector<R> {
625 contract { callsInPlace(transform) }
626 val size = size
627 val arr = arrayOfNulls<R>(size)
628 var targetSize = 0
629 val content = content as Array<T>
630 for (i in 0 until size) {
631 val target = transform(content[i])
632 if (target != null) {
633 arr[targetSize++] = target
634 }
635 }
636 return MutableVector(arr, targetSize)
637 }
638
639 /** [add] [element] to the [MutableVector]. */
640 inline operator fun plusAssign(element: T) {
641 add(element)
642 }
643
644 /** [remove] [element] from the [MutableVector] */
645 inline operator fun minusAssign(element: T) {
646 remove(element)
647 }
648
649 /**
650 * Removes [element] from the [MutableVector]. If [element] was in the [MutableVector] and was
651 * removed, `true` will be returned, or `false` will be returned if the element was not found.
652 */
653 fun remove(element: T): Boolean {
654 val index = indexOf(element)
655 if (index >= 0) {
656 removeAt(index)
657 return true
658 }
659 return false
660 }
661
662 /**
663 * Removes all [elements] from the [MutableVector] and returns `true` if anything was removed.
664 */
665 fun removeAll(elements: List<T>): Boolean {
666 val initialSize = size
667 for (i in elements.indices) {
668 remove(elements[i])
669 }
670 return initialSize != size
671 }
672
673 /**
674 * Removes all [elements] from the [MutableVector] and returns `true` if anything was removed.
675 */
676 fun removeAll(elements: MutableVector<T>): Boolean {
677 val initialSize = size
678 for (i in 0..elements.lastIndex) {
679 remove(elements[i])
680 }
681 return initialSize != size
682 }
683
684 /**
685 * Removes all [elements] from the [MutableVector] and returns `true` if anything was removed.
686 */
687 fun removeAll(elements: Collection<T>): Boolean {
688 if (elements.isEmpty()) {
689 return false
690 }
691 val initialSize = size
692 elements.forEach { remove(it) }
693 return initialSize != size
694 }
695
696 /** Removes the element at the given [index] and returns it. */
697 fun removeAt(index: Int): T {
698 val content = content
699 val item = content[index] as T
700 if (index != lastIndex) {
701 content.fastCopyInto(
702 destination = content,
703 destinationOffset = index,
704 startIndex = index + 1,
705 endIndex = size
706 )
707 }
708 size--
709 content[size] = null
710 return item
711 }
712
713 /** Removes items from index [start] (inclusive) to [end] (exclusive). */
714 fun removeRange(start: Int, end: Int) {
715 if (end > start) {
716 if (end < size) {
717 content.fastCopyInto(
718 destination = content,
719 destinationOffset = start,
720 startIndex = end,
721 endIndex = size
722 )
723 }
724 val newSize = size - (end - start)
725 for (i in newSize..lastIndex) {
726 content[i] = null // clean up the removed items
727 }
728 size = newSize
729 }
730 }
731
732 // Workaround to allow setting size from inline functions
733 @PublishedApi
734 internal fun setSize(newSize: Int) {
735 size = newSize
736 }
737
738 /** Removes items that satisfy [predicate] */
739 inline fun removeIf(predicate: (T) -> Boolean) {
740 var gap = 0
741 val size = size
742 for (i in 0 until size) {
743 if (predicate(content[i] as T)) {
744 gap++
745 continue
746 }
747
748 if (gap > 0) {
749 content[i - gap] = content[i]
750 }
751 }
752 content.fill(null, fromIndex = size - gap, toIndex = size)
753 setSize(size - gap)
754 }
755
756 /** Keeps only [elements] in the [MutableVector] and removes all other values. */
757 fun retainAll(elements: Collection<T>): Boolean {
758 val initialSize = size
759 for (i in lastIndex downTo 0) {
760 val item = get(i)
761 if (item !in elements) {
762 removeAt(i)
763 }
764 }
765 return initialSize != size
766 }
767
768 /** Sets the value at [index] to [element]. */
769 operator fun set(index: Int, element: T): T {
770 val content = content
771 val old = content[index] as T
772 content[index] = element
773 return old
774 }
775
776 /** Sorts the [MutableVector] using [comparator] to order the items. */
777 fun sortWith(comparator: Comparator<T>) {
778 (content as Array<T>).sortWith(comparator = comparator, fromIndex = 0, toIndex = size)
779 }
780
781 /**
782 * Returns the sum of all values produced by [selector] for each element in the [MutableVector].
783 */
784 inline fun sumBy(selector: (T) -> Int): Int {
785 contract { callsInPlace(selector) }
786 var sum = 0
787 val content = content as Array<T>
788 var i = 0
789 while (i < size) {
790 sum += selector(content[i])
791 i++
792 }
793 return sum
794 }
795
796 private class VectorListIterator<T>(private val list: MutableList<T>, private var index: Int) :
797 MutableListIterator<T> {
798
799 override fun hasNext(): Boolean {
800 return index < list.size
801 }
802
803 override fun next(): T {
804 return list[index++]
805 }
806
807 override fun remove() {
808 index--
809 list.removeAt(index)
810 }
811
812 override fun hasPrevious(): Boolean {
813 return index > 0
814 }
815
816 override fun nextIndex(): Int {
817 return index
818 }
819
820 override fun previous(): T {
821 index--
822 return list[index]
823 }
824
825 override fun previousIndex(): Int {
826 return index - 1
827 }
828
829 override fun add(element: T) {
830 list.add(index, element)
831 index++
832 }
833
834 override fun set(element: T) {
835 list[index] = element
836 }
837 }
838
839 /** [MutableList] implementation for a [MutableVector], used in [asMutableList]. */
840 private class MutableVectorList<T>(private val vector: MutableVector<T>) : MutableList<T> {
841 override val size: Int
842 get() = vector.size
843
844 override fun contains(element: T): Boolean = vector.contains(element)
845
846 override fun containsAll(elements: Collection<T>): Boolean = vector.containsAll(elements)
847
848 override fun get(index: Int): T {
849 checkIndex(index)
850 return vector[index]
851 }
852
853 override fun indexOf(element: T): Int = vector.indexOf(element)
854
855 override fun isEmpty(): Boolean = vector.isEmpty()
856
857 override fun iterator(): MutableIterator<T> = VectorListIterator(this, 0)
858
859 override fun lastIndexOf(element: T): Int = vector.lastIndexOf(element)
860
861 override fun add(element: T): Boolean = vector.add(element)
862
863 override fun add(index: Int, element: T) = vector.add(index, element)
864
865 override fun addAll(index: Int, elements: Collection<T>): Boolean =
866 vector.addAll(index, elements)
867
868 override fun addAll(elements: Collection<T>): Boolean = vector.addAll(elements)
869
870 override fun clear() = vector.clear()
871
872 override fun listIterator(): MutableListIterator<T> = VectorListIterator(this, 0)
873
874 override fun listIterator(index: Int): MutableListIterator<T> =
875 VectorListIterator(this, index)
876
877 override fun remove(element: T): Boolean = vector.remove(element)
878
879 override fun removeAll(elements: Collection<T>): Boolean = vector.removeAll(elements)
880
881 override fun removeAt(index: Int): T {
882 checkIndex(index)
883 return vector.removeAt(index)
884 }
885
886 override fun retainAll(elements: Collection<T>): Boolean = vector.retainAll(elements)
887
888 override fun set(index: Int, element: T): T {
889 checkIndex(index)
890 return vector.set(index, element)
891 }
892
893 override fun subList(fromIndex: Int, toIndex: Int): MutableList<T> {
894 checkSubIndex(fromIndex, toIndex)
895 return SubList(this, fromIndex, toIndex)
896 }
897 }
898
899 /**
900 * A view into an underlying [MutableList] that directly accesses the underlying [MutableList].
901 * This is important for the implementation of [List.subList]. A change to the [SubList] also
902 * changes the referenced [MutableList].
903 */
904 private class SubList<T>(
905 private val list: MutableList<T>,
906 private val start: Int,
907 private var end: Int
908 ) : MutableList<T> {
909 override val size: Int
910 get() = end - start
911
912 override fun contains(element: T): Boolean {
913 for (i in start until end) {
914 if (list[i] == element) {
915 return true
916 }
917 }
918 return false
919 }
920
921 override fun containsAll(elements: Collection<T>): Boolean {
922 elements.forEach {
923 if (!contains(it)) {
924 return false
925 }
926 }
927 return true
928 }
929
930 override fun get(index: Int): T {
931 checkIndex(index)
932 return list[index + start]
933 }
934
935 override fun indexOf(element: T): Int {
936 for (i in start until end) {
937 if (list[i] == element) {
938 return i - start
939 }
940 }
941 return -1
942 }
943
944 override fun isEmpty(): Boolean = end == start
945
946 override fun iterator(): MutableIterator<T> = VectorListIterator(this, 0)
947
948 override fun lastIndexOf(element: T): Int {
949 for (i in end - 1 downTo start) {
950 if (list[i] == element) {
951 return i - start
952 }
953 }
954 return -1
955 }
956
957 override fun add(element: T): Boolean {
958 list.add(end++, element)
959 return true
960 }
961
962 override fun add(index: Int, element: T) {
963 list.add(index + start, element)
964 end++
965 }
966
967 override fun addAll(index: Int, elements: Collection<T>): Boolean {
968 list.addAll(index + start, elements)
969 val size = elements.size
970 end += size
971 return size > 0
972 }
973
974 override fun addAll(elements: Collection<T>): Boolean {
975 list.addAll(end, elements)
976 val size = elements.size
977 end += size
978 return size > 0
979 }
980
981 override fun clear() {
982 for (i in end - 1 downTo start) {
983 list.removeAt(i)
984 }
985 end = start
986 }
987
988 override fun listIterator(): MutableListIterator<T> = VectorListIterator(this, 0)
989
990 override fun listIterator(index: Int): MutableListIterator<T> =
991 VectorListIterator(this, index)
992
993 override fun remove(element: T): Boolean {
994 for (i in start until end) {
995 if (list[i] == element) {
996 list.removeAt(i)
997 end--
998 return true
999 }
1000 }
1001 return false
1002 }
1003
1004 override fun removeAll(elements: Collection<T>): Boolean {
1005 val originalEnd = end
1006 elements.forEach { remove(it) }
1007 return originalEnd != end
1008 }
1009
1010 override fun removeAt(index: Int): T {
1011 checkIndex(index)
1012 val item = list.removeAt(index + start)
1013 end--
1014 return item
1015 }
1016
1017 override fun retainAll(elements: Collection<T>): Boolean {
1018 val originalEnd = end
1019 for (i in end - 1 downTo start) {
1020 val item = list[i]
1021 if (item !in elements) {
1022 list.removeAt(i)
1023 end--
1024 }
1025 }
1026 return originalEnd != end
1027 }
1028
1029 override fun set(index: Int, element: T): T {
1030 checkIndex(index)
1031 return list.set(index + start, element)
1032 }
1033
1034 override fun subList(fromIndex: Int, toIndex: Int): MutableList<T> {
1035 checkSubIndex(fromIndex, toIndex)
1036 return SubList(this, fromIndex, toIndex)
1037 }
1038 }
1039 }
1040
checkIndexnull1041 internal fun List<*>.checkIndex(index: Int) {
1042 val size = size
1043 if (index < 0 || index >= size) {
1044 throwListIndexOutOfBoundsException(index, size)
1045 }
1046 }
1047
throwListIndexOutOfBoundsExceptionnull1048 private fun throwListIndexOutOfBoundsException(index: Int, size: Int) {
1049 throw IndexOutOfBoundsException("Index $index is out of bounds. The list has $size elements.")
1050 }
1051
checkSubIndexnull1052 internal fun List<*>.checkSubIndex(fromIndex: Int, toIndex: Int) {
1053 if (fromIndex > toIndex) {
1054 throwReversedIndicesException(fromIndex, toIndex)
1055 }
1056 if (fromIndex < 0) {
1057 throwNegativeIndexException(fromIndex)
1058 }
1059 if (toIndex > size) {
1060 throwOutOfRangeException(toIndex, size)
1061 }
1062 }
1063
throwOutOfRangeExceptionnull1064 private fun throwOutOfRangeException(toIndex: Int, size: Int) {
1065 throw IndexOutOfBoundsException("toIndex ($toIndex) is more than than the list size ($size)")
1066 }
1067
throwNegativeIndexExceptionnull1068 private fun throwNegativeIndexException(fromIndex: Int) {
1069 throw IndexOutOfBoundsException("fromIndex ($fromIndex) is less than 0.")
1070 }
1071
throwReversedIndicesExceptionnull1072 private fun throwReversedIndicesException(fromIndex: Int, toIndex: Int) {
1073 throw IllegalArgumentException(
1074 "Indices are out of order. fromIndex ($fromIndex) is greater than toIndex ($toIndex)."
1075 )
1076 }
1077
1078 /**
1079 * Create a [MutableVector] with a given initial [capacity].
1080 *
1081 * @see MutableVector.ensureCapacity
1082 */
MutableVectornull1083 inline fun <reified T> MutableVector(capacity: Int = 16) =
1084 MutableVector(arrayOfNulls<T>(capacity), 0)
1085
1086 /**
1087 * Create a [MutableVector] with a given [size], initializing each element using the [init]
1088 * function.
1089 *
1090 * [init] is called for each element in the [MutableVector], starting from the first one and should
1091 * return the value to be assigned to the element at its given index.
1092 */
1093 @Suppress("LEAKED_IN_PLACE_LAMBDA")
1094 @OptIn(ExperimentalContracts::class)
1095 inline fun <reified T> MutableVector(size: Int, noinline init: (Int) -> T): MutableVector<T> {
1096 contract { callsInPlace(init) }
1097 val arr = Array(size, init)
1098 return MutableVector(arr as Array<T?>, size)
1099 }
1100
1101 /** Creates an empty [MutableVector] with a [capacity][MutableVector.ensureCapacity] of 16. */
mutableVectorOfnull1102 inline fun <reified T> mutableVectorOf() = MutableVector<T>()
1103
1104 /**
1105 * Creates a [MutableVector] with the given values. This will use the passed vararg [elements]
1106 * storage.
1107 */
1108 inline fun <reified T> mutableVectorOf(vararg elements: T): MutableVector<T> {
1109 return MutableVector(elements as Array<T?>, elements.size)
1110 }
1111