minmax.kt

import com.google.common.truth.Truth.assertThat
import org.junit.Test
import java.lang.Integer.MAX_VALUE
import java.lang.Integer.MIN_VALUE
import java.util.*
import kotlin.system.measureTimeMillis

class MinMaxTest {
    
    fun classicMinMax(elements: IntArray): Pair<Int, Int> {

        var min = MAX_VALUE
        var max = MIN_VALUE

        elements.forEach {
            if (it < min) min = it
            if (it > max) max = it
        }
        // 2N

        return Pair(min, max)
    }

    /*
        1. Pick 2 elements(a, b), compare them. (say a > b)
        2. Update min by comparing (min, b)
        3. Update max by comparing (max, a)
     */

    fun divideAndConquer(elements: IntArray): Pair<Int, Int> {
        var min = MAX_VALUE
        var max = MIN_VALUE

        for (i in 0..elements.size-2 step 2) {
            val a = elements[i]
            val b = elements[i + 1]

            if (a > b) {
                if (b < min) min = b
                if (a > max) max = a
            } else {
                if (a < min) min = a
                if (b > max) max = b
            }
        }
        // 3N/2 comparisons
        if (elements.size % 2 != 0) { // can omit and recalculate always last element
            val lastElement = elements[elements.size - 1]
            if (lastElement < min) min = lastElement
            if (lastElement > max) max = lastElement
        }

        return Pair(min, max)
    }

    @Test
    fun classicMinMax() {
        val elements = arrayOf(1, 2, 3, 4, 5, 6, 7).toIntArray()
        val (min, max) = classicMinMax(elements)
        assertThat(min).isEqualTo(1)
        assertThat(max).isEqualTo(7)
    }

    @Test
    fun divideAndConquerMinMaxEven() {
        val elements = arrayOf(1, 2, 3, 4, 5, 6).toIntArray()
        val (min, max) = divideAndConquer(elements)
        assertThat(min).isEqualTo(1)
        assertThat(max).isEqualTo(6)
    }

    @Test
    fun divideAndConquerMinMaxOdd() {
        val elements = arrayOf(7, 6, 5, 4, 3, 2, -1).toIntArray()
        val (min, max) = divideAndConquer(elements)
        assertThat(min).isEqualTo(-1)
        assertThat(max).isEqualTo(7)
    }

    @Test
    fun timings() {

        val random = Random()

        val size = 1000

        for (i in 1000 .. 10000 step 1000 ) {

            val arraySize = size * i
            println("step is $arraySize")
            val elements = IntArray(arraySize, { _ -> random.nextInt(1_000_000) })

            val classic = measureTimeMillis { classicMinMax(elements) }
            val divideAndConquer = measureTimeMillis { divideAndConquer(elements) }

            println("classic is $classic")
            println("divideAndConquer is $divideAndConquer")

        }
    }
}