From d28b47c43ef73efbe06f77acea077bee9ccec492 Mon Sep 17 00:00:00 2001 From: Paul Buetow Date: Sat, 5 Dec 2020 08:35:12 +0000 Subject: rename set to search --- set/balancedbst.go | 5 -- set/bst.go | 171 ----------------------------------------------------- set/elementary.go | 79 ------------------------- set/set.go | 15 ----- set/set_test.go | 130 ---------------------------------------- 5 files changed, 400 deletions(-) delete mode 100644 set/balancedbst.go delete mode 100644 set/bst.go delete mode 100644 set/elementary.go delete mode 100644 set/set.go delete mode 100644 set/set_test.go (limited to 'set') 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) - } - }) -} -- cgit v1.2.3