add Size to search interface and fix redblacktree tests

5 files changed, 71 insertions, 18 deletions

diff --git a/go.sum b/go.sum
new file mode 100644
index 0000000..4efbf80
--- /dev/null
+++ b/go.sum
@@ -0,0 +1,52 @@
+github.com/BurntSushi/toml v0.3.1/go.mod h1:xHWCNGjB5oqiDr8zfno3MHue2Ht5sIBksp03qcyfWMU=
+github.com/davecgh/go-spew v1.1.0/go.mod h1:J7Y8YcW2NihsgmVo/mv3lAwl/skON4iLHjSsI+c5H38=
+github.com/davecgh/go-spew v1.1.1/go.mod h1:J7Y8YcW2NihsgmVo/mv3lAwl/skON4iLHjSsI+c5H38=
+github.com/google/go-cmp v0.5.1/go.mod h1:v8dTdLbMG2kIc/vJvl+f65V22dbkXbowE6jgT/gNBxE=
+github.com/google/renameio v0.1.0/go.mod h1:KWCgfxg9yswjAJkECMjeO8J8rahYeXnNhOm40UhjYkI=
+github.com/kisielk/gotool v1.0.0/go.mod h1:XhKaO+MFFWcvkIS/tQcRk01m1F5IRFswLeQ+oQHNcck=
+github.com/kr/pretty v0.1.0/go.mod h1:dAy3ld7l9f0ibDNOQOHHMYYIIbhfbHSm3C4ZsoJORNo=
+github.com/kr/pty v1.1.1/go.mod h1:pFQYn66WHrOpPYNljwOMqo10TkYh1fy3cYio2l3bCsQ=
+github.com/kr/text v0.1.0/go.mod h1:4Jbv+DJW3UT/LiOwJeYQe1efqtUx/iVham/4vfdArNI=
+github.com/pmezard/go-difflib v1.0.0/go.mod h1:iKH77koFhYxTK1pcRnkKkqfTogsbg7gZNVY4sRDYZ/4=
+github.com/rogpeppe/go-internal v1.3.0/go.mod h1:M8bDsm7K2OlrFYOpmOWEs/qY81heoFRclV5y23lUDJ4=
+github.com/rogpeppe/go-internal v1.5.2/go.mod h1:xXDCJY+GAPziupqXw64V24skbSoqbTEfhy4qGm1nDQc=
+github.com/rogpeppe/go-internal v1.6.1/go.mod h1:xXDCJY+GAPziupqXw64V24skbSoqbTEfhy4qGm1nDQc=
+github.com/sergi/go-diff v1.1.0/go.mod h1:STckp+ISIX8hZLjrqAeVduY0gWCT9IjLuqbuNXdaHfM=
+github.com/stretchr/objx v0.1.0/go.mod h1:HFkY916IF+rwdDfMAkV7OtwuqBVzrE8GR6GFx+wExME=
+github.com/stretchr/testify v1.4.0/go.mod h1:j7eGeouHqKxXV5pUuKE4zz7dFj8WfuZ+81PSLYec5m4=
+github.com/yuin/goldmark v1.1.32/go.mod h1:3hX8gzYuyVAZsxl0MRgGTJEmQBFcNTphYh9decYSb74=
+github.com/yuin/goldmark v1.2.1/go.mod h1:3hX8gzYuyVAZsxl0MRgGTJEmQBFcNTphYh9decYSb74=
+golang.org/x/crypto v0.0.0-20190308221718-c2843e01d9a2/go.mod h1:djNgcEr1/C05ACkg1iLfiJU5Ep61QUkGW8qpdssI0+w=
+golang.org/x/crypto v0.0.0-20190510104115-cbcb75029529/go.mod h1:yigFU9vqHzYiE8UmvKecakEJjdnWj3jj499lnFckfCI=
+golang.org/x/crypto v0.0.0-20191011191535-87dc89f01550/go.mod h1:yigFU9vqHzYiE8UmvKecakEJjdnWj3jj499lnFckfCI=
+golang.org/x/crypto v0.0.0-20200622213623-75b288015ac9/go.mod h1:LzIPMQfyMNhhGPhUkYOs5KpL4U8rLKemX1yGLhDgUto=
+golang.org/x/mod v0.0.0-20190513183733-4bf6d317e70e/go.mod h1:mXi4GBBbnImb6dmsKGUJ2LatrhH/nqhxcFungHvyanc=
+golang.org/x/mod v0.3.0/go.mod h1:s0Qsj1ACt9ePp/hMypM3fl4fZqREWJwdYDEqhRiZZUA=
+golang.org/x/net v0.0.0-20190404232315-eb5bcb51f2a3/go.mod h1:t9HGtf8HONx5eT2rtn7q6eTqICYqUVnKs3thJo3Qplg=
+golang.org/x/net v0.0.0-20190620200207-3b0461eec859/go.mod h1:z5CRVTTTmAJ677TzLLGU+0bjPO0LkuOLi4/5GtJWs/s=
+golang.org/x/net v0.0.0-20200625001655-4c5254603344/go.mod h1:/O7V0waA8r7cgGh81Ro3o1hOxt32SMVPicZroKQ2sZA=
+golang.org/x/net v0.0.0-20200822124328-c89045814202/go.mod h1:/O7V0waA8r7cgGh81Ro3o1hOxt32SMVPicZroKQ2sZA=
+golang.org/x/sync v0.0.0-20190423024810-112230192c58/go.mod h1:RxMgew5VJxzue5/jJTE5uejpjVlOe/izrB70Jof72aM=
+golang.org/x/sync v0.0.0-20200625203802-6e8e738ad208/go.mod h1:RxMgew5VJxzue5/jJTE5uejpjVlOe/izrB70Jof72aM=
+golang.org/x/sys v0.0.0-20190215142949-d0b11bdaac8a/go.mod h1:STP8DvDyc/dI5b8T5hshtkjS+E42TnysNCUPdjciGhY=
+golang.org/x/sys v0.0.0-20190412213103-97732733099d/go.mod h1:h1NjWce9XRLGQEsW7wpKNCjG9DtNlClVuFLEZdDNbEs=
+golang.org/x/sys v0.0.0-20200323222414-85ca7c5b95cd/go.mod h1:h1NjWce9XRLGQEsW7wpKNCjG9DtNlClVuFLEZdDNbEs=
+golang.org/x/text v0.3.0/go.mod h1:NqM8EUOU14njkJ3fqMW+pc6Ldnwhi/IjpwHt7yyuwOQ=
+golang.org/x/tools v0.0.0-20191119224855-298f0cb1881e/go.mod h1:b+2E5dAYhXwXZwtnZ6UAqBI28+e2cm9otk0dWdXHAEo=
+golang.org/x/tools v0.0.0-20191130070609-6e064ea0cf2d/go.mod h1:b+2E5dAYhXwXZwtnZ6UAqBI28+e2cm9otk0dWdXHAEo=
+golang.org/x/tools v0.0.0-20200731060945-b5fad4ed8dd6/go.mod h1:njjCfa9FT2d7l9Bc6FUM5FLjQPp3cFF28FI3qnDFljA=
+golang.org/x/tools v0.0.0-20201028153306-37f0764111ff/go.mod h1:z6u4i615ZeAfBE4XtMziQW1fSVJXACjjbWkB/mvPzlU=
+golang.org/x/tools/gopls v0.5.2/go.mod h1:Ye30ua0XTIpPhh5d9Mdz5ohQchW2pCnpwCj24FWNw9g=
+golang.org/x/xerrors v0.0.0-20190717185122-a985d3407aa7/go.mod h1:I/5z698sn9Ka8TeJc9MKroUUfqBBauWjQqLJ2OPfmY0=
+golang.org/x/xerrors v0.0.0-20191011141410-1b5146add898/go.mod h1:I/5z698sn9Ka8TeJc9MKroUUfqBBauWjQqLJ2OPfmY0=
+golang.org/x/xerrors v0.0.0-20191204190536-9bdfabe68543/go.mod h1:I/5z698sn9Ka8TeJc9MKroUUfqBBauWjQqLJ2OPfmY0=
+golang.org/x/xerrors v0.0.0-20200804184101-5ec99f83aff1/go.mod h1:I/5z698sn9Ka8TeJc9MKroUUfqBBauWjQqLJ2OPfmY0=
+gopkg.in/check.v1 v0.0.0-20161208181325-20d25e280405/go.mod h1:Co6ibVJAznAaIkqp8huTwlJQCZ016jof/cbN4VW5Yz0=
+gopkg.in/check.v1 v1.0.0-20180628173108-788fd7840127/go.mod h1:Co6ibVJAznAaIkqp8huTwlJQCZ016jof/cbN4VW5Yz0=
+gopkg.in/check.v1 v1.0.0-20190902080502-41f04d3bba15/go.mod h1:Co6ibVJAznAaIkqp8huTwlJQCZ016jof/cbN4VW5Yz0=
+gopkg.in/errgo.v2 v2.1.0/go.mod h1:hNsd1EY+bozCKY1Ytp96fpM3vjJbqLJn88ws8XvfDNI=
+gopkg.in/yaml.v2 v2.2.2/go.mod h1:hI93XBmqTisBFMUTm0b8Fm+jr3Dg1NNxqwp+5A1VGuI=
+gopkg.in/yaml.v2 v2.2.4/go.mod h1:hI93XBmqTisBFMUTm0b8Fm+jr3Dg1NNxqwp+5A1VGuI=
+honnef.co/go/tools v0.0.1-2020.1.5/go.mod h1:X/FiERA/W4tHapMX5mGpAtMSVEeEUOyHaw9vFzvIQ3k=
+mvdan.cc/gofumpt v0.0.0-20200802201014-ab5a8192947d/go.mod h1:bzrjFmaD6+xqohD3KYP0H2FEuxknnBmyyOxdhLdaIws=
+mvdan.cc/xurls/v2 v2.2.0/go.mod h1:EV1RMtya9D6G5DMYPGD8zTQzaHet6Jh8gFlRgGRJeO8=
diff --git a/search/bst.go b/search/bst.go
index b1d12bc..a1d2fe0 100644
--- a/search/bst.go
+++ b/search/bst.go
@@ -26,6 +26,7 @@ func (n *node) String() string {
 
 type BST struct {
 	root *node
+	size int
 }
 
 func NewBST() *BST {
@@ -44,9 +45,14 @@ func (t *BST) Empty() bool {
 	return t.root == nil
 }
 
+func (t *BST) Size() int {
+	return t.size
+}
+
 func (t *BST) Put(key, val int) {
 	if t.Empty() {
 		t.root = &node{key, val, nil, nil}
+		t.size++
 		return
 	}
 	ptr, _, err := t.search(&t.root, key)
@@ -56,6 +62,7 @@ func (t *BST) Put(key, val int) {
 		return
 	case NotFound:
 		*ptr = &node{key, val, nil, nil}
+		t.size++
 		return
 	default:
 		panic(err)
@@ -75,6 +82,7 @@ func (t *BST) Del(key int) (int, error) {
 	if err != nil {
 		return 0, err
 	}
+	t.size--
 
 	// Case 1: n is leaf node
 	// Case 2: n has one child
@@ -152,20 +160,3 @@ func (t *BST) min(ptr **node) (**node, *node, error) {
 		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
index b522cd0..ed00159 100644
--- a/search/elementary.go
+++ b/search/elementary.go
@@ -8,6 +8,7 @@ type ElementaryElem struct {
 
 type Elementary struct {
 	root *ElementaryElem
+	size int
 }
 
 func NewElementary() *Elementary {
@@ -18,9 +19,14 @@ func (s *Elementary) Empty() bool {
 	return s.root == nil
 }
 
+func (s *Elementary) Size() int {
+	return s.size
+}
+
 func (s *Elementary) Put(key int, val int) {
 	if s.Empty() {
 		s.root = &ElementaryElem{key, val, nil}
+		s.size++
 		return
 	}
 
@@ -33,6 +39,7 @@ func (s *Elementary) Put(key int, val int) {
 		}
 		if elem.next == nil {
 			elem.next = &ElementaryElem{key, val, nil}
+			s.size++
 			return
 		}
 		elem = elem.next
@@ -61,6 +68,7 @@ func (s *Elementary) Del(key int) (int, error) {
 		defer func() {
 			s.root = s.root.next
 		}()
+		s.size--
 		return s.root.val, nil
 	}
 
@@ -70,6 +78,7 @@ func (s *Elementary) Del(key int) (int, error) {
 			defer func() {
 				elem.next = elem.next.next
 			}()
+			s.size--
 			return elem.next.val, nil
 		}
 		elem = elem.next
diff --git a/search/redblackbst.go b/search/redblackbst.go
index 6644aea..856d562 100644
--- a/search/redblackbst.go
+++ b/search/redblackbst.go
@@ -110,8 +110,8 @@ func (t *RedBlackBST) put(n *rbNode, key, val int) *rbNode {
 	default:
 		if n.deleted {
 			n.deleted = false
+			t.size++
 		}
-		t.size++
 		n.val = val
 	}
 
diff --git a/search/set.go b/search/set.go
index 17024ea..407ca44 100644
--- a/search/set.go
+++ b/search/set.go
@@ -9,6 +9,7 @@ var (
 
 type Put interface {
 	Empty() bool
+	Size() int
 	Put(key int, val int)
 	Get(key int) (int, error)
 	Del(key int) (int, error)