package ru.brainsofter.lernkotlin

internal class ArrayIns(max: Int) {
    private val theArray: LongArray
    private var nElems: Int = 0

    init {
        theArray = LongArray(max)
        nElems = 0
    }

    fun insert(value: Long) {
        theArray[nElems] = value
        nElems++
    }

    fun display(){
        print("A=")
        for (j in 0..nElems - 1) print(theArray[j].toString() + " ")
        println("")
    }

    fun quickSort() {
        recQuickSort(0, nElems - 1)
    }

    fun recQuickSort(left: Int, right: Int) {
        val size = right-left+1
        if(size <= 3) manualSort(left, right)
        else{
            val median = medianOf3(left,right)
            val partition = partitionIt(left,right,median)
            recQuickSort(left, partition-1)
            recQuickSort(partition+1, right)
        }
    }

    fun partitionIt(left: Int, right: Int, pivot: Long): Int {
        var leftPtr = left
        var rightPtr = right - 1
        while (true) {
            while (theArray[++leftPtr] < pivot){}
            while (theArray[--rightPtr] > pivot){}
            if (leftPtr >= rightPtr) break
            else swap(leftPtr, rightPtr)
        }
        swap(leftPtr, right)
        return leftPtr
    }

    fun medianOf3(left: Int, right: Int):Long{
        val center = (left+right)/2
        if (theArray[left] > theArray[center]) swap(left,center)
        if (theArray[left] > theArray[right]) swap(left,right)
        if (theArray[center] > theArray[right]) swap(center,right)
        swap(center,right-1)
        return theArray[right-1]
    }

    fun manualSort(left: Int,right: Int){
        val size = right-left+1
        if (size <= 1) return
        if (size == 2){
            if (theArray[left] > theArray[right]) swap(left,right)
            return
        }else{
            if (theArray[left] > theArray[right-1]) swap(left,right-1)
            if (theArray[left] > theArray[right]) swap(left, right)
            if (theArray[right-1] > theArray[right]) swap(right-1,right)
        }
    }

    fun swap(dex1: Int, dex2: Int){
        val temp = theArray[dex1]
        theArray[dex1] = theArray[dex2]
        theArray[dex2] = temp
    }
}

internal object QuickSort1App {
    @JvmStatic fun main(args: Array<String>) {
        val maxSize = 2
        val arr: ArrayIns = ArrayIns(2)
        for (j in 0..maxSize - 1) arr.insert((java.lang.Math.random() * 99).toInt().toLong())

        arr.display()
        arr.quickSort()
        arr.display()

        //TODO Решить вопрос с повторяющимися элементами
    }
}