--- a/BinaryTreeNode.st	Mon Sep 28 18:16:39 2009 +0200
+++ b/BinaryTreeNode.st	Mon Sep 28 18:16:58 2009 +0200
@@ -1,5 +1,5 @@
 "
-    Public domain (I guess, as it was published in c.l.s) no limitation on use.
+    Public domain (1996 published in c.l.s) no limitation on use.
 
     This class is provided as-is, without any warranty. 
     It is not part of or covered by the ST/X copyright.
@@ -17,7 +17,7 @@
 
 copyright
 "
-    Public domain (I guess, as it was published in c.l.s) no limitation on use.
+    Public domain (1996 published in c.l.s) no limitation on use.
 
     This class is provided as-is, without any warranty. 
     It is not part of or covered by the ST/X copyright.
@@ -77,7 +77,7 @@
 data:data
     "Returns a new binary tree node, holding data"
 
-    ^ self basicNew initialize data:data
+    ^ self basicNew data:data
 
     "Modified: 10.5.1996 / 15:00:13 / cg"
     "Created: 10.5.1996 / 15:00:35 / cg"
@@ -91,23 +91,15 @@
 	    rightSubtree: self new
 
     "Modified: 10.5.1996 / 15:00:02 / cg"
-!
-
-new
-    "Returns a new empty binary tree node"
-
-    ^ self basicNew initialize
-
-    "Modified: 10.5.1996 / 15:00:13 / cg"
 ! !
 
 !BinaryTreeNode methodsFor:'accessing'!
 
 data
-    ^data
+    ^ data
 !
 
-data:   anObject
+data:anObject 
     data := anObject
 !
 
@@ -119,18 +111,34 @@
     leftSubtree := aBinaryTree
 !
 
+nextNodeInOrder
+    ^ rightSubtree leftMostNode
+!
+
+predecessor
+    ^ self prevNodeInOrder data
+!
+
+prevNodeInOrder
+    ^ leftSubtree rightMostNode
+!
+
 rightSubtree
     ^rightSubtree
 !
 
 rightSubtree: aBinaryTree
     rightSubtree := aBinaryTree
+!
+
+successor
+    ^ self nextNodeInOrder data
 ! !
 
 !BinaryTreeNode methodsFor:'enumeration'!
 
 do: aBlock
-    "applies aBlock to each elements data in the binary tree in inorder"
+    "applies aBlock to each element's data in the binary tree in inorder"
 
     self inOrderDo:[:eachNode | aBlock value:eachNode data]
 !
@@ -263,63 +271,6 @@
     "
      BinaryTree withAll:#(16 3 1 0 4 7 9)             
     "
-!
-
-removeIdenticalValue:oldValue sortBlock:sortBlock
-    "remove a value - returns a new treeNode, or nil if the value is not in the tree"
-
-    ^ self removeValue:oldValue using:#== sortBlock:sortBlock
-!
-
-removeValue:oldValue sortBlock:sortBlock
-    "remove a value - returns a new treeNode, or nil if the value is not in the tree"
-
-    ^ self removeValue:oldValue using:#= sortBlock:sortBlock
-!
-
-removeValue:oldValue using:compareOp sortBlock:sortBlock
-    "remove a value - returns a new treeNode, or nil if the value is not in the tree"
-
-    |thisIsMyNode newTop|
-
-    "/ speed hack - avoids message sends
-    compareOp == #== ifTrue:[
-        thisIsMyNode := (data == oldValue).
-    ] ifFalse:[
-        compareOp == #= ifTrue:[
-            thisIsMyNode := (data = oldValue).
-        ] ifFalse:[
-            thisIsMyNode := data perform:compareOp with:oldValue.
-        ].
-    ].
-
-    thisIsMyNode ifTrue:[
-        leftSubtree isNil ifTrue:[
-            ^ rightSubtree
-        ].
-        rightSubtree isNil ifTrue:[
-            ^ leftSubtree
-        ].
-        newTop := self removeLeftRightMostNode.
-        newTop leftSubtree:leftSubtree.
-        newTop rightSubtree:rightSubtree.
-        ^ newTop.
-    ].
-
-    (sortBlock value:oldValue value:data) ifTrue:[
-        "/ the value should be in the left half.
-        leftSubtree isNil ifTrue:[
-            ^ nil
-        ].
-        leftSubtree := leftSubtree removeValue:oldValue using:compareOp sortBlock:sortBlock.
-    ] ifFalse:[
-        "/ the value should be in the right half.
-        rightSubtree isNil ifTrue:[
-            ^ nil
-        ].
-        rightSubtree := rightSubtree removeValue:oldValue using:compareOp sortBlock:sortBlock.
-    ].
-    ^ self. 
 ! !
 
 !BinaryTreeNode methodsFor:'printing'!
