Disjoint set DS

UnionSequence.scala

import scala.language._

// https://en.wikipedia.org/wiki/Disjoint-set_data_structure
// Not optimized version
// Supports only integer element sequences starting with 0, where n1 - n2 = -1 

object UnionSequence {
  def apply(elems: Int*): UnionSequence = {
    new UnionSequence(Array(elems:_*) toIndexedSeq)
  }
}

case class UnionSequence(elems: IndexedSeq[Int]) {
  
  lazy val count : Int = elems.size
  
  def union(p: Int, q: Int): UnionSequence = {
    if (!connected(p, q)) {
      val newValue = elems(p)
      val oldValue = elems(q)
      val ds = Array.ofDim[Int](elems.size)
      elems.view.zipWithIndex.map {
        case (_, id) if id == oldValue => ds(id) = newValue
        case (value, id) => ds(id) = value
      }
      this.copy(elems = ds toIndexedSeq)  
    } else this
  }
  
  def find(p:Int):Int = elems(p)
  def connected(p: Int, q: Int): Boolean = elems(p) == elems(q)
}