// Implements a dicitonary using a binary tree data structure. // This is not "production quality" code; in particular, the tree is // not kept balanced. import "math" as math inherits collectionFactory.trait // provides implementations of `empty` and `with`, defined using `withAll` def ConcurrentModification = ProgrammingError.refine "ConcurrentModification" // Raised if the tree is modified while being iterated. factory method withAll(pairs:Collection>) { // Creates a new dictionary and initializes it with the key::value // bindings in the collection pairs. def emptyNode = object { inherits Singleton.named "⏚" method isEmpty { true } method height { 0 } method do(action:Block1) { } method preorderKeysAndValuesDo(action:Block2) { } } type Node = type { key -> K key:=(k:K) -> Done value -> V value:=(v:V) -> Done left -> MaybeNode left:=(n: MaybeNode) -> Done right -> MaybeNode right:=(n: MaybeNode) -> Done height -> Number do(Action:Block1) -> Done preorderKeysAndValuesDo(action:Block2) -> Done isEmpty -> Boolean hash -> Number } type MaybeNode = Node | emptyNode // References in the binary tree may be to other nodes, or to emptyNode factory method nodeContaining(key':K, value':V) withChildren(left':MaybeNode, right':MaybeNode) -> Node { var key is public := key' var value is public := value' var left is public := left' var right is public := right' def hash is public = math.random * 1099511627776 method isEmpty { false } method asString { "nd({key}, {value}, {left}, {right})" } method height { 1 + max(left.height, right.height) } method do(action:Block1) { left.do(action) action.apply(key::value) right.do(action) } method preorderKeysAndValuesDo(action:Block2) { action.apply(key, value) left.preorderKeysAndValuesDo(action) right.preorderKeysAndValuesDo(action) } } method nodeContaining(key:K, value:V) -> Node is confidential { nodeContaining(key, value) withChildren(emptyNode, emptyNode) } var root is readable := emptyNode var size is readable := 0 var eventCount := 0 addAll(pairs) method height { root.height } method at(key) put(value) { addNode(nodeContaining(key, value)) in (root) setParent { new -> root := new } eventCount := eventCount + 1 self } method asString { var result := "dict⟬" var first := true bindingsDo { each -> if (first.not) then { result := result ++ ", " } else { first := false } result := result ++ each } result ++ "⟭" } method addNode(newNode) in (r) setParent (setParentRef) is confidential { // Adds newNode to the binary search tree rooted at r. setParentRef // is a block that is used to modify the final step of the path by // which this node was reached. if (r.isEmpty) then { setParentRef.apply(newNode) size := size + 1 } elseif (newNode.key == r.key) then { r.value := newNode.value } elseif { newNode.key < r.key } then { addNode(newNode) in (r.left) setParent { new -> r.left := new } } else { addNode(newNode) in (r.right) setParent { new -> r.right := new } } } method addAll(newPairs) { newPairs.do { each -> at(each.key) put(each.value) } } method removeKey(key) { // Remove key and its associated value from this tree. // It's an error for key not to be present. eventCount := eventCount + 1 removeKey(key) from(root) ifAbsent { NoSuchObject.raise "key {key} not present" } setParent { val -> root := val } } method removeKey(key) ifAbsent (absentAction) { // Remove key from this tree, and return the removed key::value binding. // If key is not present, apply absentAction and return its result. eventCount := eventCount + 1 removeKey(key) from (root) ifAbsent (absentAction) setParent { val -> root := val } } method removeKey(key) from (r) ifAbsent (absentAction) setParent (setParentReference) is confidential { // Remove key from the subtree r. setParentReference is a block that // will assign its argument to a variable of the caller's choosing. // Returns key and its associated value as a binding. // If key is not present, then absentAction will be applied and its // result returned. if (r.isEmpty) then { absentAction.apply } elseif { key == r.key } then { def result = r.key::r.value if (r.right.isEmpty) then { setParentReference.apply(r.left) size := size - 1 } elseif { r.left.isEmpty } then { setParentReference.apply(r.right) size := size - 1 } else { // two children def leftMax = maxElement(r.left) removeKey(leftMax.key) from (r.left) ifAbsent { ... } setParent { val -> r.left := val } r.key := leftMax.key r.value := leftMax.value } result } elseif { key > r.key } then { removeKey(key) from (r.right) ifAbsent (absentAction) setParent { new -> r.right := new } } else { // key < r.key removeKey(key) from (r.left) ifAbsent (absentAction) setParent { new -> r.left := new } } } method maxElement(rootNode) is confidential { // return the maximum key::value binding from the subtree // rooted at rootNode, which must not be empty. var current := rootNode while { current.right.isEmpty.not } do { current := current.right } def maxKey = current.key def maxVal = current.value return maxKey::maxVal } method at(key) { at(key) ifAbsent { NoSuchObject.raise "key {key} not present" } } method at(key) ifAbsent (absentAction) { def at' = { key', currentNode -> if (currentNode.isEmpty) then { absentAction.apply } elseif (key' < currentNode.key) then { at'.apply(key', currentNode.left) } elseif (key' > currentNode.key) then { at'.apply(key', currentNode.right) } else { return currentNode.value } } at'.apply(key, root) } method isEmpty { root.isEmpty } method asDebugString { root.asString } method copy { def newTree = outer.with() root.preorderKeysAndValuesDo { k, v -> newTree.at(k) put(v) } // we use preorder to create the copy to avoid creating a // highly unblanced tree. newTree } method do(block1) { root.do{ each:Binding -> block1.apply(each.value) } } method valuesDo(block1) { root.do{ each:Binding -> block1.apply(each.value) } } method keysDo(block1) { root.do{ each:Binding -> block1.apply(each.key) } } method keysAndValuesDo(block1) { root.do{ each:Binding -> block1.apply(each.key, each.value) } } method bindingsDo(block1) { root.do(block1) } type MinimalDict = type { size -> Number at(k:Object) ifAbsent(aciton:Block1) -> Object } method == (other:MinimalDict) { if (size != other.size) then { return false } keysAndValuesDo { k, v -> if ((other.at(k) ifAbsent { return false }) != v) then { return false } } true } factory method iterator { def zipper is readable = list.empty def savedEventCount = eventCount addLeftmostPath(root) method addLeftmostPath(start) is confidential { var n := start while { n.isEmpty.not } do { zipper.addLast(n) n := n.left } } method hasNext { zipper.isEmpty.not } method next { if (savedEventCount != eventCount) then { ConcurrentModification.raise "the tree has changed!" } if (!hasNext) then { IteratorExhausted.raise "on Tree" } def current = zipper.removeLast addLeftmostPath(current.right) current.key::current.value } } }