1 /* 2 * Copyright 2016-2019 JetBrains s.r.o. 3 * Use of this source code is governed by the Apache 2.0 License that can be found in the LICENSE.txt file. 4 */ 5 6 package androidx.compose.runtime.external.kotlinx.collections.immutable 7 8 import androidx.compose.runtime.external.kotlinx.collections.immutable.internal.ListImplementation 9 10 /** 11 * A generic immutable ordered collection of elements. Methods in this interface support only read-only access to the immutable list. 12 * 13 * Modification operations are supported through the [PersistentList] interface. 14 * 15 * Implementors of this interface take responsibility to be immutable. 16 * Once constructed they must contain the same elements in the same order. 17 * 18 * @param E the type of elements contained in the list. The immutable list is covariant on its element type. 19 */ 20 internal interface ImmutableList<out E> : List<E>, ImmutableCollection<E> { 21 22 /** 23 * Returns a view of the portion of this list between the specified [fromIndex] (inclusive) and [toIndex] (exclusive). 24 * 25 * The returned list is backed by this list. 26 * 27 * @throws IndexOutOfBoundsException if [fromIndex] is less than zero or [toIndex] is greater than the size of this list. 28 * @throws IllegalArgumentException if [fromIndex] is greater than [toIndex]. 29 */ subListnull30 override fun subList(fromIndex: Int, toIndex: Int): ImmutableList<E> = SubList(this, fromIndex, toIndex) 31 32 private class SubList<E>(private val source: ImmutableList<E>, private val fromIndex: Int, private val toIndex: Int) : ImmutableList<E>, AbstractList<E>() { 33 private var _size: Int = 0 34 35 init { 36 ListImplementation.checkRangeIndexes(fromIndex, toIndex, source.size) 37 this._size = toIndex - fromIndex 38 } 39 40 override fun get(index: Int): E { 41 ListImplementation.checkElementIndex(index, _size) 42 43 return source[fromIndex + index] 44 } 45 46 override val size: Int get() = _size 47 48 override fun subList(fromIndex: Int, toIndex: Int): ImmutableList<E> { 49 ListImplementation.checkRangeIndexes(fromIndex, toIndex, this._size) 50 return SubList(source, this.fromIndex + fromIndex, this.fromIndex + toIndex) 51 } 52 } 53 } 54 55 /** 56 * A generic persistent ordered collection of elements that supports adding and removing elements. 57 * 58 * Modification operations return new instances of the persistent list with the modification applied. 59 * 60 * @param E the type of elements contained in the list. The persistent list is covariant on its element type. 61 */ 62 internal interface PersistentList<out E> : ImmutableList<E>, PersistentCollection<E> { 63 /** 64 * Returns a new persistent list with the specified [element] appended. 65 */ addnull66 override fun add(element: @UnsafeVariance E): PersistentList<E> 67 68 /** 69 * Returns the result of appending all elements of the specified [elements] collection to this list. 70 * 71 * The elements are appended in the order they appear in the specified collection. 72 * 73 * @return a new persistent list with elements of the specified [elements] collection appended; 74 * or this instance if the specified collection is empty. 75 */ 76 override fun addAll(elements: Collection<@UnsafeVariance E>): PersistentList<E> // = super<ImmutableCollection>.addAll(elements) as ImmutableList 77 78 /** 79 * Returns the result of removing the first appearance of the specified [element] from this list. 80 * 81 * @return a new persistent list with the first appearance of the specified [element] removed; 82 * or this instance if there is no such element in this list. 83 */ 84 override fun remove(element: @UnsafeVariance E): PersistentList<E> 85 86 /** 87 * Returns the result of removing all elements in this list that are also 88 * contained in the specified [elements] collection. 89 * 90 * @return a new persistent list with elements in this list that are also 91 * contained in the specified [elements] collection removed; 92 * or this instance if no modifications were made in the result of this operation. 93 */ 94 override fun removeAll(elements: Collection<@UnsafeVariance E>): PersistentList<E> 95 96 /** 97 * Returns the result of removing all elements in this list that match the specified [predicate]. 98 * 99 * @return a new persistent list with elements matching the specified [predicate] removed; 100 * or this instance if no elements match the predicate. 101 */ 102 override fun removeAll(predicate: (E) -> Boolean): PersistentList<E> 103 104 /** 105 * Returns all elements in this list that are also 106 * contained in the specified [elements] collection. 107 * 108 * @return a new persistent list with elements in this list that are also 109 * contained in the specified [elements] collection; 110 * or this instance if no modifications were made in the result of this operation. 111 */ 112 override fun retainAll(elements: Collection<@UnsafeVariance E>): PersistentList<E> 113 114 /** 115 * Returns an empty persistent list. 116 */ 117 override fun clear(): PersistentList<E> 118 119 120 /** 121 * Returns the result of inserting the specified [c] collection at the specified [index]. 122 * 123 * @return a new persistent list with the specified [c] collection inserted at the specified [index]; 124 * or this instance if the specified collection is empty. 125 * 126 * @throws IndexOutOfBoundsException if [index] is out of bounds of this list. 127 */ 128 fun addAll(index: Int, c: Collection<@UnsafeVariance E>): PersistentList<E> // = builder().apply { addAll(index, c.toList()) }.build() 129 130 /** 131 * Returns a new persistent list with the element at the specified [index] replaced with the specified [element]. 132 * 133 * @throws IndexOutOfBoundsException if [index] is out of bounds of this list. 134 */ 135 fun set(index: Int, element: @UnsafeVariance E): PersistentList<E> 136 137 /** 138 * Returns a new persistent list with the specified [element] inserted at the specified [index]. 139 * 140 * @throws IndexOutOfBoundsException if [index] is out of bounds of this list. 141 */ 142 fun add(index: Int, element: @UnsafeVariance E): PersistentList<E> 143 144 /** 145 * Returns a new persistent list with the element at the specified [index] removed. 146 * 147 * @throws IndexOutOfBoundsException if [index] is out of bounds of this list. 148 */ 149 fun removeAt(index: Int): PersistentList<E> 150 151 /** 152 * A generic builder of the persistent list. Builder exposes its modification operations through the [MutableList] interface. 153 * 154 * Builders are reusable, that is [build] method can be called multiple times with modifications between these calls. 155 * However, modifications applied do not affect previously built persistent list instances. 156 * 157 * Builder is backed by the same underlying data structure as the persistent list it was created from. 158 * Thus, [builder] and [build] methods take constant time consisting of passing the backing storage to the 159 * new builder and persistent list instances, respectively. 160 * 161 * The builder tracks which nodes in the structure are shared with the persistent list, 162 * and which are owned by it exclusively. It owns the nodes it copied during modification 163 * operations and avoids copying them on subsequent modifications. 164 * 165 * When [build] is called the builder forgets about all owned nodes it had created. 166 */ 167 interface Builder<E>: MutableList<E>, PersistentCollection.Builder<E> { 168 override fun build(): PersistentList<E> 169 } 170 buildernull171 override fun builder(): Builder<@UnsafeVariance E> 172 }