README
¶
filter
The filter package supports sorting and partitioning the contents of a slice
in-place according to a selection rule.
After partitioning, all the selected elements are at low-order indices of the collection, in their original relative order; the unselected elements follow in arbitrary order. This operation takes linear time in the size of the collection, and constant space overhead for bookkeeping.
This operation permits a collection to be filtered efficiently without redundant copying or movement of data. Some convenience functions are provided for applying this to common built-in data types.
Documentation
¶
Overview ¶
Package filter implements a general-purpose filter for slices.
Index ¶
Examples ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func LessThan ¶
func LessThan[V constraints.Ordered](x, y V) bool
LessThan implements a comparison function for ordered built-in types.
func Partition ¶
Partition rearranges v so that there is an index 0 ≤ i < len(vs) such that keep(j) is true for all j < i and keep(j) is false for all j ≥ i. The value of i is returned.
The relative input order of the kept elements (indexes < i) is preserved, but the unkept elements (indexes ≥ i) are permuted arbitrarily.
Partition does not allocate storage outside vs. It uses time proportional to len(vs) and swaps each kept element at most once.
Example (Ints) ¶
package main
import (
"fmt"
"github.com/creachadair/filter"
)
func main() {
zs := []int{-8, 6, -7, 5, -3, 0, -9}
n := filter.Partition(zs, func(z int) bool {
return z >= 0
})
fmt.Println(zs[:n])
}
Output: [6 5 0]
Example (Primes) ¶
package main
import (
"fmt"
"github.com/creachadair/filter"
)
func isPrime(z int) bool {
for i := 3; i*i <= z; i += 2 {
if z%i == 0 {
return false
}
}
return z == 2 || z > 2 && z%2 == 1
}
func main() {
zz := []int{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15}
n := filter.Partition(zz, isPrime)
fmt.Printf("primes: %+v\n", zz[:n])
}
Output: primes: [2 3 5 7 11 13]
Example (Strings) ¶
package main
import (
"fmt"
"sort"
"strings"
"github.com/creachadair/filter"
)
func main() {
s1 := strings.Split("a,lot,,of,values,,here,", ",")
fmt.Printf("in %+q\n", s1)
i := filter.Partition(sort.StringSlice(s1), func(s string) bool {
return s != ""
})
fmt.Println("i =", i)
fmt.Printf("old %+q\n", s1)
s2 := s1[:i]
fmt.Printf("new %+q\n", s2)
}
Output: in ["a" "lot" "" "of" "values" "" "here" ""] i = 5 old ["a" "lot" "of" "values" "here" "" "" ""] new ["a" "lot" "of" "values" "here"]
func SortUnique ¶
SortUnique sorts v, which must be a slice or a pointer to a slice, then partitions the slice in-place so that all the elements to the left of the partition point are unique and in order, with any duplicates at or to the right of the partition point. The elements after the partition point will not in general be in order. The return value is the number of unique elements.
In addition to the cost of sorting (using sort.Sort), deduplication uses time proportional to len(vs) and constant space for bookkeeping.
Example ¶
package main
import (
"fmt"
"sort"
"strings"
"github.com/creachadair/filter"
)
func main() {
ss := strings.Fields("and or not or if and not but and if not or and and if")
// SortUnique can be used to remove duplicates from a slice without
// allocating a new slice. It sorts the slice in-place and moves all the
// unique elements to the head of the slice, duplicates to the tail.
n := filter.SortUnique(sort.StringSlice(ss), func(x, y string) bool {
return x < y
})
fmt.Println(n)
fmt.Println(strings.Join(ss[:n], " "), "| ...", len(ss[n:]), "more")
}
Output: 5 and but if not or | ... 10 more
Types ¶
This section is empty.
Source Files