initial generics

11 files changed, 59 insertions, 56 deletions

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
 	})
 }