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
|
/*
* 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.
*/
package test.collections.binarySearch
import kotlin.test.*
class ListBinarySearchTest {
val values = listOf(1, 3, 7, 10, 12, 15, 22, 45)
fun notFound(index: Int) = -(index + 1)
private val comparator = compareBy<IncomparableDataItem<Int>?> { it?.value }
@Test
fun binarySearchByElement() {
val list = values
list.forEachIndexed { index, item ->
assertEquals(index, list.binarySearch(item))
assertEquals(notFound(index), list.binarySearch(item.pred()))
assertEquals(notFound(index + 1), list.binarySearch(item.succ()))
if (index > 0) {
index.let { from -> assertEquals(notFound(from), list.binarySearch(list.first(), fromIndex = from)) }
(list.size - index).let { to -> assertEquals(notFound(to), list.binarySearch(list.last(), toIndex = to)) }
}
}
}
@Test
fun binarySearchByElementNullable() {
val list = listOf(null) + values
list.forEachIndexed { index, item ->
assertEquals(index, list.binarySearch(item))
if (index > 0) {
index.let { from -> assertEquals(notFound(from), list.binarySearch(list.first(), fromIndex = from)) }
(list.size - index).let { to -> assertEquals(notFound(to), list.binarySearch(list.last(), toIndex = to)) }
}
}
}
@Test
fun binarySearchWithComparator() {
val list = values.map { IncomparableDataItem(it) }
list.forEachIndexed { index, item ->
assertEquals(index, list.binarySearch(item, comparator))
assertEquals(notFound(index), list.binarySearch(item.pred(), comparator))
assertEquals(notFound(index + 1), list.binarySearch(item.succ(), comparator))
if (index > 0) {
index.let { from -> assertEquals(notFound(from), list.binarySearch(list.first(), comparator, fromIndex = from)) }
(list.size - index).let { to -> assertEquals(notFound(to), list.binarySearch(list.last(), comparator, toIndex = to)) }
}
}
}
@Test
fun binarySearchByKey() {
val list = values.map { IncomparableDataItem(it) }
list.forEachIndexed { index, item ->
assertEquals(index, list.binarySearchBy(item.value) { it.value })
assertEquals(notFound(index), list.binarySearchBy(item.value.pred()) { it.value })
assertEquals(notFound(index + 1), list.binarySearchBy(item.value.succ()) { it.value })
if (index > 0) {
index.let { from -> assertEquals(notFound(from), list.binarySearchBy(list.first().value, fromIndex = from) { it.value }) }
(list.size - index).let { to -> assertEquals(notFound(to), list.binarySearchBy(list.last().value, toIndex = to) { it.value }) }
}
}
}
@Test
fun binarySearchByKeyWithComparator() {
val list = values.map { IncomparableDataItem(IncomparableDataItem(it)) }
list.forEachIndexed { index, item ->
assertEquals(index, list.binarySearch { comparator.compare(it.value, item.value) })
assertEquals(notFound(index), list.binarySearch { comparator.compare(it.value, item.value.pred()) })
assertEquals(notFound(index + 1), list.binarySearch { comparator.compare(it.value, item.value.succ()) })
if (index > 0) {
index.let { from ->
assertEquals(notFound(from), list.binarySearch(fromIndex = from) { comparator.compare(it.value, list.first().value) })
}
(list.size - index).let { to ->
assertEquals(notFound(to), list.binarySearch(toIndex = to) { comparator.compare(it.value, list.last().value) })
}
}
}
}
@Test
fun binarySearchByMultipleKeys() {
val list = values.flatMap { v1 -> values.map { v2 -> Pair(v1, v2) } }
list.forEachIndexed { index, item ->
assertEquals(index, list.binarySearch { compareValuesBy(it, item, { it.first }, { it.second }) })
}
}
}
private data class IncomparableDataItem<T>(public val value: T)
private fun IncomparableDataItem<Int>.pred(): IncomparableDataItem<Int> = IncomparableDataItem(value - 1)
private fun IncomparableDataItem<Int>.succ(): IncomparableDataItem<Int> = IncomparableDataItem(value + 1)
private fun Int.pred() = dec()
private fun Int.succ() = inc()
|
