class StringSearchTree private constructor(val key: Char, var isLeaf: Boolean,
                                           val parent: StringSearchTree?) {

    private val children = mutableMapOf<Char, StringSearchTree>()

    constructor(): this('\u0000', false, null)

    fun add(value: String) {
        assert(parent == null)
        add(value, 0)
    }

    private fun add(value: String, offset: Int) {
        if (offset >= value.length) {
            return
        }
        var subTree = children.get(value[offset])
        if (subTree == null) {
            subTree = StringSearchTree(value[offset], offset == (value.length - 1), this)
            children.put(subTree.key, subTree)
        }
        if (offset == (value.length - 1)) {
            subTree.isLeaf = true
        } else {
            subTree.add(value, offset + 1)
        }
    }

    fun remove(value: String) {
        assert(parent == null)
        remove(value, 0)
    }

    private fun remove(value: String, offset: Int) {
        if (offset >= value.length) {
            return
        }
        val subTree = children.get(value[offset]) ?: return
        if (offset == (value.length - 1)) {
            subTree.isLeaf = false
        } else {
            subTree.remove(value, offset + 1)
        }
        if (subTree.children.isEmpty() && !subTree.isLeaf) {
            children.remove(value[offset])
        }
    }

    fun search(value: Char): StringSearchTree? {
        return children.get(value)
    }

    fun reverseLookup(): String {
        assert(parent != null)
        val result = StringBuilder()
        result.append(key)
        var parent = parent
        while (parent!!.parent != null) {
            result.append(parent.key)
            parent = parent.parent
        }
        return result.reversed().toString()
    }

    class Search(var tree: StringSearchTree) {

        var finished = false
            private set

        fun next(char: Char): Result {
            assert(!finished)
            val nextTree = tree.search(char)
            if (nextTree == null) {
                finished = true;
                if (tree.isLeaf) {
                    return Result.FOUND
                } else {
                    return Result.NOT_FOUND
                }
            } else {
                tree = nextTree
                return Result.NEED_MORE
            }
        }

        fun reset() {
            finished = false
        }

        enum class Result {
            NEED_MORE,
            FOUND,
            NOT_FOUND
        }

    }

}