2
\$\begingroup\$

Here are a few questions on my mind:

  1. What improvements to the above code can you think of?
  2. I want to say new UnionFind(x) where x is a Set[T] (I emphatically don't want to say new UnionFind(x.toList). Is Traversable[T] (and .toList inside the UnionFind) the right choice for that?
  3. Note that the union method requires an equality test on T. Would it be sensible to take an explicit or implicit equality test as an additional argument? What are the best arguments against? (Other than "it's more code of perhaps limited benefit"—which is a relevant consideration, but I'm not asking to improve that area of my thinking.)
  4. Is the placement of the import statement reasonable?

    • In favor of it: it makes minimal the scope of a rename-import
    • In favor of beginning of class or beginning of file: the substance is header-ish, so it should be in a place where people expect to find header-ish things. In favor particularly of beginning of class is that it both header-ish and local.
    • Are there trade-offs other than findability/discoverability vs. breakage prevention that I'm making (unknowingly)?

class UnionFind[T](nodes: Traversable[T]) {
    private type Node[T] = Either[T, Int]

    private val parent: MutableMap[T, Node[T]] = {
        import scala.collection.mutable.{Map => MutableMap}
        MutableMap((for (n <- nodes.toList) yield (n -> Right(1))): _*)
    }

    private def root(a: T): (T, Int) = parent(a) match {
        case Right(n) => (a, n)
        case Left(parent_of_a) => {
            val (root_over_a, n) = root(parent_of_a)
            parent(a) = Left(root_over_a)
            (root_over_a, n)
        }
    }

    def find(a: T): T = root(a)._1

    def size(a: T): Int = root(a)._2

    def union(a: T, b: T) {
        val (root_a, size_a) = root(a)
        val (root_b, size_b) = root(b)
        if (root_a != root_b) {
            val size_union = size_a + size_b
            if (size_a <= size_b) {
                parent(root_a) = Left(root_b)
                parent(root_b) = Right(size_union)
            } else {
                parent(root_b) = Left(root_a)
                parent(root_a) = Right(size_union)
            }
        }
    }
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.