Simple Tree Implementation: Why MutableSet equality returns false for what seems to be the same sets?

Support
1

As I’m learning Kotlin, I’m trying to implement a simple Tree.

The problem is my equals implementation is buggy, and i can’t figure out why

I have a node class with autogenerated by intellij equals

class Node(val value: String) {
    var parent: Node? = null
    val children = mutableSetOf<Node>()
    var depth: Int = 0

    fun addChild(child: Node) {
        children.add(child)
        child.parent = this
        child.depth = depth + 1
    }

    override fun toString(): String {
        return "$value-$depth" + (children.map { it.toString() })
    }

    override fun equals(other: Any?): Boolean {
        if (this === other) return true
        if (javaClass != other?.javaClass) return false

        other as Node

        if (value != other.value) return false
        if (children != other.children) return false // why is this false?
        if (depth != other.depth) return false

        return true
    }

    override fun hashCode(): Int {
        var result = value.hashCode()
        result = 31 * result + children.hashCode()
        result = 31 * result + depth
        return result
    }
}

And a very simple Junit test

    @Test
    fun `Equals Implementation Ignores Child Order`() {
        val root = Node("COM")
        val b = Node("B"); root.addChild(b)
        val g = Node("G"); b.addChild(g)
        val h = Node("H"); g.addChild(h)


        val root1 = Node("COM")
        val b1 = Node("B"); root1.addChild(b1)
        val g1 = Node("G"); b1.addChild(g1)
        val h1 = Node("H"); g1.addChild(h1)

        assertEquals(root, root1)
    }

During debugging, the equals fails at the line if (children != other.children) return false, but I cannot figure out why.

Checking equality of mutableSetOf(Node("a"))==mutableSetOf(Node("a")) returns true, as expected, and if i remove the children check inside equals, the jUnit also returns true. (I cannot remove that equals though as 2 trees must have equal children to be equal)

A second question is: Why is equals not called recursively for each child? This is what i would expect, but it doesn’t happen.

2

The problem is that you mutate b after adding it to the set root.children, by adding additional children to b. From Javas documentation of Set:

Note: Great care must be exercised if mutable objects are used as set elements. The behavior of a set is not specified if the value of an object is changed in a manner that affects equals comparisons while the object is an element in the set.

What happens in particular is the following:

val root = Node("COM")
val b = Node("B") // b = {value: "b", children: [], depth 0}
root.addChild(b) // b is inserted in root.children under h1 = b.hashCode = hash("b", [], 0)
val g = Node("G")
b.addChild(g) // b = {value: "b", children: [<G>], depth 0}
// Repeat for root1. b1 will be inserted in root1.children under h1 as well
root.children == root1.children
// During this check, it will see if root1.children contains b
//  It will do so by computing the hash of b, which is currently h2 = hash("b", [<G>], 0)
//  root1.children does not contain anything under h2, since b1 was inserted under h1. Thus this check returns false
2 Likes
3

Thanks you so much for the detailed explanation. Having not used Sets a lot generally, i forgot about this Contract they impose (that is, if i even knew about it).

And just to confirm your result, if i change children to MutableList from MutableSet, the unit test passes as expected for my limited example.

Your example is so easy to follow thanks to those comments :). Thanks again.

The only problem is that nodes in a tree can be added in different orders.
Back to the drawing board for me, to see how to properly implement the tree.

1 Like