rename set to search

5 files changed, 0 insertions, 400 deletions

diff --git a/set/balancedbst.go b/set/balancedbst.go
deleted file mode 100644
index 12673c5..0000000
--- a/set/balancedbst.go
+++ /dev/null
@@ -1,5 +0,0 @@
-package set
-
-func NewBalancedBST() *BST {
-	return NewBST()
-}
diff --git a/set/bst.go b/set/bst.go
deleted file mode 100644
index 0eecb9e..0000000
--- a/set/bst.go
+++ /dev/null
@@ -1,171 +0,0 @@
-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/set/elementary.go b/set/elementary.go
deleted file mode 100644
index a9d367e..0000000
--- a/set/elementary.go
+++ /dev/null
@@ -1,79 +0,0 @@
-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/set/set.go b/set/set.go
deleted file mode 100644
index 29bfad7..0000000
--- a/set/set.go
+++ /dev/null
@@ -1,15 +0,0 @@
-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/set/set_test.go b/set/set_test.go
deleted file mode 100644
index 098947d..0000000
--- a/set/set_test.go
+++ /dev/null
@@ -1,130 +0,0 @@
-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)
-		}
-	})
-}