summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorShulhan <ms@kilabit.info>2024-12-28 22:14:09 +0700
committerShulhan <ms@kilabit.info>2024-12-29 00:06:17 +0700
commit7a57091317cd86b9c88f4c6b5127c76bee0f6ede (patch)
treef1ec2aac093ff02890a62068001be177c93c1486
parent5a00dfe102a3a06ddee1b79800060dd70231055b (diff)
downloadpakakeh.go-7a57091317cd86b9c88f4c6b5127c76bee0f6ede.tar.xz
all: merge package "lib/ints" and "lib/ints64" into "slices"
Now that Go has type parameter, we can use it to use the same function that accept different types for working with slice of int, int64.
-rw-r--r--README.md3
-rw-r--r--go.mod1
-rw-r--r--go.sum4
-rw-r--r--lib/floats64/floats64.go12
-rw-r--r--lib/ints/ints.go396
-rw-r--r--lib/ints/ints_benchmark_test.go59
-rw-r--r--lib/ints/ints_example_test.go30
-rw-r--r--lib/ints/ints_test.go425
-rw-r--r--lib/ints64/ints64.go352
-rw-r--r--lib/ints64/ints64_test.go382
-rw-r--r--lib/memfs/memfs.go4
-rw-r--r--lib/mining/classifier/rf/rf.go4
-rw-r--r--lib/mining/classifier/runtime.go4
-rw-r--r--lib/slices/benchmark_test.go50
-rw-r--r--lib/slices/example_test.go34
-rw-r--r--lib/slices/slices.go403
-rw-r--r--lib/slices/slices_int_test.go463
-rw-r--r--lib/strings/statistic.go4
-rw-r--r--lib/strings/strings.go4
-rw-r--r--lib/tabula/claset.go10
-rw-r--r--lib/time/scheduler.go5
-rw-r--r--lib/websocket/clientmanager.go9
22 files changed, 980 insertions, 1678 deletions
diff --git a/README.md b/README.md
index 3a3d440b..a0308fc5 100644
--- a/README.md
+++ b/README.md
@@ -123,9 +123,6 @@ A library to parse the Hunspell file format.
A library for reading and writing INI configuration as defined by Git
configuration file syntax.
-[**ints**](https://pkg.go.dev/git.sr.ht/~shulhan/pakakeh.go/lib/ints)::
-A library for working with slice of integer.
-
[**ints64**](https://pkg.go.dev/git.sr.ht/~shulhan/pakakeh.go/lib/ints64)::
A library for working with slice of int64.
diff --git a/go.mod b/go.mod
index 5193fe80..b7e34aba 100644
--- a/go.mod
+++ b/go.mod
@@ -8,6 +8,7 @@ go 1.23.4
require (
golang.org/x/crypto v0.31.0
+ golang.org/x/exp v0.0.0-20241217172543-b2144cdd0a67
golang.org/x/net v0.33.0
golang.org/x/sys v0.28.0
golang.org/x/term v0.27.0
diff --git a/go.sum b/go.sum
index 5e5874ce..03c09627 100644
--- a/go.sum
+++ b/go.sum
@@ -2,10 +2,10 @@ github.com/google/go-cmp v0.6.0 h1:ofyhxvXcZhMsU5ulbFiLKl/XBFqE1GSq7atu8tAmTRI=
github.com/google/go-cmp v0.6.0/go.mod h1:17dUlkBOakJ0+DkrSSNjCkIjxS6bF9zb3elmeNGIjoY=
golang.org/x/crypto v0.31.0 h1:ihbySMvVjLAeSH1IbfcRTkD/iNscyz8rGzjF/E5hV6U=
golang.org/x/crypto v0.31.0/go.mod h1:kDsLvtWBEx7MV9tJOj9bnXsPbxwJQ6csT/x4KIN4Ssk=
+golang.org/x/exp v0.0.0-20241217172543-b2144cdd0a67 h1:1UoZQm6f0P/ZO0w1Ri+f+ifG/gXhegadRdwBIXEFWDo=
+golang.org/x/exp v0.0.0-20241217172543-b2144cdd0a67/go.mod h1:qj5a5QZpwLU2NLQudwIN5koi3beDhSAlJwa67PuM98c=
golang.org/x/mod v0.22.0 h1:D4nJWe9zXqHOmWqj4VMOJhvzj7bEZg4wEYa759z1pH4=
golang.org/x/mod v0.22.0/go.mod h1:6SkKJ3Xj0I0BrPOZoBy3bdMptDDU9oJrpohJ3eWZ1fY=
-golang.org/x/net v0.32.0 h1:ZqPmj8Kzc+Y6e0+skZsuACbx+wzMgo5MQsJh9Qd6aYI=
-golang.org/x/net v0.32.0/go.mod h1:CwU0IoeOlnQQWJ6ioyFrfRuomB8GKF6KbYXZVyeXNfs=
golang.org/x/net v0.33.0 h1:74SYHlV8BIgHIFC/LrYkOGIwL19eTYXQ5wc6TBuO36I=
golang.org/x/net v0.33.0/go.mod h1:HXLR5J+9DxmrqMwG9qjGCxZ+zKXxBru04zlTvWlWuN4=
golang.org/x/sync v0.10.0 h1:3NQrjDixjgGwUOCaF8w2+VYHv0Ve/vGYSbdkTa98gmQ=
diff --git a/lib/floats64/floats64.go b/lib/floats64/floats64.go
index 397e9a89..1781abb2 100644
--- a/lib/floats64/floats64.go
+++ b/lib/floats64/floats64.go
@@ -5,9 +5,7 @@
// Package floats64 provide a library for working with slice of 64 bit float.
package floats64
-import (
- "git.sr.ht/~shulhan/pakakeh.go/lib/ints"
-)
+import "git.sr.ht/~shulhan/pakakeh.go/lib/slices"
// Count number of class in data.
func Count(d []float64, class float64) (count int) {
@@ -104,12 +102,12 @@ func InplaceInsertionSort(d []float64, ids []int, l, r int, asc bool) {
for y := x + 1; y < r; y++ {
if asc {
if d[x] > d[y] {
- ints.Swap(ids, x, y)
+ slices.Swap(ids, x, y)
Swap(d, x, y)
}
} else {
if d[x] < d[y] {
- ints.Swap(ids, x, y)
+ slices.Swap(ids, x, y)
Swap(d, x, y)
}
}
@@ -186,7 +184,7 @@ func MaxCountOf(d, classes []float64) (float64, bool) {
counts := Counts(d, classes)
- _, maxi, _ := ints.Max(counts)
+ _, maxi := slices.Max2(counts)
return classes[maxi], true
}
@@ -340,7 +338,7 @@ func moveY(d []float64, x, y, r int, asc bool) int {
func multiswap(d []float64, idx []int, x, y, ylast int) int {
for y < ylast {
- ints.Swap(idx, x, y)
+ slices.Swap(idx, x, y)
Swap(d, x, y)
x++
y++
diff --git a/lib/ints/ints.go b/lib/ints/ints.go
deleted file mode 100644
index 4e252420..00000000
--- a/lib/ints/ints.go
+++ /dev/null
@@ -1,396 +0,0 @@
-// Copyright 2018, Shulhan <ms@kilabit.info>. All rights reserved.
-// Use of this source code is governed by a BSD-style
-// license that can be found in the LICENSE file.
-
-// Package ints provide a library for working with slice of integer.
-package ints
-
-import (
- "sort"
-)
-
-// Count number of class in data.
-func Count(d []int, class int) (count int) {
- if len(d) == 0 {
- return
- }
- for x := 0; x < len(d); x++ {
- if d[x] == class {
- count++
- }
- }
- return
-}
-
-// Counts number of each class in slice.
-//
-// For example, if data is "[1,1,2]" and classes is "[1,2]", this function
-// will return "[2,1]".
-func Counts(d, classes []int) (counts []int) {
- if len(classes) == 0 {
- return
- }
- counts = make([]int, len(classes))
- for x, c := range classes {
- counts[x] = Count(d, c)
- }
- return
-}
-
-// IndirectSort sort the data and return the sorted index.
-func IndirectSort(d []int, asc bool) (sortedIdx []int) {
- sortedIdx = make([]int, len(d))
- for i := 0; i < len(d); i++ {
- sortedIdx[i] = i
- }
-
- InplaceMergesort(d, sortedIdx, 0, len(d), asc)
-
- return
-}
-
-// InplaceInsertionSort will sort the data and their index using
-// insertion-sort algorithm.
-//
-// Parameters:
-// `d` is slice that will be sorted,
-// `ids` is indices of data,
-// `l` is starting index of slice to be sorted, and
-// `r` is end index of slice to be sorted.
-func InplaceInsertionSort(d, ids []int, l, r int, asc bool) {
- for x := l; x < r; x++ {
- for y := x + 1; y < r; y++ {
- if asc {
- if d[x] > d[y] {
- Swap(ids, x, y)
- Swap(d, x, y)
- }
- } else {
- if d[x] < d[y] {
- Swap(ids, x, y)
- Swap(d, x, y)
- }
- }
- }
- }
-}
-
-// InplaceMergesort sort the slice "d" in-place, without memory allocation,
-// using mergesort algorithm.
-func InplaceMergesort(d []int, idx []int, l, r int, asc bool) {
- if l+7 >= r {
- // If data length <= Threshold, then use insertion sort.
- InplaceInsertionSort(d, idx, l, r, asc)
- return
- }
-
- // Divide into left and right.
- c := ((r + l) / 2) + (r+l)%2
-
- // Sort left.
- InplaceMergesort(d, idx, l, c, asc)
-
- // Sort right.
- InplaceMergesort(d, idx, c, r, asc)
-
- // Merge sorted left and right.
- if asc {
- if d[c-1] <= d[c] {
- // If the last element of the left is lower then
- // the first element of the right, i.e. [1 2] [3 4];
- // no merging needed, return immediately.
- return
- }
- } else {
- if d[c-1] >= d[c] {
- return
- }
- }
-
- inplaceMerge(d, idx, l, c, r, asc)
-}
-
-// IsExist will return true if value `v` exist in slice of `d`,
-// otherwise it will return false.
-func IsExist(d []int, v int) bool {
- for x := 0; x < len(d); x++ {
- if d[x] == v {
- return true
- }
- }
- return false
-}
-
-// Max find the maximum value in slice and return its value and index.
-//
-// If slice is empty, it will return false in ok.
-func Max(d []int) (v int, i int, ok bool) {
- if len(d) == 0 {
- return
- }
- v = d[0]
- i = 0
- for x := 1; x < len(d); x++ {
- if d[x] > v {
- v = d[x]
- i = x
- }
- }
- return v, i, true
-}
-
-// MaxCountOf count number of occurrence of each element of classes
-// in data and return the class with maximum count.
-//
-// If `classes` is empty, it will return -1 and false.
-// If `data` is empty, it will return -2 and false.
-// If classes has the same count value, then the first max in the class will be
-// returned.
-//
-// For example, given a data [5, 6, 5, 6, 5] and classes [5, 6, 7], the
-// function will count 5 as 3, 6 as 2, and 7 as 0.
-// Since frequency of 5 is greater than 6 and 7, then it will return `5` and
-// `true`.
-func MaxCountOf(d, classes []int) (int, bool) {
- if len(classes) == 0 {
- return -1, false
- }
- if len(d) == 0 {
- return -2, false
- }
-
- counts := Counts(d, classes)
-
- _, i, _ := Max(counts)
-
- return classes[i], true
-}
-
-// MaxRange find the (last) maximum value in slice between index "l" and "r".
-//
-// WARNING: This function does not check index out of range.
-func MaxRange(d []int, l, r int) (v, i int) {
- v = d[l]
- i = l
- for l++; l < r; l++ {
- if d[l] >= v {
- v = d[l]
- i = l
- }
- }
- return
-}
-
-// MergeByDistance merge two slice of integers by their distance between each
-// others.
-//
-// For example, if slice a contains "{1, 5, 9}" and b contains
-// "{4, 11, 15}" and the distance is 3, the output of merged is
-// "{1, 5, 9, 15}". The 4 and 11 are not included because 4 is in
-// range between 1 and (1+3), and 11 is in range between 9 and 9+3.
-func MergeByDistance(a, b []int, distance int) (out []int) {
- lenab := len(a) + len(b)
- if lenab == 0 {
- return nil
- }
-
- ab := make([]int, 0, lenab)
- ab = append(ab, a...)
- ab = append(ab, b...)
-
- sort.Ints(ab)
-
- out = append(out, ab[0])
- last := ab[0]
- for x := 1; x < len(ab); x++ {
- if ab[x] > last+distance {
- out = append(out, ab[x])
- last = ab[x]
- continue
- }
- }
-
- return out
-}
-
-// Min find the minimum value in slice and return its value and index.
-//
-// If slice is empty, it will return false in ok.
-func Min(d []int) (v int, i int, ok bool) {
- if len(d) == 0 {
- return
- }
- v = d[0]
- i = 0
- for x := 1; x < len(d); x++ {
- if d[x] < v {
- v = d[x]
- i = x
- }
- }
- return v, i, true
-}
-
-// MinRange find the (last) minimum value in slice between index "l" and "r".
-//
-// WARNING: This function does not check index out of range.
-func MinRange(d []int, l, r int) (v, i int) {
- v = d[l]
- i = l
- for l++; l < r; l++ {
- if d[l] <= v {
- v = d[l]
- i = l
- }
- }
- return
-}
-
-// Remove value "v" from slice if its exist and return new slice and true;
-// otherwise, if not found, return unmodified slice and false.
-func Remove(d []int, v int) ([]int, bool) {
- for x := 0; x < len(d); x++ {
- if d[x] == v {
- d = append(d[:x], d[x+1:]...)
- return d, true
- }
- }
- return d, false
-}
-
-// SortByIndex will sort the slice `d` using sorted index `sortedListID`.
-func SortByIndex(d *[]int, sortedListID []int) {
- newd := make([]int, len(*d))
-
- for x := 0; x < len(sortedListID); x++ {
- newd[x] = (*d)[sortedListID[x]]
- }
-
- (*d) = newd
-}
-
-// Sum all value in slice.
-func Sum(d []int) (sum int) {
- for x := 0; x < len(d); x++ {
- sum += d[x]
- }
- return
-}
-
-// Swap two indices value of slice.
-func Swap(d []int, x, y int) {
- if x == y || len(d) <= 1 || x > len(d) || y > len(d) {
- return
- }
- d[x], d[y] = d[y], d[x]
-}
-
-// To64 convert slice of integer to 64 bit values.
-func To64(ints []int) []int64 {
- i64 := make([]int64, len(ints))
- for x, v := range ints {
- i64[x] = int64(v)
- }
- return i64
-}
-
-// Let `x` be the first index of left-side, `y` be the first index of
-// the right-side, and `r` as length of slice `d`
-func inplaceMerge(d []int, idx []int, x, y, r int, asc bool) {
- var ylast int
-
- // (4.3) Loop until either x or y reached the maximum slice.
- for x < r && y < r {
- // (4.3.1) IF DATA[x] <= DATA[y]
- if asc {
- if d[x] <= d[y] {
- x++
-
- // (4.3.1.2) IF x > y THEN GOTO 4.3
- if x >= y {
- goto next
- }
-
- // (4.3.1.3) GOTO 4.3
- continue
- }
- } else {
- if d[x] >= d[y] {
- x++
-
- if x >= y {
- goto next
- }
-
- continue
- }
- }
-
- // (4.3.2) LET YLAST := the next DATA[y] that is less DATA[x]
- ylast = moveY(d, x, y, r, asc)
-
- // (4.3.3) SWAP DATA, X, Y, YLAST
- inplaceMultiswap(d, idx, x, y, ylast)
-
- next:
- // (4.3.4) LET Y := the minimum value between x and r on `d`
- minY(d, &x, &y, r, asc)
- }
-}
-
-func inplaceMultiswap(d []int, idx []int, x, y, ylast int) int {
- for y < ylast {
- Swap(idx, x, y)
- Swap(d, x, y)
- x++
- y++
- if y >= ylast {
- return y
- }
- if d[x] <= d[y] {
- return y
- }
- }
-
- return y
-}
-
-// (4.3.4) LET Y := the minimum value between x and r on `d`.
-func minY(d []int, x, y *int, r int, asc bool) {
- for *x < r {
- if asc {
- _, *y = MinRange(d, *x, r)
- } else {
- _, *y = MaxRange(d, *x, r)
- }
-
- if *y != *x {
- break
- }
- (*x)++
- }
-}
-
-func moveY(d []int, x, y, r int, asc bool) int {
- yorg := y
- y++
- for y < r {
- if asc {
- if d[y] >= d[x] {
- break
- }
- if d[y] < d[yorg] {
- break
- }
- } else {
- if d[y] <= d[x] {
- break
- }
- if d[y] > d[yorg] {
- break
- }
- }
- y++
- }
- return y
-}
diff --git a/lib/ints/ints_benchmark_test.go b/lib/ints/ints_benchmark_test.go
deleted file mode 100644
index 953629f8..00000000
--- a/lib/ints/ints_benchmark_test.go
+++ /dev/null
@@ -1,59 +0,0 @@
-// Copyright 2019, Shulhan <ms@kilabit.info>. All rights reserved.
-// Use of this source code is governed by a BSD-style
-// license that can be found in the LICENSE file.
-
-package ints
-
-import (
- "crypto/rand"
- "log"
- "math"
- "math/big"
- "sort"
- "testing"
-)
-
-const n = 10000
-
-func generateRandomInts(data []int) {
- var (
- max = big.NewInt(math.MaxInt)
- randv *big.Int
- err error
- )
- for x := 0; x < n; x++ {
- randv, err = rand.Int(rand.Reader, max)
- if err != nil {
- log.Fatalf(`generateRandomInts: %s`, err)
- }
- data[x] = int(randv.Int64())
- }
-}
-
-func BenchmarkIndirectSort(b *testing.B) {
- data := make([]int, n)
- generateRandomInts(data)
- b.ResetTimer()
-
- for x := 0; x < b.N; x++ {
- IndirectSort(data, true)
-
- b.StopTimer()
- generateRandomInts(data)
- b.StartTimer()
- }
-}
-
-func BenchmarkStdSortInts(b *testing.B) {
- data := make([]int, n)
- generateRandomInts(data)
- b.ResetTimer()
-
- for x := 0; x < b.N; x++ {
- sort.Ints(data)
-
- b.StopTimer()
- generateRandomInts(data)
- b.StartTimer()
- }
-}
diff --git a/lib/ints/ints_example_test.go b/lib/ints/ints_example_test.go
deleted file mode 100644
index f29fe748..00000000
--- a/lib/ints/ints_example_test.go
+++ /dev/null
@@ -1,30 +0,0 @@
-// Copyright 2018, Shulhan <ms@kilabit.info>. All rights reserved.
-// Use of this source code is governed by a BSD-style
-// license that can be found in the LICENSE file.
-
-package ints
-
-import (
- "fmt"
-)
-
-func ExampleMax() {
- ints := []int{5, 6, 7, 8, 9, 0, 1, 2, 3, 4}
-
- fmt.Println(Max(ints))
- // Output:
- // 9 4 true
-}
-
-func ExampleMergeByDistance() {
- a := []int{1, 5, 9}
- b := []int{4, 11, 15}
-
- ab := MergeByDistance(a, b, 3)
- ba := MergeByDistance(b, a, 3)
- fmt.Println(ab)
- fmt.Println(ba)
- // Output:
- // [1 5 9 15]
- // [1 5 9 15]
-}
diff --git a/lib/ints/ints_test.go b/lib/ints/ints_test.go
deleted file mode 100644
index a0d6c90d..00000000
--- a/lib/ints/ints_test.go
+++ /dev/null
@@ -1,425 +0,0 @@
-// Copyright 2018, Shulhan <ms@kilabit.info>. All rights reserved.
-// Use of this source code is governed by a BSD-style
-// license that can be found in the LICENSE file.
-
-package ints
-
-import (
- "fmt"
- "sort"
- "testing"
-
- "git.sr.ht/~shulhan/pakakeh.go/lib/test"
-)
-
-var (
- d = [][]int{
- {},
- {5, 6, 7, 8, 9, 0, 1, 2, 3, 4},
- {0, 1, 0, 1, 0, 1, 0, 1, 0},
- {1, 1, 2, 2, 3, 1, 2},
- }
- dSorted = [][]int{
- {},
- {0, 1, 2, 3, 4, 5, 6, 7, 8, 9},
- {0, 0, 0, 0, 0, 1, 1, 1, 1},
- {1, 1, 1, 2, 2, 2, 3},
- }
- dSortedDesc = [][]int{
- {},
- {9, 8, 7, 6, 5, 4, 3, 2, 1, 0},
- {1, 1, 1, 1, 0, 0, 0, 0, 0},
- {3, 2, 2, 2, 1, 1, 1},
- }
-)
-
-func TestMaxEmpty(t *testing.T) {
- maxv, maxi, ok := Max(d[0])
-
- test.Assert(t, "", 0, maxv)
- test.Assert(t, "", 0, maxi)
- test.Assert(t, "", false, ok)
-}
-
-func TestMax(t *testing.T) {
- maxv, maxi, ok := Max(d[1])
-
- test.Assert(t, "", 9, maxv)
- test.Assert(t, "", 4, maxi)
- test.Assert(t, "", true, ok)
-}
-
-func TestMinEmpty(t *testing.T) {
- minv, mini, ok := Min(d[0])
-
- test.Assert(t, "", 0, minv)
- test.Assert(t, "", 0, mini)
- test.Assert(t, "", false, ok)
-}
-
-func TestMin(t *testing.T) {
- minv, mini, ok := Min(d[1])
-
- test.Assert(t, "", 0, minv)
- test.Assert(t, "", 5, mini)
- test.Assert(t, "", true, ok)
-}
-
-func TestSum(t *testing.T) {
- got := Sum(d[1])
-
- test.Assert(t, "", 45, got)
-}
-
-func TestCount(t *testing.T) {
- got := Count(d[0], 0)
-
- test.Assert(t, "", 0, got)
-
- got = Count(d[1], 1)
-
- test.Assert(t, "", 1, got)
-
- got = Count(d[2], 1)
-
- test.Assert(t, "", 4, got)
-
- got = Count(d[3], 0)
-
- test.Assert(t, "", 0, got)
-
- got = Count(d[3], 3)
-
- test.Assert(t, "", 1, got)
-}
-
-func TestCountsEmpty(t *testing.T) {
- classes := []int{1, 2, 3}
- exp := []int{0, 0, 0}
-
- got := Counts(d[0], classes)
-
- test.Assert(t, "", exp, got)
-}
-
-func TestCountsEmptyClasses(t *testing.T) {
- classes := []int{}
- var exp []int
-
- got := Counts(d[1], classes)
-
- test.Assert(t, "", exp, got)
-}
-
-func TestCounts(t *testing.T) {
- classes := []int{1, 2, 3}
- exp := []int{3, 3, 1}
-
- got := Counts(d[3], classes)
-
- test.Assert(t, "", exp, got)
-}
-
-func TestMaxCountOf(t *testing.T) {
- classes := []int{0, 1}
- exp := int(0)
- got, _ := MaxCountOf(d[2], classes)
-
- test.Assert(t, "", exp, got)
-
- // Swap the class values.
- classes = []int{1, 0}
- got, _ = MaxCountOf(d[2], classes)
-
- test.Assert(t, "", exp, got)
-}
-
-func TestSwapEmpty(t *testing.T) {
- exp := []int{}
-
- Swap(d[0], 1, 6)
-
- test.Assert(t, "", exp, d[0])
-}
-
-func TestSwapEqual(t *testing.T) {
- in := make([]int, len(d[1]))
- copy(in, d[1])
-
- exp := make([]int, len(in))
- copy(exp, in)
-
- Swap(in, 1, 1)
-
- test.Assert(t, "", exp, in)
-}
-
-func TestSwapOutOfRange(t *testing.T) {
- in := make([]int, len(d[1]))
- copy(in, d[1])
-
- exp := make([]int, len(in))
- copy(exp, in)
-
- Swap(in, 1, 100)
-
- test.Assert(t, "", exp, in)
-}
-
-func TestSwap(t *testing.T) {
- in := make([]int, len(d[1]))
- copy(in, d[1])
-
- exp := make([]int, len(in))
- copy(exp, in)
-
- Swap(in, 0, len(in)-1)
-
- exp[0], exp[len(exp)-1] = exp[len(exp)-1], exp[0]
-
- test.Assert(t, "", exp, in)
-}
-
-func TestIsExist(t *testing.T) {
- var s bool
-
- // True positive.
- for _, d := range d {
- for _, v := range d {
- s = IsExist(d, v)
-
- test.Assert(t, "", true, s)
- }
- }
-
- // False positive.
- for _, d := range d {
- s = IsExist(d, -1)
- test.Assert(t, "", false, s)
- s = IsExist(d, 10)
- test.Assert(t, "", false, s)
- }
-}
-
-func TestInplaceInsertionSort(t *testing.T) {
- for x := range d {
- data := make([]int, len(d[x]))
-
- copy(data, d[x])
-
- ids := make([]int, len(data))
- for x := range ids {
- ids[x] = x
- }
-
- InplaceInsertionSort(data, ids, 0, len(ids), true)
-
- test.Assert(t, "", dSorted[x], data)
- }
-}
-
-func TestInplaceInsertionSortDesc(t *testing.T) {
- for x := range d {
- data := make([]int, len(d[x]))
-
- copy(data, d[x])
-
- ids := make([]int, len(data))
- for x := range ids {
- ids[x] = x
- }
-
- InplaceInsertionSort(data, ids, 0, len(ids), false)
-
- test.Assert(t, "", dSortedDesc[x], data)
- }
-}
-
-func TestSortByIndex(t *testing.T) {
- ids := [][]int{
- {},
- {5, 6, 7, 8, 9, 0, 1, 2, 3, 4},
- {0, 2, 4, 6, 8, 1, 3, 5, 7},
- {0, 1, 5, 6, 2, 3, 4},
- }
-
- for x := range d {
- data := make([]int, len(d[x]))
-
- copy(data, d[x])
-
- SortByIndex(&data, ids[x])
-
- test.Assert(t, "", dSorted[x], data)
- }
-}
-
-var intsInSorts = [][]int{
- {9, 8, 7, 6, 5, 4, 3},
- {9, 8, 7, 6, 5, 4, 3, 2, 1, 0},
- {0, 1, 2, 3, 4, 5, 6, 7, 8, 9},
- {0, 6, 7, 8, 5, 1, 2, 3, 4, 9},
- {9, 8, 7, 6, 5, 4, 3, 2, 1},
- {0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
- {51, 50, 56, 55, 55, 58, 55, 55, 58, 56,
- 57, 50, 56, 59, 62, 60, 49, 63, 61, 56,
- 58, 67, 61, 59, 60, 49, 56, 52, 61, 64,
- 70, 57, 65, 69, 57, 64, 62, 66, 63, 62,
- 54, 67, 61, 57, 55, 60, 30, 66, 57, 60,
- 68, 60, 61, 63, 58, 58, 56, 57, 60, 69,
- 69, 64, 63, 63, 67, 65, 58, 63, 64, 67,
- 59, 72, 63, 63, 65, 71, 67, 76, 73, 64,
- 67, 74, 60, 68, 65, 64, 67, 64, 65, 69,
- 77, 67, 72, 77, 72, 77, 61, 79, 77, 68,
- 62},
-}
-
-var intsExpSorts = [][]int{
- {3, 4, 5, 6, 7, 8, 9},
- {0, 1, 2, 3, 4, 5, 6, 7, 8, 9},
- {0, 1, 2, 3, 4, 5, 6, 7, 8, 9},
- {0, 1, 2, 3, 4, 5, 6, 7, 8, 9},
- {1, 2, 3, 4, 5, 6, 7, 8, 9},
- {0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
- {30, 49, 49, 50, 50, 51, 52, 54, 55, 55,
- 55, 55, 55, 56, 56, 56, 56, 56, 56, 57,
- 57, 57, 57, 57, 57, 58, 58, 58, 58, 58,
- 58, 59, 59, 59, 60, 60, 60, 60, 60, 60,
- 60, 61, 61, 61, 61, 61, 61, 62, 62, 62,
- 62, 63, 63, 63, 63, 63, 63, 63, 63, 64,
- 64, 64, 64, 64, 64, 64, 65, 65, 65, 65,
- 65, 66, 66, 67, 67, 67, 67, 67, 67, 67,
- 67, 68, 68, 68, 69, 69, 69, 69, 70, 71,
- 72, 72, 72, 73, 74, 76, 77, 77, 77, 77,
- 79},
-}
-
-var intsExpSortsDesc = [][]int{
- {9, 8, 7, 6, 5, 4, 3},
- {9, 8, 7, 6, 5, 4, 3, 2, 1, 0},
- {9, 8, 7, 6, 5, 4, 3, 2, 1, 0},
- {9, 8, 7, 6, 5, 4, 3, 2, 1, 0},
- {9, 8, 7, 6, 5, 4, 3, 2, 1},
- {0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
- {79, 77, 77, 77, 77, 76, 74, 73, 72, 72,
- 72, 71, 70, 69, 69, 69, 69, 68, 68, 68,
- 67, 67, 67, 67, 67, 67, 67, 67, 66, 66,
- 65, 65, 65, 65, 65, 64, 64, 64, 64, 64,
- 64, 64, 63, 63, 63, 63, 63, 63, 63, 63,
- 62, 62, 62, 62, 61, 61, 61, 61, 61, 61,
- 60, 60, 60, 60, 60, 60, 60, 59, 59, 59,
- 58, 58, 58, 58, 58, 58, 57, 57, 57, 57,
- 57, 57, 56, 56, 56, 56, 56, 56, 55, 55,
- 55, 55, 55, 54, 52, 51, 50, 50, 49, 49,
- 30},
-}
-
-func TestCompareSort(t *testing.T) {
- d1 := make([]int, n)
- generateRandomInts(d1)
- d2 := make([]int, len(d1))
- copy(d2, d1)
-
- sort.Ints(d1)
- IndirectSort(d2, true)
-
- test.Assert(t, "Compare sort", d1, d2)
-}
-
-func TestIndirectSort2(t *testing.T) {
- var res, exp string
-
- for i := range intsInSorts {
- IndirectSort(intsInSorts[i], true)
-
- res = fmt.Sprint(intsInSorts[i])
- exp = fmt.Sprint(intsExpSorts[i])
-
- test.Assert(t, "", exp, res)
- }
-}
-
-func TestIndirectSortDesc(t *testing.T) {
- var res, exp string
-
- for i := range intsInSorts {
- IndirectSort(intsInSorts[i], false)
-
- res = fmt.Sprint(intsInSorts[i])
- exp = fmt.Sprint(intsExpSortsDesc[i])
-
- test.Assert(t, "", exp, res)
- }
-}
-
-func TestIndirectSort_Stability(t *testing.T) {
- exp := []int{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
- got := IndirectSort(intsInSorts[5], true)
-
- test.Assert(t, "", exp, got)
-}
-
-func TestIndirectSortDesc_Stability(t *testing.T) {
- exp := []int{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
- got := IndirectSort(intsInSorts[5], false)
-
- test.Assert(t, "", exp, got)
-}
-
-func TestInplaceMergesort(t *testing.T) {
- size := len(intsInSorts[6])
- idx := make([]int, size)
-
- InplaceMergesort(intsInSorts[6], idx, 0, size, true)
-
- test.Assert(t, "", intsExpSorts[6], intsInSorts[6])
-}
-
-func TestIndirectSort_SortByIndex(t *testing.T) {
- expListID := []int{9, 8, 7, 6, 5, 4, 3, 2, 1, 0}
- in1 := []int{9, 8, 7, 6, 5, 4, 3, 2, 1, 0}
- in2 := []int{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
-
- exp := fmt.Sprint(in1)
-
- sortedListID := IndirectSort(in1, true)
-
- test.Assert(t, "", expListID, sortedListID)
-
- // Reverse the sort.
- SortByIndex(&in2, sortedListID)
-
- got := fmt.Sprint(in2)
-
- test.Assert(t, "", exp, got)
-}
-
-func TestRemove(t *testing.T) {
- cases := []struct {
- d []int
- exp []int
- v int
- }{{
- d: []int{},
- v: 1,
- exp: []int{},
- }, {
- d: []int{1},
- v: 1,
- exp: []int{},
- }, {
- d: []int{1, 2, 3, 4},
- v: 5,
- exp: []int{1, 2, 3, 4},
- }, {
- d: []int{1, 2, 3, 4},
- v: 1,
- exp: []int{2, 3, 4},
- }}
-
- for _, c := range cases {
- got, _ := Remove(c.d, c.v)
-
- test.Assert(t, "Remove", c.exp, got)
- }
-}
diff --git a/lib/ints64/ints64.go b/lib/ints64/ints64.go
deleted file mode 100644
index 812096f8..00000000
--- a/lib/ints64/ints64.go
+++ /dev/null
@@ -1,352 +0,0 @@
-// Copyright 2018, Shulhan <ms@kilabit.info>. All rights reserved.
-// Use of this source code is governed by a BSD-style
-// license that can be found in the LICENSE file.
-
-// Package ints64 provide a library for working with slice of 64 bit integer.
-package ints64
-
-import (
- "git.sr.ht/~shulhan/pakakeh.go/lib/ints"
-)
-
-// Count number of class in slice.
-func Count(d []int64, class int64) (count int) {
- if len(d) == 0 {
- return
- }
- for x := 0; x < len(d); x++ {
- if d[x] == class {
- count++
- }
- }
- return
-}
-
-// Counts number of each class in slice.
-//
-// For example, if data is "[3,3,4]" and classes is "[3,4,5]", this function
-// will return "[2,1,0]".
-func Counts(d, classes []int64) (counts []int) {
- if len(classes) == 0 {
- return
- }
- counts = make([]int, len(classes))
- for x, c := range classes {
- counts[x] = Count(d, c)
- }
- return
-}
-
-// IndirectSort will sort the data and return the sorted index.
-func IndirectSort(d []int64, asc bool) (sortedIdx []int) {
- if len(d) == 0 {
- return
- }
-
- sortedIdx = make([]int, len(d))
- for x := 0; x < len(d); x++ {
- sortedIdx[x] = x
- }
-
- InplaceMergesort(d, sortedIdx, 0, len(d), asc)
-
- return
-}
-
-// InplaceMergesort in-place merge-sort without memory allocation.
-func InplaceMergesort(d []int64, idx []int, l, r int, asc bool) {
- // If length of data == Threshold, then use insertion sort.
- if l+7 >= r {
- InsertionSortWithIndices(d, idx, l, r, asc)
- return
- }
-
- // Divide into left and right.
- res := (r + l) % 2
- c := (r + l) / 2
- if res == 1 {
- c++
- }
-
- // Sort left.
- InplaceMergesort(d, idx, l, c, asc)
-
- // Sort right.
- InplaceMergesort(d, idx, c, r, asc)
-
- // Merge sorted left and right.
- if asc {
- if d[c-1] <= d[c] {
- // (4.1) If the last element of the left is lower then
- // the first element of the right, i.e. [1 2] [3 4];
- // no merging needed, return immediately.
- return
- }
- } else {
- if d[c-1] >= d[c] {
- return
- }
- }
-
- inplaceMerge(d, idx, l, c, r, asc)
-}
-
-// InsertionSortWithIndices will sort the data using insertion-sort algorithm.
-//
-// Parameters:
-// `d` is slice that will be sorted,
-// `ids` is indices of data "d",
-// `l` is starting index of slice to be sorted, and
-// `r` is end index of slice to be sorted.
-func InsertionSortWithIndices(d []int64, ids []int, l, r int, asc bool) {
- for x := l; x < r; x++ {
- for y := x + 1; y < r; y++ {
- if asc {
- if d[x] > d[y] {
- ints.Swap(ids, x, y)
- Swap(d, x, y)
- }
- } else {
- if d[x] < d[y] {
- ints.Swap(ids, x, y)
- Swap(d, x, y)
- }
- }
- }
- }
-}
-
-// Max find the maximum value in slice and return its value and index.
-//
-// If slice is empty, it will return false in ok.
-func Max(d []int64) (v int64, i int, ok bool) {
- if len(d) == 0 {
- return 0, 0, false
- }
- v = d[0]
- i = 0
- for x := 1; x < len(d); x++ {
- if d[x] > v {
- v = d[x]
- i = x
- }
- }
- return v, i, true
-}
-
-// IsExist will return true if value `v` exist in slice of `d`,
-// otherwise it will return false.
-func IsExist(d []int64, v int64) bool {
- for x := 0; x < len(d); x++ {
- if d[x] == v {
- return true
- }
- }
- return false
-}
-
-// MaxCountOf count number of occurrence of each element of classes
-// in data and return the class with maximum count.
-//
-// If `classes` is empty, it will return -1 and false.
-// If `data` is empty, it will return -2 and false.
-// If two or more class has the same count value, then the first max in the
-// class will be returned.
-//
-// For example, given a data [0, 1, 0, 1, 0] and classes [0, 1], the function
-// will count 0 as 3, 1 as 2; and return (0, true).
-func MaxCountOf(d, classes []int64) (int64, bool) {
- if len(classes) == 0 {
- return -1, false
- }
- if len(d) == 0 {
- return -2, false
- }
-
- counts := Counts(d, classes)
-
- _, i, _ := ints.Max(counts)
-
- return classes[i], true
-}
-
-// MaxRange find the (last) maximum value in range of slice between index "l"
-// and "r".
-//
-// WARNING: Caller must check for out of range index of "l" or "r" before
-// calling this function or it will be panic.
-func MaxRange(d []int64, l, r int) (v int64, i int) {
- v = d[l]
- i = l
- for l++; l < r; l++ {
- if d[l] >= v {
- v = d[l]
- i = l
- }
- }
- return
-}
-
-// Min find the minimum value in slice and return its value and index.
-//
-// If slice is empty, it will return false in ok.
-func Min(d []int64) (v int64, i int, ok bool) {
- if len(d) == 0 {
- return 0, 0, false
- }
- v = d[0]
- i = 0
- for x := 1; x < len(d); x++ {
- if d[x] < v {
- v = d[x]
- i = x
- }
- }
- return v, i, true
-}
-
-// MinRange find the (last) minimum value in range of slice between "l" to "r"
-// index.
-//
-// WARNING: this function does not check if slice is empty or index value of
-// "l" or "r" out of range, it other words you must check manually before
-// calling this function of it will become panic.
-func MinRange(d []int64, l, r int) (v int64, i int) {
- v = d[l]
- i = l
- for l++; l < r; l++ {
- if d[l] <= v {
- v = d[l]
- i = l
- }
- }
- return
-}
-
-// SortByIndex will sort the slice `d` using sorted index `sortedListID`.
-func SortByIndex(d *[]int64, sortedListID []int) {
- newd := make([]int64, len(*d))
-
- for x := range sortedListID {
- newd[x] = (*d)[sortedListID[x]]
- }
-
- (*d) = newd
-}
-
-// Sum all value in slice.
-func Sum(d []int64) (sum int64) {
- for x := 0; x < len(d); x++ {
- sum += d[x]
- }
- return
-}
-
-// Swap two indices value of slice.
-func Swap(d []int64, x, y int) {
- if x == y || len(d) <= 1 || x > len(d) || y > len(d) {
- return
- }
- d[x], d[y] = d[y], d[x]
-}
-
-// Let `x` be the first index of left-side, `y` be the first index of
-// the right-side, and `r` as length of slice `d`
-func inplaceMerge(d []int64, idx []int, x, y, r int, asc bool) {
- var ylast int
-
- // (4.3) Loop until either x or y reached the maximum slice.
- for x < r && y < r {
- // (4.3.1) IF DATA[x] <= DATA[y]
- if asc {
- if d[x] <= d[y] {
- x++
-
- // (4.3.1.2) IF x > y THEN GOTO 4.3
- if x >= y {
- goto next
- }
-
- // (4.3.1.3) GOTO 4.3
- continue
- }
- } else {
- if d[x] >= d[y] {
- x++
-
- if x >= y {
- goto next
- }
-
- continue
- }
- }
-
- // (4.3.2) LET YLAST := the next DATA[y] that is less DATA[x]
- ylast = moveY(d, x, y, r, asc)
-
- // (4.3.3) SWAP DATA, X, Y, YLAST
- multiswap(d, idx, x, y, ylast)
-
- next:
- // (4.3.4) LET Y := the minimum value between x and r on `d`
- minY(d, &x, &y, r, asc)
- }
-}
-
-// (4.3.4) LET Y := the minimum value between x and r on `d`.
-func minY(d []int64, x, y *int, r int, asc bool) {
- for *x < r {
- if asc {
- _, *y = MinRange(d, *x, r)
- } else {
- _, *y = MaxRange(d, *x, r)
- }
-
- if *y != *x {
- break
- }
- (*x)++
- }
-}
-
-func moveY(d []int64, x, y, r int, asc bool) int {
- yorg := y
- y++
- for y < r {
- if asc {
- if d[y] >= d[x] {
- break
- }
- if d[y] < d[yorg] {
- break
- }
- } else {
- if d[y] <= d[x] {
- break
- }
- if d[y] > d[yorg] {
- break
- }
- }
- y++
- }
- return y
-}
-
-func multiswap(d []int64, idx []int, x, y, ylast int) int {
- for y < ylast {
- ints.Swap(idx, x, y)
- Swap(d, x, y)
- x++
- y++
- if y >= ylast {
- return y
- }
- if d[x] <= d[y] {
- return y
- }
- }
-
- return y
-}
diff --git a/lib/ints64/ints64_test.go b/lib/ints64/ints64_test.go
deleted file mode 100644
index 828e5b35..00000000
--- a/lib/ints64/ints64_test.go
+++ /dev/null
@@ -1,382 +0,0 @@
-// Copyright 2018, Shulhan <ms@kilabit.info>. All rights reserved.
-// Use of this source code is governed by a BSD-style
-// license that can be found in the LICENSE file.
-
-package ints64
-
-import (
- "fmt"
- "testing"
-
- "git.sr.ht/~shulhan/pakakeh.go/lib/test"
-)
-
-var (
- d = [][]int64{
- {},
- {5, 6, 7, 8, 9, 0, 1, 2, 3, 4},
- {0, 1, 0, 1, 0, 1, 0, 1, 0},
- {1, 1, 2, 2, 3, 1, 2},
- }
- dSorted = [][]int64{
- {},
- {0, 1, 2, 3, 4, 5, 6, 7, 8, 9},
- {0, 0, 0, 0, 0, 1, 1, 1, 1},
- {1, 1, 1, 2, 2, 2, 3},
- }
- dSortedDesc = [][]int64{
- {},
- {9, 8, 7, 6, 5, 4, 3, 2, 1, 0},
- {1, 1, 1, 1, 0, 0, 0, 0, 0},
- {3, 2, 2, 2, 1, 1, 1},
- }
-)
-
-func TestMaxEmpty(t *testing.T) {
- gotv, goti, gotok := Max(d[0])
-
- test.Assert(t, "", int64(0), gotv)
- test.Assert(t, "", 0, goti)
- test.Assert(t, "", false, gotok)
-}
-
-func TestMax(t *testing.T) {
- gotv, goti, gotok := Max(d[1])
-
- test.Assert(t, "", int64(9), gotv)
- test.Assert(t, "", 4, goti)
- test.Assert(t, "", true, gotok)
-}
-
-func TestMinEmpty(t *testing.T) {
- gotv, goti, gotok := Min(d[0])
-
- test.Assert(t, "", int64(0), gotv)
- test.Assert(t, "", 0, goti)
- test.Assert(t, "", false, gotok)
-}
-
-func TestMin(t *testing.T) {
- gotv, goti, gotok := Min(d[1])
-
- test.Assert(t, "", int64(0), gotv)
- test.Assert(t, "", 5, goti)
- test.Assert(t, "", true, gotok)
-}
-
-func TestSum(t *testing.T) {
- got := Sum(d[1])
-
- test.Assert(t, "", int64(45), got)
-}
-
-func TestCount(t *testing.T) {
- got := Count(d[0], 0)
-
- test.Assert(t, "", 0, got)
-
- got = Count(d[1], 1)
-
- test.Assert(t, "", 1, got)
-
- got = Count(d[2], 1)
-
- test.Assert(t, "", 4, got)
-
- got = Count(d[3], 0)
-
- test.Assert(t, "", 0, got)
-
- got = Count(d[3], 3)
-
- test.Assert(t, "", 1, got)
-}
-
-func TestCountsEmpty(t *testing.T) {
- classes := []int64{1, 2, 3}
- exp := []int{0, 0, 0}
-
- got := Counts(d[0], classes)
-
- test.Assert(t, "", exp, got)
-}
-
-func TestCountsEmptyClasses(t *testing.T) {
- classes := []int64{}
- var exp []int
-
- got := Counts(d[1], classes)
-
- test.Assert(t, "", exp, got)
-}
-
-func TestCounts(t *testing.T) {
- classes := []int64{1, 2, 3}
- exp := []int{3, 3, 1}
-
- got := Counts(d[3], classes)
-
- test.Assert(t, "", exp, got)
-}
-
-func Test64MaxCountOf(t *testing.T) {
- classes := []int64{0, 1}
- exp := int64(0)
- got, _ := MaxCountOf(d[2], classes)
-
- test.Assert(t, "", exp, got)
-
- // Swap the class values.
- classes = []int64{1, 0}
- got, _ = MaxCountOf(d[2], classes)
-
- test.Assert(t, "", exp, got)
-}
-
-func TestSwapEmpty(t *testing.T) {
- exp := []int64{}
-
- Swap(d[0], 1, 6)
-
- test.Assert(t, "", exp, d[0])
-}
-
-func TestSwapEqual(t *testing.T) {
- in := make([]int64, len(d[1]))
- copy(in, d[1])
-
- exp := make([]int64, len(in))
- copy(exp, in)
-
- Swap(in, 1, 1)
-
- test.Assert(t, "", exp, in)
-}
-
-func TestSwapOutOfRange(t *testing.T) {
- in := make([]int64, len(d[1]))
- copy(in, d[1])
-
- exp := make([]int64, len(in))
- copy(exp, in)
-
- Swap(in, 1, 100)
-
- test.Assert(t, "", exp, in)
-}
-
-func TestSwap(t *testing.T) {
- in := make([]int64, len(d[1]))
- copy(in, d[1])
-
- exp := make([]int64, len(in))
- copy(exp, in)
-
- Swap(in, 0, len(in)-1)
-
- exp[0], exp[len(exp)-1] = exp[len(exp)-1], exp[0]
-
- test.Assert(t, "", exp, in)
-}
-
-func TestIsExist(t *testing.T) {
- var s bool
-
- // True positive.
- for _, d := range d {
- for _, v := range d {
- s = IsExist(d, v)
-
- test.Assert(t, "", true, s)
- }
- }
-
- // False positive.
- for _, d := range d {
- s = IsExist(d, -1)
- test.Assert(t, "", false, s)
- s = IsExist(d, 10)
- test.Assert(t, "", false, s)
- }
-}
-
-func TestInsertionSortWithIndices(t *testing.T) {
- for x := range d {
- data := make([]int64, len(d[x]))
-
- copy(data, d[x])
-
- ids := make([]int, len(data))
- for x := range ids {
- ids[x] = x
- }
-
- InsertionSortWithIndices(data, ids, 0, len(ids), true)
-
- test.Assert(t, "", dSorted[x], data)
- }
-}
-
-func TestInsertionSortWithIndicesDesc(t *testing.T) {
- for x := range d {
- data := make([]int64, len(d[x]))
-
- copy(data, d[x])
-
- ids := make([]int, len(data))
- for x := range ids {
- ids[x] = x
- }
-
- InsertionSortWithIndices(data, ids, 0, len(ids), false)
-
- test.Assert(t, "", dSortedDesc[x], data)
- }
-}
-
-func TestSortByIndex(t *testing.T) {
- ids := [][]int{
- {},
- {5, 6, 7, 8, 9, 0, 1, 2, 3, 4},
- {0, 2, 4, 6, 8, 1, 3, 5, 7},
- {0, 1, 5, 6, 2, 3, 4},
- }
-
- for x := range d {
- data := make([]int64, len(d[x]))
-
- copy(data, d[x])
-
- SortByIndex(&data, ids[x])
-
- test.Assert(t, "", dSorted[x], data)
- }
-}
-
-var ints64InSorts = [][]int64{
- {9, 8, 7, 6, 5, 4, 3},
- {9, 8, 7, 6, 5, 4, 3, 2, 1, 0},
- {0, 1, 2, 3, 4, 5, 6, 7, 8, 9},
- {0, 6, 7, 8, 5, 1, 2, 3, 4, 9},
- {9, 8, 7, 6, 5, 4, 3, 2, 1},
- {0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
- {51, 50, 56, 55, 55, 58, 55, 55, 58, 56,
- 57, 50, 56, 59, 62, 60, 49, 63, 61, 56,
- 58, 67, 61, 59, 60, 49, 56, 52, 61, 64,
- 70, 57, 65, 69, 57, 64, 62, 66, 63, 62,
- 54, 67, 61, 57, 55, 60, 30, 66, 57, 60,
- 68, 60, 61, 63, 58, 58, 56, 57, 60, 69,
- 69, 64, 63, 63, 67, 65, 58, 63, 64, 67,
- 59, 72, 63, 63, 65, 71, 67, 76, 73, 64,
- 67, 74, 60, 68, 65, 64, 67, 64, 65, 69,
- 77, 67, 72, 77, 72, 77, 61, 79, 77, 68,
- 62},
-}
-
-var ints64ExpSorts = [][]int64{
- {3, 4, 5, 6, 7, 8, 9},
- {0, 1, 2, 3, 4, 5, 6, 7, 8, 9},
- {0, 1, 2, 3, 4, 5, 6, 7, 8, 9},
- {0, 1, 2, 3, 4, 5, 6, 7, 8, 9},
- {1, 2, 3, 4, 5, 6, 7, 8, 9},
- {0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
- {30, 49, 49, 50, 50, 51, 52, 54, 55, 55,
- 55, 55, 55, 56, 56, 56, 56, 56, 56, 57,
- 57, 57, 57, 57, 57, 58, 58, 58, 58, 58,
- 58, 59, 59, 59, 60, 60, 60, 60, 60, 60,
- 60, 61, 61, 61, 61, 61, 61, 62, 62, 62,
- 62, 63, 63, 63, 63, 63, 63, 63, 63, 64,
- 64, 64, 64, 64, 64, 64, 65, 65, 65, 65,
- 65, 66, 66, 67, 67, 67, 67, 67, 67, 67,
- 67, 68, 68, 68, 69, 69, 69, 69, 70, 71,
- 72, 72, 72, 73, 74, 76, 77, 77, 77, 77,
- 79},
-}
-
-var ints64ExpSortsDesc = [][]int64{
- {9, 8, 7, 6, 5, 4, 3},
- {9, 8, 7, 6, 5, 4, 3, 2, 1, 0},
- {9, 8, 7, 6, 5, 4, 3, 2, 1, 0},
- {9, 8, 7, 6, 5, 4, 3, 2, 1, 0},
- {9, 8, 7, 6, 5, 4, 3, 2, 1},
- {0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
- {79, 77, 77, 77, 77, 76, 74, 73, 72, 72,
- 72, 71, 70, 69, 69, 69, 69, 68, 68, 68,
- 67, 67, 67, 67, 67, 67, 67, 67, 66, 66,
- 65, 65, 65, 65, 65, 64, 64, 64, 64, 64,
- 64, 64, 63, 63, 63, 63, 63, 63, 63, 63,
- 62, 62, 62, 62, 61, 61, 61, 61, 61, 61,
- 60, 60, 60, 60, 60, 60, 60, 59, 59, 59,
- 58, 58, 58, 58, 58, 58, 57, 57, 57, 57,
- 57, 57, 56, 56, 56, 56, 56, 56, 55, 55,
- 55, 55, 55, 54, 52, 51, 50, 50, 49, 49,
- 30},
-}
-
-func TestIndirectSort(t *testing.T) {
- var res, exp string
-
- for i := range ints64InSorts {
- IndirectSort(ints64InSorts[i], true)
-
- res = fmt.Sprint(ints64InSorts[i])
- exp = fmt.Sprint(ints64ExpSorts[i])
-
- test.Assert(t, "", exp, res)
- }
-}
-
-func TestIndirectSortDesc(t *testing.T) {
- var res, exp string
-
- for i := range ints64InSorts {
- IndirectSort(ints64InSorts[i], false)
-
- res = fmt.Sprint(ints64InSorts[i])
- exp = fmt.Sprint(ints64ExpSortsDesc[i])
-
- test.Assert(t, "", exp, res)
- }
-}
-
-func TestIndirectSort_Stability(t *testing.T) {
- exp := []int{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
- got := IndirectSort(ints64InSorts[5], true)
-
- test.Assert(t, "", exp, got)
-}
-
-func TestIndirectSortDesc_Stability(t *testing.T) {
- exp := []int{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
- got := IndirectSort(ints64InSorts[5], false)
-
- test.Assert(t, "", exp, got)
-}
-
-func TestInplaceMergesort(t *testing.T) {
- size := len(ints64InSorts[6])
- idx := make([]int, size)
-
- InplaceMergesort(ints64InSorts[6], idx, 0, size, true)
-
- test.Assert(t, "", ints64ExpSorts[6], ints64InSorts[6])
-}
-
-func TestIndirectSort_SortByIndex(t *testing.T) {
- expListID := []int{9, 8, 7, 6, 5, 4, 3, 2, 1, 0}
- in1 := []int64{9, 8, 7, 6, 5, 4, 3, 2, 1, 0}
- in2 := []int64{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
-
- exp := fmt.Sprint(in1)
-
- sortedListID := IndirectSort(in1, true)
-
- test.Assert(t, "", expListID, sortedListID)
-
- // Reverse the sort.
- SortByIndex(&in2, sortedListID)
-
- got := fmt.Sprint(in2)
-
- test.Assert(t, "", exp, got)
-}
diff --git a/lib/memfs/memfs.go b/lib/memfs/memfs.go
index e2f35ef8..e80b7e58 100644
--- a/lib/memfs/memfs.go
+++ b/lib/memfs/memfs.go
@@ -18,7 +18,7 @@ import (
libbytes "git.sr.ht/~shulhan/pakakeh.go/lib/bytes"
libhtml "git.sr.ht/~shulhan/pakakeh.go/lib/html"
- libints "git.sr.ht/~shulhan/pakakeh.go/lib/ints"
+ "git.sr.ht/~shulhan/pakakeh.go/lib/slices"
libstrings "git.sr.ht/~shulhan/pakakeh.go/lib/strings"
"git.sr.ht/~shulhan/pakakeh.go/lib/watchfs/v2"
)
@@ -372,7 +372,7 @@ func (mfs *MemFS) Search(words []string, snippetLen int) (results []SearchResult
continue
}
- allIndexes = libints.MergeByDistance(allIndexes, nil, snippetLen)
+ allIndexes = slices.MergeByDistance(allIndexes, nil, snippetLen)
snippets := libbytes.SnippetByIndexes(node.lowerv, allIndexes, snippetLen)
for _, snippet := range snippets {
result.Snippets = append(result.Snippets, string(snippet))
diff --git a/lib/mining/classifier/rf/rf.go b/lib/mining/classifier/rf/rf.go
index 2ac77845..07da00ea 100644
--- a/lib/mining/classifier/rf/rf.go
+++ b/lib/mining/classifier/rf/rf.go
@@ -14,9 +14,9 @@ import (
"errors"
"fmt"
"math"
+ "slices"
"git.sr.ht/~shulhan/pakakeh.go/lib/floats64"
- "git.sr.ht/~shulhan/pakakeh.go/lib/ints"
"git.sr.ht/~shulhan/pakakeh.go/lib/mining/classifier"
"git.sr.ht/~shulhan/pakakeh.go/lib/mining/classifier/cart"
libstrings "git.sr.ht/~shulhan/pakakeh.go/lib/strings"
@@ -314,7 +314,7 @@ func (forest *Runtime) Votes(sample *tabula.Row, sampleIdx int) (
for x, tree := range forest.trees {
// (1)
if sampleIdx >= 0 {
- exist := ints.IsExist(forest.bagIndices[x],
+ exist := slices.Contains(forest.bagIndices[x],
sampleIdx)
if exist {
continue
diff --git a/lib/mining/classifier/runtime.go b/lib/mining/classifier/runtime.go
index d6ddd7bb..eeea1621 100644
--- a/lib/mining/classifier/runtime.go
+++ b/lib/mining/classifier/runtime.go
@@ -10,8 +10,8 @@ import (
"git.sr.ht/~shulhan/pakakeh.go/lib/dsv"
"git.sr.ht/~shulhan/pakakeh.go/lib/floats64"
- "git.sr.ht/~shulhan/pakakeh.go/lib/ints"
"git.sr.ht/~shulhan/pakakeh.go/lib/numbers"
+ "git.sr.ht/~shulhan/pakakeh.go/lib/slices"
libstrings "git.sr.ht/~shulhan/pakakeh.go/lib/strings"
"git.sr.ht/~shulhan/pakakeh.go/lib/tabula"
)
@@ -336,7 +336,7 @@ func (rt *Runtime) computePerfByProbs(samples tabula.ClasetInterface,
actuals []string, probs []float64,
) {
vs := samples.GetClassValueSpace()
- nactuals := ints.To64(samples.Counts())
+ nactuals := slices.ToInt64(samples.Counts())
nclass := libstrings.CountTokens(actuals, vs, false)
pprev := math.Inf(-1)
diff --git a/lib/slices/benchmark_test.go b/lib/slices/benchmark_test.go
new file mode 100644
index 00000000..923f9429
--- /dev/null
+++ b/lib/slices/benchmark_test.go
@@ -0,0 +1,50 @@
+// SPDX-FileCopyrightText: 2019 M. Shulhan <ms@kilabit.info>
+//
+// SPDX-License-Identifier: BSD-3-Clause
+
+package slices_test
+
+import (
+ "sort"
+ "testing"
+
+ "git.sr.ht/~shulhan/pakakeh.go/lib/slices"
+)
+
+func BenchmarkSort_int(b *testing.B) {
+ const n = 10_000
+
+ var data = make([]int, n)
+ generateRandomInts(data, n)
+
+ var dataIndirect = make([]int, n)
+ copy(dataIndirect, data)
+
+ var dataInplaceMergesort = make([]int, n)
+ var inplaceIdx = make([]int, n)
+ copy(dataInplaceMergesort, data)
+
+ var dataSortInts = make([]int, n)
+ copy(dataSortInts, data)
+ b.ResetTimer()
+
+ b.Run(`sort.Ints`, func(b *testing.B) {
+ for x := 0; x < b.N; x++ {
+ sort.Ints(dataSortInts)
+ }
+ })
+
+ b.Run(`IndirectSort`, func(b *testing.B) {
+ for x := 0; x < b.N; x++ {
+ slices.IndirectSort(dataIndirect, true)
+ }
+ })
+
+ b.Run(`InplaceMergesort`, func(b *testing.B) {
+ for x := 0; x < b.N; x++ {
+ slices.InplaceMergesort(dataInplaceMergesort,
+ inplaceIdx, 0, n, true)
+ }
+ })
+
+}
diff --git a/lib/slices/example_test.go b/lib/slices/example_test.go
new file mode 100644
index 00000000..587d80fd
--- /dev/null
+++ b/lib/slices/example_test.go
@@ -0,0 +1,34 @@
+// SPDX-FileCopyrightText: 2018 M. Shulhan <ms@kilabit.info>
+//
+// SPDX-License-Identifier: BSD-3-Clause
+
+package slices_test
+
+import (
+ "fmt"
+
+ "git.sr.ht/~shulhan/pakakeh.go/lib/slices"
+)
+
+func ExampleMax2() {
+ ints := []int{5, 6, 7, 8, 9, 0, 1, 2, 3, 4}
+
+ fmt.Println(slices.Max2(ints))
+
+ // Output:
+ // 9 4
+}
+
+func ExampleMergeByDistance() {
+ a := []int{1, 5, 9}
+ b := []int{4, 11, 15}
+
+ ab := slices.MergeByDistance(a, b, 3)
+ ba := slices.MergeByDistance(b, a, 3)
+ fmt.Println(ab)
+ fmt.Println(ba)
+
+ // Output:
+ // [1 5 9 15]
+ // [1 5 9 15]
+}
diff --git a/lib/slices/slices.go b/lib/slices/slices.go
new file mode 100644
index 00000000..40c80629
--- /dev/null
+++ b/lib/slices/slices.go
@@ -0,0 +1,403 @@
+// SPDX-FileCopyrightText: 2024 M. Shulhan <ms@kilabit.info>
+//
+// SPDX-License-Identifier: BSD-3-Clause
+
+// Package slices complement the standard [slices] package for working with
+// slices with type that is comparable.
+package slices
+
+import (
+ "cmp"
+
+ "golang.org/x/exp/constraints"
+)
+
+// Count the number of occurence of val in slice.
+func Count[S []E, E comparable](slice S, val E) (count int) {
+ if len(slice) == 0 {
+ return 0
+ }
+ for _, v := range slice {
+ if v == val {
+ count++
+ }
+ }
+ return count
+}
+
+// Counts number of each class in slice.
+//
+// For example, if slice is "[1,1,2]" and classes is "[1,2]", this function
+// will return "[2,1]".
+func Counts[S []E, E comparable](slice S, classes S) (counts []int) {
+ if len(classes) == 0 {
+ return nil
+ }
+ counts = make([]int, len(classes))
+ for x, val := range classes {
+ counts[x] = Count(slice, val)
+ }
+ return counts
+}
+
+// IndirectSort sort the data and return the sorted index.
+func IndirectSort[S []E, E cmp.Ordered](slice S, isAsc bool) (
+ sortedIdx []int,
+) {
+ sortedIdx = make([]int, len(slice))
+ for x := range len(slice) {
+ sortedIdx[x] = x
+ }
+
+ InplaceMergesort(slice, sortedIdx, 0, len(slice), isAsc)
+
+ return sortedIdx
+}
+
+// InplaceInsertionSort sort the data and their index using insertion-sort
+// algorithm.
+//
+// The parameter
+// `slice` is the slice that will be sorted,
+// `ids` is indices of slice,
+// `l` is starting index of slice to be sorted, and
+// `r` is the end index of slice to be sorted.
+func InplaceInsertionSort[S []E, E cmp.Ordered](
+ slice S, ids []int, l, r int, isAsc bool,
+) {
+ var x int
+ var y int
+ for x = l; x < r; x++ {
+ for y = x + 1; y < r; y++ {
+ if isAsc {
+ if slice[x] > slice[y] {
+ Swap(ids, x, y)
+ Swap(slice, x, y)
+ }
+ } else {
+ if slice[x] < slice[y] {
+ Swap(ids, x, y)
+ Swap(slice, x, y)
+ }
+ }
+ }
+ }
+}
+
+// InplaceMergesort sort the slice "slice" in-place, without memory
+// allocation, using mergesort algorithm.
+// The ids parameter is empty slice with length equal to the length of slice,
+// which will used for storing sorted index.
+func InplaceMergesort[S []E, E cmp.Ordered](
+ slice S, ids []int, l, r int, isAsc bool,
+) {
+ if l+7 >= r {
+ // If data length <= Threshold, then use insertion sort.
+ InplaceInsertionSort(slice, ids, l, r, isAsc)
+ return
+ }
+
+ // Divide into left and right.
+ var c = ((r + l) / 2) + (r+l)%2
+
+ // Sort left.
+ InplaceMergesort(slice, ids, l, c, isAsc)
+
+ // Sort right.
+ InplaceMergesort(slice, ids, c, r, isAsc)
+
+ // Merge sorted left and right.
+ if isAsc {
+ if slice[c-1] <= slice[c] {
+ // If the last element of the left is lower then
+ // the first element of the right, i.e. [1 2] [3 4];
+ // no merging needed, return immediately.
+ return
+ }
+ } else {
+ if slice[c-1] >= slice[c] {
+ return
+ }
+ }
+
+ inplaceMerge(slice, ids, l, c, r, isAsc)
+}
+
+// Max2 find the maximum value in slice and return its value and index.
+// If slice is empty, it will return (0, -1).
+func Max2[S []E, E cmp.Ordered](slice S) (max E, idx int) {
+ if len(slice) == 0 {
+ return max, -1
+ }
+ max = slice[0]
+ idx = 0
+ for x := 1; x < len(slice); x++ {
+ if slice[x] > max {
+ max = slice[x]
+ idx = x
+ }
+ }
+ return max, idx
+}
+
+// MaxCountOf count number of occurrence of each element of classes
+// in data and return the class with maximum count.
+//
+// If classes has the same count value, then the first max in the class will
+// be returned.
+//
+// For example, given a data [5, 6, 5, 6, 5] and classes [5, 6, 7], the
+// function will count 5 as 3, 6 as 2, and 7 as 0.
+// Since frequency of 5 is greater than 6 and 7, then it will return `5` and
+// true.
+func MaxCountOf[S []E, E comparable](slice S, classes S) (maxClass E, state int) {
+ if len(classes) == 0 {
+ return maxClass, -1
+ }
+ if len(slice) == 0 {
+ return maxClass, -2
+ }
+
+ var counts []int = Counts(slice, classes)
+
+ _, idx := Max2(counts)
+
+ return classes[idx], 0
+}
+
+// MaxRange find the (last) maximum value in slice between index "l" and "r".
+//
+// WARNING: This function does not check index out of range.
+func MaxRange[S []E, E cmp.Ordered](slice S, l, r int) (v E, i int) {
+ v = slice[l]
+ i = l
+ for l++; l < r; l++ {
+ if slice[l] >= v {
+ v = slice[l]
+ i = l
+ }
+ }
+ return
+}
+
+// MergeByDistance merge two slice of integers by their distance between each
+// others.
+//
+// For example, if slice a contains "{1, 5, 9}" and b contains
+// "{4, 11, 15}" and the distance is 3, the output of merged is
+// "{1, 5, 9, 15}". The 4 and 11 are not included because 4 is in
+// range between 1 and (1+3), and 11 is in range between 9 and 9+3.
+func MergeByDistance[S []E, E ~int | ~int8 | ~int16 | ~int32 | ~int64](
+ a, b S, distance E,
+) (out S) {
+ var lenab = len(a) + len(b)
+ if lenab == 0 {
+ return nil
+ }
+
+ var ab = make(S, 0, lenab)
+ ab = append(ab, a...)
+ ab = append(ab, b...)
+
+ var idx = make([]int, lenab)
+ InplaceMergesort(ab, idx, 0, lenab, true)
+
+ out = append(out, ab[0])
+ var last E = ab[0]
+ for x := 1; x < len(ab); x++ {
+ if ab[x] > last+distance {
+ out = append(out, ab[x])
+ last = ab[x]
+ continue
+ }
+ }
+
+ return out
+}
+
+// Min2 find the minimum value in slice and return its value and index.
+//
+// If slice is empty, it will return (0, -1).
+func Min2[S []E, E cmp.Ordered](slice S) (min E, idx int) {
+ if len(slice) == 0 {
+ return min, -1
+ }
+ min = slice[0]
+ idx = 0
+ for x := 1; x < len(slice); x++ {
+ if slice[x] < min {
+ min = slice[x]
+ idx = x
+ }
+ }
+ return min, idx
+}
+
+// MinRange find the (last) minimum value in slice between index "l" and "r".
+//
+// WARNING: This function does not check index out of range.
+func MinRange[S []E, E cmp.Ordered](slice S, l, r int) (v E, i int) {
+ v = slice[l]
+ i = l
+ for l++; l < r; l++ {
+ if slice[l] <= v {
+ v = slice[l]
+ i = l
+ }
+ }
+ return
+}
+
+// Remove val from slice if its exist and return new slice and true.
+// Otherwise, if val not found, return unmodified slice and false.
+func Remove[S []E, E comparable](slice S, v E) (S, bool) {
+ for x := 0; x < len(slice); x++ {
+ if slice[x] == v {
+ slice = append(slice[:x], slice[x+1:]...)
+ return slice, true
+ }
+ }
+ return slice, false
+}
+
+// SortByIndex sort the slice using sorted index sortedIdx.
+func SortByIndex[S []E, E cmp.Ordered](slice *S, sortedIdx []int) {
+ var newSlice = make([]E, len(*slice))
+
+ for x := range len(sortedIdx) {
+ newSlice[x] = (*slice)[sortedIdx[x]]
+ }
+
+ (*slice) = newSlice
+}
+
+// Sum all value in slice.
+func Sum[S []E, E constraints.Integer | constraints.Float](slice S) (sum E) {
+ for x := 0; x < len(slice); x++ {
+ sum += slice[x]
+ }
+ return sum
+}
+
+// Swap two indices value of slice.
+func Swap[S []E, E any](slice S, x, y int) {
+ if x == y || len(slice) <= 1 || x > len(slice) || y > len(slice) {
+ return
+ }
+ slice[x], slice[y] = slice[y], slice[x]
+}
+
+// ToInt64 convert slice of integer to its 64 bit values.
+func ToInt64[S []E, E constraints.Integer](ints S) []int64 {
+ i64 := make([]int64, len(ints))
+ for x, v := range ints {
+ i64[x] = int64(v)
+ }
+ return i64
+}
+
+// Let `x` be the first index of left-side, `y` be the first index of
+// the right-side, and `r` as length of slice `slice`
+func inplaceMerge[S []E, E cmp.Ordered](
+ slice S, ids []int, x, y, r int, isAsc bool,
+) {
+ var ylast int
+
+ // (4.3) Loop until either x or y reached the maximum slice.
+ for x < r && y < r {
+ // (4.3.1) IF DATA[x] <= DATA[y]
+ if isAsc {
+ if slice[x] <= slice[y] {
+ x++
+
+ // (4.3.1.2) IF x > y THEN GOTO 4.3
+ if x >= y {
+ goto next
+ }
+
+ // (4.3.1.3) GOTO 4.3
+ continue
+ }
+ } else {
+ if slice[x] >= slice[y] {
+ x++
+
+ if x >= y {
+ goto next
+ }
+
+ continue
+ }
+ }
+
+ // (4.3.2) LET YLAST := the next DATA[y] that is less DATA[x]
+ ylast = moveY(slice, x, y, r, isAsc)
+
+ // (4.3.3) SWAP DATA, X, Y, YLAST
+ inplaceMultiswap(slice, ids, x, y, ylast)
+
+ next:
+ // (4.3.4) LET Y := the minimum value between x and r on
+ // `slice`.
+ minY(slice, &x, &y, r, isAsc)
+ }
+}
+
+func inplaceMultiswap[S []E, E cmp.Ordered](
+ slice S, ids []int, x, y, ylast int,
+) int {
+ for y < ylast {
+ Swap(ids, x, y)
+ Swap(slice, x, y)
+ x++
+ y++
+ if y >= ylast {
+ return y
+ }
+ if slice[x] <= slice[y] {
+ return y
+ }
+ }
+
+ return y
+}
+
+// (4.3.4) LET Y := the minimum value between x and r on slice.
+func minY[S []E, E cmp.Ordered](slice S, x, y *int, r int, isAsc bool) {
+ for *x < r {
+ if isAsc {
+ _, *y = MinRange(slice, *x, r)
+ } else {
+ _, *y = MaxRange(slice, *x, r)
+ }
+
+ if *y != *x {
+ break
+ }
+ (*x)++
+ }
+}
+
+func moveY[S []E, E cmp.Ordered](slice S, x, y, r int, isAsc bool) int {
+ yorg := y
+ y++
+ for y < r {
+ if isAsc {
+ if slice[y] >= slice[x] {
+ break
+ }
+ if slice[y] < slice[yorg] {
+ break
+ }
+ } else {
+ if slice[y] <= slice[x] {
+ break
+ }
+ if slice[y] > slice[yorg] {
+ break
+ }
+ }
+ y++
+ }
+ return y
+}
diff --git a/lib/slices/slices_int_test.go b/lib/slices/slices_int_test.go
new file mode 100644
index 00000000..ebb327e0
--- /dev/null
+++ b/lib/slices/slices_int_test.go
@@ -0,0 +1,463 @@
+// SPDX-FileCopyrightText: 2024 M. Shulhan <ms@kilabit.info>
+//
+// SPDX-License-Identifier: BSD-3-Clause
+
+package slices_test
+
+import (
+ "crypto/rand"
+ "log"
+ "math"
+ "math/big"
+ "sort"
+ "testing"
+
+ "git.sr.ht/~shulhan/pakakeh.go/lib/slices"
+ "git.sr.ht/~shulhan/pakakeh.go/lib/test"
+)
+
+func TestCount_int(t *testing.T) {
+ var listCase = []struct {
+ desc string
+ list []int
+ val int
+ exp int
+ }{{
+ desc: `empty list`,
+ list: []int{},
+ }, {
+ desc: `found`,
+ list: []int{5, 6, 7, 8, 9, 0, 1, 2, 3, 4},
+ val: 1,
+ exp: 1,
+ }, {
+ desc: `not found`,
+ list: []int{5, 6, 7, 8, 9, 0, 1, 2, 3, 4},
+ val: 10,
+ }}
+
+ for _, tcase := range listCase {
+ var got = slices.Count(tcase.list, tcase.val)
+ test.Assert(t, tcase.desc, tcase.exp, got)
+ }
+}
+
+func TestCounts_int(t *testing.T) {
+ var listCase = []struct {
+ desc string
+ list []int
+ classes []int
+ exp []int
+ }{{
+ desc: `empty list`,
+ classes: []int{1, 2, 3},
+ exp: []int{0, 0, 0},
+ }, {
+ desc: `empty classes`,
+ list: []int{5, 6, 7, 8, 9, 0, 1, 2, 3, 4},
+ }, {
+ desc: `ok`,
+ list: []int{1, 1, 2, 2, 3, 1, 2},
+ classes: []int{1, 2, 3},
+ exp: []int{3, 3, 1},
+ }}
+
+ for _, tcase := range listCase {
+ var got = slices.Counts(tcase.list, tcase.classes)
+ test.Assert(t, tcase.desc, tcase.exp, got)
+ }
+}
+
+func TestIndirectSort_int(t *testing.T) {
+ var listCase = []struct {
+ desc string
+ slice []int
+ expSortedIdx []int
+ exp []int
+ isAsc bool
+ }{{
+ desc: `case 1 asc`,
+ slice: []int{9, 8, 7, 6, 5, 4, 3},
+ expSortedIdx: []int{6, 5, 4, 3, 2, 1, 0},
+ exp: []int{3, 4, 5, 6, 7, 8, 9},
+ isAsc: true,
+ }, {
+ desc: `case 1 desc`,
+ slice: []int{9, 8, 7, 6, 5, 4, 3},
+ expSortedIdx: []int{0, 1, 2, 3, 4, 5, 6},
+ exp: []int{9, 8, 7, 6, 5, 4, 3},
+ isAsc: false,
+ }, {
+ desc: `case 2 asc`,
+ slice: []int{9, 8, 7, 6, 5, 4, 3, 2, 1, 0},
+ expSortedIdx: []int{9, 8, 7, 6, 5, 4, 3, 2, 1, 0},
+ exp: []int{0, 1, 2, 3, 4, 5, 6, 7, 8, 9},
+ isAsc: true,
+ }, {
+ desc: `case 2 desc`,
+ slice: []int{9, 8, 7, 6, 5, 4, 3, 2, 1, 0},
+ expSortedIdx: []int{0, 1, 2, 3, 4, 5, 6, 7, 8, 9},
+ exp: []int{9, 8, 7, 6, 5, 4, 3, 2, 1, 0},
+ isAsc: false,
+ }, {
+ desc: `case 3 asc`,
+ slice: []int{0, 1, 2, 3, 4, 5, 6, 7, 8, 9},
+ expSortedIdx: []int{0, 1, 2, 3, 4, 5, 6, 7, 8, 9},
+ exp: []int{0, 1, 2, 3, 4, 5, 6, 7, 8, 9},
+ isAsc: true,
+ }, {
+ desc: `case 3 desc`,
+ slice: []int{0, 1, 2, 3, 4, 5, 6, 7, 8, 9},
+ expSortedIdx: []int{9, 8, 7, 6, 5, 4, 3, 2, 1, 0},
+ exp: []int{9, 8, 7, 6, 5, 4, 3, 2, 1, 0},
+ isAsc: false,
+ }, {
+ desc: `case 4 asc`,
+ slice: []int{0, 6, 7, 8, 5, 1, 2, 3, 4, 9},
+ expSortedIdx: []int{0, 5, 6, 7, 8, 4, 1, 2, 3, 9},
+ exp: []int{0, 1, 2, 3, 4, 5, 6, 7, 8, 9},
+ isAsc: true,
+ }, {
+ desc: `case 4 desc`,
+ slice: []int{0, 6, 7, 8, 5, 1, 2, 3, 4, 9},
+ expSortedIdx: []int{9, 3, 2, 1, 4, 8, 7, 6, 5, 0},
+ exp: []int{9, 8, 7, 6, 5, 4, 3, 2, 1, 0},
+ isAsc: false,
+ }, {
+ desc: `stability asc`,
+ slice: []int{0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
+ expSortedIdx: []int{0, 1, 2, 3, 4, 5, 6, 7, 8, 9},
+ exp: []int{0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
+ isAsc: true,
+ }, {
+ desc: `stability desc`,
+ slice: []int{0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
+ expSortedIdx: []int{0, 1, 2, 3, 4, 5, 6, 7, 8, 9},
+ exp: []int{0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
+ isAsc: false,
+ }}
+
+ for _, tcase := range listCase {
+ var gotSortedIdx = slices.IndirectSort(tcase.slice,
+ tcase.isAsc)
+ test.Assert(t, tcase.desc+` sortedIdx`,
+ tcase.expSortedIdx, gotSortedIdx)
+ test.Assert(t, tcase.desc, tcase.exp, tcase.slice)
+ }
+}
+
+func TestIndirectSort_compareSortInts_int(t *testing.T) {
+ const n = 10_000
+ var slice1 = make([]int, n)
+ generateRandomInts(slice1, n)
+
+ var slice2 = make([]int, len(slice1))
+ copy(slice2, slice1)
+
+ sort.Ints(slice1)
+ slices.IndirectSort(slice2, true)
+
+ test.Assert(t, `vs sort.Ints`, slice1, slice2)
+}
+
+func TestInplaceInsertionSort_int(t *testing.T) {
+ var listCase = []struct {
+ desc string
+ slice []int
+ exp []int
+ isAsc bool
+ }{{
+ desc: `empty`,
+ }, {
+ desc: `case 1 asc`,
+ slice: []int{5, 6, 7, 8, 9, 0, 1, 2, 3, 4},
+ exp: []int{0, 1, 2, 3, 4, 5, 6, 7, 8, 9},
+ isAsc: true,
+ }, {
+ desc: `case 1 desc`,
+ slice: []int{5, 6, 7, 8, 9, 0, 1, 2, 3, 4},
+ exp: []int{9, 8, 7, 6, 5, 4, 3, 2, 1, 0},
+ isAsc: false,
+ }, {
+ desc: `case 2 asc`,
+ slice: []int{0, 1, 0, 1, 0, 1, 0, 1, 0},
+ exp: []int{0, 0, 0, 0, 0, 1, 1, 1, 1},
+ isAsc: true,
+ }, {
+ desc: `case 2 desc`,
+ slice: []int{0, 1, 0, 1, 0, 1, 0, 1, 0},
+ exp: []int{1, 1, 1, 1, 0, 0, 0, 0, 0},
+ isAsc: false,
+ }, {
+ desc: `case 3 asc`,
+ slice: []int{1, 1, 2, 2, 3, 1, 2},
+ exp: []int{1, 1, 1, 2, 2, 2, 3},
+ isAsc: true,
+ }, {
+ desc: `case 3 desc`,
+ slice: []int{1, 1, 2, 2, 3, 1, 2},
+ exp: []int{3, 2, 2, 2, 1, 1, 1},
+ }}
+
+ for _, tcase := range listCase {
+ var idx = make([]int, len(tcase.slice))
+
+ slices.InplaceInsertionSort(tcase.slice, idx,
+ 0, len(tcase.slice), tcase.isAsc)
+
+ test.Assert(t, tcase.desc, tcase.exp, tcase.slice)
+ }
+}
+
+func TestInplaceMergesort_int(t *testing.T) {
+ var list = []int{
+ 51, 50, 56, 55, 55, 58, 55, 55, 58, 56,
+ 57, 50, 56, 59, 62, 60, 49, 63, 61, 56,
+ 58, 67, 61, 59, 60, 49, 56, 52, 61, 64,
+ 70, 57, 65, 69, 57, 64, 62, 66, 63, 62,
+ 54, 67, 61, 57, 55, 60, 30, 66, 57, 60,
+ 68, 60, 61, 63, 58, 58, 56, 57, 60, 69,
+ 69, 64, 63, 63, 67, 65, 58, 63, 64, 67,
+ 59, 72, 63, 63, 65, 71, 67, 76, 73, 64,
+ 67, 74, 60, 68, 65, 64, 67, 64, 65, 69,
+ 77, 67, 72, 77, 72, 77, 61, 79, 77, 68,
+ 62,
+ }
+ var exp = []int{
+ 30, 49, 49, 50, 50, 51, 52, 54, 55, 55,
+ 55, 55, 55, 56, 56, 56, 56, 56, 56, 57,
+ 57, 57, 57, 57, 57, 58, 58, 58, 58, 58,
+ 58, 59, 59, 59, 60, 60, 60, 60, 60, 60,
+ 60, 61, 61, 61, 61, 61, 61, 62, 62, 62,
+ 62, 63, 63, 63, 63, 63, 63, 63, 63, 64,
+ 64, 64, 64, 64, 64, 64, 65, 65, 65, 65,
+ 65, 66, 66, 67, 67, 67, 67, 67, 67, 67,
+ 67, 68, 68, 68, 69, 69, 69, 69, 70, 71,
+ 72, 72, 72, 73, 74, 76, 77, 77, 77, 77,
+ 79,
+ }
+
+ var size = len(list)
+ var idx = make([]int, size)
+
+ slices.InplaceMergesort(list, idx, 0, size, true)
+
+ test.Assert(t, `InplaceMergesort`, exp, list)
+}
+
+func TestMax_int(t *testing.T) {
+ var listCase = []struct {
+ desc string
+ slice []int
+ exp int
+ expIdx int
+ }{{
+ desc: `empty slice`,
+ expIdx: -1,
+ }, {
+ desc: `case 1`,
+ slice: []int{5, 6, 7, 8, 9, 0, 1, 2, 3, 4},
+ exp: 9,
+ expIdx: 4,
+ }}
+
+ for _, tcase := range listCase {
+ gotMax, gotIdx := slices.Max2(tcase.slice)
+ test.Assert(t, tcase.desc+` max`, tcase.exp, gotMax)
+ test.Assert(t, tcase.desc+` idx`, tcase.expIdx, gotIdx)
+ }
+}
+
+func TestMaxCountOf_int(t *testing.T) {
+ var listCase = []struct {
+ desc string
+ slice []int
+ classes []int
+ exp int
+ expState int
+ }{{
+ desc: `empty classes`,
+ slice: []int{1, 2, 1},
+ expState: -1,
+ }, {
+ desc: `empty slice`,
+ classes: []int{1, 2},
+ expState: -2,
+ }, {
+ desc: `case 1`,
+ slice: []int{0, 1, 0, 1, 0, 1, 0, 1, 0},
+ classes: []int{0, 1},
+ exp: 0,
+ expState: 0,
+ }, {
+ desc: `case 2`,
+ slice: []int{0, 1, 0, 1, 0, 1, 0, 1, 0},
+ classes: []int{1, 0},
+ exp: 0,
+ expState: 0,
+ }}
+
+ for _, tcase := range listCase {
+ got, gotState := slices.MaxCountOf(tcase.slice, tcase.classes)
+ test.Assert(t, tcase.desc+` maxCount`, tcase.exp, got)
+ test.Assert(t, tcase.desc+` state`, tcase.expState, gotState)
+ }
+}
+
+func TestMin_int(t *testing.T) {
+ var listCase = []struct {
+ desc string
+ slice []int
+ exp int
+ expIdx int
+ }{{
+ desc: `empty`,
+ expIdx: -1,
+ }, {
+ desc: `case 1`,
+ slice: []int{5, 6, 7, 8, 9, 0, 1, 2, 3, 4},
+ exp: 0,
+ expIdx: 5,
+ }}
+
+ for _, tcase := range listCase {
+ gotMin, gotIdx := slices.Min2(tcase.slice)
+ test.Assert(t, tcase.desc, tcase.exp, gotMin)
+ test.Assert(t, tcase.desc, tcase.expIdx, gotIdx)
+ }
+}
+
+func TestRemove_int(t *testing.T) {
+ var listCase = []struct {
+ slice []int
+ exp []int
+ val int
+ expOK bool
+ }{{
+ slice: []int{},
+ val: 1,
+ exp: []int{},
+ }, {
+ slice: []int{1},
+ val: 1,
+ exp: []int{},
+ expOK: true,
+ }, {
+ slice: []int{1, 2, 3, 4},
+ val: 5,
+ exp: []int{1, 2, 3, 4},
+ }, {
+ slice: []int{1, 2, 3, 4},
+ val: 1,
+ exp: []int{2, 3, 4},
+ expOK: true,
+ }}
+
+ var got []int
+ var ok bool
+ for _, tcase := range listCase {
+ got, ok = slices.Remove(tcase.slice, tcase.val)
+ test.Assert(t, `ok`, tcase.expOK, ok)
+ test.Assert(t, `result`, tcase.exp, got)
+ }
+}
+
+func TestSortByIndex_int(t *testing.T) {
+ var listCase = []struct {
+ desc string
+ slice []int
+ sortedIdx []int
+ exp []int
+ }{{
+ desc: `empty slice`,
+ }, {
+ desc: `case 1`,
+ slice: []int{9, 8, 7, 6, 5, 4, 3, 2, 1, 0},
+ sortedIdx: []int{9, 8, 7, 6, 5, 4, 3, 2, 1, 0},
+ exp: []int{0, 1, 2, 3, 4, 5, 6, 7, 8, 9},
+ }, {
+ desc: `case 2`,
+ slice: []int{0, 1, 0, 1, 0, 1, 0, 1, 0},
+ sortedIdx: []int{0, 2, 4, 6, 8, 1, 3, 5, 7},
+ exp: []int{0, 0, 0, 0, 0, 1, 1, 1, 1},
+ }, {
+ desc: `case 3`,
+ slice: []int{1, 1, 2, 2, 3, 1, 2},
+ sortedIdx: []int{0, 1, 5, 6, 2, 3, 4},
+ exp: []int{1, 1, 1, 2, 2, 2, 3},
+ }}
+
+ for _, tcase := range listCase {
+ slices.SortByIndex(&tcase.slice, tcase.sortedIdx)
+ test.Assert(t, tcase.desc, tcase.exp, tcase.slice)
+ }
+}
+
+func TestSum_int(t *testing.T) {
+ var listCase = []struct {
+ desc string
+ slice []int
+ exp int
+ }{{
+ desc: `case 1`,
+ slice: []int{5, 6, 7, 8, 9, 0, 1, 2, 3, 4},
+ exp: 45,
+ }}
+
+ for _, tcase := range listCase {
+ var got = slices.Sum(tcase.slice)
+ test.Assert(t, tcase.desc, tcase.exp, got)
+ }
+}
+
+func TestSwap_int(t *testing.T) {
+ var listCase = []struct {
+ desc string
+ list []int
+ exp []int
+ idx1 int
+ idx2 int
+ }{{
+ desc: `empty list`,
+ idx1: 1,
+ idx2: 6,
+ }, {
+ desc: `equal index`,
+ list: []int{5, 6, 7, 8, 9, 0, 1, 2, 3, 4},
+ exp: []int{5, 6, 7, 8, 9, 0, 1, 2, 3, 4},
+ idx1: 1,
+ idx2: 1,
+ }, {
+ desc: `index 2 out of range`,
+ list: []int{5, 6, 7, 8, 9, 0, 1, 2, 3, 4},
+ exp: []int{5, 6, 7, 8, 9, 0, 1, 2, 3, 4},
+ idx1: 1,
+ idx2: 100,
+ }, {
+ desc: `ok`,
+ list: []int{5, 6, 7, 8, 9, 0, 1, 2, 3, 4},
+ exp: []int{4, 6, 7, 8, 9, 0, 1, 2, 3, 5},
+ idx1: 0,
+ idx2: 9,
+ }}
+
+ for _, tcase := range listCase {
+ slices.Swap(tcase.list, tcase.idx1, tcase.idx2)
+ test.Assert(t, tcase.desc, tcase.exp, tcase.list)
+ }
+}
+
+func generateRandomInts(data []int, n int) {
+ var (
+ max = big.NewInt(math.MaxInt)
+ randv *big.Int
+ err error
+ )
+ for x := 0; x < n; x++ {
+ randv, err = rand.Int(rand.Reader, max)
+ if err != nil {
+ log.Fatalf(`generateRandomInts: %s`, err)
+ }
+ data[x] = int(randv.Int64())
+ }
+}
diff --git a/lib/strings/statistic.go b/lib/strings/statistic.go
index d9580dc6..0a77c6ad 100644
--- a/lib/strings/statistic.go
+++ b/lib/strings/statistic.go
@@ -8,8 +8,8 @@ import (
"strings"
"unicode"
- "git.sr.ht/~shulhan/pakakeh.go/lib/ints"
"git.sr.ht/~shulhan/pakakeh.go/lib/runes"
+ "git.sr.ht/~shulhan/pakakeh.go/lib/slices"
)
// CountAlnum return number of alpha-numeric character in text.
@@ -163,7 +163,7 @@ func MaxCharSequence(text string) (rune, int) {
return 0, 0
}
- _, idx, _ := ints.Max(counts)
+ _, idx := slices.Max2(counts)
return chars[idx], counts[idx]
}
diff --git a/lib/strings/strings.go b/lib/strings/strings.go
index 4c9dd027..dd20ba1e 100644
--- a/lib/strings/strings.go
+++ b/lib/strings/strings.go
@@ -9,7 +9,7 @@ package strings
import (
"strings"
- "git.sr.ht/~shulhan/pakakeh.go/lib/ints"
+ "git.sr.ht/~shulhan/pakakeh.go/lib/slices"
)
// AppendUniq append case-insensitive strings to slice of input without
@@ -228,7 +228,7 @@ func MostFrequentTokens(words []string, tokens []string, sensitive bool) string
}
tokensCount := CountTokens(words, tokens, sensitive)
- _, maxIdx, _ := ints.Max(tokensCount)
+ _, maxIdx := slices.Max2(tokensCount)
return tokens[maxIdx]
}
diff --git a/lib/tabula/claset.go b/lib/tabula/claset.go
index e6383e04..4ea7b1f3 100644
--- a/lib/tabula/claset.go
+++ b/lib/tabula/claset.go
@@ -8,7 +8,7 @@ import (
"fmt"
"strconv"
- "git.sr.ht/~shulhan/pakakeh.go/lib/ints"
+ "git.sr.ht/~shulhan/pakakeh.go/lib/slices"
libstrings "git.sr.ht/~shulhan/pakakeh.go/lib/strings"
)
@@ -186,13 +186,13 @@ func (claset *Claset) CountValueSpaces() {
func (claset *Claset) RecountMajorMinor() {
claset.CountValueSpaces()
- _, maxIdx, maxok := ints.Max(claset.counts)
- _, minIdx, minok := ints.Min(claset.counts)
+ _, maxIdx := slices.Max2(claset.counts)
+ _, minIdx := slices.Min2(claset.counts)
- if maxok {
+ if maxIdx >= 0 {
claset.major = claset.vs[maxIdx]
}
- if minok {
+ if minIdx >= 0 {
claset.minor = claset.vs[minIdx]
}
}
diff --git a/lib/time/scheduler.go b/lib/time/scheduler.go
index 70ec0e04..50306305 100644
--- a/lib/time/scheduler.go
+++ b/lib/time/scheduler.go
@@ -7,13 +7,12 @@ package time
import (
"errors"
"fmt"
+ "slices"
"sort"
"strconv"
"strings"
"sync"
"time"
-
- "git.sr.ht/~shulhan/pakakeh.go/lib/ints"
)
// ErrScheduleUnknown define an error when unknown schedule kind parsed from
@@ -290,7 +289,7 @@ func (sch *Scheduler) parseListDayOfWeek(days string) {
if dayInt == -1 {
continue
}
- if !ints.IsExist(sch.dow, dayInt) {
+ if !slices.Contains(sch.dow, dayInt) {
sch.dow = append(sch.dow, dayInt)
}
}
diff --git a/lib/websocket/clientmanager.go b/lib/websocket/clientmanager.go
index e623bc23..7c1ad61e 100644
--- a/lib/websocket/clientmanager.go
+++ b/lib/websocket/clientmanager.go
@@ -6,9 +6,10 @@ package websocket
import (
"context"
+ "slices"
"sync"
- "git.sr.ht/~shulhan/pakakeh.go/lib/ints"
+ libslices "git.sr.ht/~shulhan/pakakeh.go/lib/slices"
)
// ClientManager manage list of active websocket connections on server.
@@ -169,7 +170,7 @@ func (cls *ClientManager) add(ctx context.Context, conn int) {
cls.Lock()
defer cls.Unlock()
- if !ints.IsExist(cls.all, conn) {
+ if !slices.Contains(cls.all, conn) {
cls.all = append(cls.all, conn)
}
@@ -204,7 +205,7 @@ func (cls *ClientManager) remove(conn int) {
delete(cls.frame, conn)
delete(cls.frames, conn)
- cls.all, _ = ints.Remove(cls.all, conn)
+ cls.all, _ = libslices.Remove(cls.all, conn)
ctx, ok = cls.ctx[conn]
if ok {
@@ -218,7 +219,7 @@ func (cls *ClientManager) remove(conn int) {
if uid > 0 {
conns, ok = cls.conns[uid]
if ok {
- conns, _ = ints.Remove(conns, conn)
+ conns, _ = libslices.Remove(conns, conn)
if len(conns) == 0 {
delete(cls.conns, uid)