initial generics

7 files changed, 149 insertions, 130 deletions

diff --git a/search/bst.go b/search/bst.go
index a1d2fe0..2dd0b5b 100644
--- a/search/bst.go
+++ b/search/bst.go
@@ -1,57 +1,60 @@
 package search
 
-import "fmt"
-
-type node struct {
-	key   int
-	val   int
-	left  *node
-	right *node
+import (
+	"fmt"
+	"codeberg.org/snonux/algorithms/ds"
+)
+
+type node[K, V ds.Number] struct {
+	key   K
+	val   V
+	left  *node[K,V]
+	right *node[K,V]
 }
 
-func (n *node) String() string {
-	recurse := func(n *node) string {
+func (n *node[K,V]) String() string {
+	recurse := func(n *node[K,V]) string {
 		if n == nil {
 			return ""
 		}
 		return n.String()
 	}
 
-	return fmt.Sprintf("node{%d:%d,%s,%s}",
+	return fmt.Sprintf("node[K,V]{%d:%d,%s,%s}",
 		n.key,
 		n.val,
 		recurse(n.left),
 		recurse(n.right))
 }
 
-type BST struct {
-	root *node
+type BST[K,V ds.Number] struct {
+	root *node[K,V]
 	size int
 }
 
-func NewBST() *BST {
-	return &BST{}
+func NewBST[K,V ds.Number]() *BST[K,V] {
+	return &BST[K,V]{}
 }
 
-func (t *BST) String() string {
+func (t *BST[K,V]) String() string {
 	if t.Empty() {
-		return "BST{}"
+		return "BST[K,V]{}"
 	}
 
-	return fmt.Sprintf("BST{%s}", t.root)
+	return fmt.Sprintf("BST[K,V]{%s}", t.root)
 }
 
-func (t *BST) Empty() bool {
+func (t *BST[K,V]) Empty() bool {
 	return t.root == nil
 }
 
-func (t *BST) Size() int {
+func (t *BST[K,V]) Size() int {
 	return t.size
 }
 
-func (t *BST) Put(key, val int) {
+func (t *BST[K,V]) Put(key K, val V) {
 	if t.Empty() {
-		t.root = &node{key, val, nil, nil}
+		t.root = &node[K,V]{key, val, nil, nil}
 		t.size++
 		return
 	}
@@ -61,7 +64,7 @@ func (t *BST) Put(key, val int) {
 		// key already in the tree
 		return
 	case NotFound:
-		*ptr = &node{key, val, nil, nil}
+		*ptr = &node[K,V]{key, val, nil, nil}
 		t.size++
 		return
 	default:
@@ -69,7 +72,7 @@ func (t *BST) Put(key, val int) {
 	}
 }
 
-func (t *BST) Get(key int) (int, error) {
+func (t *BST[K,V]) Get(key K) (V, error) {
 	_, n, err := t.search(&t.root, key)
 	if err != nil {
 		return 0, err
@@ -77,7 +80,7 @@ func (t *BST) Get(key int) (int, error) {
 	return n.val, nil
 }
 
-func (t *BST) Del(key int) (int, error) {
+func (t *BST[K,V]) Del(key K) (V, error) {
 	ptr, n, err := t.search(&t.root, key)
 	if err != nil {
 		return 0, err
@@ -119,7 +122,7 @@ func (t *BST) Del(key int) (int, error) {
 	}
 }
 
-func (t *BST) search(ptr **node, key int) (**node, *node, error) {
+func (t *BST[K,V]) search(ptr **node[K,V], key K) (**node[K,V], *node[K,V], error) {
 	n := *ptr
 	if n == nil {
 		return ptr, nil, NotFound
@@ -135,7 +138,7 @@ func (t *BST) search(ptr **node, key int) (**node, *node, error) {
 	}
 }
 
-func (t *BST) deleteMin(ptr **node) (*node, error) {
+func (t *BST[K,V]) deleteMin(ptr **node[K,V]) (*node[K,V], error) {
 	ptr, n, err := t.min(ptr)
 	if err != nil {
 		return nil, err
@@ -146,7 +149,7 @@ func (t *BST) deleteMin(ptr **node) (*node, error) {
 	return n, nil
 }
 
-func (t *BST) min(ptr **node) (**node, *node, error) {
+func (t *BST[K,V]) min(ptr **node[K,V]) (**node[K,V], *node[K,V], error) {
 	n := *ptr
 	if n == nil {
 		return nil, nil, NotFound
diff --git a/search/elementary.go b/search/elementary.go
index ed00159..abfc7de 100644
--- a/search/elementary.go
+++ b/search/elementary.go
@@ -1,31 +1,35 @@
 package search
 
-type ElementaryElem struct {
-	key  int
-	val  int
-	next *ElementaryElem
+import (
+	"codeberg.org/snonux/algorithms/ds"
+)
+
+type ElementaryElem[K, V ds.Number] struct {
+	key  K
+	val  V
+	next *ElementaryElem[K,V]
 }
 
-type Elementary struct {
-	root *ElementaryElem
+type Elementary[K,V ds.Number] struct {
+	root *ElementaryElem[K,V]
 	size int
 }
 
-func NewElementary() *Elementary {
-	return &Elementary{}
+func NewElementary[K, V ds.Number]() *Elementary[K,V] {
+	return &Elementary[K,V]{}
 }
 
-func (s *Elementary) Empty() bool {
+func (s *Elementary[K,V]) Empty() bool {
 	return s.root == nil
 }
 
-func (s *Elementary) Size() int {
+func (s *Elementary[K,V]) Size() int {
 	return s.size
 }
 
-func (s *Elementary) Put(key int, val int) {
+func (s *Elementary[K,V]) Put(key K, val V) {
 	if s.Empty() {
-		s.root = &ElementaryElem{key, val, nil}
+		s.root = &ElementaryElem[K,V]{key, val, nil}
 		s.size++
 		return
 	}
@@ -38,7 +42,7 @@ func (s *Elementary) Put(key int, val int) {
 			return
 		}
 		if elem.next == nil {
-			elem.next = &ElementaryElem{key, val, nil}
+			elem.next = &ElementaryElem[K,V]{key, val, nil}
 			s.size++
 			return
 		}
@@ -46,7 +50,7 @@ func (s *Elementary) Put(key int, val int) {
 	}
 }
 
-func (s *Elementary) Get(key int) (int, error) {
+func (s *Elementary[K,V]) Get(key K) (V, error) {
 	elem := s.root
 
 	for elem != nil {
@@ -59,7 +63,7 @@ func (s *Elementary) Get(key int) (int, error) {
 	return 0, NotFound
 }
 
-func (s *Elementary) Del(key int) (int, error) {
+func (s *Elementary[K,V]) Del(key K) (V, error) {
 	if s.Empty() {
 		return 0, NotFound
 	}
diff --git a/search/gomap.go b/search/gomap.go
index 6749b0d..c8912d9 100644
--- a/search/gomap.go
+++ b/search/gomap.go
@@ -1,35 +1,39 @@
 package search
 
-type GoMap map[int]int
+import (
+	"codeberg.org/snonux/algorithms/ds"
+)
 
-func NewGoMap() GoMap {
-	return make(GoMap)
+type GoMap[K,V ds.Number] map[K]V
+
+func NewGoMap[K,V ds.Number] () GoMap[K,V] {
+	return make(GoMap[K,V])
 }
 
-func (m GoMap) Empty() bool {
+func (m GoMap[K,V]) Empty() bool {
 	return m.Size() == 0
 }
 
-func (m GoMap) Size() int {
+func (m GoMap[K,V]) Size() int {
 	return len(m)
 }
 
-func (m GoMap) Put(key, val int) {
+func (m GoMap[K,V]) Put(key K, val V) {
 	m[key] = val
 }
 
-func (m GoMap) Get(key int) (int, error) {
+func (m GoMap[K,V]) Get(key K) (V, error) {
 	val, ok := m[key]
 	if !ok {
-		return -1, NotFound
+		return 0, NotFound
 	}
 	return val, nil
 }
 
-func (m GoMap) Del(key int) (int, error) {
+func (m GoMap[K,V]) Del(key K) (V, error) {
 	val, ok := m[key]
 	if !ok {
-		return -1, NotFound
+		return 0, NotFound
 	}
 	delete(m, key)
 	return val, nil
diff --git a/search/hash.go b/search/hash.go
index 717a825..0b41b6b 100644
--- a/search/hash.go
+++ b/search/hash.go
@@ -1,39 +1,43 @@
 package search
 
-type Hash struct {
-	buckets  []*Elementary
+import (
+	"codeberg.org/snonux/algorithms/ds"
+)
+
+type Hash[K ds.Integer,V ds.Number] struct {
+	buckets  []*Elementary[K,V]
 	capacity int
 	size     int
 }
 
-func NewHash(capacity int) *Hash {
-	return &Hash{
-		buckets:  make([]*Elementary, capacity),
+func NewHash[K ds.Integer,V ds.Number](capacity int) *Hash[K,V] {
+	return &Hash[K,V]{
+		buckets:  make([]*Elementary[K,V], capacity),
 		capacity: capacity,
 	}
 }
 
-func (h *Hash) Empty() bool {
+func (h *Hash[K,V]) Empty() bool {
 	return h.Size() == 0
 }
 
-func (h *Hash) Size() int {
+func (h *Hash[K,V]) Size() int {
 	return h.size
 }
 
-func (h *Hash) hash(key int) int {
+func (h *Hash[K,V]) hash(key K) int {
 	i := key + key*2 + key<<10 + key>>2
 	if i < 0 {
 		i = -i
 	}
-	return i % h.capacity
+	return int(i) % h.capacity
 }
 
-func (h *Hash) Put(key int, val int) {
+func (h *Hash[K,V]) Put(key K, val V) {
 	i := h.hash(key)
 
 	if h.buckets[i] == nil {
-		elem := NewElementary()
+		elem := NewElementary[K,V]()
 		elem.Put(key, val)
 		h.buckets[i] = elem
 		return
@@ -42,21 +46,21 @@ func (h *Hash) Put(key int, val int) {
 	h.buckets[i].Put(key, val)
 }
 
-func (h *Hash) Get(key int) (int, error) {
+func (h *Hash[K,V]) Get(key K) (V, error) {
 	i := h.hash(key)
 
 	if h.buckets[i] == nil {
-		return -1, NotFound
+		return 0, NotFound
 	}
 
 	return h.buckets[i].Get(key)
 }
 
-func (h *Hash) Del(key int) (int, error) {
+func (h *Hash[K,V]) Del(key K) (V, error) {
 	i := h.hash(key)
 
 	if h.buckets[i] == nil {
-		return -1, NotFound
+		return 0, NotFound
 	}
 
 	return h.buckets[i].Del(key)
diff --git a/search/redblackbst.go b/search/redblackbst.go
index 856d562..8f699eb 100644
--- a/search/redblackbst.go
+++ b/search/redblackbst.go
@@ -2,6 +2,7 @@ package search
 
 import (
 	"fmt"
+	"codeberg.org/snonux/algorithms/ds"
 )
 
 type linkColor bool
@@ -11,19 +12,19 @@ const (
 	black linkColor = false
 )
 
-type rbNode struct {
-	key      int
-	val      int
+type rbNode[K,V ds.Number] struct {
+	key      K
+	val      V
 	color    linkColor
 	capacity int
-	left     *rbNode
-	right    *rbNode
+	left     *rbNode[K,V]
+	right    *rbNode[K,V]
 	// Just mark a node as deleted if deleted. Not fully implemented in lecture.
 	deleted bool
 }
 
-func (n *rbNode) String() string {
-	recurse := func(n *rbNode) string {
+func (n *rbNode[K,V]) String() string {
+	recurse := func(n *rbNode[K,V]) string {
 		if n == nil {
 			return ""
 		}
@@ -34,7 +35,7 @@ func (n *rbNode) String() string {
 	if n.color == black {
 		color = "black"
 	}
-	return fmt.Sprintf("rbNode{%v;%d:%d,%s,%d,%s,%s}",
+	return fmt.Sprintf("rbNode[K,V]{%v;%d:%d,%s,%d,%s,%s}",
 		n.deleted,
 		n.key,
 		n.val,
@@ -45,61 +46,61 @@ func (n *rbNode) String() string {
 	)
 }
 
-func (n *rbNode) isRed() bool {
+func (n *rbNode[K,V]) isRed() bool {
 	if n == nil {
 		return false
 	}
 	return n.color == red
 }
 
-func (n *rbNode) Capacity() int {
+func (n *rbNode[K,V]) Capacity() int {
 	if n == nil {
 		return 0
 	}
 	return n.capacity
 }
 
-type RedBlackBST struct {
-	root *rbNode
+type RedBlackBST[K,V ds.Number] struct {
+	root *rbNode[K,V]
 	size int
 }
 
-func NewRedBlackBST() *RedBlackBST {
-	return &RedBlackBST{}
+func NewRedBlackBST[K,V ds.Number]() *RedBlackBST[K,V] {
+	return &RedBlackBST[K,V]{}
 }
 
-func (t *RedBlackBST) String() string {
+func (t *RedBlackBST[K,V]) String() string {
 	if t.Empty() {
-		return fmt.Sprintf("RedBlackBST{%d:%d}", t.Size(), t.Capacity())
+		return fmt.Sprintf("RedBlackBST[K,V]{%d:%d}", t.Size(), t.Capacity())
 	}
 
-	return fmt.Sprintf("RedBlackBST{%d:%d;%s}", t.Size(), t.Capacity(), t.root)
+	return fmt.Sprintf("RedBlackBST[K,V]{%d:%d;%s}", t.Size(), t.Capacity(), t.root)
 }
 
-func (t *RedBlackBST) Size() int {
+func (t *RedBlackBST[K,V]) Size() int {
 	return t.size
 }
 
-func (t *RedBlackBST) Empty() bool {
+func (t *RedBlackBST[K,V]) Empty() bool {
 	return t.Size() == 0
 }
 
-func (t *RedBlackBST) Capacity() int {
+func (t *RedBlackBST[K,V]) Capacity() int {
 	if t.root == nil {
 		return 0
 	}
 	return t.root.capacity
 }
 
-func (t *RedBlackBST) Put(key, val int) {
+func (t *RedBlackBST[K,V]) Put(key K, val V) {
 	t.root = t.put(t.root, key, val)
 	t.root.color = black
 }
 
-func (t *RedBlackBST) put(n *rbNode, key, val int) *rbNode {
+func (t *RedBlackBST[K,V]) put(n *rbNode[K,V], key K, val V) *rbNode[K,V] {
 	if n == nil {
 		t.size++
-		return &rbNode{key, val, red, 1, nil, nil, false}
+		return &rbNode[K,V]{key, val, red, 1, nil, nil, false}
 	}
 
 	switch {
@@ -128,11 +129,11 @@ func (t *RedBlackBST) put(n *rbNode, key, val int) *rbNode {
 	return n
 }
 
-func (t *RedBlackBST) Get(key int) (int, error) {
+func (t *RedBlackBST[K,V]) Get(key K) (V, error) {
 	return t.get(t.root, key)
 }
 
-func (t *RedBlackBST) get(n *rbNode, key int) (int, error) {
+func (t *RedBlackBST[K,V]) get(n *rbNode[K,V], key K) (V, error) {
 	if n == nil {
 		return 0, NotFound
 	}
@@ -150,11 +151,11 @@ func (t *RedBlackBST) get(n *rbNode, key int) (int, error) {
 	}
 }
 
-func (t *RedBlackBST) Del(key int) (int, error) {
+func (t *RedBlackBST[K,V]) Del(key K) (V, error) {
 	return t.del(t.root, key)
 }
 
-func (t *RedBlackBST) del(n *rbNode, key int) (int, error) {
+func (t *RedBlackBST[K,V]) del(n *rbNode[K,V], key K) (V, error) {
 	if n == nil {
 		return 0, NotFound
 	}
@@ -171,12 +172,12 @@ func (t *RedBlackBST) del(n *rbNode, key int) (int, error) {
 		t.size--
 		n.deleted = true
 		val := n.val
-		n.val = -1
+		n.val = 0 
 		return val, nil
 	}
 }
 
-func (t *RedBlackBST) rotateLeft(n *rbNode) *rbNode {
+func (t *RedBlackBST[K,V]) rotateLeft(n *rbNode[K,V]) *rbNode[K,V] {
 	x := n.right
 	n.right = x.left
 	x.left = n
@@ -190,7 +191,7 @@ func (t *RedBlackBST) rotateLeft(n *rbNode) *rbNode {
 	return x
 }
 
-func (t *RedBlackBST) rotateRight(n *rbNode) *rbNode {
+func (t *RedBlackBST[K,V]) rotateRight(n *rbNode[K,V]) *rbNode[K,V] {
 	x := n.left
 	n.left = x.right
 	x.right = n
@@ -204,7 +205,7 @@ func (t *RedBlackBST) rotateRight(n *rbNode) *rbNode {
 	return x
 }
 
-func (t *RedBlackBST) flipColors(n *rbNode) {
+func (t *RedBlackBST[K,V]) flipColors(n *rbNode[K,V]) {
 	n.color = red
 	n.left.color = black
 	n.right.color = black
diff --git a/search/search_test.go b/search/search_test.go
index 8b46f65..ebd0a01 100644
--- a/search/search_test.go
+++ b/search/search_test.go
@@ -17,41 +17,41 @@ var benchResult int
 
 func TestElementary(t *testing.T) {
 	for i := minLength; i <= maxLength; i *= factor {
-		test(NewElementary(), i, t)
+		test[int,int](NewElementary[int,int](), i, t)
 	}
 }
 
 func TestBST(t *testing.T) {
 	for i := minLength; i <= maxLength; i *= factor {
-		test(NewBST(), i, t)
+		test[int,int](NewBST[int,int](), i, t)
 	}
 }
 
 func TestRedBlackBST(t *testing.T) {
 	for i := minLength; i <= maxLength; i *= factor {
-		test(NewRedBlackBST(), i, t)
+		test[int,int](NewRedBlackBST[int,int](), i, t)
 	}
 }
 
 func TestHash(t *testing.T) {
 	for i := minLength; i <= maxLength; i *= factor {
-		test(NewHash(i*2), i, t)
+		test[int,int](NewHash[int,int](i*2), i, t)
 	}
 }
 
 func TestGoMap(t *testing.T) {
 	for i := minLength; i <= maxLength; i *= factor {
-		test(NewGoMap(), i, t)
+		test[int,int](NewGoMap[int,int](), 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)
+func test[K ds.Integer, V ds.Number](s Set[K,V], l int, t *testing.T) {
+	keys := ds.NewRandomArrayList[V](l, l)
+	randoms := ds.NewRandomArrayList[V](l, -1)
+	mapping := make(map[K]V, l)
 
-	get := func(key int, del bool) int {
-		var val int
+	get := func(key K, del bool) V {
+		var val V
 		var err error
 		switch {
 		case del:
@@ -78,10 +78,10 @@ func test(s Set, l int, t *testing.T) {
 		}
 		return val
 	}
-	testGet := func(key int) int { return get(key, false) }
-	testDel := func(key int) int { return get(key, true) }
+	testGet := func(key K) V { return get(key, false) }
+	testDel := func(key K) V { return get(key, true) }
 
-	testPut := func(key, val int) {
+	testPut := func(key K, val V) {
 		s.Put(key, val)
 		mapping[key] = val
 		//t.Log("Put", key, val)
@@ -89,7 +89,7 @@ func test(s Set, l int, t *testing.T) {
 	}
 
 	//t.Log("Put random key-values", l)
-	var prevKey int
+	var prevKey K
 	for _, key := range sort.Shuffle(keys) {
 		testPut(key, randoms[key])
 		testGet(prevKey)
@@ -107,42 +107,42 @@ func test(s Set, l int, t *testing.T) {
 }
 
 func BenchmarkElementary(t *testing.B) {
-	s := NewElementary()
+	s := NewElementary[int,int]()
 	for i := minLength; i <= maxLength; i *= factor {
-		benchmark(s, i, t)
+		benchmark[int,int](s, i, t)
 	}
 }
 
 func BenchmarkBST(t *testing.B) {
-	s := NewBST()
+	s := NewBST[int,int]()
 	for i := minLength; i <= maxLength; i *= factor {
-		benchmark(s, i, t)
+		benchmark[int,int](s, i, t)
 	}
 }
 
 func BenchmarkRedBlackBST(t *testing.B) {
-	s := NewRedBlackBST()
+	s := NewRedBlackBST[int,int]()
 	for i := minLength; i <= maxLength; i *= factor {
-		benchmark(s, i, t)
+		benchmark[int,int](s, i, t)
 	}
 }
 
 func BenchmarkHash(t *testing.B) {
-	s := NewHash(maxLength * 2)
+	s := NewHash[int,int](maxLength * 2)
 	for i := minLength; i <= maxLength; i *= factor {
-		benchmark(s, i, t)
+		benchmark[int,int](s, i, t)
 	}
 }
 
 func BenchmarkGoMap(t *testing.B) {
-	s := NewGoMap()
+	s := NewGoMap[int,int]()
 	for i := minLength; i <= maxLength; i *= factor {
-		benchmark(s, i, t)
+		benchmark[int,int](s, i, t)
 	}
 }
 
-func benchmark(s Set, l int, b *testing.B) {
-	list := ds.NewRandomArrayList(l, -1)
+func benchmark[K ds.Integer, V ds.Number](s Set[K,V], l int, b *testing.B) {
+	list := ds.NewRandomArrayList[V](l, -1)
 
 	b.Run(fmt.Sprintf("random(%d)", l), func(b *testing.B) {
 		b.ResetTimer()
diff --git a/search/set.go b/search/set.go
index ed5b442..58ac2fb 100644
--- a/search/set.go
+++ b/search/set.go
@@ -1,16 +1,19 @@
 package search
 
-import "fmt"
+import (
+	"fmt"
+	"codeberg.org/snonux/algorithms/ds"
+)
 
 var (
 	NotFound       = fmt.Errorf("could not find entry")
 	NotImplemented = fmt.Errorf("method not implemented")
 )
 
-type Set interface {
+type Set[K ds.Integer,V ds.Number] interface {
 	Empty() bool
 	Size() int
-	Put(key int, val int)
-	Get(key int) (int, error)
-	Del(key int) (int, error)
+	Put(key K, val V)
+	Get(key K) (V, error)
+	Del(key K) (V, error)
 }