2 abstract class IntSet() {
3 def add(x
: Int
): IntSet
4 def +(x
: Int
): IntSet
= this add x
5 def contains(x
: Int
): Boolean
6 def foreach(f
: Int
=> Unit
): Unit
7 def union(other
: IntSet
): IntSet
8 def intersect(other
: IntSet
): IntSet
9 def excl(x
: Int
): IntSet
10 def -(x
: Int
): IntSet
= this excl x
11 def isEmpty(): Boolean
14 class NonEmpty(elem
: Int
, left
: IntSet
, right
: IntSet
) extends IntSet
{
15 def add(x
: Int
): IntSet
= {
16 if (x
< elem
) new NonEmpty(elem
, left add x
, right
)
17 else if (x
> elem
) new NonEmpty(elem
, left
, right add x
)
20 def contains(x
: Int
): Boolean
= {
21 if (x
< elem
) left contains x
22 else if (x
> elem
) right contains x
25 override def toString(): String
= s
"($left|$elem|$right)"
26 def foreach(f
: Int
=> Unit
): Unit
= {
31 def union(other
: IntSet
): IntSet
= {
32 val newSet
= (left union right
) union other
35 def intersect(other
: IntSet
): IntSet
= {
36 val l
= left intersect other
37 val r
= right intersect other
38 val newSet
= l union r
39 if (other contains elem
)
44 def excl(x
: Int
): IntSet
= {
45 if (x
< elem
) new NonEmpty(elem
, left excl x
, right
)
46 else if (x
> elem
) new NonEmpty(elem
, left
, right excl x
)
49 def isEmpty(): Boolean
= false
52 object Empty
extends IntSet
{
53 def add(x
: Int
): IntSet
= new NonEmpty(x
, Empty
, Empty
)
54 def contains(x
: Int
): Boolean
= false
55 override def toString(): String
= "-"
56 def foreach(f
: Int
=> Unit
): Unit
= ()
57 def union(other
: IntSet
): IntSet
= other
58 def intersect(other
: IntSet
): IntSet
= Empty
59 def excl(x
: Int
): IntSet
= Empty
60 def isEmpty(): Boolean
= true
63 def main(args
: Array
[String
]) = {
68 println(Empty
.add(3).add(2))
71 val s
= Empty
.add(3).add(2).add(6).add(1)
75 s
foreach ((v
: Int
) => print(s
"${v + 1}, "))
79 val s2
= Empty
.add(2).add(3).add(8).add(10).add(1)
80 println(s
"a) $s union $s2 = ${s union s2}")
81 println(s
"b) $s intersect $s2 = ${s intersect s2}")
84 println(s
"a) $s excl 3 = ${s excl 3}")
85 println(s
"b) Empty + 3 + 4 + 12 + 5 = ${Empty + 3 + 4 + 12 + 5}")
86 println(s
"c) $s - 1 - 2 - 3 - 4 = ${s - 1 - 2 - 3 - 4}")