initial generics

24 files changed, 268 insertions, 234 deletions

diff --git a/ds/arraylist.go b/ds/arraylist.go
index feee14e..de27832 100644
--- a/ds/arraylist.go
+++ b/ds/arraylist.go
@@ -4,46 +4,54 @@ import (
 	"fmt"
 	"math/rand"
 	"strings"
+	"golang.org/x/exp/constraints"
 )
 
-// Idea: Once Go got generics use generics here instead of hard coded int type
-type ArrayList []int
+type Integer interface {
+	constraints.Integer
+}
+
+type Number interface {
+	constraints.Integer | constraints.Float
+}
+
+type ArrayList[V Number] []V
 
-func NewArrayList(l int) ArrayList {
-	return make(ArrayList, l)
+func NewArrayList[V Number](l int) ArrayList[V] {
+	return make(ArrayList[V], l)
 }
 
-func NewRandomArrayList(l, max int) ArrayList {
-	a := make(ArrayList, l)
+func NewRandomArrayList[V Number](l, max int) ArrayList[V] {
+	a := make(ArrayList[V], l)
 	for i := 0; i < l; i++ {
 		if max > 0 {
-			a[i] = rand.Intn(max)
+			a[i] = V(rand.Intn(max))
 			continue
 		}
-		a[i] = rand.Int()
+		a[i] = V(rand.Int())
 	}
 	return a
 }
 
-func NewAscendingArrayList(l int) ArrayList {
-	a := make(ArrayList, l)
+func NewAscendingArrayList[V Number](l int) ArrayList[V] {
+	a := make(ArrayList[V], l)
 	for i := 0; i < l; i++ {
-		a[i] = i
+		a[i] = V(i)
 	}
 	return a
 }
 
-func NewDescendingArrayList(l int) ArrayList {
-	a := make(ArrayList, l)
+func NewDescendingArrayList[V Number](l int) ArrayList[V] {
+	a := make(ArrayList[V], l)
 	j := l - 1
 	for i := 0; i < l; i++ {
-		a[i] = j
+		a[i] = V(j)
 		j--
 	}
 	return a
 }
 
-func (a ArrayList) FirstN(n int) string {
+func (a ArrayList[V]) FirstN(n int) string {
 	var sb strings.Builder
 	j := n
 
@@ -63,7 +71,7 @@ func (a ArrayList) FirstN(n int) string {
 	return sb.String()
 }
 
-func (a ArrayList) Sorted() bool {
+func (a ArrayList[V]) Sorted() bool {
 	for i := len(a) - 1; i > 0; i-- {
 		if a[i] < a[i-1] {
 			return false
@@ -72,7 +80,7 @@ func (a ArrayList) Sorted() bool {
 	return true
 }
 
-func (a ArrayList) Swap(i, j int) {
+func (a ArrayList[V]) Swap(i, j int) {
 	aux := a[i]
 	a[i] = a[j]
 	a[j] = aux
diff --git a/go.mod b/go.mod
index c233836..0d1a255 100644
--- a/go.mod
+++ b/go.mod
@@ -1,3 +1,5 @@
 module codeberg.org/snonux/algorithms
 
 go 1.19
+
+require golang.org/x/exp v0.0.0-20230321023759-10a507213a29 // indirect
diff --git a/go.sum b/go.sum
index e69de29..4555300 100644
--- a/go.sum
+++ b/go.sum
@@ -0,0 +1,2 @@
+golang.org/x/exp v0.0.0-20230321023759-10a507213a29 h1:ooxPy7fPvB4kwsA2h+iBNHkAbp/4JxTSwCmvdjEYmug=
+golang.org/x/exp v0.0.0-20230321023759-10a507213a29/go.mod h1:CxIveKay+FTh1D0yPZemJVgC/95VzuuOLq5Qi4xnoYc=
diff --git a/queue/elementarypriority.go b/queue/elementarypriority.go
index a0bbfba..391d948 100644
--- a/queue/elementarypriority.go
+++ b/queue/elementarypriority.go
@@ -4,26 +4,26 @@ import (
 	"codeberg.org/snonux/algorithms/ds"
 )
 
-type ElementaryPriority struct {
-	a ds.ArrayList
+type ElementaryPriority[T ds.Number] struct {
+	a ds.ArrayList[T]
 	// Initial capacity
 	capacity int
 }
 
-func NewElementaryPriority(capacity int) *ElementaryPriority {
-	return &ElementaryPriority{make(ds.ArrayList, 0, capacity), capacity}
+func NewElementaryPriority[T ds.Number](capacity int) *ElementaryPriority[T] {
+	return &ElementaryPriority[T]{make(ds.ArrayList[T], 0, capacity), capacity}
 }
 
-func (q *ElementaryPriority) Insert(a int) {
+func (q *ElementaryPriority[T]) Insert(a T) {
 	q.a = append(q.a, a)
 }
 
-func (q *ElementaryPriority) Max() (max int) {
+func (q *ElementaryPriority[T]) Max() (max T) {
 	_, max = q.max()
 	return
 }
 
-func (q *ElementaryPriority) DeleteMax() int {
+func (q *ElementaryPriority[T]) DeleteMax() T {
 	if q.Empty() {
 		return 0
 	}
@@ -37,19 +37,19 @@ func (q *ElementaryPriority) DeleteMax() int {
 	return max
 }
 
-func (q *ElementaryPriority) Empty() bool {
+func (q *ElementaryPriority[T]) Empty() bool {
 	return q.Size() == 0
 }
 
-func (q *ElementaryPriority) Size() int {
+func (q *ElementaryPriority[T]) Size() int {
 	return len(q.a)
 }
 
-func (q *ElementaryPriority) Clear() {
-	q.a = make(ds.ArrayList, 0, q.capacity)
+func (q *ElementaryPriority[T]) Clear() {
+	q.a = make(ds.ArrayList[T], 0, q.capacity)
 }
 
-func (q *ElementaryPriority) max() (ind, max int) {
+func (q *ElementaryPriority[T]) max() (ind int, max T) {
 	for i, a := range q.a {
 		if a > max {
 			ind, max = i, a
diff --git a/queue/heappriority.go b/queue/heappriority.go
index b607e2c..bfcae71 100644
--- a/queue/heappriority.go
+++ b/queue/heappriority.go
@@ -4,13 +4,13 @@ import (
 	"codeberg.org/snonux/algorithms/ds"
 )
 
-type HeapPriority struct {
-	ElementaryPriority
+type HeapPriority[T ds.Number] struct {
+	ElementaryPriority[T]
 }
 
-func NewHeapPriority(capacity int) *HeapPriority {
-	q := HeapPriority{
-		ElementaryPriority: ElementaryPriority{make(ds.ArrayList, 0, capacity), capacity},
+func NewHeapPriority[T ds.Number](capacity int) *HeapPriority[T] {
+	q := HeapPriority[T]{
+		ElementaryPriority: ElementaryPriority[T]{make(ds.ArrayList[T], 0, capacity), capacity},
 	}
 
 	// Index 0 unused
@@ -18,20 +18,20 @@ func NewHeapPriority(capacity int) *HeapPriority {
 	return &q
 }
 
-func (q *HeapPriority) Empty() bool {
+func (q *HeapPriority[T]) Empty() bool {
 	return q.Size() == 0
 }
 
-func (q *HeapPriority) Size() int {
+func (q *HeapPriority[T]) Size() int {
 	return len(q.a) - 1
 }
 
-func (q *HeapPriority) Insert(a int) {
+func (q *HeapPriority[T]) Insert(a T) {
 	q.a = append(q.a, a)
 	q.swim(len(q.a) - 1)
 }
 
-func (q *HeapPriority) Max() (max int) {
+func (q *HeapPriority[T]) Max() (max T) {
 	if q.Empty() {
 		return 0
 	}
@@ -39,7 +39,7 @@ func (q *HeapPriority) Max() (max int) {
 	return q.a[1]
 }
 
-func (q *HeapPriority) DeleteMax() int {
+func (q *HeapPriority[T]) DeleteMax() T {
 	switch q.Size() {
 	case 0:
 		return 0
@@ -60,14 +60,14 @@ func (q *HeapPriority) DeleteMax() int {
 	}
 }
 
-func (q *HeapPriority) swim(k int) {
+func (q *HeapPriority[T]) swim(k int) {
 	for k > 1 && q.a[k/2] < q.a[k] {
 		q.a.Swap(k/2, k)
 		k = k / 2
 	}
 }
 
-func (q *HeapPriority) sink(k int) {
+func (q *HeapPriority[T]) sink(k int) {
 	// Last index
 	max := len(q.a) - 1
 
diff --git a/queue/queue_test.go b/queue/queue_test.go
index 3130b42..e3c37b8 100644
--- a/queue/queue_test.go
+++ b/queue/queue_test.go
@@ -12,17 +12,17 @@ const maxLength int = 10000
 const factor int = 100
 
 // Store results here to avoid compiler optimizations
-var benchResult ds.ArrayList
+var benchResult ds.ArrayList[int]
 
 func TestElementaryPriority(t *testing.T) {
-	q := NewElementaryPriority(1)
+	q := NewElementaryPriority[int](1)
 	for i := minLength; i <= maxLength; i *= factor {
 		test(q, i, t)
 	}
 }
 
 func TestHeapPriority(t *testing.T) {
-	q := NewHeapPriority(1)
+	q := NewHeapPriority[int](1)
 	for i := minLength; i <= maxLength; i *= factor {
 		test(q, i, t)
 	}
@@ -30,7 +30,7 @@ func TestHeapPriority(t *testing.T) {
 
 func test(q PriorityQueue, l int, t *testing.T) {
 	cb := func(t *testing.T) {
-		for _, a := range ds.NewRandomArrayList(l, -1) {
+		for _, a := range ds.NewRandomArrayList[int](l, -1) {
 			q.Insert(a)
 		}
 		prev, started := 0, false
@@ -53,21 +53,21 @@ func test(q PriorityQueue, l int, t *testing.T) {
 }
 
 func BenchmarkElementaryPriority(b *testing.B) {
-	q := NewElementaryPriority(1)
+	q := NewElementaryPriority[int](1)
 	for i := minLength; i <= maxLength; i *= factor {
 		benchmark(q, i, b)
 	}
 }
 
 func BenchmarkHeapPriority(b *testing.B) {
-	q := NewHeapPriority(1)
+	q := NewHeapPriority[int](1)
 	for i := minLength; i <= maxLength; i *= factor {
 		benchmark(q, i, b)
 	}
 }
 
 func benchmark(q PriorityQueue, l int, b *testing.B) {
-	benchResult = ds.NewRandomArrayList(l, -1)
+	benchResult = ds.NewRandomArrayList[int](l, -1)
 
 	b.Run(fmt.Sprintf("randomInsert(%d)", l), func(b *testing.B) {
 		for i := 0; i < b.N; i++ {
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)
 }
diff --git a/sort/bottomupmerge.go b/sort/bottomupmerge.go
index 7708767..312d272 100644
--- a/sort/bottomupmerge.go
+++ b/sort/bottomupmerge.go
@@ -4,9 +4,9 @@ import (
 	"codeberg.org/snonux/algorithms/ds"
 )
 
-func BottomUpMerge(a ds.ArrayList) ds.ArrayList {
+func BottomUpMerge[V ds.Number](a ds.ArrayList[V]) ds.ArrayList[V] {
 	l := len(a)
-	aux := make(ds.ArrayList, l)
+	aux := make(ds.ArrayList[V], l)
 
 	for sz := 1; sz < l; sz = sz + sz {
 		for lo := 0; lo < l-sz; lo += sz + sz {
diff --git a/sort/insertion.go b/sort/insertion.go
index 62dcf32..a6b3c85 100644
--- a/sort/insertion.go
+++ b/sort/insertion.go
@@ -4,7 +4,7 @@ import (
 	"codeberg.org/snonux/algorithms/ds"
 )
 
-func Insertion(a ds.ArrayList) ds.ArrayList {
+func Insertion[V ds.Number](a ds.ArrayList[V]) ds.ArrayList[V] {
 	for i, _ := range a {
 		for j := i; j > 0; j-- {
 			if a[j] > a[j-1] {
diff --git a/sort/merge.go b/sort/merge.go
index d333b6d..66a7fd6 100644
--- a/sort/merge.go
+++ b/sort/merge.go
@@ -4,14 +4,14 @@ import (
 	"codeberg.org/snonux/algorithms/ds"
 )
 
-func Merge(a ds.ArrayList) ds.ArrayList {
-	aux := make(ds.ArrayList, len(a))
+func Merge[V ds.Number](a ds.ArrayList[V]) ds.ArrayList[V] {
+	aux := make(ds.ArrayList[V], len(a))
 	mergeSort(a, aux)
 
 	return a
 }
 
-func mergeSort(a, aux ds.ArrayList) {
+func mergeSort[V ds.Number](a, aux ds.ArrayList[V]) {
 	l := len(a)
 	if l <= 10 {
 		Insertion(a)
@@ -24,7 +24,7 @@ func mergeSort(a, aux ds.ArrayList) {
 	merge(a, aux, 0, mi, l-1)
 }
 
-func merge(a, aux ds.ArrayList, lo, mi, hi int) {
+func merge[V ds.Number](a, aux ds.ArrayList[V], lo, mi, hi int) {
 	for i := lo; i <= hi; i++ {
 		aux[i] = a[i]
 	}
diff --git a/sort/parallelmerge.go b/sort/parallelmerge.go
index 8c6f780..1f5030c 100644
--- a/sort/parallelmerge.go
+++ b/sort/parallelmerge.go
@@ -6,12 +6,12 @@ import (
 	"codeberg.org/snonux/algorithms/ds"
 )
 
-func ParallelMerge(a ds.ArrayList) ds.ArrayList {
-	parallelMerge(a, make(ds.ArrayList, len(a)))
+func ParallelMerge[V ds.Number](a ds.ArrayList[V]) ds.ArrayList[V] {
+	parallelMerge[V](a, make(ds.ArrayList[V], len(a)))
 	return a
 }
 
-func parallelMerge(a, aux ds.ArrayList) {
+func parallelMerge[V ds.Number](a, aux ds.ArrayList[V]) {
 	l := len(a)
 
 	if l < 1000 {
diff --git a/sort/parallelquick.go b/sort/parallelquick.go
index ae203f2..5763efc 100644
--- a/sort/parallelquick.go
+++ b/sort/parallelquick.go
@@ -6,13 +6,13 @@ import (
 	"codeberg.org/snonux/algorithms/ds"
 )
 
-func ParallelQuick(a ds.ArrayList) ds.ArrayList {
+func ParallelQuick[V ds.Number](a ds.ArrayList[V]) ds.ArrayList[V] {
 	//Shuffle(a)
 	parallelQuick(a)
 	return a
 }
 
-func parallelQuick(a ds.ArrayList) {
+func parallelQuick[V ds.Number](a ds.ArrayList[V]) {
 	l := len(a)
 
 	if l < 1000 {
diff --git a/sort/quick.go b/sort/quick.go
index 46b750a..32c1a4d 100644
--- a/sort/quick.go
+++ b/sort/quick.go
@@ -6,12 +6,12 @@ import (
 	"codeberg.org/snonux/algorithms/ds"
 )
 
-func Quick(a ds.ArrayList) ds.ArrayList {
+func Quick[V ds.Number](a ds.ArrayList[V]) ds.ArrayList[V] {
 	quick(a)
 	return a
 }
 
-func quick(a ds.ArrayList) {
+func quick[V ds.Number](a ds.ArrayList[V]) {
 	if len(a) <= 10 {
 		Insertion(a)
 		return
@@ -22,7 +22,7 @@ func quick(a ds.ArrayList) {
 	quick(a[j+1:])
 }
 
-func quickPartition(a ds.ArrayList) int {
+func quickPartition[V ds.Number](a ds.ArrayList[V]) int {
 	l := len(a)
 	i := 0 // Left scan index
 	j := l // Right scan index
@@ -53,7 +53,7 @@ func quickPartition(a ds.ArrayList) int {
 	return j
 }
 
-func median(a ds.ArrayList, l int) int {
+func median[V ds.Number](a ds.ArrayList[V], l int) int {
 	u := rand.Intn(l)
 	v := rand.Intn(l)
 	w := rand.Intn(l)
diff --git a/sort/quick3way.go b/sort/quick3way.go
index 343fae9..156a0ae 100644
--- a/sort/quick3way.go
+++ b/sort/quick3way.go
@@ -5,13 +5,13 @@ import (
 )
 
 // Quick3Way uses a 3-way partitioning so it is more efficient dealing with duplicates
-func Quick3Way(a ds.ArrayList) ds.ArrayList {
+func Quick3Way[V ds.Number](a ds.ArrayList[V]) ds.ArrayList[V] {
 	Shuffle(a)
 	quick3Way(a)
 	return a
 }
 
-func quick3Way(a ds.ArrayList) {
+func quick3Way[V ds.Number](a ds.ArrayList[V]) {
 	l := len(a)
 	if l <= 10 {
 		Insertion(a)
diff --git a/sort/selection.go b/sort/selection.go
index 20a53a5..b902c7a 100644
--- a/sort/selection.go
+++ b/sort/selection.go
@@ -4,7 +4,7 @@ import (
 	"codeberg.org/snonux/algorithms/ds"
 )
 
-func Selection(a ds.ArrayList) ds.ArrayList {
+func Selection[V ds.Number](a ds.ArrayList[V]) ds.ArrayList[V] {
 	l := len(a)
 
 	for i := 0; i < l; i++ {
diff --git a/sort/shell.go b/sort/shell.go
index 3041627..0ce32fc 100644
--- a/sort/shell.go
+++ b/sort/shell.go
@@ -4,7 +4,7 @@ import (
 	"codeberg.org/snonux/algorithms/ds"
 )
 
-func Shell(a ds.ArrayList) ds.ArrayList {
+func Shell[V ds.Number](a ds.ArrayList[V]) ds.ArrayList[V] {
 	l := len(a)
 	// h-sort the array
 	h := 1
diff --git a/sort/shuffle.go b/sort/shuffle.go
index cf5bb14..202faaf 100644
--- a/sort/shuffle.go
+++ b/sort/shuffle.go
@@ -6,7 +6,7 @@ import (
 	"codeberg.org/snonux/algorithms/ds"
 )
 
-func Shuffle(a ds.ArrayList) ds.ArrayList {
+func Shuffle[V ds.Number](a ds.ArrayList[V]) ds.ArrayList[V] {
 	l := len(a)
 
 	for i := 0; i < l; i++ {
diff --git a/sort/sort_test.go b/sort/sort_test.go
index a0ac527..c8f3ef8 100644
--- a/sort/sort_test.go
+++ b/sort/sort_test.go
@@ -7,148 +7,145 @@ import (
 	"codeberg.org/snonux/algorithms/ds"
 )
 
-// Store results here to avoid compiler optimizations
-var benchResult ds.ArrayList
-
 const minLength int = 1
 const maxLength int = 1000000
 const factor int = 100
 const maxSlowLength int = 100000
 
-var arrayListCache map[string]ds.ArrayList
+var arrayListCache map[string]ds.ArrayList[int]
 
-type sortAlgorithm func(ds.ArrayList) ds.ArrayList
+type sortAlgorithm[V ds.Number] func(ds.ArrayList[V]) ds.ArrayList[V]
 type sortAlgorithmInt func([]int) []int
 
 func TestSelectionSort(t *testing.T) {
 	for i := minLength; i <= maxSlowLength; i *= factor {
-		test(Selection, i, t)
+		test[int](Selection[int], i, t)
 	}
 }
 
 func TestInsertionSort(t *testing.T) {
 	for i := minLength; i <= maxSlowLength; i *= factor {
-		test(Insertion, i, t)
+		test[int](Insertion[int], i, t)
 	}
 }
 
 func TestShellSort(t *testing.T) {
 	for i := minLength; i <= maxLength; i *= factor {
-		test(Shell, i, t)
+		test[int](Shell[int], i, t)
 	}
 }
 
 func TestMergeSort(t *testing.T) {
 	for i := minLength; i <= maxLength; i *= factor {
-		test(Merge, i, t)
+		test[int](Merge[int], i, t)
 	}
 }
 
 func TestBottomUpMergeSort(t *testing.T) {
 	t.Log("Parallel merge sort")
 	for i := minLength; i <= maxLength; i *= factor {
-		test(BottomUpMerge, i, t)
+		test[int](BottomUpMerge[int], i, t)
 	}
-	test(BottomUpMerge, maxLength*2, t)
+	test[int](BottomUpMerge[int], maxLength*2, t)
 }
 
 func TestParallelMergeSort(t *testing.T) {
 	t.Log("Bottom-up merge sort")
 	for i := minLength; i <= maxLength; i *= factor {
-		test(ParallelMerge, i, t)
+		test[int](ParallelMerge[int], i, t)
 	}
 }
 
 func TestQuickSort(t *testing.T) {
 	for i := minLength; i <= maxLength; i *= factor {
-		test(Quick, i, t)
+		test[int](Quick[int], i, t)
 	}
 }
 
 func TestParallelQuickSort(t *testing.T) {
 	for i := minLength; i <= maxLength; i *= factor {
-		test(ParallelQuick, i, t)
+		test[int](ParallelQuick[int], i, t)
 	}
 }
 
 func TestQuick3WaySort(t *testing.T) {
 	for i := minLength; i <= maxLength; i *= factor {
-		test(Quick3Way, i, t)
+		test[int](Quick3Way[int], i, t)
 	}
 }
 
 func TestShuffleSort(t *testing.T) {
 	for i := 10; i <= maxLength; i *= factor {
-		testShuffle(Shuffle, i, t)
+		testShuffle[int](Shuffle[int], i, t)
 	}
 }
 
 func BenchmarkInsertionSort(b *testing.B) {
 	for i := minLength; i <= maxSlowLength; i *= factor {
-		benchmark(Insertion, i, b)
+		benchmark[int](Insertion[int], i, b)
 	}
 }
 
 func BenchmarkSelectionSort(b *testing.B) {
 	for i := minLength; i <= maxSlowLength; i *= factor {
-		benchmark(Selection, i, b)
+		benchmark[int](Selection[int], i, b)
 	}
 }
 
 func BenchmarkShellSort(b *testing.B) {
 	for i := minLength; i <= maxLength; i *= factor {
-		benchmark(Shell, i, b)
+		benchmark[int](Shell[int], i, b)
 	}
 }
 
 func BenchmarkMergeSort(b *testing.B) {
 	for i := minLength; i <= maxLength; i *= factor {
-		benchmark(Merge, i, b)
+		benchmark[int](Merge[int], i, b)
 	}
 }
 
 func BenchmarkBottomUpMergeSort(b *testing.B) {
 	for i := minLength; i <= maxLength; i *= factor {
-		benchmark(BottomUpMerge, i, b)
+		benchmark[int](BottomUpMerge[int], i, b)
 	}
 }
 
 func BenchmarkParallelMergeSort(b *testing.B) {
 	for i := minLength; i <= maxLength; i *= factor {
-		benchmark(ParallelMerge, i, b)
+		benchmark[int](ParallelMerge[int], i, b)
 	}
 }
 
 func BenchmarkQuickSort(b *testing.B) {
 	for i := minLength; i <= maxLength; i *= factor {
-		benchmark(Quick, i, b)
+		benchmark[int](Quick[int], i, b)
 	}
 }
 
 func BenchmarkParallelQuickSort(b *testing.B) {
 	for i := minLength; i <= maxLength; i *= factor {
-		benchmark(ParallelQuick, i, b)
+		benchmark[int](ParallelQuick[int], i, b)
 	}
 }
 
 func BenchmarkQuick3WaySort(b *testing.B) {
 	for i := minLength; i <= maxLength; i *= factor {
-		benchmark(Quick3Way, i, b)
+		benchmark[int](Quick3Way[int], i, b)
 	}
 }
 
 /*
 func BenchmarkShuffleSort(b *testing.B) {
 	for i := minLength; i <= maxLength; i *= factor {
-		benchmark(Shuffle, i, b)
+		benchmark[int](Shuffle[int], i, b)
 	}
 }
 */
 
-func test(sort sortAlgorithm, l int, t *testing.T) {
+func test[V ds.Number](sort sortAlgorithm[V], l int, t *testing.T) {
 	cb := func(t *testing.T) {
 		t.Parallel()
-		a := ds.NewRandomArrayList(l, -1)
+		a := ds.NewRandomArrayList[V](l, -1)
 		a = sort(a)
 		if !a.Sorted() {
 			t.Errorf("Array not sorted: %v", a)
@@ -157,10 +154,10 @@ func test(sort sortAlgorithm, l int, t *testing.T) {
 	t.Run(fmt.Sprintf("%d", l), cb)
 }
 
-func testShuffle(sort sortAlgorithm, l int, t *testing.T) {
+func testShuffle[V ds.Number](sort sortAlgorithm[V], l int, t *testing.T) {
 	cb := func(t *testing.T) {
 		t.Parallel()
-		a := sort(ds.NewAscendingArrayList(l))
+		a := sort(ds.NewAscendingArrayList[V](l))
 		if a.Sorted() {
 			t.Errorf("Array sorted: %v", a.FirstN(10))
 		}
@@ -168,33 +165,39 @@ func testShuffle(sort sortAlgorithm, l int, t *testing.T) {
 	t.Run(fmt.Sprintf("%d", l), cb)
 }
 
-func benchmark(sort sortAlgorithm, l int, b *testing.B) {
-	a := ds.NewRandomArrayList(l, -1)
-	aux := ds.NewArrayList(l)
+func benchmark[V ds.Number](sort sortAlgorithm[V], l int, b *testing.B) {
+	a := ds.NewRandomArrayList[V](l, -1)
+	aux := ds.NewArrayList[V](l)
 
 	b.Run(fmt.Sprintf("random(%d)", l), func(b *testing.B) {
+		var benchResult ds.ArrayList[V]
 		b.ResetTimer()
 		for i := 0; i < b.N; i++ {
 			copy(aux, a)
 			benchResult = sort(aux)
 		}
+		_ = benchResult
 	})
 
-	a = ds.NewAscendingArrayList(l)
+	a = ds.NewAscendingArrayList[V](l)
 	b.Run(fmt.Sprintf("ascending(%d)", l), func(b *testing.B) {
+		var benchResult ds.ArrayList[V]
 		b.ResetTimer()
 		for i := 0; i < b.N; i++ {
 			copy(aux, a)
 			benchResult = sort(aux)
 		}
+		_ = benchResult
 	})
 
-	a = ds.NewDescendingArrayList(l)
+	a = ds.NewDescendingArrayList[V](l)
 	b.Run(fmt.Sprintf("descending(%d)", l), func(b *testing.B) {
+		var benchResult ds.ArrayList[V]
 		b.ResetTimer()
 		for i := 0; i < b.N; i++ {
 			copy(aux, a)
 			benchResult = sort(aux)
 		}
+		_ = benchResult
 	})
 }