Documentation
¶
Overview ¶
Package sorted provides functions for manipulating sorted slices.
Index ¶
- func BisectRight[S ~[]E, E cmp.Ordered](s S, target E) int
- func BisectRightFunc[S ~[]E, E, T any](s S, target T, cmp func(E, T) int) int
- func Delete[S ~[]E, E cmp.Ordered](s S, e E) S
- func DeleteFunc[E any, S ~[]E](s S, e E, cmp func(a, b E) int) S
- func Find[S ~[]E, E cmp.Ordered](s S, e E) S
- func FindFunc[E any, S ~[]E](s S, e E, cmp func(a, b E) int) S
- func Insert[S ~[]E, E cmp.Ordered](s S, e E) S
- func InsertFunc[E any, S ~[]E](s S, e E, cmp func(a, b E) int) S
- func Prefix[E cmp.Ordered, S ~[]E](s S) S
- func PrefixFunc[E any, S ~[]E](s S, cmp func(a, b E) int) S
Examples ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func BisectRight ¶
BisectRight searches for the insertion point for x in a sorted slice. The return value is the index where x would be inserted such that all elements in s[:i] are <= x, and all elements in s[i:] are > x.
Example ¶
package main
import (
"fmt"
"github.com/mkch/gg/slices2/sorted"
)
func main() {
type Int int
var s = []Int{1, 2, 2, 3}
i := sorted.BisectRight(s, 2)
fmt.Printf("The latest insert position of 2 in %v is %v", s, i)
}
Output: The latest insert position of 2 in [1 2 2 3] is 3
func BisectRightFunc ¶
BisectRightFunc works like BisectRight, but uses a custom comparison function.
Example ¶
package main
import (
"cmp"
"fmt"
"github.com/mkch/gg/slices2/sorted"
)
func main() {
type Entry struct {
ID int
Name string
}
cmpName := func(a, b Entry) int {
return cmp.Compare(a.Name, b.Name)
}
var entries = []Entry{
{1, "a"},
{2, "b"},
{3, "b"},
{4, "c"},
}
var toInsert = Entry{5, "b"}
i := sorted.BisectRightFunc(entries, toInsert, cmpName)
fmt.Printf("The latest insert position of %v in %v is %v", toInsert, entries, i)
}
Output: The latest insert position of {5 b} in [{1 a} {2 b} {3 b} {4 c}] is 3
func Delete ¶
Delete deletes all elements e from a ascendingly sorted slice s.
Example ¶
package main
import (
"fmt"
"github.com/mkch/gg/slices2/sorted"
)
func main() {
type Int int
var s = []Int{1, 2, 2, 3}
s = sorted.Delete(s, 2)
fmt.Println(s)
}
Output: [1 3]
func DeleteFunc ¶
DeleteFunc works like Delete, but use a custom comparison function. The slice must be sorted in increasing order, where "increasing" is defined the same way as in slices.BinarySearchFunc.
Example ¶
package main
import (
"cmp"
"fmt"
"github.com/mkch/gg/slices2/sorted"
)
func main() {
type Entry struct {
ID int
Name string
}
cmpName := func(a, b Entry) int {
return cmp.Compare(a.Name, b.Name)
}
var entries = []Entry{
{1, "a"},
{2, "b"},
{3, "b"},
{4, "c"},
}
var toInsert = Entry{Name: "b"}
// All entries with Name "b" will be deleted.
entries = sorted.DeleteFunc(entries, toInsert, cmpName)
fmt.Println(entries)
}
Output: [{1 a} {4 c}]
func Find ¶
Find returns a run of elements equal to e from an ascendingly sorted slice s. The content of returned slice must not be modified; it is valid only until the next update of s
Example ¶
package main
import (
"fmt"
"github.com/mkch/gg/slices2/sorted"
)
func main() {
var s = []int{1, 2, 2, 3}
s2 := sorted.Find(s, 2)
fmt.Println(s2)
}
Output: [2 2]
func FindFunc ¶
FindFunc works like Find, but use a custom comparison function. The slice must be sorted in increasing order, where "increasing" is defined the same way as in slices.BinarySearchFunc.
Example ¶
package main
import (
"cmp"
"fmt"
"github.com/mkch/gg/slices2/sorted"
)
func main() {
type Entry struct {
ID int
Name string
}
cmpName := func(a, b Entry) int {
return cmp.Compare(a.Name, b.Name)
}
var entries = []Entry{
{1, "a"},
{3, "b"},
{4, "b"},
{2, "c"},
}
var target = Entry{Name: "b"}
found := sorted.FindFunc(entries, target, cmpName)
fmt.Println(found)
}
Output: [{3 b} {4 b}]
func Insert ¶
Insert inserts an element e into a ascendingly sorted slice s, such that the elements in the updated slice remain in ascending order. The insertion position is determined by slices.BinarySearch: inserting before any existing elements equal to e.
Example ¶
package main
import (
"fmt"
"github.com/mkch/gg/slices2/sorted"
)
func main() {
type Int int
var s = []Int{1, 2, 3}
s = sorted.Insert(s, 2)
fmt.Println(s)
}
Output: [1 2 2 3]
func InsertFunc ¶
InsertFunc works like Insert, but use a custom comparison function. The slice must be sorted in increasing order, where "increasing" is defined the same way as in slices.BinarySearchFunc.
Example ¶
package main
import (
"cmp"
"fmt"
"github.com/mkch/gg/slices2/sorted"
)
func main() {
type Entry struct {
ID int
Name string
}
cmpName := func(a, b Entry) int {
return cmp.Compare(a.Name, b.Name)
}
var entries = []Entry{
{1, "a"},
{2, "b"},
{3, "b"},
{4, "c"},
}
var toInsert = Entry{5, "b"}
entries = sorted.InsertFunc(entries, toInsert, cmpName)
fmt.Println(entries)
}
Output: [{1 a} {5 b} {2 b} {3 b} {4 c}]
func Prefix ¶
Prefix returns the prefix run of ascendingly sorted slice s. The prefix run is the maximal sequence of identical elements from the start of s. If the length of s is 0, the returned prefix is nil.
Example ¶
package main
import (
"fmt"
"github.com/mkch/gg/slices2/sorted"
)
func main() {
var s = []int{1, 1, 1, 2, 2, 3}
for {
prefix := sorted.Prefix(s)
if prefix == nil {
break
}
s = s[len(prefix):]
fmt.Println(prefix)
}
}
Output: [1 1 1] [2 2] [3]
func PrefixFunc ¶
PrefixFunc works like Prefix, but use a custom comparison function. The slice must be sorted in increasing order, where "increasing" is defined the same way as in slices.BinarySearchFunc.
Example ¶
package main
import (
"cmp"
"fmt"
"github.com/mkch/gg/slices2/sorted"
)
func main() {
type Entry struct {
ID int
Name string
}
cmpName := func(a, b Entry) int {
return cmp.Compare(a.Name, b.Name)
}
var entries = []Entry{
{1, "a"},
{3, "b"},
{4, "b"},
{2, "c"},
}
for {
prefix := sorted.PrefixFunc(entries, cmpName)
if prefix == nil {
break
}
entries = entries[len(prefix):]
fmt.Println(prefix)
}
}
Output: [{1 a}] [{3 b} {4 b}] [{2 c}]
Types ¶
This section is empty.
Source Files