Лес непересекающихся множеств. Ок норм работает, только не функционально

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
//файл Node
class Node[T](val value: T) {
private var depth: Int = 0
private var parent: T = value
def this (value:T, p:T, d:Int) = {
this(value)
this.depth = d
this.parent = p
}
def Parent() = parent
def Depth() = depth
def isRoot() = this == this.parent
/* def printTree(n: Node[T] = this) {
println(n)
if (n != n.parent) printTree(n.parent)
}*/
override def toString():String = {
"value: " + value + " parent:" + parent
}
}
//файл DSU
import scala.collection.mutable.HashMap
class DSU[T](private var matchNode:HashMap[T, Node[T]] = new HashMap[T, Node[T]]) {
private var relationship: HashMap[Node[T], Node[T]] = new HashMap[Node[T], Node[T]]
//private var resultSet:T = new T()
def this(a:HashMap[T, Node[T]], b:HashMap[Node[T], Node[T]] ) = {
this(a)
this.relationship = b
}
/*def this(a:HashMap[T, Node[T]], b:HashMap[Node[T], Node[T]], r:T ){
this(a, b)
resultSet = r
}*/
def makeSet(value: T) = {
new DSU ( matchNode += (value -> new Node[T](value)))
}
def findSet(value: T): T = matchNode apply value Parent match {
case (parent) if (value == parent && !relationship.contains(matchNode apply value)) => value
case (parent) if (value == parent) => {
val res = relationship.apply(matchNode.apply(value)).value
matchNode += (relationship.apply(matchNode.apply(value)).value -> new Node[T](relationship.apply(matchNode.apply(value)).value, relationship.apply(matchNode.apply(value)).value, relationship.apply(matchNode.apply(value)).Depth + 1))
matchNode += (value -> new Node[T](value, relationship.apply(matchNode.apply(value)).value, matchNode.apply(value).Depth))
res
}
case (parent) => {
val result: T = findSet(matchNode.apply(value).Parent)
matchNode += (value -> new Node[T](value, result, matchNode.apply(value).Depth))
result
}
}
def unionSets(a: T, b: T): DSU[T] = findSet(a) match{
case (z) if (z == findSet(b)) => this
case (z) if (matchNode.apply(z).Depth < matchNode.apply(findSet(b)).Depth) => {
new DSU (matchNode, relationship += (matchNode.apply(z) -> matchNode.apply(findSet(b))))
}
case (z) if (matchNode.apply(z).Depth >= matchNode.apply(findSet(b)).Depth) => {
new DSU (matchNode,relationship += (matchNode.apply(findSet(b)) -> matchNode.apply(z)))
}
}
def print = {
println(matchNode)
println(relationship)
}
}
//файл main
object main extends App {
override def main(args: Array[String]) = {
var dsu = new DSU[Int]
dsu = dsu.makeSet(2)
println(dsu.findSet(2))
dsu = dsu.makeSet(3)
println(dsu.findSet(3))
dsu.print
dsu = dsu.unionSets(2, 3)
dsu.print
println(dsu.findSet(2) + " " + dsu.findSet(3))
dsu = dsu.makeSet(4)
dsu.print
dsu = dsu.unionSets(3, 4)
println(dsu.findSet(4))
dsu.print
/*println(dsu.findSet(3) + " " + dsu.findSet(2))
dsu1 = dsu1.unionSets(4, 2)
println(dsu1.findSet(3))
println(dsu1.findSet(2))
println(dsu1.findSet(4))
*/
}
}