README
¶
esort
Package esort provides mechanisms for sorting user-defined types according to compound criteria extensibly. It is mutually compatible with package sort from the standard library. The package name comes from the combination of the words "extensible" and "sort" and shortened as "esort."
Goals
- Type Safe
- Zero Allocation (in common workflows if sorting basis is known a priori)
- Zero Reflection
- Safe and Accurate
- Reasonable Degree of Ergonomics
Motivation
This is an experimental library.
Stupid as it sounds: during code review out in the field, I have seen more
half-baked (sort.Interface).Less implementations than I am comfortable with,
particularly where compound criteria are evaluated. I wondered whether the
situation could be solved through an API.
I'm not suggesting anyone should use this. There are potentially other solutions to improve ergonomics and performance. For the time being, it is a minimally-viable prototype.
Its API documentation is available at https://pkg.go.dev/github.com/matttproud/esort.
Documentation
¶
Overview ¶
Package esort provides mechanisms for sorting user-defined types according to compound criteria extensibly. It is mutually compatible with package sort from the standard library. The package name comes from the combination of the words "extensible" and "sort" and shortened as "esort."
Consider a case of sorting a user-defined type of a Person:
type Person struct {
GivenName string
ID int
}
Suppose GivenName is to be sorted in descending order and ties of the GivenName by ID in ascending order:
sorter := esort.New().
ByString(func(p Person) string { return p.GivenName }, esort.Desc).
ByInt(func(p Person) int { return p.ID }, esort.Asc)
The data can then be sorted:
var data []Person
sort.Slice(data, func(i, j int) bool { return sorter.Less(data[i], data[j]) })
The same mechanism can be used directly with generics:
slices.SortFunc(data, sorter.Less)
Sorting Instructions ¶
The methods prefixed with By copy the current sorting rule set and add a new instruction to the copy. Each rule set is evaluated according to the order in which the instructions were added to the Sorter, so earlier sorting rules carry higher sorting weight than the previous.
A Sorter without rules is invalid and panics upon use.
Due to the copy on write semantics of the instructions API, rule sets can be templatized:
base := esort.New().
ByString(func(p Person) string { return p.GivenName }, esort.Desc).
idAsc := base.ByInt(func(p Person) int { return p.ID }, esort.Asc)
idDesc := base.ByInt(func(p Person) int { return p.ID }, esort.Desc)
Efficiency ¶
Prefer using the simple, scalar By methods for comparing individual fields versus encoding their logic in the Sorter.ByFunc method. These individual methods are implemented efficiently.
Prefer:
sorter := esort.New().
ByString(func(p Person) string { return p.GivenName }, esort.Desc).
ByInt(func(p Person) int { return p.ID }, esort.Asc)
Over:
sorter := esort.New().
ByFunc(func(l, r Person) bool {
if l.GivenName != r.GivenName {
return l.GivenName < r.GivenName
}
}, esort.Desc).
ByInt(func(p Person) int { return p.ID }, esort.Asc)
Prefer defining the sorters as top-level variables if they have a static sorting basis. They will allocate zero memory during later program runtime — provided of course no user-defined functions registered with ByFunc do.
User-Defined Sorting Functions ¶
The ByFunc method enables types to be sorted by user-defined functions. The ByFunc method follows the same logic as the other instructions; it is appended to the rule set and evaluated accordingly.
If the function provided to ByFunc compares only one sorting basis, it may be implemented in a naive fashion whereby it only compares one side of the basis. Consider a data-transmission object (DTO)
func lessDTO(l, r *dto.SomeData) bool {
return l.GetField() < r.GetField()
}
sorter := esort.New().
ByFunc(lessDTO, esort.Asc)
The function lessDTO needn't consider the inverse case:
func lessDTO(l, r *dto.SomeData) bool {
if l.GetField() < r.GetField() {
return true
}
return r.GetField() < l.GetField()
}
The Sorter checks inverse cases automatically.
Ergonomics of Value Accessors ¶
The examples above are implemented using anonymous functions, similar to this:
func(p Person) string { return p.GivenName }
You are free to use free-standing, top-level functions:
func name(p Person) string { return p.GivenName }
sorter := esort.New().
ByFunc(name, esort.Asc)
And method expressions on the types, though consider whether getters are even appropriate for the API first:
func (p Person) GivenName string { return p.givenName }
sorter := esort.New().
ByFunc(p.GivenName, esort.Asc)
Performance ¶
A hand-implemented sort.Interface.Less function readily beats a Sorter. As implemented today, a Sorter with a simple double-compound sort criteria takes approximately 5-7x the time of a hand-written Less.
Index ¶
- Constants
- type Dir
- type SortFunc
- type Sorter
- func (s *Sorter[T]) ByBool(f func(T) bool, d Dir) *Sorter[T]
- func (s *Sorter[T]) ByByte(f func(T) byte, d Dir) *Sorter[T]
- func (s *Sorter[T]) ByBytes(f func(T) []byte, d Dir) *Sorter[T]
- func (s *Sorter[T]) ByFloat32(f func(T) float32, d Dir) *Sorter[T]
- func (s *Sorter[T]) ByFloat64(f func(T) float64, d Dir) *Sorter[T]
- func (s *Sorter[T]) ByFunc(f SortFunc[T], d Dir) *Sorter[T]
- func (s *Sorter[T]) ByInt(f func(T) int, d Dir) *Sorter[T]
- func (s *Sorter[T]) ByInt16(f func(T) int16, d Dir) *Sorter[T]
- func (s *Sorter[T]) ByInt32(f func(T) int32, d Dir) *Sorter[T]
- func (s *Sorter[T]) ByInt64(f func(T) int64, d Dir) *Sorter[T]
- func (s *Sorter[T]) ByInt8(f func(T) int8, d Dir) *Sorter[T]
- func (s *Sorter[T]) ByPointer(f func(T) uintptr, d Dir) *Sorter[T]
- func (s *Sorter[T]) ByRune(f func(T) rune, d Dir) *Sorter[T]
- func (s *Sorter[T]) ByString(f func(T) string, d Dir) *Sorter[T]
- func (s *Sorter[T]) ByUint(f func(T) uint, d Dir) *Sorter[T]
- func (s *Sorter[T]) ByUint16(f func(T) uint16, d Dir) *Sorter[T]
- func (s *Sorter[T]) ByUint32(f func(T) uint32, d Dir) *Sorter[T]
- func (s *Sorter[T]) ByUint64(f func(T) uint64, d Dir) *Sorter[T]
- func (s *Sorter[T]) ByUint8(f func(T) uint8, d Dir) *Sorter[T]
- func (s *Sorter[T]) Less(l, r T) bool
Constants ¶
const ( // Asc sorts the results in ascending order. Asc = Dir(iota) // Desc sorts the results in descending order. Desc )
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type SortFunc ¶
SortFunc sorts the data according to an arbitrary function.
SortFunc mimics a sort.Interface.Less function. Functions that sort by one criterion may return a simple l before r check. Consider:
sorter := esort.New().
ByFunc(func(l, r T) bool {
return l.GivenName < r.GivenName
})
Functions that perform compound comparisons must perform symmetric checks of r before l in order to produce sensible results:
sorter := esort.New().
ByFunc(func(l, r T) bool {
if l.GivenName != r.GivenName {
return l.GivenName < r.GivenName
}
return l.ID < r.ID
})
Implementations of SortFunc must not sort in a way that conflicts with a pre-existing instruction in a Sorter; otherwise inconsistent results may be produced.
Using the native By-prefixed functions to generate sorting rule sets is preferable to using this API.
type Sorter ¶
type Sorter[T any] struct { // contains filtered or unexported fields }
Sorter is the representation of a compound sorting program. A Sorter is safe for concurrent use by multiple goroutines.
func (*Sorter[T]) ByFunc ¶
ByFunc sorts the data according to an arbitrary given SortFunc. The SortFunc must not the underlying data by that any pre-existing intruction does.
func (*Sorter[T]) Less ¶
Less is a sort ordering function that fulfills the contract expected by sort.Interface.Less and related APIs.
Source Files