/
Collections.kt
392 lines (338 loc) · 16 KB
/
Collections.kt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
/*
* Copyright 2010-2017 JetBrains s.r.o.
*
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
* You may obtain a copy of the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*/
@file:kotlin.jvm.JvmMultifileClass
@file:kotlin.jvm.JvmName("CollectionsKt")
package kotlin.collections
import kotlin.comparisons.compareValues
internal object EmptyIterator : ListIterator<Nothing> {
override fun hasNext(): Boolean = false
override fun hasPrevious(): Boolean = false
override fun nextIndex(): Int = 0
override fun previousIndex(): Int = -1
override fun next(): Nothing = throw NoSuchElementException()
override fun previous(): Nothing = throw NoSuchElementException()
}
internal object EmptyList : List<Nothing>, Serializable, RandomAccess {
private const val serialVersionUID: Long = -7390468764508069838L
override fun equals(other: Any?): Boolean = other is List<*> && other.isEmpty()
override fun hashCode(): Int = 1
override fun toString(): String = "[]"
override val size: Int get() = 0
override fun isEmpty(): Boolean = true
override fun contains(element: Nothing): Boolean = false
override fun containsAll(elements: Collection<Nothing>): Boolean = elements.isEmpty()
override fun get(index: Int): Nothing = throw IndexOutOfBoundsException("Empty list doesn't contain element at index $index.")
override fun indexOf(element: Nothing): Int = -1
override fun lastIndexOf(element: Nothing): Int = -1
override fun iterator(): Iterator<Nothing> = EmptyIterator
override fun listIterator(): ListIterator<Nothing> = EmptyIterator
override fun listIterator(index: Int): ListIterator<Nothing> {
if (index != 0) throw IndexOutOfBoundsException("Index: $index")
return EmptyIterator
}
override fun subList(fromIndex: Int, toIndex: Int): List<Nothing> {
if (fromIndex == 0 && toIndex == 0) return this
throw IndexOutOfBoundsException("fromIndex: $fromIndex, toIndex: $toIndex")
}
private fun readResolve(): Any = EmptyList
}
internal fun <T> Array<out T>.asCollection(): Collection<T> = ArrayAsCollection(this, isVarargs = false)
private class ArrayAsCollection<T>(val values: Array<out T>, val isVarargs: Boolean): Collection<T> {
override val size: Int get() = values.size
override fun isEmpty(): Boolean = values.isEmpty()
override fun contains(element: T): Boolean = values.contains(element)
override fun containsAll(elements: Collection<T>): Boolean = elements.all { contains(it) }
override fun iterator(): Iterator<T> = values.iterator()
// override hidden toArray implementation to prevent copying of values array
public fun toArray(): Array<out Any?> = values.copyToArrayOfAny(isVarargs)
}
/**
* Returns an empty read-only list. The returned list is serializable (JVM).
* @sample samples.collections.Collections.Lists.emptyReadOnlyList
*/
public fun <T> emptyList(): List<T> = EmptyList
/**
* Returns a new read-only list of given elements. The returned list is serializable (JVM).
* @sample samples.collections.Collections.Lists.readOnlyList
*/
public fun <T> listOf(vararg elements: T): List<T> = if (elements.size > 0) elements.asList() else emptyList()
/**
* Returns an empty read-only list. The returned list is serializable (JVM).
* @sample samples.collections.Collections.Lists.emptyReadOnlyList
*/
@kotlin.internal.InlineOnly
public inline fun <T> listOf(): List<T> = emptyList()
/**
* Returns an immutable list containing only the specified object [element].
* The returned list is serializable.
* @sample samples.collections.Collections.Lists.singletonReadOnlyList
*/
@JvmVersion
public fun <T> listOf(element: T): List<T> = java.util.Collections.singletonList(element)
/**
* Returns an empty new [MutableList].
* @sample samples.collections.Collections.Lists.emptyMutableList
*/
@SinceKotlin("1.1")
@kotlin.internal.InlineOnly
public inline fun <T> mutableListOf(): MutableList<T> = ArrayList()
/**
* Returns an empty new [ArrayList].
* @sample samples.collections.Collections.Lists.emptyArrayList
*/
@SinceKotlin("1.1")
@kotlin.internal.InlineOnly
public inline fun <T> arrayListOf(): ArrayList<T> = ArrayList()
/**
* Returns a new [MutableList] with the given elements.
* @sample samples.collections.Collections.Lists.mutableList
*/
public fun <T> mutableListOf(vararg elements: T): MutableList<T>
= if (elements.size == 0) ArrayList() else ArrayList(ArrayAsCollection(elements, isVarargs = true))
/**
* Returns a new [ArrayList] with the given elements.
* @sample samples.collections.Collections.Lists.arrayList
*/
public fun <T> arrayListOf(vararg elements: T): ArrayList<T>
= if (elements.size == 0) ArrayList() else ArrayList(ArrayAsCollection(elements, isVarargs = true))
/**
* Returns a new read-only list either of single given element, if it is not null, or empty list if the element is null. The returned list is serializable (JVM).
* @sample samples.collections.Collections.Lists.listOfNotNull
*/
public fun <T : Any> listOfNotNull(element: T?): List<T> = if (element != null) listOf(element) else emptyList()
/**
* Returns a new read-only list only of those given elements, that are not null. The returned list is serializable (JVM).
* @sample samples.collections.Collections.Lists.listOfNotNull
*/
public fun <T : Any> listOfNotNull(vararg elements: T?): List<T> = elements.filterNotNull()
/**
* Creates a new read-only list with the specified [size], where each element is calculated by calling the specified
* [init] function. The [init] function returns a list element given its index.
* @sample samples.collections.Collections.Lists.readOnlyListFromInitializer
*/
@SinceKotlin("1.1")
@kotlin.internal.InlineOnly
public inline fun <T> List(size: Int, init: (index: Int) -> T): List<T> = MutableList(size, init)
/**
* Creates a new mutable list with the specified [size], where each element is calculated by calling the specified
* [init] function. The [init] function returns a list element given its index.
* @sample samples.collections.Collections.Lists.mutableListFromInitializer
*/
@SinceKotlin("1.1")
@kotlin.internal.InlineOnly
public inline fun <T> MutableList(size: Int, init: (index: Int) -> T): MutableList<T> {
val list = ArrayList<T>(size)
repeat(size) { index -> list.add(init(index)) }
return list
}
/**
* Returns an [IntRange] of the valid indices for this collection.
* @sample samples.collections.Collections.Collections.indicesOfCollection
*/
public val Collection<*>.indices: IntRange
get() = 0..size - 1
/**
* Returns the index of the last item in the list or -1 if the list is empty.
*
* @sample samples.collections.Collections.Lists.lastIndexOfList
*/
public val <T> List<T>.lastIndex: Int
get() = this.size - 1
/**
* Returns `true` if the collection is not empty.
* @sample samples.collections.Collections.Collections.collectionIsNotEmpty
*/
@kotlin.internal.InlineOnly
public inline fun <T> Collection<T>.isNotEmpty(): Boolean = !isEmpty()
/**
* Returns this Collection if it's not `null` and the empty list otherwise.
* @sample samples.collections.Collections.Collections.collectionOrEmpty
*/
@kotlin.internal.InlineOnly
public inline fun <T> Collection<T>?.orEmpty(): Collection<T> = this ?: emptyList()
/**
* Returns this List if it's not `null` and the empty list otherwise.
* @sample samples.collections.Collections.Lists.listOrEmpty
*/
@kotlin.internal.InlineOnly
public inline fun <T> List<T>?.orEmpty(): List<T> = this ?: emptyList()
/**
* Returns a list containing the elements returned by this enumeration
* in the order they are returned by the enumeration.
* @sample samples.collections.Collections.Lists.listFromEnumeration
*/
@JvmVersion
@kotlin.internal.InlineOnly
public inline fun <T> java.util.Enumeration<T>.toList(): List<T> = java.util.Collections.list(this)
/**
* Checks if all elements in the specified collection are contained in this collection.
*
* Allows to overcome type-safety restriction of `containsAll` that requires to pass a collection of type `Collection<E>`.
* @sample samples.collections.Collections.Collections.collectionContainsAll
*/
@Suppress("EXTENSION_SHADOWED_BY_MEMBER") // false warning, extension takes precedence in some cases
@kotlin.internal.InlineOnly
public inline fun <@kotlin.internal.OnlyInputTypes T> Collection<T>.containsAll(elements: Collection<T>): Boolean = this.containsAll(elements)
internal fun <T> List<T>.optimizeReadOnlyList() = when (size) {
0 -> emptyList()
1 -> listOf(this[0])
else -> this
}
@JvmVersion
@kotlin.internal.InlineOnly
internal inline fun copyToArrayImpl(collection: Collection<*>): Array<Any?> =
kotlin.jvm.internal.collectionToArray(collection)
@JvmVersion
@kotlin.internal.InlineOnly
internal inline fun <T> copyToArrayImpl(collection: Collection<*>, array: Array<T>): Array<T> =
kotlin.jvm.internal.collectionToArray(collection, array as Array<Any?>) as Array<T>
// copies typed varargs array to array of objects
@JvmVersion
private fun <T> Array<out T>.copyToArrayOfAny(isVarargs: Boolean): Array<Any?> =
if (isVarargs && this.javaClass == Array<Any?>::class.java)
// if the array came from varargs and already is array of Any, copying isn't required
@Suppress("UNCHECKED_CAST") (this as Array<Any?>)
else
java.util.Arrays.copyOf(this, this.size, Array<Any?>::class.java)
/**
* Searches this list or its range for the provided [element] using the binary search algorithm.
* The list is expected to be sorted into ascending order according to the Comparable natural ordering of its elements,
* otherwise the result is undefined.
*
* If the list contains multiple elements equal to the specified [element], there is no guarantee which one will be found.
*
* `null` value is considered to be less than any non-null value.
*
* @return the index of the element, if it is contained in the list within the specified range;
* otherwise, the inverted insertion point `(-insertion point - 1)`.
* The insertion point is defined as the index at which the element should be inserted,
* so that the list (or the specified subrange of list) still remains sorted.
* @sample samples.collections.Collections.Lists.binarySearchOnComparable
* @sample samples.collections.Collections.Lists.binarySearchWithBoundaries
*/
public fun <T: Comparable<T>> List<T?>.binarySearch(element: T?, fromIndex: Int = 0, toIndex: Int = size): Int {
rangeCheck(size, fromIndex, toIndex)
var low = fromIndex
var high = toIndex - 1
while (low <= high) {
val mid = (low + high).ushr(1) // safe from overflows
val midVal = get(mid)
val cmp = compareValues(midVal, element)
if (cmp < 0)
low = mid + 1
else if (cmp > 0)
high = mid - 1
else
return mid // key found
}
return -(low + 1) // key not found
}
/**
* Searches this list or its range for the provided [element] using the binary search algorithm.
* The list is expected to be sorted into ascending order according to the specified [comparator],
* otherwise the result is undefined.
*
* If the list contains multiple elements equal to the specified [element], there is no guarantee which one will be found.
*
* `null` value is considered to be less than any non-null value.
*
* @return the index of the element, if it is contained in the list within the specified range;
* otherwise, the inverted insertion point `(-insertion point - 1)`.
* The insertion point is defined as the index at which the element should be inserted,
* so that the list (or the specified subrange of list) still remains sorted according to the specified [comparator].
* @sample samples.collections.Collections.Lists.binarySearchWithComparator
*/
public fun <T> List<T>.binarySearch(element: T, comparator: Comparator<in T>, fromIndex: Int = 0, toIndex: Int = size): Int {
rangeCheck(size, fromIndex, toIndex)
var low = fromIndex
var high = toIndex - 1
while (low <= high) {
val mid = (low + high).ushr(1) // safe from overflows
val midVal = get(mid)
val cmp = comparator.compare(midVal, element)
if (cmp < 0)
low = mid + 1
else if (cmp > 0)
high = mid - 1
else
return mid // key found
}
return -(low + 1) // key not found
}
/**
* Searches this list or its range for an element having the key returned by the specified [selector] function
* equal to the provided [key] value using the binary search algorithm.
* The list is expected to be sorted into ascending order according to the Comparable natural ordering of keys of its elements.
* otherwise the result is undefined.
*
* If the list contains multiple elements with the specified [key], there is no guarantee which one will be found.
*
* `null` value is considered to be less than any non-null value.
*
* @return the index of the element with the specified [key], if it is contained in the list within the specified range;
* otherwise, the inverted insertion point `(-insertion point - 1)`.
* The insertion point is defined as the index at which the element should be inserted,
* so that the list (or the specified subrange of list) still remains sorted.
* @sample samples.collections.Collections.Lists.binarySearchByKey
*/
public inline fun <T, K : Comparable<K>> List<T>.binarySearchBy(key: K?, fromIndex: Int = 0, toIndex: Int = size, crossinline selector: (T) -> K?): Int =
binarySearch(fromIndex, toIndex) { compareValues(selector(it), key) }
// do not introduce this overload --- too rare
//public fun <T, K> List<T>.binarySearchBy(key: K, comparator: Comparator<K>, fromIndex: Int = 0, toIndex: Int = size(), selector: (T) -> K): Int =
// binarySearch(fromIndex, toIndex) { comparator.compare(selector(it), key) }
/**
* Searches this list or its range for an element for which [comparison] function returns zero using the binary search algorithm.
* The list is expected to be sorted into ascending order according to the provided [comparison],
* otherwise the result is undefined.
*
* If the list contains multiple elements for which [comparison] returns zero, there is no guarantee which one will be found.
*
* @param comparison function that compares an element of the list with the element being searched.
*
* @return the index of the found element, if it is contained in the list within the specified range;
* otherwise, the inverted insertion point `(-insertion point - 1)`.
* The insertion point is defined as the index at which the element should be inserted,
* so that the list (or the specified subrange of list) still remains sorted.
* @sample samples.collections.Collections.Lists.binarySearchWithComparisonFunction
*/
public fun <T> List<T>.binarySearch(fromIndex: Int = 0, toIndex: Int = size, comparison: (T) -> Int): Int {
rangeCheck(size, fromIndex, toIndex)
var low = fromIndex
var high = toIndex - 1
while (low <= high) {
val mid = (low + high).ushr(1) // safe from overflows
val midVal = get(mid)
val cmp = comparison(midVal)
if (cmp < 0)
low = mid + 1
else if (cmp > 0)
high = mid - 1
else
return mid // key found
}
return -(low + 1) // key not found
}
/**
* Checks that `from` and `to` are in
* the range of [0..size] and throws an appropriate exception, if they aren't.
*/
private fun rangeCheck(size: Int, fromIndex: Int, toIndex: Int) {
when {
fromIndex > toIndex -> throw IllegalArgumentException("fromIndex ($fromIndex) is greater than toIndex ($toIndex).")
fromIndex < 0 -> throw IndexOutOfBoundsException("fromIndex ($fromIndex) is less than zero.")
toIndex > size -> throw IndexOutOfBoundsException("toIndex ($toIndex) is greater than size ($size).")
}
}