Scala : add 4-intset.scala

1 files changed, 45 insertions, 0 deletions

diff --git a/Scala/sandbox/4-intset.scala b/Scala/sandbox/4-intset.scala
new file mode 100644
index 0000000..031d9fe
--- /dev/null
+++ b/Scala/sandbox/4-intset.scala
@@ -0,0 +1,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)
+  }
+
+}