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 elements 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 {
sorted, a, b, err := ps.Sort()
if err == pullsorter.ErrUnknownComparison {
// Simulate prompting the user to compare a and b:
// negative if a < b, positive if a > b, and zero if a == b.
userResponse := a - b
// Store the comparison result so subsequent calls to ps.Sort can
// use it.
ps.Store.Add(a, b, userResponse)
} else if err != nil {
fmt.Fprintln(os.Stderr, err)
break
} else {
fmt.Println(sorted)
break
}
}
}
Output: [1 2 3 4 5]
Example (UserRanking) ¶
package main
import (
"bufio"
"fmt"
"os"
"dwh.moe/pullsorter"
)
func main() {
var (
sorted []string
items = []string{"apple", "orange", "pear", "banana"}
ps = pullsorter.New(items)
scanner = bufio.NewScanner(os.Stdin)
)
for {
var a, b string
var err error
sorted, a, b, err = ps.Sort()
if err == pullsorter.ErrUnknownComparison {
fmt.Printf("Which fruit do you prefer: %q or %q (any other answer indicates no preference)? ", a, b)
if !scanner.Scan() { // error or EOF?
os.Exit(2)
}
if scanner.Text() == a {
ps.Store.Add(a, b, -1) // a < b
} else if scanner.Text() == b {
ps.Store.Add(a, b, 1) // a > b
} else {
ps.Store.Add(a, b, 0) // a == b
}
} else if err != nil {
fmt.Fprintln(os.Stderr, "error:", err)
os.Exit(1)
} else {
break
}
}
fmt.Println("Your fruit ranking:")
for i, e := range 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 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 // 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 store for previously saved comparison results. The Sort method returns the sorted slice if all comparisons were successful; otherwise it returns the pair of elements needing comparison.
func New ¶
func New[S ~[]E, E comparable](s S) *PullSorter[S, E]
New initializes and returns a new PullSorter for sorting s.
func (*PullSorter[S, E]) Sort ¶
func (p *PullSorter[S, E]) Sort() (sorted S, a, b E, err error)
Sort attempts to sort a copy of p.Slice, consulting p.Comparator (if non-nil) and p.Store for comparison results as needed. If no comparison result can be found for a pair of elements during the sorting process, Sort aborts and returns ErrUnknownComparison along with the pair of elements a and b needing comparison. If no more comparisons are needed, Sort returns the sorted slice and a nil error.
Source Files