[stdlib] Fix ArrayDeque.indexOf and lastIndexOf
There are two related bugs:
- KT-80390: ArrayDeque.indexOf(null) returns some index when a deque had some elements, but later was cleaned
- KT-80661: ArrayDeque.lastIndexOf returns -1 when the internal storage is full (i.e. head == internalIndex(size))
In both cases, we have to be more careful when scanning the internal storage if head == internalIndex(size).
^KT-80390 fixed
^KT-80661 fixed
Merge-request: KT-MR-23363
Merged-by: Filipp Zhinkin <filipp.zhinkin@jetbrains.com>
diff --git a/libraries/stdlib/src/kotlin/collections/ArrayDeque.kt b/libraries/stdlib/src/kotlin/collections/ArrayDeque.kt
index 4d16866..27eb6a6 100644
--- a/libraries/stdlib/src/kotlin/collections/ArrayDeque.kt
+++ b/libraries/stdlib/src/kotlin/collections/ArrayDeque.kt
@@ -1,5 +1,5 @@
/*
- * Copyright 2010-2019 JetBrains s.r.o. and Kotlin Programming Language contributors.
+ * Copyright 2010-2025 JetBrains s.r.o. and Kotlin Programming Language contributors.
* Use of this source code is governed by the Apache 2.0 license that can be found in the license/LICENSE.txt file.
*/
@@ -393,7 +393,7 @@
for (index in head until tail) {
if (element == elementData[index]) return index - head
}
- } else if (head >= tail) {
+ } else if (isNotEmpty() && head >= tail) {
for (index in head until elementData.size) {
if (element == elementData[index]) return index - head
}
@@ -412,7 +412,7 @@
for (index in tail - 1 downTo head) {
if (element == elementData[index]) return index - head
}
- } else if (head > tail) {
+ } else if (isNotEmpty() && head >= tail) {
for (index in tail - 1 downTo 0) {
if (element == elementData[index]) return index + elementData.size - head
}
diff --git a/libraries/stdlib/test/collections/ArrayDequeTest.kt b/libraries/stdlib/test/collections/ArrayDequeTest.kt
index c8c6a9a..aa2dd80 100644
--- a/libraries/stdlib/test/collections/ArrayDequeTest.kt
+++ b/libraries/stdlib/test/collections/ArrayDequeTest.kt
@@ -1,5 +1,5 @@
/*
- * Copyright 2010-2020 JetBrains s.r.o. and Kotlin Programming Language contributors.
+ * Copyright 2010-2025 JetBrains s.r.o. and Kotlin Programming Language contributors.
* Use of this source code is governed by the Apache 2.0 license that can be found in the license/LICENSE.txt file.
*/
@@ -429,6 +429,63 @@
(0..6).forEach { assertEquals(it, deque.indexOf(it - 4)) }
assertEquals(-1, deque.indexOf(100))
}
+
+ testArrayDeque { bufferSize, _, head, tail ->
+ generateArrayDeque(head, tail, bufferSize).let { deque ->
+ deque.forEachIndexed { index, element ->
+ val actualIndex = deque.indexOf(element)
+ if (actualIndex != index) {
+ assertEquals(index, actualIndex, "indexOf($element) for $deque")
+ }
+ }
+ }
+ }
+ }
+
+ @Test
+ fun indexOfNull() {
+ val deque = ArrayDeque<Int?>()
+ assertEquals(-1, deque.indexOf(null))
+ deque.addLast(42)
+ assertEquals(-1, deque.indexOf(null))
+ deque.clear()
+ assertEquals(-1, deque.indexOf(null))
+ }
+
+ @Test
+ fun lastIndexOf() {
+ // head < tail
+ generateArrayDeque(0, 7).let { deque ->
+ (0..6).forEach { assertEquals(it, deque.lastIndexOf(it)) }
+ assertEquals(-1, deque.lastIndexOf(100))
+ }
+
+ // head > tail
+ generateArrayDeque(-4, 3).let { deque ->
+ (0..6).forEach { assertEquals(it, deque.lastIndexOf(it - 4)) }
+ assertEquals(-1, deque.lastIndexOf(100))
+ }
+
+ testArrayDeque { bufferSize, _, head, tail ->
+ generateArrayDeque(head, tail, bufferSize).let { deque ->
+ deque.forEachIndexed { index, element ->
+ val actualIndex = deque.lastIndexOf(element)
+ if (actualIndex != index) {
+ assertEquals(index, actualIndex, "lastIndexOf($element) for $deque")
+ }
+ }
+ }
+ }
+ }
+
+ @Test
+ fun lastIndexOfNull() {
+ val deque = ArrayDeque<Int?>()
+ assertEquals(-1, deque.lastIndexOf(null))
+ deque.addLast(42)
+ assertEquals(-1, deque.lastIndexOf(null))
+ deque.clear()
+ assertEquals(-1, deque.lastIndexOf(null))
}
@Test
@@ -694,4 +751,4 @@
deque.internalStructure { head, _ -> assertEquals(-2, head) } // deque min capacity is 10
testContentEquals(arrayOf(-3, -2, -1, 1, 2, 3, 4, 5, 6, 7))
}
-}
\ No newline at end of file
+}
