Kotlin函数参数:Val不能重新分配

Question

我在Kotlin写了红黑树.有趣的insertFixup在插入新元素后恢复平衡(z:Node？是新元素).树平衡算法从这里开始(第2-3页).该问题是,科特林不允许我重新分配 ž到z.parent和z.parent.parent.我希望z成为一个指针.问题是如何让Kotlin明白我对他的要求？

class Node(key: Int) {...}

class BinarySearchTree {
    var root: Node? = null

    fun insert(newNode: Node) {...}

    fun RotateLeft(x: Node?) {...}

    fun RotateRight(x: Node?) {...}

    fun insertFixup(z: Node?) {
        var y: Node?
        while (z?.parent?.color == "RED") {
            if (z?.parent == z?.parent?.parent?.left) {
                y = z?.parent?.parent?.right
                if (y?.color == "RED") {
                    z?.parent?.color = "BLACK"
                    y?.color = "BLACK"
                    z?.parent?.parent?.color = "RED"
                    z = z?.parent?.parent
                }
                if (z == z?.parent?.right) {
                    z = z?.parent
                    RotateLeft(z)
                    z?.parent?.color = "BLACK"
                    z?.parent?.parent?.color = "RED"
                    RotateRight(z?.parent?.parent)
                }
            } else {
                y = z?.parent?.parent?.left
                if (y?.color == "RED") {
                    z?.parent?.color = "BLACK"
                    y?.color = "BLACK"
                    z?.parent?.parent?.color = "RED"
                    z = z?.parent?.parent
                }
                if (z != z?.parent?.left) {
                    z = z?.parent
                    RotateLeft(z)
                    z?.parent?.color = "BLACK"
                    z?.parent?.parent?.color = "RED"
                    RotateRight(z?.parent?.parent)
                }
            }
        }
        root?.color = "BLACK"
    }
}

fun main(args: Array<String>) {
    val bst = BinarySearchTree()

    while (true) {
        var newNode = Node(readLine()!!.toInt())
        bst.insert(newNode)
        bst.insertFixup(newNode)
    }
}

UPD:谢谢大家!所有的答案都很有帮助,我在你的回复中找到了解决方案.

Answer 1

Kotlin中的函数参数在val函数内部是只读的,因此z这里总是引用传入的原始对象.

如果你需要在函数运行时修改它所指向的内容,你必须在函数的开头创建它的本地副本,然后你可以创建它var.

例如,您可以像这样启动您的函数:

fun insertFixup(_z: Node?) {
    var z = _z

Answer 2

Kotlin函数参数是只读值,不可分配.

但是,您可以创建一个ReadWriteProperty要传递给的对象来insertFixup获取/设置newNode:

...
class BinarySearchTree {
...
    fun insertFixup(zProperty: ReadWriteProperty<Any?, Node?>) {
        var z by zProperty
...

fun main(args: Array<String>) {
    val bst = BinarySearchTree()

    var newNode: Node? = null
    val newNodeProperty = object : ReadWriteProperty<Any?, Node?> {
        override operator fun getValue(thisRef: Any?, property: KProperty<*>): Node? {
            return newNode
        }

        override operator fun setValue(thisRef: Any?, property: KProperty<*>,
                                       value: Node?) {
            newNode = value
        }
    }

    while (true) {
        newNode = Node(readLine()!!.toInt())
        bst.insert(newNode!!)
        bst.insertFixup(newNodeProperty)
    }
}

如果你愿意用一个属性,而不是一个变量,那么你可以使用属性引用来获得/设置newNode的insertFixup,而不是:

...
class BinarySearchTree {
...
    fun insertFixup(zProperty: KMutableProperty0<Node?>) {
        var z by zProperty
...

var newNode: Node? = null

fun main(args: Array<String>) {
    val bst = BinarySearchTree()

    while (true) {
        newNode = Node(readLine()!!.toInt())
        bst.insert(newNode!!)
        bst.insertFixup(::newNode)
    }
}

// the following allow `KMutableProperty0` to be used as a read/write delegate
operator fun <T> KProperty0<T>.getValue(thisRef: Any?, property: KProperty<*>): T = get()
operator fun <T> KMutableProperty0<T>.setValue(thisRef: Any?, property: KProperty<*>, 
                                               value: T) = set(value)