@@ -386,17 +337,20 @@
 !
 
 removeRightMostNode
-    |removedNode|
+    |right rr parent|
 
     rightSubtree isNil ifTrue:[
         self error:'should not happen'
     ].
-    rightSubtree rightSubtree notNil ifTrue:[
-        ^ rightSubtree removeRightMostNode.
+
+    parent := self.
+    right := rightSubtree.
+    [ (rr := right rightSubtree) notNil ] whileTrue:[
+        parent := right.
+        right := rr.
     ].
-    removedNode := rightSubtree.
-    rightSubtree := nil.
-    ^ removedNode
+    parent rightSubtree:(right leftSubtree).
+    ^ right.
 
     "
      |tree|
@@ -410,12 +364,69 @@
      Transcript showCR:(tree removeLeftRightMostNode). 
      Transcript showCR:tree.
     "
+!
+
+removeValue:oldValue using:compareOp sortBlock:sortBlock
+    "remove a value - returns a new treeNode, or nil if the value is not in the tree"
+
+    |thisIsMyNode newTop newLeft newRight|
+
+    "/ speed hack - avoids message sends (and also better inline caching)
+    compareOp == #== ifTrue:[
+        thisIsMyNode := (data == oldValue).
+    ] ifFalse:[
+        compareOp == #= ifTrue:[
+            thisIsMyNode := (data = oldValue).
+        ] ifFalse:[
+            thisIsMyNode := data perform:compareOp with:oldValue.
+        ].
+    ].
+
+    thisIsMyNode ifTrue:[
+        leftSubtree isNil ifTrue:[
+            ^ rightSubtree
+        ].
+        rightSubtree isNil ifTrue:[
+            ^ leftSubtree
+        ].
+        newTop := self removeLeftRightMostNode.
+        newTop leftSubtree:leftSubtree.
+        newTop rightSubtree:rightSubtree.
+        ^ newTop.
+    ].
+
+    (sortBlock value:oldValue value:data) ifTrue:[
+        "/ the value should be in the left part.
+        leftSubtree isNil ifTrue:[
+            ^ nil
+        ].
+        newLeft := leftSubtree removeValue:oldValue using:compareOp sortBlock:sortBlock.
+        newLeft isNil ifTrue:[
+            (leftSubtree data perform:compareOp with:oldValue) ifFalse:[
+                ^ nil
+            ].
+        ].
+        leftSubtree := newLeft.
+    ] ifFalse:[
+        "/ the value should be in the right part.
+        rightSubtree isNil ifTrue:[
+            ^ nil
+        ].
+        newRight := rightSubtree removeValue:oldValue using:compareOp sortBlock:sortBlock.
+        newRight isNil ifTrue:[
+            (rightSubtree data perform:compareOp with:oldValue) ifFalse:[
+                ^ nil
+            ].
+        ].
+        rightSubtree := newRight.
+    ].
+    ^ self. 
 ! !
 
 !BinaryTreeNode methodsFor:'queries'!
 
 depth
-    "Returns the depth of the binary list"
+    "Returns the depth of the binary tree"
 
     ^ self level - 1.
 !
@@ -462,12 +473,12 @@
         leftSubtree isNil ifTrue:[
             ^ false
         ].
-        ^ leftSubtree includesIdenticalValue:aValue.
+        ^ leftSubtree includesValue:aValue sortBlock:sortBlock.
     ].
     rightSubtree isNil ifTrue:[
         ^ false
     ].
-    ^ rightSubtree includesIdenticalValue:aValue.
+    ^ rightSubtree includesValue:aValue sortBlock:sortBlock.
 !
 
 isEmpty
@@ -490,7 +501,7 @@
 !
 
 level
-    "Returns the depth of the binary tree"
+    "Returns the level of the binary tree (0 for leafs)"
 
     |l|
 
@@ -512,17 +523,15 @@
 !
 
 size
-    "Returns the size of the binary tree by traversing each element inorder"
-
-    |count|
+    "Returns the size of the binary tree"
 
-    count := 0.
-    self inOrderDo: [:each | count := count + 1].
-    ^ count
+    ^ 1
+    + (leftSubtree isNil ifTrue: [0] ifFalse:[leftSubtree size])
+    + (rightSubtree isNil ifTrue: [0] ifFalse:[rightSubtree size])
 ! !
 
 !BinaryTreeNode class methodsFor:'documentation'!
 
 version
-    ^ '$Header: /cvs/stx/stx/libbasic2/BinaryTreeNode.st,v 1.1 2009-09-28 09:35:24 cg Exp $'
+    ^ '$Header: /cvs/stx/stx/libbasic2/BinaryTreeNode.st,v 1.2 2009-09-28 16:16:58 cg Exp $'
 ! !