proposal: iter/sorted: functions on sorted iterators

[jba]

I propose adding a package of functions that operate on iterators whose values are sorted.

Sorted sequences can arise in a number of ways:

• From a slice that has been sorted.
• From the keys of an ordered map, such as github.com/google/btree or the one in #60630.
• From an external source, like a database with sorted keys.
• Naturally, as in the line numbers of a file or the times of a monotonic clock.

Common operations on pairs of sorted sequences include merging them into a single sorted sequence, as well as the set operations union, intersection and set difference. I propose a package with these operations, with the API given below.

As is common in packages like slices, there are two functions for each operation, one using the natural ordering of a type and one that accepts a comparison function. We could also consider adding functions that operate on the keys of iter.Seq2s, bringing along the corresponding values. I don't know if those sequences would arise enough to make that worthwhile. We could reconsider adding the Seq2 functions if and when we add ordered maps.

API

package sorted

Package sorted provides operations over iterators whose values are sorted.

FUNCTIONS

func Intersect[T cmp.Ordered](s1, s2 iter.Seq[T]) iter.Seq[T]
    Intersect returns an iterator over all elements of s1 that are also in s2,
    in the same order. Each element of s1 appears only once in the result.
    Both s1 and s2 must be sorted.

func IntersectFunc[T any](s1, s2 iter.Seq[T], cmp func(T, T) int) iter.Seq[T]
    IntersectFunc returns an iterator over all elements of s1 that are also in
    s2, in the same order. Each element of s1 appears only once in the result.
    Both s1 and s2 must be sorted according to cmp.

func Merge[T cmp.Ordered](s1, s2 iter.Seq[T]) iter.Seq[T]
    Merge returns an iterator over all elements of s1 and s2, in the same order.
    Both s1 and s2 must be sorted.

func MergeFunc[T any](s1, s2 iter.Seq[T], cmp func(T, T) int) iter.Seq[T]
    MergeFunc returns an iterator over all elements of s1 and s2, in the same
    order. Both s1 and s2 must be sorted according to cmp.

func Subtract[T cmp.Ordered](s1, s2 iter.Seq[T]) iter.Seq[T]
    Subtract returns an iterator over all elements of s1 that are not in s2,
    in the same order. Each element of s1 appears only once in the result.
    Both s1 and s2 must be sorted.

func SubtractFunc[T any](s1, s2 iter.Seq[T], cmp func(T, T) int) iter.Seq[T]
    SubtractFunc returns an iterator over all elements of s1 that are not in s2,
    in the same order. Each element of s1 appears only once in the result.
    Both s1 and s2 must be sorted according to cmp.

func Union[T cmp.Ordered](s1, s2 iter.Seq[T]) iter.Seq[T]
    Union returns an iterator over all elements of s1 and s2, in the same order.
    Each element appears only once in the result. Both s1 and s2 must be sorted.

func UnionFunc[T any](s1, s2 iter.Seq[T], cmp func(T, T) int) iter.Seq[T]
    UnionFunc returns an iterator over all elements of s1 and s2, in the same
    order. Each element appears only once in the result. Both s1 and s2 must be
    sorted according to cmp.

There is a working implementation at github.com/jba/sorted.

[gabyhelp]

Related Issues and Documentation

• proposal: container: add tree-based ordered.Map/Set #60630
• proposal: container/set: new package to provide a generic set type #69230
• proposal: x/exp/xiter: new package with iterator adapters #61898

_{(Emoji vote if this was helpful or unhelpful; more detailed feedback welcome in this discussion.)}

[jimmyfrasche]

Is there any difference between this Merge and the one in #61898?

If this package gets added, it seems like a good place for the sequence equivalent for Compact: #67441