diff options
| author | Shulhan <ms@kilabit.info> | 2018-09-16 17:11:38 +0700 |
|---|---|---|
| committer | Shulhan <ms@kilabit.info> | 2018-09-17 22:51:23 +0700 |
| commit | f911fdc362d2a98a9f4deb93c18231ae77df12a1 (patch) | |
| tree | a3265026d5e9f94ac1053dc20d5dd23bf2bfeba6 | |
| parent | cdcee0eb01305a18b330d2e3c811091fe5164c11 (diff) | |
| download | pakakeh.go-f911fdc362d2a98a9f4deb93c18231ae77df12a1.tar.xz | |
Merge package "github.com/shuLhan/numerus" into "lib/numbers"
| -rw-r--r-- | lib/numbers/LICENSE | 38 | ||||
| -rw-r--r-- | lib/numbers/README.md | 16 | ||||
| -rw-r--r-- | lib/numbers/float64.go | 29 | ||||
| -rw-r--r-- | lib/numbers/float64_test.go | 30 | ||||
| -rw-r--r-- | lib/numbers/floats64.go | 398 | ||||
| -rw-r--r-- | lib/numbers/floats64_bench_test.go | 18 | ||||
| -rw-r--r-- | lib/numbers/floats64_test.go | 378 | ||||
| -rw-r--r-- | lib/numbers/int.go | 81 | ||||
| -rw-r--r-- | lib/numbers/int64.go | 18 | ||||
| -rw-r--r-- | lib/numbers/int64_test.go | 18 | ||||
| -rw-r--r-- | lib/numbers/int_test.go | 33 | ||||
| -rw-r--r-- | lib/numbers/ints.go | 405 | ||||
| -rw-r--r-- | lib/numbers/ints64.go | 395 | ||||
| -rw-r--r-- | lib/numbers/ints64_test.go | 386 | ||||
| -rw-r--r-- | lib/numbers/ints_example_test.go | 17 | ||||
| -rw-r--r-- | lib/numbers/ints_test.go | 386 | ||||
| -rw-r--r-- | lib/numbers/numerus.go | 25 |
17 files changed, 2671 insertions, 0 deletions
diff --git a/lib/numbers/LICENSE b/lib/numbers/LICENSE new file mode 100644 index 00000000..771f6ea6 --- /dev/null +++ b/lib/numbers/LICENSE @@ -0,0 +1,38 @@ +Copyright 2018, Shulhan (ms@kilabit.info). All rights reserved. + +Redistribution and use in source and binary forms, with or without +modification, are permitted provided that the following conditions are met: + +* Redistributions of source code must retain the above copyright notice, this + list of conditions and the following disclaimer. + +* Redistributions in binary form must reproduce the above copyright notice, + this list of conditions and the following disclaimer in the documentation + and/or other materials provided with the distribution. + +* Neither the name of Kilabit nor the names of its + contributors may be used to endorse or promote products derived from + this software without specific prior written permission. + +THIS SOFTWARE IS PROVIDED BY M.SHULHAN "AS IS" AND ANY EXPRESS OR IMPLIED +WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF +MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO +EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, +INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, +BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, +DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY +OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING +NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, +EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + + --- --- --- --- --- --- --- + + TT TT II BB AAAA LLLLLL II KKKKKKKK + TT TT II BB AA AA LL LL II KK + TTTT II BB AA AA LL LL II KK + TT TT II BB AAAAAAAA LLLLLL II KK + TT TT II BB AA AA LL LL II KK + TT TT II BBBBBBBB AA AA LLLLLL II KK + +Website: http://kilabit.info +Contact: ms@kilabit.info diff --git a/lib/numbers/README.md b/lib/numbers/README.md new file mode 100644 index 00000000..667b48d5 --- /dev/null +++ b/lib/numbers/README.md @@ -0,0 +1,16 @@ +[](https://godoc.org/github.com/shuLhan/share/lib/numbers) +[](https://goreportcard.com/report/github.com/shuLhan/share/lib/numbers) + +Package `numbers` provide functions for working with integer, float, slice of +integers, and slice of floats. + +Currently it have function to, + +- sort slice of floats using in-place mergesort algorithm +- sort slice of integer/floats by predefined index +- count number of value occurence in slice of integer/float +- find minimum or maximum value in slice of integer/float +- sum slice of integer/float + +See [documentation](https://godoc.org/github.com/shuLhan/share/lib/numbers) +for more information. diff --git a/lib/numbers/float64.go b/lib/numbers/float64.go new file mode 100644 index 00000000..829db1c3 --- /dev/null +++ b/lib/numbers/float64.go @@ -0,0 +1,29 @@ +// 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 numbers + +import ( + "math" +) + +// +// Float64Round will round `v` to `nprec` digit in fraction. +// +func Float64Round(v float64, nprec int) float64 { + pow := math.Pow(10, float64(nprec)) + tmp := v * pow + _, frac := math.Modf(tmp) + x := .5 + if frac < 0.0 { + x = -.5 + } + if frac >= x { + v = math.Ceil(tmp) + } else { + v = math.Floor(tmp) + } + + return v / pow +} diff --git a/lib/numbers/float64_test.go b/lib/numbers/float64_test.go new file mode 100644 index 00000000..01cf88c8 --- /dev/null +++ b/lib/numbers/float64_test.go @@ -0,0 +1,30 @@ +// 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 numbers + +import ( + "testing" + + "github.com/shuLhan/share/lib/test" +) + +func TestFloat64Round(t *testing.T) { + data := []float64{0.553, -0.553, 0.49997, -0.49997, 0.4446, -0.4446} + exps := [][]float64{ + {1, 0.6, 0.55}, + {-1, -0.6, -0.55}, + {0.0, 0.5, 0.5}, + {0.0, -0.5, -0.5}, + {0, 0.4, 0.44}, + {0, -0.4, -0.44}, + } + + for x := range data { + for y, exp := range exps[x] { + got := Float64Round(data[x], y) + test.Assert(t, "", exp, got, true) + } + } +} diff --git a/lib/numbers/floats64.go b/lib/numbers/floats64.go new file mode 100644 index 00000000..b32727f1 --- /dev/null +++ b/lib/numbers/floats64.go @@ -0,0 +1,398 @@ +// 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 numbers + +// +// Floats64FindMax given slice of float, find the maximum value in slice and +// and return it with their index. +// +// If data is empty, return -1 in value and index, and false in ok. +// +// Example, given data: [0.0 0.1 0.2 0.2 0.4], it will return 0.4 as max and 4 +// as index of maximum value. +// +func Floats64FindMax(d []float64) (maxv float64, maxi int, ok bool) { + l := len(d) + if l <= 0 { + return -1, -1, false + } + + x := 0 + maxv = d[x] + maxi = x + + for x = 1; x < l; x++ { + if d[x] > maxv { + maxv = d[x] + maxi = x + } + } + + return maxv, maxi, true +} + +// +// Floats64FindMin given slice of float, find the minimum value in slice and +// and return it with their index. +// +// If data is empty, return -1 in value and index, and false in ok. +// +// Example, given data: [0.0 0.1 0.2 0.2 0.4], it will return 0 as min and 0 +// as index of minimum value. +// +func Floats64FindMin(d []float64) (minv float64, mini int, ok bool) { + l := len(d) + if l <= 0 { + return -1, -1, false + } + + x := 0 + minv = d[x] + mini = x + + for x = 1; x < l; x++ { + if d[x] < minv { + minv = d[x] + mini = x + } + } + + return minv, mini, true +} + +// +// Floats64Sum return sum of slice of float64. +// +func Floats64Sum(d []float64) (sum float64) { + for _, v := range d { + sum += v + } + return +} + +// +// Floats64Count will count number of class in data. +// +func Floats64Count(d []float64, class float64) (count int) { + if len(d) <= 0 { + return + } + + for _, v := range d { + if v == class { + count++ + } + } + return count +} + +// +// Floats64Counts will count class in data and return each of the counter. +// +// For example, if data is "[1,1,2]" and class is "[1,2]", this function will +// return "[2,1]". +// +// idx class count +// 0 : 1 -> 2 +// 1 : 2 -> 1 +// +// +func Floats64Counts(d, classes []float64) (counts []int) { + if len(classes) <= 0 { + return + } + + counts = make([]int, len(classes)) + + for x, c := range classes { + counts[x] = Floats64Count(d, c) + } + return +} + +// +// Floats64MaxCountOf will count number of occurence 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 Floats64MaxCountOf(d, classes []float64) (float64, bool) { + if len(classes) == 0 { + return -1, false + } + if len(d) == 0 { + return -2, false + } + + counts := Floats64Counts(d, classes) + + _, maxi, _ := IntsFindMax(counts) + if maxi < 0 { + return -1, false + } + + return classes[maxi], true +} + +// +// Floats64Swap swap two indices value of 64bit float. +// +func Floats64Swap(d []float64, x, y int) { + if x == y { + return + } + if len(d) <= 1 || x > len(d) || y > len(d) { + return + } + + tmp := d[x] + d[x] = d[y] + d[y] = tmp +} + +// +// Floats64IsExist will return true if value `v` exist in slice of `d`, +// otherwise it will return false. +// +func Floats64IsExist(d []float64, v float64) bool { + for _, x := range d { + if v == x { + return true + } + } + return false +} + +// +// Floats64InsertionSort will sort the data using insertion-sort algorithm. +// +// Parameters: +// - `data` is slice that will be sorted. +// - `idx` is indices of data. +// - `l` is starting index of slice to be sorted. +// - `r` is end index of slice to be sorted. +// +func Floats64InsertionSort(d []float64, 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] { + IntsSwap(ids, x, y) + Floats64Swap(d, x, y) + } + } else { + if d[x] < d[y] { + IntsSwap(ids, x, y) + Floats64Swap(d, x, y) + } + } + } + } +} + +// +// Floats64SortByIndex will sort the slice of float using sorted index. +// +func Floats64SortByIndex(d *[]float64, sortedIds []int) { + newd := make([]float64, len(*d)) + + for i := range sortedIds { + newd[i] = (*d)[sortedIds[i]] + } + + (*d) = newd +} + +// +// Floats64InplaceMergesort in-place merge-sort without memory allocation. +// +func Floats64InplaceMergesort(d []float64, idx []int, l, r int, asc bool) { + // (0) If data length == Threshold, then + if l+SortThreshold >= r { + // (0.1) use insertion sort. + Floats64InsertionSort(d, idx, l, r, asc) + return + } + + // (1) Divide into left and right. + res := (r + l) % 2 + c := (r + l) / 2 + if res == 1 { + c++ + } + + // (2) Sort left. + Floats64InplaceMergesort(d, idx, l, c, asc) + + // (3) Sort right. + Floats64InplaceMergesort(d, idx, c, r, asc) + + // (4) 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 + } + } + + floats64InplaceMerge(d, idx, l, c, r, asc) +} + +// +// 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 floats64InplaceMerge(d []float64, 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.4 + 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 = floats64MoveY(d, x, y, r, asc) + + // (4.3.3) SWAP DATA, X, Y, YLAST + floats64Multiswap(d, idx, x, y, ylast) + + next: + // (4.3.4) LET Y := the minimum value between x and r on `d` + floats64MinY(d, &x, &y, r, asc) + } +} + +// (4.3.4) LET Y := the minimum value between x and r on `d` +func floats64MinY(d []float64, x, y *int, r int, asc bool) { + for *x < r { + if asc { + *y = floats64Min(d, *x, r) + } else { + *y = floats64Max(d, *x, r) + } + + if *y != *x { + break + } + (*x)++ + } +} + +func floats64MoveY(d []float64, 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 floats64Multiswap(d []float64, idx []int, x, y, ylast int) int { + for y < ylast { + IntsSwap(idx, x, y) + Floats64Swap(d, x, y) + x++ + y++ + if y >= ylast { + return y + } + if d[x] <= d[y] { + return y + } + } + + return y +} + +func floats64Min(d []float64, l, r int) (m int) { + min := d[l] + m = l + for l++; l < r; l++ { + if d[l] <= min { + min = d[l] + m = l + } + } + return +} + +func floats64Max(d []float64, l, r int) (m int) { + maxv := d[l] + m = l + for l++; l < r; l++ { + if d[l] >= maxv { + maxv = d[l] + m = l + } + } + return m +} + +// +// Floats64IndirectSort will sort the data and return the sorted index. +// +func Floats64IndirectSort(d []float64, asc bool) (sortedIdx []int) { + dlen := len(d) + + sortedIdx = make([]int, dlen) + for i := 0; i < dlen; i++ { + sortedIdx[i] = i + } + + Floats64InplaceMergesort(d, sortedIdx, 0, dlen, asc) + + return +} diff --git a/lib/numbers/floats64_bench_test.go b/lib/numbers/floats64_bench_test.go new file mode 100644 index 00000000..013fa2c7 --- /dev/null +++ b/lib/numbers/floats64_bench_test.go @@ -0,0 +1,18 @@ +// 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 numbers + +import ( + "testing" +) + +func BenchmarkFloats64InplaceMergesort(b *testing.B) { + size := len(inSorts[6]) + ids := make([]int, size) + + for i := 0; i < b.N; i++ { + Floats64InplaceMergesort(inSorts[6], ids, 0, size, true) + } +} diff --git a/lib/numbers/floats64_test.go b/lib/numbers/floats64_test.go new file mode 100644 index 00000000..e066e3fb --- /dev/null +++ b/lib/numbers/floats64_test.go @@ -0,0 +1,378 @@ +// 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 numbers + +import ( + "fmt" + "testing" + + "github.com/shuLhan/share/lib/test" +) + +var ( + dFloats64 = [][]float64{ + {}, + {0.5, 0.6, 0.7, 0.8, 0.9, 0.0, 0.1, 0.2, 0.3, 0.4}, + {0.0, 0.1, 0.0, 0.1, 0.0, 0.1, 0.0, 0.1, 0.0}, + {1, 1, 2, 2, 3, 1, 2}, + } + dFloats64Sorted = [][]float64{ + {}, + {0.0, 0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9}, + {0.0, 0.0, 0.0, 0.0, 0.0, 0.1, 0.1, 0.1, 0.1}, + {1, 1, 1, 2, 2, 2, 3}, + } + dFloats64SortedDesc = [][]float64{ + {}, + {0.9, 0.8, 0.7, 0.6, 0.5, 0.4, 0.3, 0.2, 0.1, 0.0}, + {0.1, 0.1, 0.1, 0.1, 0.0, 0.0, 0.0, 0.0, 0.0}, + {3, 2, 2, 2, 1, 1, 1}, + } +) + +func TestFloats64FindMaxEmpty(t *testing.T) { + gotv, goti, gotok := Floats64FindMax(dFloats64[0]) + + test.Assert(t, "", float64(-1), gotv, true) + test.Assert(t, "", -1, goti, true) + test.Assert(t, "", false, gotok, true) +} + +func TestFloats64FindMax(t *testing.T) { + gotv, goti, gotok := Floats64FindMax(dFloats64[1]) + + test.Assert(t, "", float64(0.9), gotv, true) + test.Assert(t, "", 4, goti, true) + test.Assert(t, "", true, gotok, true) +} + +func TestFloats64FindMinEmpty(t *testing.T) { + gotv, goti, gotok := Floats64FindMin(dFloats64[0]) + + test.Assert(t, "", gotv, float64(-1), true) + test.Assert(t, "", goti, -1, true) + test.Assert(t, "", gotok, false, true) +} + +func TestFloats64FindMin(t *testing.T) { + gotv, goti, gotok := Floats64FindMin(dFloats64[1]) + + test.Assert(t, "", gotv, float64(0.0), true) + test.Assert(t, "", goti, 5, true) + test.Assert(t, "", gotok, true, true) +} + +func TestFloats64Sum(t *testing.T) { + got := Floats64Sum(dFloats64[1]) + + test.Assert(t, "", float64(4.5), Float64Round(got, 1), true) +} + +func TestFloats64Count(t *testing.T) { + got := Floats64Count(dFloats64[0], 0) + + test.Assert(t, "", 0, got, true) + + got = Floats64Count(dFloats64[1], 0.1) + + test.Assert(t, "", 1, got, true) + + got = Floats64Count(dFloats64[2], 0.1) + + test.Assert(t, "", 4, got, true) + + got = Floats64Count(dFloats64[3], 0.1) + + test.Assert(t, "", 0, got, true) + + got = Floats64Count(dFloats64[3], 3) + + test.Assert(t, "", 1, got, true) +} + +func TestFloats64CountsEmpty(t *testing.T) { + classes := []float64{1, 2, 3} + exp := []int{0, 0, 0} + + got := Floats64Counts(dFloats64[0], classes) + + test.Assert(t, "", exp, got, true) +} + +func TestFloats64CountsEmptyClasses(t *testing.T) { + classes := []float64{} + var exp []int + + got := Floats64Counts(dFloats64[1], classes) + + test.Assert(t, "", exp, got, true) +} + +func TestFloats64Counts(t *testing.T) { + classes := []float64{1, 2, 3} + exp := []int{3, 3, 1} + + got := Floats64Counts(dFloats64[3], classes) + + test.Assert(t, "", exp, got, true) +} + +func TestFloats64MaxCountOf(t *testing.T) { + classes := []float64{0, 1} + exp := float64(0) + got, _ := Floats64MaxCountOf(dFloats64[2], classes) + + test.Assert(t, "", exp, got, true) + + // Swap the class values. + classes = []float64{1, 0} + got, _ = Floats64MaxCountOf(dFloats64[2], classes) + + test.Assert(t, "", exp, got, true) +} + +func TestFloats64SwapEmpty(t *testing.T) { + exp := []float64{} + + Floats64Swap(dFloats64[0], 1, 6) + + test.Assert(t, "", exp, dFloats64[0], true) +} + +func TestFloats64SwapEqual(t *testing.T) { + in := make([]float64, len(dFloats64[1])) + copy(in, dFloats64[1]) + + exp := make([]float64, len(in)) + copy(exp, in) + + Floats64Swap(in, 1, 1) + + test.Assert(t, "", exp, in, true) +} + +func TestFloats64SwapOutOfRange(t *testing.T) { + in := make([]float64, len(dFloats64[1])) + copy(in, dFloats64[1]) + + exp := make([]float64, len(in)) + copy(exp, in) + + Floats64Swap(in, 1, 100) + + test.Assert(t, "", exp, in, true) +} + +func TestFloats64Swap(t *testing.T) { + in := make([]float64, len(dFloats64[1])) + copy(in, dFloats64[1]) + + exp := make([]float64, len(in)) + copy(exp, in) + + Floats64Swap(in, 0, len(in)-1) + + test.Assert(t, "", exp, in, false) + + tmp := exp[0] + exp[0] = exp[len(exp)-1] + exp[len(exp)-1] = tmp + + test.Assert(t, "", exp, in, true) +} + +func TestFloats64IsExist(t *testing.T) { + got := Floats64IsExist(dFloats64[0], 0) + + test.Assert(t, "", false, got, true) + + got = Floats64IsExist(dFloats64[1], float64(0)) + + test.Assert(t, "", true, got, true) + + got = Floats64IsExist(dFloats64[1], float64(0.01)) + + test.Assert(t, "", false, got, true) +} + +func TestFloats64InsertionSort(t *testing.T) { + for x := range dFloats64 { + d := make([]float64, len(dFloats64[x])) + + copy(d, dFloats64[x]) + + ids := make([]int, len(d)) + for x := range ids { + ids[x] = x + } + + Floats64InsertionSort(d, ids, 0, len(ids), true) + + test.Assert(t, "", dFloats64Sorted[x], d, true) + } +} + +func TestFloats64InsertionSortDesc(t *testing.T) { + for x := range dFloats64 { + d := make([]float64, len(dFloats64[x])) + + copy(d, dFloats64[x]) + + ids := make([]int, len(d)) + for x := range ids { + ids[x] = x + } + + Floats64InsertionSort(d, ids, 0, len(ids), false) + + test.Assert(t, "", dFloats64SortedDesc[x], d, true) + } +} + +func TestFloats64SortByIndex(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 dFloats64 { + d := make([]float64, len(dFloats64[x])) + + copy(d, dFloats64[x]) + + Floats64SortByIndex(&d, ids[x]) + + test.Assert(t, "", dFloats64Sorted[x], d, true) + } +} + +var inSorts = [][]float64{ + {9.0, 8.0, 7.0, 6.0, 5.0, 4.0, 3.0}, + {9.0, 8.0, 7.0, 6.0, 5.0, 4.0, 3.0, 2.0, 1.0, 0.0}, + {0.0, 1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0, 9.0}, + {0.0, 6.0, 7.0, 8.0, 5.0, 1.0, 2.0, 3.0, 4.0, 9.0}, + {9.0, 8.0, 7.0, 6.0, 5.0, 4.0, 3.0, 2.0, 1.0}, + {0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, + {5.1, 5, 5.6, 5.5, 5.5, 5.8, 5.5, 5.5, 5.8, 5.6, + 5.7, 5, 5.6, 5.9, 6.2, 6, 4.9, 6.3, 6.1, 5.6, + 5.8, 6.7, 6.1, 5.9, 6, 4.9, 5.6, 5.2, 6.1, 6.4, + 7, 5.7, 6.5, 6.9, 5.7, 6.4, 6.2, 6.6, 6.3, 6.2, + 5.4, 6.7, 6.1, 5.7, 5.5, 6, 3, 6.6, 5.7, 6, + 6.8, 6, 6.1, 6.3, 5.8, 5.8, 5.6, 5.7, 6, 6.9, + 6.9, 6.4, 6.3, 6.3, 6.7, 6.5, 5.8, 6.3, 6.4, 6.7, + 5.9, 7.2, 6.3, 6.3, 6.5, 7.1, 6.7, 7.6, 7.3, 6.4, + 6.7, 7.4, 6, 6.8, 6.5, 6.4, 6.7, 6.4, 6.5, 6.9, + 7.7, 6.7, 7.2, 7.7, 7.2, 7.7, 6.1, 7.9, 7.7, 6.8, + 6.2}, +} + +var expSorts = [][]float64{ + {3.0, 4.0, 5.0, 6.0, 7.0, 8.0, 9.0}, + {0.0, 1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0, 9.0}, + {0.0, 1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0, 9.0}, + {0.0, 1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0, 9.0}, + {1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0, 9.0}, + {0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, + {3, 4.9, 4.9, 5, 5, 5.1, 5.2, 5.4, 5.5, 5.5, + 5.5, 5.5, 5.5, 5.6, 5.6, 5.6, 5.6, 5.6, 5.6, 5.7, + 5.7, 5.7, 5.7, 5.7, 5.7, 5.8, 5.8, 5.8, 5.8, 5.8, + 5.8, 5.9, 5.9, 5.9, 6, 6, 6, 6, 6, 6, + 6, 6.1, 6.1, 6.1, 6.1, 6.1, 6.1, 6.2, 6.2, 6.2, + 6.2, 6.3, 6.3, 6.3, 6.3, 6.3, 6.3, 6.3, 6.3, 6.4, + 6.4, 6.4, 6.4, 6.4, 6.4, 6.4, 6.5, 6.5, 6.5, 6.5, + 6.5, 6.6, 6.6, 6.7, 6.7, 6.7, 6.7, 6.7, 6.7, 6.7, + 6.7, 6.8, 6.8, 6.8, 6.9, 6.9, 6.9, 6.9, 7, 7.1, + 7.2, 7.2, 7.2, 7.3, 7.4, 7.6, 7.7, 7.7, 7.7, 7.7, + 7.9}, +} + +var expSortsDesc = [][]float64{ + {9.0, 8.0, 7.0, 6.0, 5.0, 4.0, 3.0}, + {9.0, 8.0, 7.0, 6.0, 5.0, 4.0, 3.0, 2.0, 1.0, 0.0}, + {9.0, 8.0, 7.0, 6.0, 5.0, 4.0, 3.0, 2.0, 1.0, 0.0}, + {9.0, 8.0, 7.0, 6.0, 5.0, 4.0, 3.0, 2.0, 1.0, 0.0}, + {9.0, 8.0, 7.0, 6.0, 5.0, 4.0, 3.0, 2.0, 1.0}, + {0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, + {7.9, 7.7, 7.7, 7.7, 7.7, 7.6, 7.4, 7.3, 7.2, 7.2, + 7.2, 7.1, 7, 6.9, 6.9, 6.9, 6.9, 6.8, 6.8, 6.8, + 6.7, 6.7, 6.7, 6.7, 6.7, 6.7, 6.7, 6.7, 6.6, 6.6, + 6.5, 6.5, 6.5, 6.5, 6.5, 6.4, 6.4, 6.4, 6.4, 6.4, + 6.4, 6.4, 6.3, 6.3, 6.3, 6.3, 6.3, 6.3, 6.3, 6.3, + 6.2, 6.2, 6.2, 6.2, 6.1, 6.1, 6.1, 6.1, 6.1, 6.1, + 6, 6, 6, 6, 6, 6, 6, 5.9, 5.9, 5.9, + 5.8, 5.8, 5.8, 5.8, 5.8, 5.8, 5.7, 5.7, 5.7, 5.7, + 5.7, 5.7, 5.6, 5.6, 5.6, 5.6, 5.6, 5.6, 5.5, 5.5, + 5.5, 5.5, 5.5, 5.4, 5.2, 5.1, 5, 5, 4.9, 4.9, 3}, +} + +func TestFloats64IndirectSort(t *testing.T) { + var res, exp string + + for i := range inSorts { + Floats64IndirectSort(inSorts[i], true) + + res = fmt.Sprint(inSorts[i]) + exp = fmt.Sprint(expSorts[i]) + + test.Assert(t, "", exp, res, true) + } +} + +func TestFloats64IndirectSortDesc(t *testing.T) { + var res, exp string + + for i := range inSorts { + Floats64IndirectSort(inSorts[i], false) + + res = fmt.Sprint(inSorts[i]) + exp = fmt.Sprint(expSortsDesc[i]) + + test.Assert(t, "", exp, res, true) + } +} + +func TestFloats64IndirectSort_Stability(t *testing.T) { + exp := []int{0, 1, 2, 3, 4, 5, 6, 7, 8, 9} + got := Floats64IndirectSort(inSorts[5], true) + + test.Assert(t, "", exp, got, true) +} + +func TestFloats64IndirectSortDesc_Stability(t *testing.T) { + exp := []int{0, 1, 2, 3, 4, 5, 6, 7, 8, 9} + got := Floats64IndirectSort(inSorts[5], false) + + test.Assert(t, "", exp, got, true) +} + +func TestFloats64InplaceMergesort(t *testing.T) { + size := len(inSorts[6]) + idx := make([]int, size) + + Floats64InplaceMergesort(inSorts[6], idx, 0, size, true) + + test.Assert(t, "", expSorts[6], inSorts[6], true) +} + +func TestFloats64IndirectSort_SortByIndex(t *testing.T) { + expIds := []int{9, 8, 7, 6, 5, 4, 3, 2, 1, 0} + in1 := []float64{9.0, 8.0, 7.0, 6.0, 5.0, 4.0, 3.0, 2.0, 1.0, 0.0} + in2 := []float64{0.0, 1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0, 9.0} + + exp := fmt.Sprint(in1) + + sortedIds := Floats64IndirectSort(in1, true) + + test.Assert(t, "", expIds, sortedIds, true) + + // Reverse the sort. + Floats64SortByIndex(&in2, sortedIds) + + got := fmt.Sprint(in2) + + test.Assert(t, "", exp, got, true) +} diff --git a/lib/numbers/int.go b/lib/numbers/int.go new file mode 100644 index 00000000..cf88429d --- /dev/null +++ b/lib/numbers/int.go @@ -0,0 +1,81 @@ +// 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 numbers + +import ( + "math/rand" + "time" +) + +// +// IntCreateSeq will create and return sequence of integer from `min` to +// `max`. +// +// E.g. if min is 0 and max is 5 then it will return `[0 1 2 3 4 5]`. +// +func IntCreateSeq(min, max int) (seq []int) { + for ; min <= max; min++ { + seq = append(seq, min) + } + return +} + +// +// IntPickRandPositive return random integer value from 0 to maximum value +// `maxVal`. +// +// The random value is checked with already picked index: `pickedIds`. +// +// If `dup` is true, allow duplicate value in `pickedIds`, otherwise only +// single unique value allowed in `pickedIds`. +// +// If excluding index `exsIds` is not empty, do not pick the integer value +// listed in there. +// +func IntPickRandPositive(maxVal int, dup bool, pickedIds, exsIds []int) ( + idx int, +) { + rand.Seed(time.Now().UnixNano()) + + var excluded, picked bool + + for { + idx = rand.Intn(maxVal) + + // Check in exclude indices. + excluded = false + for _, v := range exsIds { + if idx == v { + excluded = true + break + } + } + if excluded { + continue + } + + if dup { + // Allow duplicate idx. + return + } + + // Check if its already picked. + picked = false + for _, v := range pickedIds { + if idx == v { + picked = true + break + } + } + + if picked { + // Get another random idx again. + continue + } + + // Bingo, we found unique idx that has not been picked. + return + } +} diff --git a/lib/numbers/int64.go b/lib/numbers/int64.go new file mode 100644 index 00000000..68279d18 --- /dev/null +++ b/lib/numbers/int64.go @@ -0,0 +1,18 @@ +// 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 numbers + +// +// Int64CreateSeq will create and return sequence of integer from `min` to +// `max`. +// +// E.g. if min is 0 and max is 5 then it will return `[0 1 2 3 4 5]`. +// +func Int64CreateSeq(min, max int64) (seq []int64) { + for ; min <= max; min++ { + seq = append(seq, min) + } + return +} diff --git a/lib/numbers/int64_test.go b/lib/numbers/int64_test.go new file mode 100644 index 00000000..d2f2a6f3 --- /dev/null +++ b/lib/numbers/int64_test.go @@ -0,0 +1,18 @@ +// 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 numbers + +import ( + "testing" + + "github.com/shuLhan/share/lib/test" +) + +func TestInt64CreateSeq(t *testing.T) { + exp := []int64{-5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5} + got := Int64CreateSeq(-5, 5) + + test.Assert(t, "", exp, got, true) +} diff --git a/lib/numbers/int_test.go b/lib/numbers/int_test.go new file mode 100644 index 00000000..c317a77a --- /dev/null +++ b/lib/numbers/int_test.go @@ -0,0 +1,33 @@ +// 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 numbers + +import ( + "testing" + + "github.com/shuLhan/share/lib/test" +) + +func TestIntCreateSeq(t *testing.T) { + exp := []int{-5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5} + got := IntCreateSeq(-5, 5) + + test.Assert(t, "", exp, got, true) +} + +func TestIntPickRandPositive(t *testing.T) { + pickedIds := []int{0, 1, 2, 3, 4, 5, 7} + exsIds := []int{8, 9} + exp := 6 + + // Pick random without duplicate. + got := IntPickRandPositive(7, false, pickedIds, nil) + + test.Assert(t, "", exp, got, true) + + // Pick random with exclude indices. + got = IntPickRandPositive(9, false, pickedIds, exsIds) + test.Assert(t, "", exp, got, true) +} diff --git a/lib/numbers/ints.go b/lib/numbers/ints.go new file mode 100644 index 00000000..07a504ca --- /dev/null +++ b/lib/numbers/ints.go @@ -0,0 +1,405 @@ +// 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 numbers + +// +// IntsFindMax given slice of integer, return the maximum value in slice and +// its index. +// +// If data is empty, it will return `-1` in value and index, and false in ok. +// +func IntsFindMax(d []int) (maxv int, maxi int, ok bool) { + l := len(d) + if l <= 0 { + return -1, -1, false + } + + x := 0 + maxv = d[x] + maxi = x + + for x = 1; x < l; x++ { + if d[x] > maxv { + maxv = d[x] + maxi = x + } + } + + return maxv, maxi, true +} + +// +// IntsFindMin given slice of integer, return the minimum value in slice and +// its index. +// +// If data is empty, return -1 in value and index, and false in ok. +// +// Example, given a slice of data: [0 1 2 3 4], it will return 0 as min and 0 +// as minimum index. +// +func IntsFindMin(d []int) (minv int, mini int, ok bool) { + l := len(d) + if l <= 0 { + return -1, -1, false + } + + x := 0 + minv = d[x] + mini = x + + for x = 1; x < l; x++ { + if d[x] < minv { + minv = d[x] + mini = x + } + } + + return minv, mini, true +} + +// +// IntsSum return sum of all value in slice. +// +func IntsSum(d []int) (sum int) { + for _, v := range d { + sum += v + } + return +} + +// +// IntsCount will count number of class in data. +// +func IntsCount(d []int, class int) (count int) { + if len(d) <= 0 { + return + } + + for _, v := range d { + if v == class { + count++ + } + } + return count +} + +// +// IntsCounts will count class in data and return each of the counter. +// +// For example, if data is "[1,1,2]" and class is "[1,2]", this function will +// return "[2,1]". +// +// idx class count +// 0 : 1 -> 2 +// 1 : 2 -> 1 +// +func IntsCounts(d, classes []int) (counts []int) { + if len(classes) <= 0 { + return + } + + counts = make([]int, len(classes)) + + for x, c := range classes { + counts[x] = IntsCount(d, c) + } + return +} + +// +// IntsMaxCountOf will count number of occurence 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 IntsMaxCountOf(d, classes []int) (int, bool) { + if len(classes) == 0 { + return -1, false + } + if len(d) == 0 { + return -2, false + } + + counts := IntsCounts(d, classes) + + _, maxi, _ := IntsFindMax(counts) + if maxi < 0 { + return -1, false + } + + return classes[maxi], true +} + +// +// IntsSwap swap two indices value of integer. +// +func IntsSwap(d []int, x, y int) { + if x == y { + return + } + if len(d) <= 1 || x > len(d) || y > len(d) { + return + } + + tmp := d[x] + d[x] = d[y] + d[y] = tmp +} + +// +// IntsIsExist will return true if value `v` exist in slice of `d`, +// otherwise it will return false. +// +func IntsIsExist(d []int, i int) bool { + for _, v := range d { + if i == v { + return true + } + } + return false +} + +// +// IntsTo64 convert slice of integer to 64bit values. +// +func IntsTo64(ints []int) []int64 { + i64 := make([]int64, len(ints)) + for x, v := range ints { + i64[x] = int64(v) + } + return i64 +} + +// +// IntsInsertionSort will sort the data using insertion-sort algorithm. +// +// Parameters: +// - `data` is slice that will be sorted. +// - `idx` is indices of data. +// - `l` is starting index of slice to be sorted. +// - `r` is end index of slice to be sorted. +// +func IntsInsertionSort(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] { + IntsSwap(ids, x, y) + IntsSwap(d, x, y) + } + } else { + if d[x] < d[y] { + IntsSwap(ids, x, y) + IntsSwap(d, x, y) + } + } + } + } +} + +// +// IntsSortByIndex will sort the slice `d` using sorted index `sortedIds`. +// +func IntsSortByIndex(d *[]int, sortedIds []int) { + newd := make([]int, len(*d)) + + for i := range sortedIds { + newd[i] = (*d)[sortedIds[i]] + } + + (*d) = newd +} + +// +// IntsInplaceMergesort in-place merge-sort without memory allocation. +// +func IntsInplaceMergesort(d []int, idx []int, l, r int, asc bool) { + // (0) If data length == Threshold, then + if l+SortThreshold >= r { + // (0.1) use insertion sort. + IntsInsertionSort(d, idx, l, r, asc) + return + } + + // (1) Divide into left and right. + res := (r + l) % 2 + c := (r + l) / 2 + if res == 1 { + c++ + } + + // (2) Sort left. + IntsInplaceMergesort(d, idx, l, c, asc) + + // (3) Sort right. + IntsInplaceMergesort(d, idx, c, r, asc) + + // (4) 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 + } + } + + intsInplaceMerge(d, idx, l, c, r, asc) +} + +// +// 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 intsInplaceMerge(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 = intsMoveY(d, x, y, r, asc) + + // (4.3.3) SWAP DATA, X, Y, YLAST + intsMultiswap(d, idx, x, y, ylast) + + next: + // (4.3.4) LET Y := the minimum value between x and r on `d` + intsMinY(d, &x, &y, r, asc) + } +} + +// (4.3.4) LET Y := the minimum value between x and r on `d` +func intsMinY(d []int, x, y *int, r int, asc bool) { + for *x < r { + if asc { + *y = intsMin(d, *x, r) + } else { + *y = intsMax(d, *x, r) + } + + if *y != *x { + break + } + (*x)++ + } +} + +func intsMoveY(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 +} + +func intsMultiswap(d []int, idx []int, x, y, ylast int) int { + for y < ylast { + IntsSwap(idx, x, y) + IntsSwap(d, x, y) + x++ + y++ + if y >= ylast { + return y + } + if d[x] <= d[y] { + return y + } + } + + return y +} + +func intsMin(d []int, l, r int) (m int) { + min := d[l] + m = l + for l++; l < r; l++ { + if d[l] <= min { + min = d[l] + m = l + } + } + return +} + +func intsMax(d []int, l, r int) (m int) { + maxv := d[l] + m = l + for l++; l < r; l++ { + if d[l] >= maxv { + maxv = d[l] + m = l + } + } + return m +} + +// +// IntsIndirectSort will sort the data and return the sorted index. +// +func IntsIndirectSort(d []int, asc bool) (sortedIdx []int) { + dlen := len(d) + + sortedIdx = make([]int, dlen) + for i := 0; i < dlen; i++ { + sortedIdx[i] = i + } + + IntsInplaceMergesort(d, sortedIdx, 0, dlen, asc) + + return +} diff --git a/lib/numbers/ints64.go b/lib/numbers/ints64.go new file mode 100644 index 00000000..40d87944 --- /dev/null +++ b/lib/numbers/ints64.go @@ -0,0 +1,395 @@ +// 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 numbers + +// +// Ints64FindMax given a slice of integer, return the maximum value in slice +// and its index. +// +// If data is empty, it will return `-1` in value and index, and false in ok. +// +// Example, given a slice of data: [0 1 2 3 4], it will return 4 as max and 4 +// as index of maximum value. +// +func Ints64FindMax(d []int64) (maxv int64, maxi int, ok bool) { + l := len(d) + if l <= 0 { + return -1, -1, false + } + + x := 0 + maxv = d[x] + maxi = x + + for x = 1; x < l; x++ { + if d[x] > maxv { + maxv = d[x] + maxi = x + } + } + + return maxv, maxi, true +} + +// +// Ints64FindMin given a slice of integer, return the minimum value in slice +// and its index. +// +// If data is empty, return -1 in value and index; and false in ok. +// +// Example, given a slice of data: [0 1 2 3 4], it will return 0 as min and 0 +// as minimum index. +// +func Ints64FindMin(d []int64) (minv int64, mini int, ok bool) { + l := len(d) + if l <= 0 { + return -1, -1, false + } + + x := 0 + minv = d[x] + mini = x + + for x = 1; x < l; x++ { + if d[x] < minv { + minv = d[x] + mini = x + } + } + + return minv, mini, true +} + +// +// Ints64Sum return sum of all value in slice. +// +func Ints64Sum(d []int64) (sum int64) { + for _, v := range d { + sum += v + } + return sum +} + +// +// Ints64Count will count number of class in data. +// +func Ints64Count(d []int64, class int64) (count int) { + if len(d) <= 0 { + return + } + + for _, v := range d { + if v == class { + count++ + } + } + return count +} + +// +// Ints64Counts will count class in data and return each of the counter. +// +// For example, if data is "[1,1,2]" and class is "[1,2]", this function will +// return "[2,1]". +// +// idx class count +// 0 : 1 -> 2 +// 1 : 2 -> 1 +// +func Ints64Counts(d, classes []int64) (counts []int) { + if len(classes) <= 0 { + return + } + + counts = make([]int, len(classes)) + + for x, c := range classes { + counts[x] = Ints64Count(d, c) + } + return +} + +// +// Ints64MaxCountOf will count number of occurence 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 [0, 1, 0, 1, 0] and classes [0, 1], the function +// will count 0 as 3, 1 as 2; and return 0. +// +func Ints64MaxCountOf(d, classes []int64) (int64, bool) { + if len(classes) == 0 { + return -1, false + } + if len(d) == 0 { + return -2, false + } + + counts := Ints64Counts(d, classes) + + _, maxi, _ := IntsFindMax(counts) + if maxi < 0 { + return -1, false + } + + return classes[maxi], true +} + +// +// Ints64Swap swap two indices value of integer. +// +func Ints64Swap(d []int64, x, y int) { + if x == y { + return + } + if len(d) <= 1 || x > len(d) || y > len(d) { + return + } + + tmp := d[x] + d[x] = d[y] + d[y] = tmp +} + +// +// Ints64IsExist will return true if value `v` exist in slice of `d`, +// otherwise it will return false. +// +func Ints64IsExist(d []int64, i int64) bool { + for _, v := range d { + if i == v { + return true + } + } + return false +} + +// +// Ints64InsertionSort will sort the data using insertion-sort algorithm. +// +// Parameters: +// - `data` is slice that will be sorted. +// - `idx` is indices of data. +// - `l` is starting index of slice to be sorted. +// - `r` is end index of slice to be sorted. +// +func Ints64InsertionSort(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] { + IntsSwap(ids, x, y) + Ints64Swap(d, x, y) + } + } else { + if d[x] < d[y] { + IntsSwap(ids, x, y) + Ints64Swap(d, x, y) + } + } + } + } +} + +// +// Ints64SortByIndex will sort the slice `d` using sorted index `sortedIds`. +// +func Ints64SortByIndex(d *[]int64, sortedIds []int) { + newd := make([]int64, len(*d)) + + for i := range sortedIds { + newd[i] = (*d)[sortedIds[i]] + } + + (*d) = newd +} + +// +// Ints64InplaceMergesort in-place merge-sort without memory allocation. +// +func Ints64InplaceMergesort(d []int64, idx []int, l, r int, asc bool) { + // (0) If data length == Threshold, then + if l+SortThreshold >= r { + // (0.1) use insertion sort. + Ints64InsertionSort(d, idx, l, r, asc) + return + } + + // (1) Divide into left and right. + res := (r + l) % 2 + c := (r + l) / 2 + if res == 1 { + c++ + } + + // (2) Sort left. + Ints64InplaceMergesort(d, idx, l, c, asc) + + // (3) Sort right. + Ints64InplaceMergesort(d, idx, c, r, asc) + + // (4) 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 + } + } + + ints64InplaceMerge(d, idx, l, c, r, asc) +} + +// +// 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 ints64InplaceMerge(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 = ints64MoveY(d, x, y, r, asc) + + // (4.3.3) SWAP DATA, X, Y, YLAST + ints64Multiswap(d, idx, x, y, ylast) + + next: + // (4.3.4) LET Y := the minimum value between x and r on `d` + ints64MinY(d, &x, &y, r, asc) + } +} + +// (4.3.4) LET Y := the minimum value between x and r on `d` +func ints64MinY(d []int64, x, y *int, r int, asc bool) { + for *x < r { + if asc { + *y = ints64Min(d, *x, r) + } else { + *y = ints64Max(d, *x, r) + } + + if *y != *x { + break + } + (*x)++ + } +} + +func ints64MoveY(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 ints64Multiswap(d []int64, idx []int, x, y, ylast int) int { + for y < ylast { + IntsSwap(idx, x, y) + Ints64Swap(d, x, y) + x++ + y++ + if y >= ylast { + return y + } + if d[x] <= d[y] { + return y + } + } + + return y +} + +func ints64Min(d []int64, l, r int) (m int) { + min := d[l] + m = l + for l++; l < r; l++ { + if d[l] <= min { + min = d[l] + m = l + } + } + return +} + +func ints64Max(d []int64, l, r int) (m int) { + maxv := d[l] + m = l + for l++; l < r; l++ { + if d[l] >= maxv { + maxv = d[l] + m = l + } + } + return m +} + +// +// Ints64IndirectSort will sort the data and return the sorted index. +// +func Ints64IndirectSort(d []int64, asc bool) (sortedIdx []int) { + dlen := len(d) + + sortedIdx = make([]int, dlen) + for i := 0; i < dlen; i++ { + sortedIdx[i] = i + } + + Ints64InplaceMergesort(d, sortedIdx, 0, dlen, asc) + + return +} diff --git a/lib/numbers/ints64_test.go b/lib/numbers/ints64_test.go new file mode 100644 index 00000000..1ca25d28 --- /dev/null +++ b/lib/numbers/ints64_test.go @@ -0,0 +1,386 @@ +// 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 numbers + +import ( + "fmt" + "testing" + + "github.com/shuLhan/share/lib/test" +) + +var ( + dInts64 = [][]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}, + } + dInts64Sorted = [][]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}, + } + dInts64SortedDesc = [][]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 TestInts64FindMaxEmpty(t *testing.T) { + gotv, goti, gotok := Ints64FindMax(dInts64[0]) + + test.Assert(t, "", int64(-1), gotv, true) + test.Assert(t, "", -1, goti, true) + test.Assert(t, "", false, gotok, true) +} + +func TestInts64FindMax(t *testing.T) { + gotv, goti, gotok := Ints64FindMax(dInts64[1]) + + test.Assert(t, "", int64(9), gotv, true) + test.Assert(t, "", 4, goti, true) + test.Assert(t, "", true, gotok, true) +} + +func TestInts64FindMinEmpty(t *testing.T) { + gotv, goti, gotok := Ints64FindMin(dInts64[0]) + + test.Assert(t, "", int64(-1), gotv, true) + test.Assert(t, "", -1, goti, true) + test.Assert(t, "", false, gotok, true) +} + +func TestInts64FindMin(t *testing.T) { + gotv, goti, gotok := Ints64FindMin(dInts64[1]) + + test.Assert(t, "", int64(0), gotv, true) + test.Assert(t, "", 5, goti, true) + test.Assert(t, "", true, gotok, true) +} + +func TestInts64Sum(t *testing.T) { + got := Ints64Sum(dInts64[1]) + + test.Assert(t, "", int64(45), got, true) +} + +func TestInts64Count(t *testing.T) { + got := Ints64Count(dInts64[0], 0) + + test.Assert(t, "", 0, got, true) + + got = Ints64Count(dInts64[1], 1) + + test.Assert(t, "", 1, got, true) + + got = Ints64Count(dInts64[2], 1) + + test.Assert(t, "", 4, got, true) + + got = Ints64Count(dInts64[3], 0) + + test.Assert(t, "", 0, got, true) + + got = Ints64Count(dInts64[3], 3) + + test.Assert(t, "", 1, got, true) +} + +func TestInts64CountsEmpty(t *testing.T) { + classes := []int64{1, 2, 3} + exp := []int{0, 0, 0} + + got := Ints64Counts(dInts64[0], classes) + + test.Assert(t, "", exp, got, true) +} + +func TestInts64CountsEmptyClasses(t *testing.T) { + classes := []int64{} + var exp []int + + got := Ints64Counts(dInts64[1], classes) + + test.Assert(t, "", exp, got, true) +} + +func TestInts64Counts(t *testing.T) { + classes := []int64{1, 2, 3} + exp := []int{3, 3, 1} + + got := Ints64Counts(dInts64[3], classes) + + test.Assert(t, "", exp, got, true) +} + +func TestInts6464MaxCountOf(t *testing.T) { + classes := []int64{0, 1} + exp := int64(0) + got, _ := Ints64MaxCountOf(dInts64[2], classes) + + test.Assert(t, "", exp, got, true) + + // Swap the class values. + classes = []int64{1, 0} + got, _ = Ints64MaxCountOf(dInts64[2], classes) + + test.Assert(t, "", exp, got, true) +} + +func TestInts64SwapEmpty(t *testing.T) { + exp := []int64{} + + Ints64Swap(dInts64[0], 1, 6) + + test.Assert(t, "", exp, dInts64[0], true) +} + +func TestInts64SwapEqual(t *testing.T) { + in := make([]int64, len(dInts64[1])) + copy(in, dInts64[1]) + + exp := make([]int64, len(in)) + copy(exp, in) + + Ints64Swap(in, 1, 1) + + test.Assert(t, "", exp, in, true) +} + +func TestInts64SwapOutOfRange(t *testing.T) { + in := make([]int64, len(dInts64[1])) + copy(in, dInts64[1]) + + exp := make([]int64, len(in)) + copy(exp, in) + + Ints64Swap(in, 1, 100) + + test.Assert(t, "", exp, in, true) +} + +func TestInts64Swap(t *testing.T) { + in := make([]int64, len(dInts64[1])) + copy(in, dInts64[1]) + + exp := make([]int64, len(in)) + copy(exp, in) + + Ints64Swap(in, 0, len(in)-1) + + test.Assert(t, "", exp, in, false) + + tmp := exp[0] + exp[0] = exp[len(exp)-1] + exp[len(exp)-1] = tmp + + test.Assert(t, "", exp, in, true) +} + +func TestInts64IsExist(t *testing.T) { + var s bool + + // True positive. + for _, d := range dInts64 { + for _, v := range d { + s = Ints64IsExist(d, v) + + test.Assert(t, "", true, s, true) + } + } + + // False positive. + for _, d := range dInts64 { + s = Ints64IsExist(d, -1) + test.Assert(t, "", false, s, true) + s = Ints64IsExist(d, 10) + test.Assert(t, "", false, s, true) + } +} + +func TestInts64InsertionSort(t *testing.T) { + for x := range dInts64 { + d := make([]int64, len(dInts64[x])) + + copy(d, dInts64[x]) + + ids := make([]int, len(d)) + for x := range ids { + ids[x] = x + } + + Ints64InsertionSort(d, ids, 0, len(ids), true) + + test.Assert(t, "", dInts64Sorted[x], d, true) + } +} + +func TestInts64InsertionSortDesc(t *testing.T) { + for x := range dInts64 { + d := make([]int64, len(dInts64[x])) + + copy(d, dInts64[x]) + + ids := make([]int, len(d)) + for x := range ids { + ids[x] = x + } + + Ints64InsertionSort(d, ids, 0, len(ids), false) + + test.Assert(t, "", dInts64SortedDesc[x], d, true) + } +} + +func TestInts64SortByIndex(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 dInts64 { + d := make([]int64, len(dInts64[x])) + + copy(d, dInts64[x]) + + Ints64SortByIndex(&d, ids[x]) + + test.Assert(t, "", dInts64Sorted[x], d, true) + } +} + +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 TestInts64IndirectSort(t *testing.T) { + var res, exp string + + for i := range ints64InSorts { + Ints64IndirectSort(ints64InSorts[i], true) + + res = fmt.Sprint(ints64InSorts[i]) + exp = fmt.Sprint(ints64ExpSorts[i]) + + test.Assert(t, "", exp, res, true) + } +} + +func TestInts64IndirectSortDesc(t *testing.T) { + var res, exp string + + for i := range ints64InSorts { + Ints64IndirectSort(ints64InSorts[i], false) + + res = fmt.Sprint(ints64InSorts[i]) + exp = fmt.Sprint(ints64ExpSortsDesc[i]) + + test.Assert(t, "", exp, res, true) + } +} + +func TestInts64IndirectSort_Stability(t *testing.T) { + exp := []int{0, 1, 2, 3, 4, 5, 6, 7, 8, 9} + got := Ints64IndirectSort(ints64InSorts[5], true) + + test.Assert(t, "", exp, got, true) +} + +func TestInts64IndirectSortDesc_Stability(t *testing.T) { + exp := []int{0, 1, 2, 3, 4, 5, 6, 7, 8, 9} + got := Ints64IndirectSort(ints64InSorts[5], false) + + test.Assert(t, "", exp, got, true) +} + +func TestInts64InplaceMergesort(t *testing.T) { + size := len(ints64InSorts[6]) + idx := make([]int, size) + + Ints64InplaceMergesort(ints64InSorts[6], idx, 0, size, true) + + test.Assert(t, "", ints64ExpSorts[6], ints64InSorts[6], true) +} + +func TestInts64IndirectSort_SortByIndex(t *testing.T) { + expIds := []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) + + sortedIds := Ints64IndirectSort(in1, true) + + test.Assert(t, "", expIds, sortedIds, true) + + // Reverse the sort. + Ints64SortByIndex(&in2, sortedIds) + + got := fmt.Sprint(in2) + + test.Assert(t, "", exp, got, true) +} diff --git a/lib/numbers/ints_example_test.go b/lib/numbers/ints_example_test.go new file mode 100644 index 00000000..45e9dfc2 --- /dev/null +++ b/lib/numbers/ints_example_test.go @@ -0,0 +1,17 @@ +// 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 numbers + +import ( + "fmt" +) + +func ExampleIntsMax() { + ints := []int{5, 6, 7, 8, 9, 0, 1, 2, 3, 4} + + fmt.Println(IntsFindMax(ints)) + // Output: + // 9 4 true +} diff --git a/lib/numbers/ints_test.go b/lib/numbers/ints_test.go new file mode 100644 index 00000000..dd5818ec --- /dev/null +++ b/lib/numbers/ints_test.go @@ -0,0 +1,386 @@ +// 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 numbers + +import ( + "fmt" + "testing" + + "github.com/shuLhan/share/lib/test" +) + +var ( + dInts = [][]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}, + } + dIntsSorted = [][]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}, + } + dIntsSortedDesc = [][]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 TestIntsFindMaxEmpty(t *testing.T) { + maxv, maxi, ok := IntsFindMax(dInts[0]) + + test.Assert(t, "", -1, maxv, true) + test.Assert(t, "", -1, maxi, true) + test.Assert(t, "", false, ok, true) +} + +func TestIntsFindMax(t *testing.T) { + maxv, maxi, ok := IntsFindMax(dInts[1]) + + test.Assert(t, "", 9, maxv, true) + test.Assert(t, "", 4, maxi, true) + test.Assert(t, "", true, ok, true) +} + +func TestIntsFindMinEmpty(t *testing.T) { + minv, mini, ok := IntsFindMin(dInts[0]) + + test.Assert(t, "", -1, minv, true) + test.Assert(t, "", -1, mini, true) + test.Assert(t, "", false, ok, true) +} + +func TestIntsFindMin(t *testing.T) { + minv, mini, ok := IntsFindMin(dInts[1]) + + test.Assert(t, "", 0, minv, true) + test.Assert(t, "", 5, mini, true) + test.Assert(t, "", true, ok, true) +} + +func TestIntsSum(t *testing.T) { + got := IntsSum(dInts[1]) + + test.Assert(t, "", 45, got, true) +} + +func TestIntsCount(t *testing.T) { + got := IntsCount(dInts[0], 0) + + test.Assert(t, "", 0, got, true) + + got = IntsCount(dInts[1], 1) + + test.Assert(t, "", 1, got, true) + + got = IntsCount(dInts[2], 1) + + test.Assert(t, "", 4, got, true) + + got = IntsCount(dInts[3], 0) + + test.Assert(t, "", 0, got, true) + + got = IntsCount(dInts[3], 3) + + test.Assert(t, "", 1, got, true) +} + +func TestIntsCountsEmpty(t *testing.T) { + classes := []int{1, 2, 3} + exp := []int{0, 0, 0} + + got := IntsCounts(dInts[0], classes) + + test.Assert(t, "", exp, got, true) +} + +func TestIntsCountsEmptyClasses(t *testing.T) { + classes := []int{} + var exp []int + + got := IntsCounts(dInts[1], classes) + + test.Assert(t, "", exp, got, true) +} + +func TestIntsCounts(t *testing.T) { + classes := []int{1, 2, 3} + exp := []int{3, 3, 1} + + got := IntsCounts(dInts[3], classes) + + test.Assert(t, "", exp, got, true) +} + +func TestIntsMaxCountOf(t *testing.T) { + classes := []int{0, 1} + exp := int(0) + got, _ := IntsMaxCountOf(dInts[2], classes) + + test.Assert(t, "", exp, got, true) + + // Swap the class values. + classes = []int{1, 0} + got, _ = IntsMaxCountOf(dInts[2], classes) + + test.Assert(t, "", exp, got, true) +} + +func TestIntsSwapEmpty(t *testing.T) { + exp := []int{} + + IntsSwap(dInts[0], 1, 6) + + test.Assert(t, "", exp, dInts[0], true) +} + +func TestIntsSwapEqual(t *testing.T) { + in := make([]int, len(dInts[1])) + copy(in, dInts[1]) + + exp := make([]int, len(in)) + copy(exp, in) + + IntsSwap(in, 1, 1) + + test.Assert(t, "", exp, in, true) +} + +func TestIntsSwapOutOfRange(t *testing.T) { + in := make([]int, len(dInts[1])) + copy(in, dInts[1]) + + exp := make([]int, len(in)) + copy(exp, in) + + IntsSwap(in, 1, 100) + + test.Assert(t, "", exp, in, true) +} + +func TestIntsSwap(t *testing.T) { + in := make([]int, len(dInts[1])) + copy(in, dInts[1]) + + exp := make([]int, len(in)) + copy(exp, in) + + IntsSwap(in, 0, len(in)-1) + + test.Assert(t, "", exp, in, false) + + tmp := exp[0] + exp[0] = exp[len(exp)-1] + exp[len(exp)-1] = tmp + + test.Assert(t, "", exp, in, true) +} + +func TestIntsIsExist(t *testing.T) { + var s bool + + // True positive. + for _, d := range dInts { + for _, v := range d { + s = IntsIsExist(d, v) + + test.Assert(t, "", true, s, true) + } + } + + // False positive. + for _, d := range dInts { + s = IntsIsExist(d, -1) + test.Assert(t, "", false, s, true) + s = IntsIsExist(d, 10) + test.Assert(t, "", false, s, true) + } +} + +func TestIntsInsertionSort(t *testing.T) { + for x := range dInts { + d := make([]int, len(dInts[x])) + + copy(d, dInts[x]) + + ids := make([]int, len(d)) + for x := range ids { + ids[x] = x + } + + IntsInsertionSort(d, ids, 0, len(ids), true) + + test.Assert(t, "", dIntsSorted[x], d, true) + } +} + +func TestIntsInsertionSortDesc(t *testing.T) { + for x := range dInts { + d := make([]int, len(dInts[x])) + + copy(d, dInts[x]) + + ids := make([]int, len(d)) + for x := range ids { + ids[x] = x + } + + IntsInsertionSort(d, ids, 0, len(ids), false) + + test.Assert(t, "", dIntsSortedDesc[x], d, true) + } +} + +func TestIntsSortByIndex(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 dInts { + d := make([]int, len(dInts[x])) + + copy(d, dInts[x]) + + IntsSortByIndex(&d, ids[x]) + + test.Assert(t, "", dIntsSorted[x], d, true) + } +} + +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 TestIntsIndirectSort(t *testing.T) { + var res, exp string + + for i := range intsInSorts { + IntsIndirectSort(intsInSorts[i], true) + + res = fmt.Sprint(intsInSorts[i]) + exp = fmt.Sprint(intsExpSorts[i]) + + test.Assert(t, "", exp, res, true) + } +} + +func TestIntsIndirectSortDesc(t *testing.T) { + var res, exp string + + for i := range intsInSorts { + IntsIndirectSort(intsInSorts[i], false) + + res = fmt.Sprint(intsInSorts[i]) + exp = fmt.Sprint(intsExpSortsDesc[i]) + + test.Assert(t, "", exp, res, true) + } +} + +func TestIntsIndirectSort_Stability(t *testing.T) { + exp := []int{0, 1, 2, 3, 4, 5, 6, 7, 8, 9} + got := IntsIndirectSort(intsInSorts[5], true) + + test.Assert(t, "", exp, got, true) +} + +func TestIntsIndirectSortDesc_Stability(t *testing.T) { + exp := []int{0, 1, 2, 3, 4, 5, 6, 7, 8, 9} + got := IntsIndirectSort(intsInSorts[5], false) + + test.Assert(t, "", exp, got, true) +} + +func TestIntsInplaceMergesort(t *testing.T) { + size := len(intsInSorts[6]) + idx := make([]int, size) + + IntsInplaceMergesort(intsInSorts[6], idx, 0, size, true) + + test.Assert(t, "", intsExpSorts[6], intsInSorts[6], true) +} + +func TestIntsIndirectSort_SortByIndex(t *testing.T) { + expIds := []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) + + sortedIds := IntsIndirectSort(in1, true) + + test.Assert(t, "", expIds, sortedIds, true) + + // Reverse the sort. + IntsSortByIndex(&in2, sortedIds) + + got := fmt.Sprint(in2) + + test.Assert(t, "", exp, got, true) +} diff --git a/lib/numbers/numerus.go b/lib/numbers/numerus.go new file mode 100644 index 00000000..4500dbd7 --- /dev/null +++ b/lib/numbers/numerus.go @@ -0,0 +1,25 @@ +// 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 numbers provide miscellaneous functions for working with integer, +// float, slice of integer, and slice of floats. +// +// Features +// +// List of current features, +// +// - sort slice of floats using in-place mergesort algorithm. +// - sort slice of integer/floats by predefined index +// - count number of value occurence in slice of integer/float +// - find minimum or maximum value in slice of integer/float +// - sum slice of integer/float +// +package numbers + +const ( + // SortThreshold when the data less than SortThreshold, insertion sort + // will be used to replace mergesort. + SortThreshold = 7 +) |
