代碼直接映射到您提供的描述。
讓我們舉一個簡單的例子來演示用法:首先有一個空集,比如說e
然後給它添加一個元素來獲得另一個集合,比如s1
。然後,您將有 2套,e
和s1
:
val e = Empty
e contains 42 // will be false
// create s1 from e
val s1 = e incl 1 // e does not change; it remains a reference to the Empty set.
// Now we have s1, a set that should contain (1) and nothing else.
s1 contains 1 // will be true
s1 contains 42 // will be false
我猜你所熟悉的斯卡拉速記,可以讓你鍵入的 s1 incl 1
代替s1.incl(1)
注意,這裏不僅可以永遠是一個空集,所以這是一樣好:
val s1 = Empty incl 1
那麼,讓我們說你想添加,說2
得到另一套s2
其元素 必須包括{1, 2}
。
val s2 = s1 incl 2
s2 contains 1 // true
s2 contains 2 // true
s2 contains 3 // false
所以任意一組的方法incl
接受一個元件和返回一個新的組 - 它不 變化的集(其include
方法被稱爲原始對象ob)。
我們有兩種類型的樹集;空和非空,並且每個具有用於incl
一個實現:
// Empty
def incl(x:Int): IntSet = new NonEmpty(x, Empty, Empty)
讀取:「添加元素爲空(樹)組產生另一組是一個非空的樹只有一個根值爲1
的節點和空的左右子樹。「
非空集具有構造函數參數elem
,它表示樹的根並且對NonEmpty
中的所有方法都可見。
// Non-Empty
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
讀取:(在上面的if-else的相反的順序):
- 添加元素
x
到非空集,其根元素也是x
給你同一組(this
)
- 添加元素
x
到非空集,其根元件比01少 x
給你另一個集,其中:
- 根元素是一樣的原來設定
- 的左子樹是不變的 - 一樣的,在原設定
- 的新權子樹變成原來的右子樹樹
x
添加到它「:right incl x
- 添加元素
x
到非空集,其根元件比x
給你另一個集,其中更大:
- 根元素是相同的原始集合
- 的right子樹不變 - 與原始集相同
- 新左子樹成爲原始左子樹
x
添加到它「:left incl x
的‘持久性’是一個事實,即沒有樹或子樹是是否會改變實現。在這個例子中
val s1 = Empty incl 1 // s1 is a tree with only a root(1) an no branches.
val s2 = s1 incl 2 // s2 is another tree with -
// - the same root(1),
// - the same left-subtree as s1, (happens to be Empty)
// - a new subtree which in turn is a tree with -
// - the root element (2)
// - no left or right brances.
s1 contains 1 // true
s1 contains 2 // false
s2 contains 1 // true
s2 contains 2 // true
val s3 = s2 incl -3 // s2.incl(-3)
// from s2 we get s3, which does not change s2's structure
// in any way.
// s3 is the new set returned by incl, whose
// - root element remains (1)
// - left subtree is a new tree that contains
// just (-3) and has empty left, right subtrees
// - right subtree is the same as s2's right subtree!
s3.contains(-3) // true; -3 is contained by s3's left subtree
s3.contains(1) // true; 1 is s3's root.
s3.contains(2) // true; 2 is contained by s3's right subtree
s3.contains(5) // false
我們只使用incl
從其它套派生集(樹),在不改變原設定。這是因爲在非常階段,我們要麼 -
- 回報新基於離開的人,而不是修改 現有結構,
- 回報現有的結構,因爲它們的數據結構。
contains
的工作方式相同:Empty
有任何輸入返回false
的實現。 NonEmpty
如果給定元素與它的根相同,或者它的左邊或右邊的子樹都包含它,它會很快返回true!
請注意,這不是一個純功能樹。它是一棵不變的樹,每個樹操作都會在內存中創建一個可以保存的類實例。 – 0kcats