blob: 031d9fefdc9f00d65b57970ebcaedd750c9c9a2a (
plain)
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
|
object IntSet {
abstract class IntSet { // extends java.lang.Object
def incl(x: Int): IntSet
def contains(x: Int): Boolean
def union(other: IntSet): IntSet
}
// singleton object
object Empty extends IntSet {
def contains(x: Int): Boolean = false
def incl(x: Int): IntSet = new NonEmpty(x, Empty, Empty)
def union(other: IntSet): IntSet = other
override def toString = "."
}
class NonEmpty(elem: Int, left: IntSet, right: IntSet) extends IntSet {
def contains(x: Int): Boolean =
if (x < elem) left contains x
else if (x > elem) right contains x
else true
// creat a new tree, but does not destroy the previous one
// persistent data structure
def incl(x: Int): IntSet =
if (x < elem) new NonEmpty(elem, left incl x, right)
else if (x > elem) new NonEmpty(elem, left, right incl x)
else this
def union(other: IntSet): IntSet =
((left union right) union other) incl elem
override def toString = "{" + left + elem + right + "}"
}
def run = {
println("IntSet")
val t1 = new NonEmpty(3, Empty, Empty)
println(t1)
println(t1 contains 4)
val t2 = t1 incl 4
println(t1)
println(t2 toString)
println(t2 contains 4)
}
}
|
