diff options
| author | Shulhan <ms@kilabit.info> | 2024-12-28 22:14:09 +0700 |
|---|---|---|
| committer | Shulhan <ms@kilabit.info> | 2024-12-29 00:06:17 +0700 |
| commit | 7a57091317cd86b9c88f4c6b5127c76bee0f6ede (patch) | |
| tree | f1ec2aac093ff02890a62068001be177c93c1486 | |
| parent | 5a00dfe102a3a06ddee1b79800060dd70231055b (diff) | |
| download | pakakeh.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.md | 3 | ||||
| -rw-r--r-- | go.mod | 1 | ||||
| -rw-r--r-- | go.sum | 4 | ||||
| -rw-r--r-- | lib/floats64/floats64.go | 12 | ||||
| -rw-r--r-- | lib/ints/ints.go | 396 | ||||
| -rw-r--r-- | lib/ints/ints_benchmark_test.go | 59 | ||||
| -rw-r--r-- | lib/ints/ints_example_test.go | 30 | ||||
| -rw-r--r-- | lib/ints/ints_test.go | 425 | ||||
| -rw-r--r-- | lib/ints64/ints64.go | 352 | ||||
| -rw-r--r-- | lib/ints64/ints64_test.go | 382 | ||||
| -rw-r--r-- | lib/memfs/memfs.go | 4 | ||||
| -rw-r--r-- | lib/mining/classifier/rf/rf.go | 4 | ||||
| -rw-r--r-- | lib/mining/classifier/runtime.go | 4 | ||||
| -rw-r--r-- | lib/slices/benchmark_test.go | 50 | ||||
| -rw-r--r-- | lib/slices/example_test.go | 34 | ||||
| -rw-r--r-- | lib/slices/slices.go | 403 | ||||
| -rw-r--r-- | lib/slices/slices_int_test.go | 463 | ||||
| -rw-r--r-- | lib/strings/statistic.go | 4 | ||||
| -rw-r--r-- | lib/strings/strings.go | 4 | ||||
| -rw-r--r-- | lib/tabula/claset.go | 10 | ||||
| -rw-r--r-- | lib/time/scheduler.go | 5 | ||||
| -rw-r--r-- | lib/websocket/clientmanager.go | 9 |
22 files changed, 980 insertions, 1678 deletions
@@ -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. @@ -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 @@ -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) |
