README
¶
pullsorter
Pullsorter is a Go module that sorts slices using a pull-style API, enabling interactive sorting scenarios.
License
Pullsorter is licensed under the terms of the MPL 2.0.
Documentation
¶
Overview ¶
Package pullsorter sorts slices using a pull-style API that produces one pair of items at a time for comparison by the user.
This package is designed for sorting scenarios where the results of some or all comparisons cannot be known in advance (e.g. interactively ranking a list by repeatedly prompting the user to choose between a pair of items).
Example ¶
package main
import (
"fmt"
"os"
"dwh.moe/pullsorter"
)
func main() {
ps := pullsorter.New([]int{5, 1, 2, 4, 3})
for {
if done, err := ps.Sort(); done {
break
} else if err != nil {
fmt.Fprintln(os.Stderr, err)
break
}
// Simulate prompting the user to compare a and b: negative if a < b,
// positive if a > b, and zero if a == b.
userResponse := ps.A - ps.B
// Store the comparison result so subsequent calls to ps.Sort can
// use it.
ps.Store.Add(ps.A, ps.B, userResponse)
}
fmt.Println(ps.Sorted)
}
Output: [1 2 3 4 5]
Example (UserRanking) ¶
package main
import (
"bufio"
"fmt"
"os"
"dwh.moe/pullsorter"
)
func main() {
var (
items = []string{"apple", "orange", "pear", "banana"}
ps = pullsorter.New(items)
scanner = bufio.NewScanner(os.Stdin)
)
for {
if done, err := ps.Sort(); done {
break
} else if err != nil {
fmt.Fprintln(os.Stderr, "error:", err)
os.Exit(1)
}
fmt.Printf("Which fruit do you prefer: %q or %q (any other answer indicates no preference)? ", ps.A, ps.B)
if !scanner.Scan() { // error or EOF?
os.Exit(2)
}
if scanner.Text() == ps.A {
ps.Store.Add(ps.A, ps.B, -1) // a < b
} else if scanner.Text() == ps.B {
ps.Store.Add(ps.A, ps.B, 1) // a > b
} else {
ps.Store.Add(ps.A, ps.B, 0) // a == b
}
}
fmt.Println("Your fruit ranking:")
for i, e := range ps.Sorted {
fmt.Printf("%2d. %s\n", i+1, e)
}
}
Output:
Index ¶
Examples ¶
Constants ¶
This section is empty.
Variables ¶
var ErrUnknownComparison = errors.New("unknown comparison")
ErrUnknownComparison is the error returned by a Comparator when the result of the comparison is unknown.
Functions ¶
This section is empty.
Types ¶
type CmpResultStore ¶
type CmpResultStore[T comparable] interface { Comparator[T] // Add stores the result of comparing a and b, where a negative result // indicates a < b, positive indicates a > b, and zero indicates a == b. Any // previous result for a and b is overwritten. Add(a, b T, result int) error // Remove deletes the stored comparison result for a and b, if one exists. Remove(a, b T) error }
A CmpResultStore stores comparison results so they can be reused in future sorts. It implements Comparator: the Compare method returns the stored result for any given pair of items or ErrUnknownComparison if no result can be found for that pair. Compare must be transposable: if Compare(a, b) = c then Compare(b, a) = -c.
type Comparator ¶
type Comparator[T any] interface { // Compare compares two items of the same type. The result is negative when // a < b, positive when a > b, and zero when a == b or err is non-nil. // Compare returns an ErrUnknownComparison error when the result of the // comparison is unknown. Compare(a, b T) (result int, err error) }
A Comparator compares two items of the same type.
func JoinComparators ¶
func JoinComparators[T any](cmps ...Comparator[T]) Comparator[T]
JoinComparators returns a new Comparator that tries each provided Comparator in order and returns the first comparison result found, or ErrUnknownComparison if none of the Comparators returned a valid result.
type ComparatorFunc ¶ added in v0.3.0
ComparatorFunc is an adapter type that allows regular functions with the appropriate signature to be used where a Comparator is expected.
func (ComparatorFunc[T]) Compare ¶ added in v0.3.0
func (f ComparatorFunc[T]) Compare(a, b T) (int, error)
Compare calls f(a, b).
type MemoryStore ¶
type MemoryStore[T comparable] struct { // contains filtered or unexported fields }
MemoryStore is an implementation of CmpResultStore that uses an in-memory storage backend.
func (*MemoryStore[T]) Add ¶
func (m *MemoryStore[T]) Add(a, b T, result int) error
Add implements the CmpResultStore interface.
func (*MemoryStore[T]) Compare ¶
func (m *MemoryStore[T]) Compare(a, b T) (result int, err error)
Compare implements the Comparator interface.
func (*MemoryStore[T]) Remove ¶
func (m *MemoryStore[T]) Remove(a, b T) error
Add implements the CmpResultStore interface.
type PullSorter ¶
type PullSorter[S ~[]E, E comparable] struct { // Slice is the slice to be sorted. Slice S // Sorted is set to the sorted slice after Sort returns true, indicating no // more comparisons need to be made. Sorted S // A and B are the current pair of items needing comparison. They are set // when Sort returns false. A, B E // Store specifies the store to be consulted for comparison results while // sorting. If Store is nil, it will be set to a new instance of // MemoryStore during the first call to Sort. Store CmpResultStore[E] // Comparator is an optional comparator that, if provided, will be consulted // first while sorting before searching the store. Comparator Comparator[E] }
A PullSorter facilitates sorting a slice interactively by consulting a CmpResultStore for previously saved comparison results. After each call to Sort, A and B will be set to a pair of items needing comparison. The caller can register the comparison result using Store.Add. Once all comparisons are complete, Sort sets Sorted and returns false.
func New ¶
func New[S ~[]E, E comparable](s S) *PullSorter[S, E]
New returns a new PullSorter for sorting s.
func (*PullSorter[S, E]) Sort ¶
func (p *PullSorter[S, E]) Sort() (done bool, err error)
Sort attempts to sort a copy of p.Slice, consulting p.Comparator (if non-nil) and p.Store for previously registered comparison results as needed. If no comparison result can be found for a pair of items during the sorting process, Sort sets p.A and p.B to the pair of items needing comparison and returns false. If no more comparisons are needed, Sort sets p.Sorted to the sorted slice and returns true.
Source Files