package helping.saten
import java.util.*
class KDTree
// constructor
@Throws(Exception::class)
constructor(datalist:ArrayList<Datum>):Iterable<Datum> {
    internal var rootNode:KDNode
    internal var k:Int = 0
    internal var numLeaves:Int = 0
    init{
        val dataListArray = arrayOfNulls<Datum>(datalist.size())
        if (datalist.size() == 0)
        {
            throw Exception("Trying to create a KD tree with no data")
        }
        else
            this.k = datalist.get(0).x.size
        val ct = 0
        for (d in datalist)
        {
            dataListArray[ct] = datalist.get(ct)
            ct++
        }
        // Construct a KDNode that is the root node of the KDTree.
        rootNode = KDNode(dataListArray)
    }
    // KDTree methods
    fun nearestPoint(queryPoint:Datum):Datum {
        return rootNode.nearestPointInNode(queryPoint)
    }
    fun height():Int {
        return this.rootNode.height()
    }
    fun countNodes():Int {
        return this.rootNode.countNodes()
    }
    fun size():Int {
        return this.numLeaves
    }
    fun meanDepth():Double {
        val sumdepths_numLeaves = this.rootNode.sumDepths_numLeaves()
        return 1.0 * sumdepths_numLeaves[0] / sumdepths_numLeaves[1]
    }
    internal inner class KDNode @Throws(Exception::class)
    constructor(datalist:Array<Datum>) {
        var leaf:Boolean = false
        var leafDatum:Datum // only stores Datum if this is a leaf
        // the next two variables are only defined if node is not a leaf
        var splitDim:Int = 0 // the dimension we will split on
        var splitValue:Int = 0 // datum is in low if value in splitDim <= splitValue, and high if value in splitDim > splitValue
        var lowChild:KDNode
        var highChild:KDNode // the low and high child of a particular node (null if leaf)
        // You may think of them as "left" and "right" instead of "low" and "high", respectively
        var test = HashSet()
        init{
            val highTemp = ArrayList<Datum>(0)
            val lowTemp = ArrayList<Datum>(0)
            if (datalist.size == 1)
            {
                if (test.add(datalist[0]))
                {
                    this.leaf = true
                    this.leafDatum = datalist[0]
                }
                else
                {
                    this.leaf = false
                }
            }
            else if (datalist.size > 1)
            {
                this.leaf = false
                this.splitDim = getRangePos(datalist)
                val highCheck = datalist[splitDim].x[0]
                val lowCheck = datalist[splitDim].x[0]
                for (z in 1 until datalist[splitDim].x.size)
                {
                    if (datalist[splitDim].x[z] > highCheck)
                    {
                        highCheck = datalist[splitDim].x[z]
                    }
                    if (datalist[splitDim].x[z] < lowCheck)
                    {
                        lowCheck = datalist[splitDim].x[z]
                    }
                }
                splitValue = (highCheck + lowCheck) / 2
                for (y in 0 until datalist.size - 1)
                {
                    if (datalist[y] != null)
                    {
                        if (datalist[y].x[splitDim] <= splitValue)
                        {
                            highTemp.ensureCapacity(highTemp.size() + 1)
                            highTemp.add(datalist[y])
                        }
                        else
                        {
                            lowTemp.ensureCapacity(lowTemp.size() + 1)
                            lowTemp.add(datalist[y])
                        }
                    }
                }
                val high = highTemp.toArray<Datum>(arrayOfNulls<Datum>(highTemp.size()))
                val low = lowTemp.toArray<Datum>(arrayOfNulls<Datum>(lowTemp.size()))
                if (high.size >= 1)
                {
                    this.highChild = KDNode(high)
                }
                if (low.size >= 1)
                {
                    this.lowChild = KDNode(low)
                }
            }
        }
        fun getRangePos(datalist:Array<Datum>):Int {
            val range = 0
            val rangePos = 0
            val highCheck = 0
            val lowCheck = 0
            if (datalist.size <= 0)
            {
                throw NullPointerException("The list is empty.")
            }
            for (y in datalist.indices)
            {
                if (datalist[y] != null)
                {
                    for (z in datalist[y].x.indices)
                    {
                        if (datalist[y].x[z] > highCheck - lowCheck)
                        {
                            highCheck = datalist[y].x[z]
                        }
                        else
                        {
                            lowCheck = datalist[y].x[z]
                        }
                    }
                    if (highCheck - lowCheck > range)
                    {
                        range = highCheck - lowCheck
                        rangePos = y
                    }
                }
                else
                {
                    break
                }
            }
            return rangePos
        }
        fun nearestPointInNode(queryPoint:Datum):Datum {
            val iterator = KDTreeIterator(this)
            val i = 0
            val j = iterator.list.size() - 1
            val mid = 0
            if (KDTree.distSquared(iterator.pos(0), queryPoint) <= 0)
            {
                return iterator.pos(0)
            }
            if (KDTree.distSquared(iterator.pos(0), queryPoint) >= 0)
            {
                return iterator.pos(iterator.list.size() - 1)
            }
            while (i < j)
            {
                mid = (i + j) / 2
                if (KDTree.distSquared(iterator.pos(mid), queryPoint) == 0L)
                {
                    return iterator.pos(mid)
                }
                /* If target is less than array element,
         then search in left */
                if (KDTree.distSquared(iterator.pos(mid), queryPoint) < 0)
                {
                    // If target is greater than previous
                    // to mid, return closest of two
                    if (mid > 0 && KDTree.distSquared(iterator.pos(mid - 1), queryPoint) > 0)
                    {
                        if (KDTree.distSquared(queryPoint, iterator.pos(mid - 1)) >= KDTree.distSquared(iterator.pos(mid), queryPoint))
                            return iterator.pos(mid)
                        else
                            return iterator.pos(mid - 1)
                    }
                    /* Repeat for left half */
                    j = mid
                }
                else
                {
                    if (mid < iterator.list.size() - 1 && (KDTree.distSquared(iterator.pos(mid + 1), queryPoint) > 0))
                    {
                        if (KDTree.distSquared(queryPoint, iterator.pos(mid - 1)) >= KDTree.distSquared(iterator.pos(mid), queryPoint))
                            return iterator.pos(mid + 1)
                        else
                            return iterator.pos(mid)
                    }
                    i = mid + 1
                }// If target is greater than mid
            }
            // Only single element left after search
            return iterator.pos(mid)
        }
        // ----------------- KDNode helper methods (might be useful for debugging) -------------------
        fun height():Int {
            if (this == null)
            {
                throw NullPointerException()
            }
            if (this.leaf)
                return 0
            else if (this.lowChild != null && this.highChild != null)
            {
                return 1 + Math.max(this.lowChild.height(), this.highChild.height())
            }
            else if (this.lowChild != null)
            {
                return 1 + this.lowChild.height()
            }
            else if (this.highChild != null)
            {
                return 1 + this.highChild.height()
            }
            else
            {
                return 0
            }
        }
        /*if (this.leaf)
                    return 0;
                else {
                    return 1 + Math.max( this.lowChild.height(), this.highChild.height());
                }*/
        fun countNodes():Int {
            if (this == null)
            {
                throw NullPointerException()
            }
            if (this.leaf)
                return 1
            else if (this.lowChild != null && this.highChild != null)
            {
                return 1 + this.lowChild.countNodes() + this.highChild.countNodes()
            }
            else if (this.lowChild != null)
            {
                return 1 + this.lowChild.countNodes()
            }
            else if (this.highChild != null)
            {
                return 1 + this.highChild.countNodes()
            }
            else
            {
                return 0
            }
        }
        /*
     * Returns a 2D array of ints. The first element is the sum of the depths of leaves
     * of the subtree rooted at this KDNode. The second element is the number of leaves
     * this subtree. Hence, I call the variables sumDepth_size_* where sumDepth refers
     * to element 0 and size refers to element 1.
     */
        fun sumDepths_numLeaves():IntArray {
            val sumDepths_numLeaves_low:IntArray
            val sumDepths_numLeaves_high:IntArray
            val return_sumDepths_numLeaves = IntArray(2)
            /*
       * The sum of the depths of the leaves is the sum of the depth of the leaves of the subtrees,
       * plus the number of leaves (size) since each leaf defines a path and the depth of each leaf
       * is one greater than the depth of each leaf in the subtree.
       */
            if (this.leaf)
            { // base case
                return_sumDepths_numLeaves[0] = 0
                return_sumDepths_numLeaves[1] = 1
            }
            else
            {
                sumDepths_numLeaves_low = this.lowChild.sumDepths_numLeaves()
                sumDepths_numLeaves_high = this.highChild.sumDepths_numLeaves()
                return_sumDepths_numLeaves[0] = sumDepths_numLeaves_low[0] + sumDepths_numLeaves_high[0] + sumDepths_numLeaves_low[1] + sumDepths_numLeaves_high[1]
                return_sumDepths_numLeaves[1] = sumDepths_numLeaves_low[1] + sumDepths_numLeaves_high[1]
            }
            return return_sumDepths_numLeaves
        }
    }
    public override fun iterator():Iterator<Datum> {
        return KDTreeIterator(this.rootNode)
    }
    private inner class KDTreeIterator internal constructor(curr:KDNode):Iterator<Datum> {
        internal var list:ArrayList<Datum> = ArrayList()
        internal var x:Int = 0
        init{
            while (!curr.leaf)
            {
                KDTreeIterator(curr.lowChild)
                KDTreeIterator(curr.highChild)
                if (curr.leaf)
                {
                    list.add(curr.leafDatum)
                    break
                }
            }
            x = 0
        }
        public override fun hasNext():Boolean {
            return !(list.get(x + 1) == null)
        }
        public override fun next():Datum {
            if (hasNext())
            {
                x++
                return list.get(x + 1)
            }
            else
            {
                throw NullPointerException()
            }
        }
        fun pos(x:Int):Datum {
            return list.get(x)
        }
    }
    companion object {
        //------------------- helper methods for KDTree ------------------------------
        fun distSquared(d1:Datum, d2:Datum):Long {
            val result:Long = 0
            for (dim in d1.x.indices)
            {
                result += (d1.x[dim] - d2.x[dim]) * ((d1.x[dim] - d2.x[dim]).toLong())
            }
            // if the Datum coordinate values are large then we can easily exceed the limit of 'int'.
            return result
        }
    }
}
internal class Datum(x:IntArray) {
    var x:IntArray
    init{
        this.x = IntArray(x.size)
        for (i in x.indices)
        {
            this.x[i] = x[i]
        }
    }
    public override fun toString():String {
        val str = "["
        val l = this.x.size
        for (i in 0 until l - 1)
        {
            str += this.x[i] + ","
        }
        str += this.x[l - 1] + "]"
        return str
    }
    public override fun hashCode():Int {
        return Arrays.hashCode(this.x)
    }
    public override fun equals(o:Any):Boolean {
        if (o === this)
        {
            return true
        }
        if (o == null || o.javaClass != this.javaClass)
        {
            return false
        }
        val d = o as Datum
        return Arrays.equals(d.x, this.x)
    }
}