Created
October 8, 2019 15:09
-
-
Save naoppy/b1aa81a3816d50a62417d0101178f6d0 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
package algorithms.search | |
/** | |
* elementをキーとして、キー以上の要素の中で最も小さい位置のインデックスを返す。 | |
* 検索範囲は[fromIndex, toIndex) | |
* | |
* @param fromIndex この位置を含む範囲 | |
* @param toIndex この位置を含まない範囲 | |
* @return 0-indexedなインデックス | |
*/ | |
fun <T : Comparable<T>> List<T>.lowerBound( | |
element: T, | |
fromIndex: Int = 0, | |
toIndex: Int = size | |
): Int { | |
rangeCheck(size, fromIndex, toIndex) | |
var low = fromIndex - 1 | |
var high = toIndex | |
while (high - low > 1) { | |
val mid = low + (high - low) / 2 | |
val midVal = get(mid) | |
if (midVal < element) low = mid | |
else high = mid | |
} | |
return high | |
} | |
/** | |
* elementをキーとして、キー以上の要素の中で最も小さい位置のインデックスを返す。 | |
* 検索範囲は[fromIndex, toIndex) | |
* | |
* @param fromIndex この位置を含む範囲 | |
* @param toIndex この位置を含まない範囲 | |
* @return 0-indexedなインデックス | |
*/ | |
fun <T> List<T>.lowerBound( | |
element: T, | |
comparator: Comparator<in T>, | |
fromIndex: Int = 0, | |
toIndex: Int = size | |
): Int { | |
rangeCheck(size, fromIndex, toIndex) | |
var low = fromIndex - 1 | |
var high = toIndex | |
while (high - low > 1) { | |
val mid = low + (high - low) / 2 | |
val midVal = get(mid) | |
val cmp = comparator.compare(midVal, element) | |
if (cmp < 0) low = mid | |
else high = mid | |
} | |
return high | |
} | |
/** | |
* elementをキーとして、キーより大きい要素の中で最も小さい位置のインデックスを返す。 | |
* 検索範囲は[fromIndex, toIndex) | |
* | |
* @param fromIndex この位置を含む範囲 | |
* @param toIndex この位置を含まない範囲 | |
* @return 0-indexedなインデックス | |
*/ | |
fun <T : Comparable<T>> List<T>.upperBound( | |
element: T, | |
fromIndex: Int = 0, | |
toIndex: Int = size | |
): Int { | |
rangeCheck(size, fromIndex, toIndex) | |
var low = fromIndex - 1 | |
var high = toIndex | |
while (high - low > 1) { | |
val mid = low + (high - low) / 2 | |
val midVal = get(mid) | |
if (midVal <= element) low = mid | |
else high = mid | |
} | |
return high | |
} | |
/** | |
* elementをキーとして、キーより大きい要素の中で最も小さい位置のインデックスを返す。 | |
* 検索範囲は[fromIndex, toIndex) | |
* | |
* @param fromIndex この位置を含む範囲 | |
* @param toIndex この位置を含まない範囲 | |
* @return 0-indexedなインデックス | |
*/ | |
fun <T> List<T>.upperBound( | |
element: T, | |
comparator: Comparator<in T>, | |
fromIndex: Int = 0, | |
toIndex: Int = size | |
): Int { | |
rangeCheck(size, fromIndex, toIndex) | |
var low = fromIndex - 1 | |
var high = toIndex | |
while (high - low > 1) { | |
val mid = low + (high - low) / 2 | |
val midVal = get(mid) | |
val cmp = comparator.compare(midVal, element) | |
if (cmp <= 0) low = mid | |
else high = mid | |
} | |
return high | |
} | |
/** | |
* 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).") | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment