package jgraspvex

class BinaryTreeK<T : Comparable<T>> (private val nullNode: BinaryTreeNodeK<T>) {

    private var size: Int = 0

    private var root: BinaryTreeNodeK<T> = nullNode

    fun add(value: T) {
        val node = BinaryTreeNodeK(value, nullNode, nullNode)
        val rt = root
        if (rt == nullNode) {
            root = node
            size++
        }
        else {
            add(rt, node)
        }
    }


    private fun add(branch: BinaryTreeNodeK<T>, node: BinaryTreeNodeK<T>) {
        val cmp = branch.value.compareTo(node.value)
        if (cmp > 0) {
            if (branch.left == nullNode) {
                branch.left = node
                size++
            }
            else {
                add(branch.left, node)
            }
        }
        else if (cmp < 0) {
            if (branch.right == nullNode) {
                branch.right = node
                size++
            }
            else {
                add(branch.right, node)
            }
        }
    }


    operator fun contains(value: T): Boolean {
        return contains(root, value)
    }


    private fun contains(branch: BinaryTreeNodeK<T>?, value: T): Boolean {
        if (branch == null) {
            return false
        }
        val cmp = branch.value.compareTo(value)
        if (cmp < 0) {
            return contains(branch.right, value)
        }
        else if (cmp > 0) {
            return contains(branch.left, value)
        }
        return true
    }


    fun remove(value: T): Boolean {
        val rt = root
        if (rt == nullNode) {
            return false
        }
        val cmp = rt.value.compareTo(value)
        if (cmp == 0) {
            when (nullNode) {
                rt.left -> root = rt.right
                rt.right -> root = rt.left
                else -> {
                    val tmp = rt.right
                    root = rt.left
                    add(rt, tmp)
                    size--
                }
            }
            size--
            return true
        }
        return remove(rt, value, cmp)
    }


    private fun remove(parentBranch: BinaryTreeNodeK<T>, value: T,
                       parentCmp: Int): Boolean {
        val branch = if (parentCmp > 0) parentBranch.left else parentBranch.right
        if (branch == nullNode) {
            return false
        }

        val cmp = branch.value.compareTo(value)
        if (cmp == 0) {
            val newRoot: BinaryTreeNodeK<T>
            when (nullNode) {
                branch.left -> newRoot = branch.right
                branch.right -> newRoot = branch.left
                else -> {
                    val tmp = branch.right
                    newRoot = branch.left
                    add(newRoot, tmp)
                    size--
                }
            }
            if (parentCmp > 0) {
                parentBranch.left = newRoot
            }
            else {
                parentBranch.right = newRoot
            }
            size--
            return true
        }
        return remove(branch, value, cmp)
    }


    fun elements(): List<T> {
        val result = mutableListOf<T>()
        fillElements(root, result)
        return result
    }


    private fun fillElements(branch: BinaryTreeNodeK<T>,
                             result: MutableList<T>) {
        if (branch.left != nullNode) {
            fillElements(branch.left, result)
        }
        result.add(branch.value)
        if (branch.right != nullNode) {
            fillElements(branch.right, result)
        }
    }


    fun clear() {
        root = nullNode
        size = 0
    }


    fun size(): Int {
        return size
    }
}