Are there alternatives to lower & upper bound or partition_point
72 views
Skip to first unread message
lijh8
Oct 10, 2024, 5:01:10 PM10/10/24
to golang-nuts
Are there alternatives to lower & upper bound or partition_point
Suppose there duplicate entries in a slice.
I need to use a loop to find out the upper bound on a sorted slice.
Are there something similar to c++ lower_bound, upper_bound, partition_point?
Thanks
```
package main
import (
"slices"
"tuple2"
)
type S struct {
name string
num int
}
func cmp(a, b S) int {
x := []any{a.name, a.num}
y := []any{b.name, b.num}
z, _ := tuple2.Compare(x, y)
return z
}
func main() {
haystack := []S{
{"aaa", 10},
{"bbb", 20},
{"ccc", 30},
{"bbb", 20},
{"bbb", 20},
}
needle := S{"bbb", 20}
slices.SortFunc(haystack, cmp)
lower, _ := slices.BinarySearchFunc(haystack, needle, cmp)
upper := lower
for i := lower; i != len(haystack); i++ {
x := []any{needle.name, needle.num}
y := []any{haystack[i].name, haystack[i].num}
z, _ := tuple2.Compare(x, y)
if z == -1 {
upper = i
break
}
}
LOG(lower, upper)
}
```
```
package tuple2
import (
"cmp"
"reflect"
)
// two tuples should be the same length and
// element types are same for same position.
func Compare(a, b []any) (int, bool) {
if len(a) != len(b) {
return 0, false
}
for i := range a {
if a[i] == nil || b[i] == nil {
return 0, false
}
if _, boolean := a[i].(bool); boolean {
return 0, false
}
if _, boolean := b[i].(bool); boolean {
return 0, false
}
if a, b := reflect.TypeOf(a[i]), reflect.TypeOf(b[i]); a != b {
return 0, false
}
if a, aOk := a[i].(string); aOk {
if b, bOk := b[i].(string); bOk {
if c := cmp.Compare(a, b); c != 0 {
return c, true
}
}
}
if a, aOk := a[i].(int); aOk {
if b, bOk := b[i].(int); bOk {
if c := cmp.Compare(a, b); c != 0 {
return c, true
}
}
}
if a, aOk := a[i].(float64); aOk {
if b, bOk := b[i].(float64); bOk {
if c := cmp.Compare(a, b); c != 0 {
return c, true
}
}
}
if a, aOk := a[i].([]any); aOk {
if b, bOk := b[i].([]any); bOk {
if c, ok := Compare(a, b); ok && c != 0 {
return c, true
} else if !ok {
return 0, false
}
}
}
}
return 0, true
}
/*
func main() {
a := []any{"abc", 123, 3.14}
b := []any{"abc", 123, 3.14}
c, ok := tuple2.Compare(a, b)
fmt.Println(c, ok)
}
*/
```
Ian Lance Taylor
Oct 10, 2024, 5:06:07 PM10/10/24
to lijh8, golang-nuts
On Thu, Oct 10, 2024 at 2:01 PM 'lijh8' via golang-nuts
<golan...@googlegroups.com> wrote:
>
> Are there alternatives to lower & upper bound or partition_point
>
> Suppose there duplicate entries in a slice.
> I need to use a loop to find out the upper bound on a sorted slice.
>
> Are there something similar to c++ lower_bound, upper_bound, partition_point?
Those don't currently exist in the Go standard library.
<golan...@googlegroups.com> wrote:
>
> Are there alternatives to lower & upper bound or partition_point
>
> Suppose there duplicate entries in a slice.
> I need to use a loop to find out the upper bound on a sorted slice.
>
> Are there something similar to c++ lower_bound, upper_bound, partition_point?
Ian
robert engels
Oct 10, 2024, 5:14:11 PM10/10/24
to lijh8, golang-nuts
Check out https://pkg.go.dev/github.com/liyue201/go...@v1.2.0/algorithm/sort but you could just as easily write those functions - they’re fairly trivial.
Almost all of the C++ STL is implemented.
--
You received this message because you are subscribed to the Google Groups "golang-nuts" group.
To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/golang-nuts/tencent_118EE485C4CA0D09E533048760E419034F0A%40qq.com.
Reply all
Reply to author
Forward
0 new messages