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
|
/*
* Copyright 2010-2018 JetBrains s.r.o. Use of this source code is governed by the Apache 2.0 license
* that can be found in the license/LICENSE.txt file.
*/
/*
* Based on GWT AbstractList
* Copyright 2007 Google Inc.
*/
package kotlin.collections
/**
* Provides a skeletal implementation of the read-only [List] interface.
*
* This class is intended to help implementing read-only lists so it doesn't support concurrent modification tracking.
*
* @param E the type of elements contained in the list. The list is covariant on its element type.
*/
@SinceKotlin("1.1")
public abstract class AbstractList<out E> protected constructor() : AbstractCollection<E>(), List<E> {
abstract override val size: Int
abstract override fun get(index: Int): E
override fun toArray(): Array<Any?> = super<AbstractCollection>.toArray()
override fun <T : Any?> toArray(p0: Array<T>): Array<T> = super<AbstractCollection>.toArray<T>(p0)
override fun iterator(): Iterator<E> = IteratorImpl()
override fun indexOf(element: @UnsafeVariance E): Int = indexOfFirst { it == element }
override fun lastIndexOf(element: @UnsafeVariance E): Int = indexOfLast { it == element }
override fun listIterator(): ListIterator<E> = ListIteratorImpl(0)
override fun listIterator(index: Int): ListIterator<E> = ListIteratorImpl(index)
override fun subList(fromIndex: Int, toIndex: Int): List<E> = SubList(this, fromIndex, toIndex)
private class SubList<out E>(private val list: AbstractList<E>, private val fromIndex: Int, toIndex: Int) : AbstractList<E>(), RandomAccess {
private var _size: Int = 0
init {
checkRangeIndexes(fromIndex, toIndex, list.size)
this._size = toIndex - fromIndex
}
override fun get(index: Int): E {
checkElementIndex(index, _size)
return list[fromIndex + index]
}
override val size: Int get() = _size
}
/**
* Compares this list with other list instance with the ordered structural equality.
*
* @return true, if [other] instance is a [List] of the same size, which contains the same elements in the same order.
*/
override fun equals(other: Any?): Boolean {
if (other === this) return true
if (other !is List<*>) return false
return orderedEquals(this, other)
}
/**
* Returns the hash code value for this list.
*/
override fun hashCode(): Int = orderedHashCode(this)
private open inner class IteratorImpl : Iterator<E> {
/** the index of the item that will be returned on the next call to [next]`()` */
protected var index = 0
override fun hasNext(): Boolean = index < size
override fun next(): E {
if (!hasNext()) throw NoSuchElementException()
return get(index++)
}
}
/**
* Implementation of [ListIterator] for abstract lists.
*/
private open inner class ListIteratorImpl(index: Int) : IteratorImpl(), ListIterator<E> {
init {
checkPositionIndex(index, this@AbstractList.size)
this.index = index
}
override fun hasPrevious(): Boolean = index > 0
override fun nextIndex(): Int = index
override fun previous(): E {
if (!hasPrevious()) throw NoSuchElementException()
return get(--index)
}
override fun previousIndex(): Int = index - 1
}
internal companion object {
internal fun checkElementIndex(index: Int, size: Int) {
if (index < 0 || index >= size) {
throw IndexOutOfBoundsException("index: $index, size: $size")
}
}
internal fun checkPositionIndex(index: Int, size: Int) {
if (index < 0 || index > size) {
throw IndexOutOfBoundsException("index: $index, size: $size")
}
}
internal fun checkRangeIndexes(fromIndex: Int, toIndex: Int, size: Int) {
if (fromIndex < 0 || toIndex > size) {
throw IndexOutOfBoundsException("fromIndex: $fromIndex, toIndex: $toIndex, size: $size")
}
if (fromIndex > toIndex) {
throw IllegalArgumentException("fromIndex: $fromIndex > toIndex: $toIndex")
}
}
internal fun orderedHashCode(c: Collection<*>): Int {
var hashCode = 1
for (e in c) {
hashCode = 31 * hashCode + (e?.hashCode() ?: 0)
}
return hashCode
}
internal fun orderedEquals(c: Collection<*>, other: Collection<*>): Boolean {
if (c.size != other.size) return false
val otherIterator = other.iterator()
for (elem in c) {
val elemOther = otherIterator.next()
if (elem != elemOther) {
return false
}
}
return true
}
}
}
|
