xsort

Documentation

Overview

Package xsort contains extensions to the standard library package sort.

Index

• func Equal[T any](less Less[T], a T, b T) bool
• func Greater[T any](less Less[T], a T, b T) bool
• func GreaterOrEqual[T any](less Less[T], a T, b T) bool
• func LessOrEqual[T any](less Less[T], a T, b T) bool
• func Merge[T any](less Less[T], in ...iterator.Iterator[T]) iterator.Iterator[T]
• func MergeSlices[T any](less Less[T], out []T, in ...[]T) []T
• func MinK[T any](less Less[T], iter iterator.Iterator[T], k int) []T
• func OrderedLess[T cmp.Ordered](a, b T) bool
• func Search[T any](x []T, less Less[T], item T) int
• func Slice[T any](x []T, less Less[T])
• func SliceIsSorted[T any](x []T, less Less[T]) bool
• func SliceStable[T any](x []T, less Less[T])
• type Less
  • func Reverse[T any](less Less[T]) Less[T]

Examples

• Merge
• MergeSlices
• MinK
• Search

Functions

func Equal

func Equal[T any](less Less[T], a T, b T) bool

Equal returns true if a == b according to less.

func Greater

func Greater[T any](less Less[T], a T, b T) bool

Greater returns true if a > b according to less.

func GreaterOrEqual

func GreaterOrEqual[T any](less Less[T], a T, b T) bool

LessOrEqual returns true if a >= b according to less.

func LessOrEqual

func LessOrEqual[T any](less Less[T], a T, b T) bool

LessOrEqual returns true if a <= b according to less.

func Merge

func Merge[T any](less Less[T], in ...iterator.Iterator[T]) iterator.Iterator[T]

Merge returns an iterator that yields all items from in in sorted order.

The results are undefined if the in iterators do not yield items in sorted order according to less.

The time complexity of Next() is O(log(k)) where k is len(in).

Example

package main

import (
	"fmt"

	"github.com/bradenaw/juniper/iterator"
	"github.com/bradenaw/juniper/xsort"
)

func main() {
	listOne := []string{"a", "f", "p", "x"}
	listTwo := []string{"b", "e", "o", "v"}
	listThree := []string{"s", "z"}

	merged := xsort.Merge(
		xsort.OrderedLess[string],
		iterator.Slice(listOne),
		iterator.Slice(listTwo),
		iterator.Slice(listThree),
	)

	fmt.Println(iterator.Collect(merged))

}

Output:

[a b e f o p s v x z]

func MergeSlices

func MergeSlices[T any](less Less[T], out []T, in ...[]T) []T

MergeSlices merges the already-sorted slices of in. Optionally, a pre-allocated out slice can be provided to store the result into.

The results are undefined if the in slices are not already sorted.

The time complexity is O(n * log(k)) where n is the total number of items and k is len(in).

Example

package main

import (
	"fmt"

	"github.com/bradenaw/juniper/xsort"
)

func main() {
	listOne := []string{"a", "f", "p", "x"}
	listTwo := []string{"b", "e", "o", "v"}
	listThree := []string{"s", "z"}

	merged := xsort.MergeSlices(
		xsort.OrderedLess[string],
		nil,
		listOne,
		listTwo,
		listThree,
	)

	fmt.Println(merged)

}

Output:

[a b e f o p s v x z]

func MinK

func MinK[T any](less Less[T], iter iterator.Iterator[T], k int) []T

MinK returns the k minimum items according to less from iter in sorted order. If iter yields fewer than k items, MinK returns all of them.

Example

package main

import (
	"fmt"

	"github.com/bradenaw/juniper/iterator"
	"github.com/bradenaw/juniper/xsort"
)

func main() {
	a := []int{7, 4, 3, 8, 2, 1, 6, 9, 0, 5}

	iter := iterator.Slice(a)
	min3 := xsort.MinK(xsort.OrderedLess[int], iter, 3)
	fmt.Println(min3)

	iter = iterator.Slice(a)
	max3 := xsort.MinK(xsort.Reverse(xsort.OrderedLess[int]), iter, 3)
	fmt.Println(max3)

}

Output:

[0 1 2]
[9 8 7]

func OrderedLess

func OrderedLess[T cmp.Ordered](a, b T) bool

OrderedLess is an implementation of Less for cmp.Ordered types by using the < operator.

Deprecated: cmp.Less is in the standard library as of Go 1.21.

func Search

func Search[T any](x []T, less Less[T], item T) int

Search searches for item in x, assumed sorted according to less, and returns the index. The return value is the index to insert item at if it is not present (it could be len(a)).

Deprecated: slices.BinarySearchFunc is in the standard library as of Go 1.21.

Example

package main

import (
	"fmt"

	"github.com/bradenaw/juniper/xsort"
)

func main() {
	x := []string{"a", "f", "h", "i", "p", "z"}

	fmt.Println(xsort.Search(x, xsort.OrderedLess[string], "h"))
	fmt.Println(xsort.Search(x, xsort.OrderedLess[string], "k"))

}

Output:

2
4

func Slice

func Slice[T any](x []T, less Less[T])

Slice sorts x in-place using the given less function to compare items.

Follows the same rules as sort.Slice.

Deprecated: slices.SortFunc is in the standard library as of Go 1.21.

func SliceIsSorted

func SliceIsSorted[T any](x []T, less Less[T]) bool

SliceIsSorted returns true if x is in sorted order according to the given less function.

Follows the same rules as sort.SliceIsSorted.

Deprecated: slices.IsSortedFunc is in the standard library as of Go 1.21.

func SliceStable

func SliceStable[T any](x []T, less Less[T])

SliceStable stably sorts x in-place using the given less function to compare items.

Follows the same rules as sort.SliceStable.

Deprecated: slices.SortStableFunc is in the standard library as of Go 1.21.

Types

type Less

type Less[T any] func(a, b T) bool

Returns true if a is less than b. Must follow the same rules as sort.Interface.Less.

func Reverse

func Reverse[T any](less Less[T]) Less[T]

Reverse returns a Less that orders elements in the opposite order of the provided less.