BloderComparable.kt

interface BloderComparable<T> {
    fun customCompareTo(b: T) : Int
}

// O(1)
fun <T : BloderComparable<T>> List<T>.firstComparableIsEqualsTo(item: T) : Boolean = this[0].customCompareTo(item) == 0

// O(n)
fun <T : BloderComparable<T>> List<T>.containsComparable(item: T) : Boolean = this.firstOrNull {
    it.customCompareTo(item) == 0
} != null

// O(n^2)
fun <T : BloderComparable<T>> List<T>.sorted() : List<T> = sortWith { x, y -> x.customCompareTo(y) == 1}

// O(n^2)
fun <T : BloderComparable<T>> List<T>.sortedDescending() : List<T> = this.sortWith { x, y -> x.customCompareTo(y) == - 1}

// O(n^2)
private fun <T : BloderComparable<T>> List<T>.sortWith(successComparation: (T, T) -> Boolean) : List<T> {
    return toMutableList().apply {
        for(x in 0 until this.size) {
            for(y in x + 1 until this.size) {
                if(successComparation(this[x], this[y])) this.swap(x, y)
            }
        }
    }
}

// O(log n)
fun <T : BloderComparable<T>> List<T>.binarySearch(item: T) : Boolean {
    if (this.isEmpty()) return false
    val midIndex = this.size / 2
    val midItem = this[midIndex]
    return when {
        item.customCompareTo(midItem) == 0 -> true
        item.customCompareTo(midItem) == -1 -> this.subList(0, midIndex).binarySearch(item)
        else -> this.subList(midIndex + 1, this.size).binarySearch(item)
    }
}

// O(log n * n^2)
fun <T: BloderComparable<T>> List<T>.mergeSort() : List<T> {
    if (this.size <= 1) return this
    val midIndex = this.size / 2
    val leftList = this.subList(0, midIndex).mergeSort()
    val rightList = this.subList(midIndex, this.size).mergeSort()
    return leftList.plus(rightList).sorted()
}

// O(n)
fun <T> MutableList<T>.swap(index1: Int, index2: Int) {
    val tmp = this[index1]
    this[index1] = this[index2]
    this[index2] = tmp
}

// O(n + nk)
fun <T : BloderComparable<T>, K> List<T>.groupedBy(keySelector: T.() -> K) : List<K> {
    return mutableMapOf<K, Int>().apply {
        for (x in 0 until this@groupedBy.size) {
            val key = this@groupedBy[x].keySelector()
            put(key, getOrDefault(key, 0) + 1)
        }
    }.asList()
}

// O(nk)
private fun <K> MutableMap<K, Int>.asList() : List<K> {
    return mutableListOf<K>().apply {
        this@asList.forEach { key, count ->
            for(i in 1..count) add(key)
        }
    }
}