initial search tree set

3 files changed, 88 insertions, 19 deletions

diff --git a/Makefile b/Makefile
index 2a2a4ac..efce335 100644
--- a/Makefile
+++ b/Makefile
@@ -9,6 +9,7 @@ sortbench:
 	go test -run=xxx -bench=. ./sort | tee sortbench.out
 queuebench:
 	go test -run=xxx -bench=. ./queue | tee queuebench.out
+	go test -run=xxx -bench=. ./queue | tee queuebench.out
 profile:
 	go test -run=xxx -bench=BenchmarkQuickSort ./sort -memprofile memprofile.out -cpuprofile cpuprofile.out
 	go tool pprof cpuprofile.out
diff --git a/set/elementary.go b/set/elementary.go
index 63a3fd8..a9d367e 100644
--- a/set/elementary.go
+++ b/set/elementary.go
@@ -2,7 +2,7 @@ package set
 
 type ElementaryElem struct {
 	key  int
-	val  interface{}
+	val  int
 	next *ElementaryElem
 }
 
@@ -14,11 +14,11 @@ func NewElementary() *Elementary {
 	return &Elementary{}
 }
 
-func (s Elementary) Empty() bool {
+func (s *Elementary) Empty() bool {
 	return s.root == nil
 }
 
-func (s Elementary) Set(key int, val interface{}) {
+func (s *Elementary) Set(key int, val int) {
 	if s.Empty() {
 		s.root = &ElementaryElem{key, val, nil}
 		return
@@ -39,38 +39,41 @@ func (s Elementary) Set(key int, val interface{}) {
 	}
 }
 
-func (s Elementary) Get(key int) interface{} {
+func (s *Elementary) Get(key int) (int, error) {
 	elem := s.root
 
 	for elem != nil {
 		if elem.key == key {
-			return elem.val
+			return elem.val, nil
 		}
 		elem = elem.next
 	}
 
-	return nil
+	return 0, NotFound
 }
 
-func (s Elementary) Del(key int) interface{} {
+func (s *Elementary) Del(key int) (int, error) {
 	if s.Empty() {
-		return nil
+		return 0, NotFound
 	}
 
 	if s.root.key == key {
-		defer func() { s.root = nil }()
-		return s.root.val
+		defer func() {
+			s.root = s.root.next
+		}()
+		return s.root.val, nil
 	}
 
 	elem := s.root
-
 	for elem.next != nil {
 		if elem.next.key == key {
-			defer func() { elem.next = elem.next.next }()
-			return elem.next.val
+			defer func() {
+				elem.next = elem.next.next
+			}()
+			return elem.next.val, nil
 		}
 		elem = elem.next
 	}
 
-	return nil
+	return 0, NotFound
 }
diff --git a/set/tree.go b/set/tree.go
index 2f34cc8..d4f7b7d 100644
--- a/set/tree.go
+++ b/set/tree.go
@@ -1,7 +1,72 @@
-package tree
+package set
 
-type Tree interface {
-	Empty() bool
-	Insert(key int, val interface{})
-	Search(key int) interface{}
+type node struct {
+	key   int
+	val   int
+	left  *node
+	right *node
 }
+
+type Tree struct {
+	root *node
+}
+
+func NewTree() *Tree {
+	return &Tree{}
+}
+
+func (t *Tree) Empty() bool {
+	return t.root == nil
+}
+
+func (t *Tree) set(n *node, key, val int) {
+	switch {
+	case key < n.key:
+		if n.left == nil {
+			n.left = &node{key, val, nil, nil}
+			return
+		}
+		t.set(n.left, key, val)
+
+	case key > n.key:
+		if n.right == nil {
+			n.right = &node{key, val, nil, nil}
+			return
+		}
+		t.set(n.right, key, val)
+	default:
+		// Val is already in the tree
+	}
+}
+
+func (t *Tree) Set(key, val int) {
+	if t.Empty() {
+		t.root = &node{key, val, nil, nil}
+		return
+	}
+	t.set(t.root, key, val)
+}
+
+func (t *Tree) get(n *node, key int) (int, error) {
+	if n == nil {
+		return 0, NotFound
+	}
+
+	switch {
+	case key < n.key:
+		return t.get(n.left, key)
+	case key > n.key:
+		return t.get(n.right, key)
+	default:
+		return n.val, nil
+	}
+}
+
+func (t *Tree) Get(key int) (int, error) {
+	return t.get(t.root, key)
+}
+
+/*
+	Get(key int) (int, error)
+	Del(key int) (int, error)
+*/