class SortedList<T>(
        val idSupplierFunction: (element: T) -> Long,
        val isDescendingOrder: Boolean = true
) {
    val innerList = mutableListOf<T>()

    fun size(): Int {
        return innerList.size
    }

    fun clear() {
        innerList.clear()
    }

    operator fun get(index: Int): T {
        return innerList[index]
    }

    private fun getIndex(index: Int, elementId: Long): Int {
        val currentElementId = idSupplierFunction(innerList[index])
        val elementToLeft = innerList.getOrNull(index - 1)
        val elementToRight = innerList.getOrNull(index + 1)

        if (elementToLeft == null && elementToRight == null) {
            val insertToRight = elementId > currentElementId
            return if (insertToRight) {
                index + 1
            } else {
                0
            }
        }

        if (elementToLeft != null && elementToRight == null) {
            val elementToLeftId = idSupplierFunction(elementToLeft)
            if (elementId > currentElementId) {
                if (elementId > elementToLeftId) {
                    return index + 1
                }
            } else {
                return index
            }
        }

        if (elementToLeft == null && elementToRight != null) {
            val elementToRightId = idSupplierFunction(elementToRight)
            if (elementId < currentElementId) {
                return index
            } else {
                if (elementId < elementToRightId) {
                    return index + 1
                }
            }
        }

        if (elementToLeft != null && elementToRight != null) {
            val elementToLeftId = idSupplierFunction(elementToLeft)
            val elementToRightId = idSupplierFunction(elementToRight)

            if (elementId > currentElementId) {
                if (elementId < elementToRightId) {
                    return index + 1
                }
            } else if (elementId < currentElementId) {
                if (elementId > elementToLeftId) {
                    return index
                }
            }
        }

        return -1
    }

    private fun getIndexForNewElement(elementId: Long, indexLow: Int, indexHigh: Int): Int {
        val index = (indexLow + indexHigh) / 2
        if (index < 0 || index > innerList.size) {
            throw IllegalStateException("Wut?")
        }

        val newIndex = getIndex(index, elementId)
        if (newIndex != -1) {
            return newIndex
        }

        return if (elementId > idSupplierFunction(innerList[index])) {
            getIndexForNewElement(elementId, index + 1, indexHigh)
        } else if (elementId < idSupplierFunction(innerList[index])) {
            getIndexForNewElement(elementId, indexLow, index - 1)
        } else {
            if (isDescendingOrder) {
                index
            } else {
                index + 1
            }
        }
    }

    fun add(element: T): Int {
        val elementId = idSupplierFunction(element)

        if (innerList.isEmpty()) {
            innerList.add(element)
            return 0
        }

        val index = getIndexForNewElement(elementId, 0, innerList.lastIndex)
        innerList.add(index, element)

        return index
    }

    fun remove(index: Int): Boolean {
        return true
    }
}