Integer Set的交集函數

Question

所以基本上我正在使用二叉樹實現整數集合。

這裏的抽象類INTSET

abstract class IntSet { 
    def incl(x: Int): IntSet 
    def contains(x: Int): Boolean 
    def union(other: IntSet): IntSet 
    def intersect(other: IntSet) : IntSet 
} 

非空設置：

/********************NonEmpty************************************/ 
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 
    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 

    override def toString = "{" + left + elem + right + "}" 

    def union(other: IntSet): IntSet= { 
    ((left union right) union other) incl elem 
    } 

} 

而且EmptySet：

/********************Empty************************************/ 
class Empty extends IntSet { 
    def contains(x: Int): Boolean = false 
    def incl(x: Int): IntSet = new NonEmpty(x, new Empty, new Empty) 
    def union(other: IntSet): IntSet = other 
    override def toString = "." 
} 

正如你所看到的，兩套工會已經實施。 我的問題是，我將如何去執行相交功能？

聯盟工作正常，你可以從輸出中看到：

val t1= new NonEmpty(1, new NonEmpty(2, new Empty(), new Empty()), new NonEmpty(3, new Empty(), new Empty())) 
                //> t1 : mid.NonEmpty = {{.2.}1{.3.}} 
val t2 =new NonEmpty(5, new NonEmpty(6, new Empty(), new Empty()), new NonEmpty(7, new Empty(), new Empty())) 
                //> t2 : mid.NonEmpty = {{.6.}5{.7.}} 
      //t1 union t2       //> res0: mid.IntSet = {{{{.1.}2{.3.}}6.}5{.7.}} 

Answer 1

平凡implementaion爲Empty類：

class Empty extends IntSet { 
    override def intersect(other: IntSet): IntSet = new Empty 
} 

遞歸實施NonEmpty（留心：所有構造函數的參數標記爲val） ：

class NonEmpty(val elem: Int, val left: IntSet, val right: IntSet) extends IntSet { 
    override def intersect(other: IntSet): IntSet = { 
    def intersect(set: IntSet, result: IntSet): IntSet = { 
     set match { 
     case e: Empty => result 
     case e: NonEmpty => 
      val afterLeft = intersect(e.left, result) 
      val afterRight = intersect(e.right, afterLeft) 
      if (other.contains(e.elem)) afterRight.incl(e.elem) 
      else afterRight 
     } 
    } 

    intersect(this, new Empty) 
    } 
} 

用法：

val e1 = new Empty().incl(1).incl(2).incl(3).incl(5).incl(9).incl(4).incl(7) 
e1: IntSet = {.1{.2{.3{{.4.}5{{.7.}9.}}}}} 
val e2 = new Empty().incl(1).incl(3).incl(7).incl(9) 
e2: IntSet = {.1{.3{.7{.9.}}}} 
e1.intersect(e2) 
res0: IntSet = {{{.1.}3.}7{.9.}} 
e2.intersect(e1) 
res1: IntSet = {{{{.1.}3.}7.}9.} 

可能的改進：

• 取代abstract class與sealed trait
• 與object Empty
• 取代class Empty與сase class NonEmpty

Answer 2

def intersection(x: IntSet) : IntSet = 
{ 
    val y = if (x contains elem) new NonEmpty(elem, new Empty, new Empty) 
      else new Empty 

    y union ((left intersection x) union (right intersection x)) 
} 

更換