rename set to search

5 files changed, 400 insertions, 0 deletions

diff --git a/search/balancedbst.go b/search/balancedbst.go
new file mode 100644
index 0000000..12673c5
--- /dev/null
+++ b/search/balancedbst.go
@@ -0,0 +1,5 @@
+package set
+
+func NewBalancedBST() *BST {
+	return NewBST()
+}
diff --git a/search/bst.go b/search/bst.go
new file mode 100644
index 0000000..0eecb9e
--- /dev/null
+++ b/search/bst.go
@@ -0,0 +1,171 @@
+package set
+
+import "fmt"
+
+type node struct {
+	key   int
+	val   int
+	left  *node
+	right *node
+}
+
+func (n *node) String() string {
+	recurse := func(n *node) string {
+		if n == nil {
+			return ""
+		}
+		return n.String()
+	}
+
+	return fmt.Sprintf("node{%d:%d,%s,%s}",
+		n.key,
+		n.val,
+		recurse(n.left),
+		recurse(n.right))
+}
+
+type BST struct {
+	root *node
+}
+
+func NewBST() *BST {
+	return &BST{}
+}
+
+func (t *BST) String() string {
+	if t.Empty() {
+		return "BST{}"
+	}
+
+	return fmt.Sprintf("BST{%s}", t.root)
+}
+
+func (t *BST) Empty() bool {
+	return t.root == nil
+}
+
+func (t *BST) Set(key, val int) {
+	if t.Empty() {
+		t.root = &node{key, val, nil, nil}
+		return
+	}
+	ptr, _, err := t.search(&t.root, key)
+	switch err {
+	case nil:
+		// key already in the tree
+		return
+	case NotFound:
+		*ptr = &node{key, val, nil, nil}
+		return
+	default:
+		panic(err)
+	}
+}
+
+func (t *BST) Get(key int) (int, error) {
+	_, n, err := t.search(&t.root, key)
+	if err != nil {
+		return 0, err
+	}
+	return n.val, nil
+}
+
+func (t *BST) Del(key int) (int, error) {
+	ptr, n, err := t.search(&t.root, key)
+	if err != nil {
+		return 0, err
+	}
+
+	// Case 1: n is leaf node
+	// Case 2: n has one child
+	// Case 3: n has two childs
+
+	switch {
+	case n.left == nil:
+		if n.right == nil {
+			// I am a leaf node
+			*ptr = nil
+			return n.val, nil
+		}
+		// I have a right child
+		*ptr = n.right
+		return n.val, nil
+
+	case n.right == nil:
+		// I have a left child
+		*ptr = n.left
+		return n.val, nil
+	default:
+		// I have two children!
+
+		o, err := t.deleteMin(&n.right)
+		if err != nil {
+			return 0, err
+		}
+
+		o.left = n.left
+		o.right = n.right
+		*ptr = o
+
+		return n.val, nil
+	}
+}
+
+func (t *BST) search(ptr **node, key int) (**node, *node, error) {
+	n := *ptr
+	if n == nil {
+		return ptr, nil, NotFound
+	}
+
+	switch {
+	case key < n.key:
+		return t.search(&n.left, key)
+	case n.key < key:
+		return t.search(&n.right, key)
+	default:
+		return ptr, n, nil
+	}
+}
+
+func (t *BST) deleteMin(ptr **node) (*node, error) {
+	ptr, n, err := t.min(ptr)
+	if err != nil {
+		return nil, err
+	}
+
+	*ptr = n.right
+	n.right = nil
+	return n, nil
+}
+
+func (t *BST) min(ptr **node) (**node, *node, error) {
+	n := *ptr
+	if n == nil {
+		return nil, nil, NotFound
+	}
+
+	for {
+		if n.left == nil {
+			return ptr, n, nil
+		}
+		ptr = &n.left
+		n = *ptr
+	}
+}
+
+/*
+func (t *BST) max(ptr **node) (**node, *node, error) {
+	n := *ptr
+	if n == nil {
+		return nil, nil, NotFound
+	}
+
+	for {
+		if n.right == nil {
+			return ptr, n, nil
+		}
+		ptr = &n.right
+		n = *ptr
+	}
+}
+*/
diff --git a/search/elementary.go b/search/elementary.go
new file mode 100644
index 0000000..a9d367e
--- /dev/null
+++ b/search/elementary.go
@@ -0,0 +1,79 @@
+package set
+
+type ElementaryElem struct {
+	key  int
+	val  int
+	next *ElementaryElem
+}
+
+type Elementary struct {
+	root *ElementaryElem
+}
+
+func NewElementary() *Elementary {
+	return &Elementary{}
+}
+
+func (s *Elementary) Empty() bool {
+	return s.root == nil
+}
+
+func (s *Elementary) Set(key int, val int) {
+	if s.Empty() {
+		s.root = &ElementaryElem{key, val, nil}
+		return
+	}
+
+	elem := s.root
+
+	for {
+		if elem.key == key {
+			elem.val = val
+			return
+		}
+		if elem.next == nil {
+			elem.next = &ElementaryElem{key, val, nil}
+			return
+		}
+		elem = elem.next
+	}
+}
+
+func (s *Elementary) Get(key int) (int, error) {
+	elem := s.root
+
+	for elem != nil {
+		if elem.key == key {
+			return elem.val, nil
+		}
+		elem = elem.next
+	}
+
+	return 0, NotFound
+}
+
+func (s *Elementary) Del(key int) (int, error) {
+	if s.Empty() {
+		return 0, NotFound
+	}
+
+	if s.root.key == key {
+		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, nil
+		}
+		elem = elem.next
+	}
+
+	return 0, NotFound
+}
diff --git a/search/set.go b/search/set.go
new file mode 100644
index 0000000..29bfad7
--- /dev/null
+++ b/search/set.go
@@ -0,0 +1,15 @@
+package set
+
+import "fmt"
+
+var (
+	NotFound       = fmt.Errorf("could not find entry")
+	NotImplemented = fmt.Errorf("method not implemented")
+)
+
+type Set interface {
+	Empty() bool
+	Set(key int, val int)
+	Get(key int) (int, error)
+	Del(key int) (int, error)
+}
diff --git a/search/set_test.go b/search/set_test.go
new file mode 100644
index 0000000..098947d
--- /dev/null
+++ b/search/set_test.go
@@ -0,0 +1,130 @@
+package set
+
+import (
+	"fmt"
+	"testing"
+
+	"github.com/snonux/algorithms/ds"
+	"github.com/snonux/algorithms/sort"
+)
+
+const factor int = 10
+const minLength int = 1
+const maxLength int = 10000
+
+// Store results here to avoid compiler optimizations
+var benchResult int
+
+func TestElementary(t *testing.T) {
+	for i := minLength; i <= maxLength; i *= factor {
+		test(NewElementary(), i, t)
+	}
+}
+
+func TestBST(t *testing.T) {
+	for i := minLength; i <= maxLength; i *= factor {
+		test(NewBST(), i, t)
+	}
+}
+
+func test(s Set, l int, t *testing.T) {
+	keys := ds.NewRandomArrayList(l, l)
+	randoms := ds.NewRandomArrayList(l, -1)
+	mapping := make(map[int]int, l)
+
+	get := func(key int, del bool) int {
+		var val int
+		var err error
+		switch {
+		case del:
+			defer delete(mapping, key)
+			val, err = s.Del(key)
+			//t.Log("Del", key, val, err)
+		default:
+			val, err = s.Get(key)
+			//t.Log("Get", key, val, err)
+		}
+
+		if mVal, ok := mapping[key]; ok {
+			if err != nil {
+				t.Error("Could not get element", key, val, mVal, err)
+			}
+			if mVal != val {
+				t.Error("Got wrong value for element", key, val, mVal)
+			}
+			return val
+		}
+
+		if err == nil {
+			t.Error("Got element but expected not to", key, val)
+		}
+		return val
+	}
+	testGet := func(key int) int { return get(key, false) }
+	testDel := func(key int) int { return get(key, true) }
+
+	testSet := func(key, val int) {
+		s.Set(key, val)
+		mapping[key] = val
+		//t.Log("Set", key, val)
+		testGet(key)
+	}
+
+	t.Log("Set random key-values", l)
+	var prevKey int
+	for _, key := range sort.Shuffle(keys) {
+		testSet(key, randoms[key])
+		testGet(prevKey)
+		prevKey = key
+	}
+	t.Log("Del random key-values", l)
+	for _, key := range sort.Shuffle(keys) {
+		testDel(key)
+		testGet(prevKey)
+		prevKey = key
+	}
+	if !s.Empty() {
+		t.Error("Expected set to be empty", l)
+	}
+}
+
+func TestBalancedBST(t *testing.T) {
+	for i := minLength; i <= maxLength; i *= factor {
+		test(NewBalancedBST(), i, t)
+	}
+}
+
+func BenchmarkElementary(t *testing.B) {
+	s := NewElementary()
+	for i := minLength; i <= maxLength; i *= factor {
+		benchmark(s, i, t)
+	}
+}
+
+func BenchmarkBST(t *testing.B) {
+	s := NewBST()
+	for i := minLength; i <= maxLength; i *= factor {
+		benchmark(s, i, t)
+	}
+}
+
+func BenchmarkBalancedBST(t *testing.B) {
+	s := NewBalancedBST()
+	for i := minLength; i <= maxLength; i *= factor {
+		benchmark(s, i, t)
+	}
+}
+
+func benchmark(s Set, l int, b *testing.B) {
+	list := ds.NewRandomArrayList(l, -1)
+
+	b.Run(fmt.Sprintf("random(%d)", l), func(b *testing.B) {
+		b.ResetTimer()
+		for i, a := range list {
+			s.Set(a, i)
+		}
+		for _, a := range list {
+			benchResult, _ = s.Get(a)
+		}
+	})
+}