I have written Red–black tree in Kotlin. Fun insertFixup restores balance after inserting new element (z: Node? is new element). Algorithm of tree balancing is taken from here (pages 2-3). The problem is that Kotlin does not allow me to reassign z to z.parent and z.parent.parent. I want z to be a pointer. The question is how to make Kotlin understand what I want from him?
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: Thanks to all! All the answers were helpful and I have found the solution in your replies.
Vals cannot be reassigned (like variables declared as final in Java) while vars can be reassigned after creation. If you need to reassign the value of a variable, you will have to declare it as a var. If you do not need to reassign the variable, you can declare it as a val.
var is like a general variable and can be assigned multiple times and is known as the mutable variable in Kotlin. Whereas val is a constant variable and can not be assigned multiple times and can be Initialized only single time and is known as the immutable variable in Kotlin.
Kotlin uses two different keywords to declare variables: val and var . Use val for a variable whose value never changes. You can't reassign a value to a variable that was declared using val . Use var for a variable whose value can change.
Function parameters in Kotlin are basically read-only val
's inside the function, so z
here will always refer to the original object that was passed in.
If you need to modify what it points to while your function is running, you'll have to make a local copy of it at the beginning of the function, and then you can make that a var
.
For example, you could start your function like this, which lets you reassign this local var
later:
fun insertFixup(_z: Node?) {
var z = _z
// ...
z = z.parent
// ...
}
Kotlin function parameters are read-only values and are not assignable.
You can however create a ReadWriteProperty
object to pass to insertFixup
for getting/setting 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)
}
}
And if you are willing to use a property instead of a variable then you can use a property reference for getting/setting newNode
from insertFixup
instead:
...
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)
I ran into this issue as well. What i did was create a data class and pass the data class as a parameter that i could then use to modify its properties.
data class SomeDataClass(
val x: Int,
val y: Int,
val z: Int
)
fun someMethod(someDataClass: SomeDataClass) {
someDataClass.z = 23 //whatever Int value you please
// more computations...
someDataClass.z = 67 // or whatever new value you need to assign.
}
fun parentMethod() {
val someDataClass = SomeDataClass()
someMethod(someDataClass)
val newZValue = someDataClass.z // someDataClass holds modified data from above
// method
}
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With