rares (owner)

Revisions

gist: 101382 Download_button fork
public
Public Clone URL: git://gist.github.com/101382.git
Embed All Files: show embed
Java #
raw 
1
2
3
4
5
6
7
8
9
10
11
12
13

package com.robares.wp.scala.collections
 
/**
 * A node in a ternary tree.
 * All nodes must to be created
 * with a value and a reference to a parent.
 */
abstract class NodeBase
case class Node(value: Int,  parent: Node) extends NodeBase {
  var lo: Node = _
  var eq: Node = _
  var hi: Node = _
}
Java #
raw 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

package com.robares.wp.scala.collections
 
class TernaryTree {
 
  private var rootNode: Node = null
  
  def root: Node = rootNode
  
  def add(value: Int): Node = {
    if(root == null) rootNode = Node(value, null)
    addToTree(rootNode, value)
  }
  def +(value: Int): Node = add(value)
  
  def find(value: Int): Node = findInTree(root, value)
  
  protected def addToTree(node: Node, value: Int): Node = node match {
    case Node(v, _) if value == v => 
      if(node.eq == null) node.eq = Node(value, node)
      node.eq
    case Node(v, _) if value < v => 
      if(node.lo == null) node.lo = Node(value, node)
      addToTree(node.lo, value)			      
    case Node(v, _) if value > v => 
      if(node.hi == null) node.hi = Node(value, node)
      addToTree(node.hi, value)      
    case _ => null
  }
  
  protected def findInTree(node: Node, value: Int): Node = node match {
    case null => null
    case Node(v, _) if value == v => node
    case Node(v, _) if value < v => findInTree(node.lo, value)    
    case Node(v, _) if value > v => findInTree(node.hi, value)
    case _ => null
  }             
 
}
Java #
raw 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

package com.robares.wp.scala
 
import org.specs._
import org.specs.matcher.Matcher
 
import com.robares.wp.scala.collections.Node
 
import org.specs.runner.JUnit4
 
class NodeSpecTest extends JUnit4(NodeSpec)
object NodeSpec extends Specification {
 
  "A Node" should {	
    var node : Node = null;
    
    doBefore {
      node = Node(4, null)
    }
 
    "be creatable via apply" in {
      Node(9876, null) mustNot beNull
    }
 
    "make its value available" in {
	  node.value must be(4)   
    }
 
    "default the lo node to Null" in {
      node.lo must beNull
    }
    
    "default the eq node to Null" in {
      node.eq must beNull
    }
    
    "default the hi node to Null" in {
      node.hi must beNull
    }
     
    "be able to add a subnode and read it's value" in {
      node.lo = Node(2, node)
      node.lo.value must be(2)
    }
    
  }
  
}
 
Java #
raw 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77

package com.robares.wp.scala
 
import org.specs._
import org.specs.matcher.Matcher
 
import com.robares.wp.scala.collections._
 
import org.specs.runner.JUnit4
 
class TernaryTreeSpecTest extends JUnit4(TernaryTreeSpec)
object TernaryTreeSpec extends Specification {
 
  "A TernaryTree" should {
    var tree : TernaryTree = null	
    
    doBefore {
      tree = new TernaryTree();
    }
    
    "make its root node available as Null without any nodes set" in {
      tree.root must beNull      
    }
    
    "return the root node once an initial node is added" in {
      tree add 3
      tree.root must notBeNull
    }
    
    "add nodes via the + operator" in {
      tree + 4
      tree.find(4).value must be(4)
    }
    
    "return the root value" in {
      tree add 5
      tree.find(5).value must be(5)
    }
    
    "return child nodes when added to a tree" in {
      tree add 5
      tree add 3
      tree.find(3) must notBeNull
    }
    
    "return null from find if the value is not present in the tree" in {
      tree add 5 
      tree.find(3) must beNull
    }
    
    //     5
    //    /|\    
    //   4 5 9
    //  /   /\
    //  2  7
    //  |
    //  2
    // added in this order: 5, 4, 9, 5, 7, 2, 2  
    "prove the question" in {
      tree add 5
      tree add 4
      tree add 9
      tree add 5
      tree add 7 
      tree add 2
      tree add 2
     
      tree.root.value must be(5)
      tree.root.lo.value must be(4)
      tree.root.eq.value must be(5)
      tree.root.hi.value must be(9)
      tree.root.hi.lo.value must be(7)
      tree.root.lo.lo.value must be(2) 
      tree.root.lo.lo.eq.value must be(2)
 
    }
  }
}