Assignment_03/src/main/scala/Main.scala

   1 object Main {
   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
  12   }
  13
  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)
  18       else this
  19     }
  20     def contains(x: Int): Boolean = {
  21       if (x < elem) left contains x
  22       else if (x > elem) right contains x
  23       else true
  24     }
  25     override def toString(): String = s"($left|$elem|$right)"
  26     def foreach(f: Int => Unit): Unit = {
  27       left foreach f
  28       f(elem)
  29       right foreach f
  30     }
  31     def union(other: IntSet): IntSet = {
  32       val newSet = (left union right) union other
  33       newSet add elem
  34     }
  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)
  40         newSet add elem
  41       else
  42         newSet
  43     }
  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)
  47       else left union right
  48     }
  49     def isEmpty(): Boolean = false
  50   }
  51
  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
  61   }
  62
  63   def main(args: Array[String]) = {
  64     println("Question 1")
  65     println("a)")
  66     println(Empty)
  67     println(Empty.add(3))
  68     println(Empty.add(3).add(2))
  69
  70     println("b)")
  71     val s = Empty.add(3).add(2).add(6).add(1)
  72     s foreach println
  73
  74     println("c)")
  75     s foreach ((v: Int) => print(s"${v + 1}, "))
  76     println()
  77
  78     println("Question 2")
  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}")
  82
  83     println("Question 3")
  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}")
  87   }
  88 }