How to avoid re-implementing sort.Interface for similar golang structs

Question

There is one problem bothering me in Golang. Say I have 2 structs:

type Dog struct {
   Name string
   Breed string
   Age int
}

type Cat struct {
    Name string
    FavoriteFood string
    Age int
}

And when I try to sort []*Dog and []*Cat by Age, I have to define 2 different sort struct like:

type SortCat []*Cat
func (c SortCat) Len() int {//..}
func (c SortCat) Swap(i, j int) {//..}
func (c SortCat) Less(i, j int) bool {//..}

type SortDog []*Dog
func (c SortDog) Len() int {//..}
func (c SortDog) Swap(i, j int) {//..}
func (c SortDog) Less(i, j int) bool {//..}

A natural thought is to implement some SortableByAge interface and create a Less function using the interface function. Like:

type SortableByAge interface {
    AgeValue() int
}

And then:

type SortAnimal []SortableByAge
func (c SortDog) Less(i, j int) bool {
    return c[i].AgeValue() < c[j].AgeValue() 
}

However, according to: http://golang.org/doc/faq#convert_slice_of_interface

dogs := make([]*Dogs, 0 , 1)
//add dogs here
sort.Sort(SortAnimal(dogs))

Above is not possible.

So I wonder what is the best practice for this case and

Is there any other technique that can reduce the need for implementing the sort.Interface for similar structs again and again that I have missed?

EDIT: I realized that my examples are terrible :(

In real life case, these 2 structs are very different, the only thing in common between them is that I wish to sort them by a common numeric value.

A better example would be:

type Laptop {//...}
type Pizza {//...}

And the only thing these 2 structs share in common is that I wish to sort a slice(agh... should not have used Pizza in example) of them by price.

So, combining them to a common struct is not really working for a lot of cases. But will look into go generate.

Concordat

I would advise reimplementing it since it's three lines. – Piemonte

Since there are no generics -> Reimplement – Retene

(The one other thing is if they're really similar maybe you really want type Animal { Species, Name string; Age int }. Not all distinct real-world categories have to map to distinct types in your programs.) – Piemonte

Thanks @Piemonte ! I think my examples are bad, in real project, these two structs are different in many ways, I just wish to make them both sortable by a numerical field, The first thing I thought of was interface, but found out that it is not supported. so just checking with stackoverflow in case i have missed anything – Concordat

Answer 1

Note: as illustrated in commit ad26bb5, in Go 1.8 (Q1 2017), you won't have to implement Len() and Swap() and Less() since issue 16721 was resolved. Only Less() is needed, the rest is done by reflection.

The problem was:

1. Vast majority of sort.Interface uses a slice
2. Have to define a new top level type
3. Len and Swap methods are always the same
4. Want to make common case simpler with least hit to performance

See the new sort.go:

// Slice sorts the provided slice given the provided less function.
//
// The sort is not guaranteed to be stable. For a stable sort, use
// SliceStable.
//
// The function panics if the provided interface is not a slice.
func Slice(slice interface{}, less func(i, j int) bool) {
    rv := reflect.ValueOf(slice)
    swap := reflect.Swapper(slice)
    length := rv.Len()
    quickSort_func(lessSwap{less, swap}, 0, length, maxDepth(length))
}

So as long as you have a Less() function comparing two instances respecting an interface, you can sort any number of struct respecting said common interface.

---

Go 1.18 generics will add another option, as illustrated in nwillc/genfuncs/container/sort.go.

// Sort sorts a slice by the LessThan order.
func (s GSlice[T]) Sort(lessThan genfuncs.BiFunction[T, T, bool]) {
    n := len(s)
    s.quickSort(0, n, maxDepth(n), lessThan)
}

With BiFunction:

// BiFunction accepts two arguments and produces a result.
type BiFunction[T, U, R any] func(T, U) R

This is just an example illustrating how a generic sort could be implemented: it is not an official one (since generics are, at the ime of writing, Q1 2022, still very new).

Brisket

Also, you simply create a Less (anonymous) lambda. sort.Slice(a, func(i, j int) bool { return a[i] < a[j] }) This will sort in ascending order, if you want the opposite, simply write a[i] > a[j] in the lambda. – Boltrope

Answer 2

This Specific Case

In this specific case you shouldn't use 2 different types as they are identical, just use a common Animal type:

type Animal struct {
    Name string
    Age  int
}

func (a Animal) String() string { return fmt.Sprintf("%s(%d)", a.Name, a.Age) }

type SortAnim []*Animal

func (c SortAnim) Len() int           { return len(c) }
func (c SortAnim) Swap(i, j int)      { c[i], c[j] = c[j], c[i] }
func (c SortAnim) Less(i, j int) bool { return c[i].Age < c[j].Age }

func main() {
    dogs := []*Animal{&Animal{"Max", 4}, &Animal{"Buddy", 3}}
    cats := []*Animal{&Animal{"Bella", 4}, &Animal{"Kitty", 3}}

    fmt.Println(dogs)
    sort.Sort(SortAnim(dogs))
    fmt.Println(dogs)

    fmt.Println(cats)
    sort.Sort(SortAnim(cats))
    fmt.Println(cats)
}

Output (Go Playground):

[Max(4) Buddy(3)]
[Buddy(3) Max(4)]
[Bella(4) Kitty(3)]
[Kitty(3) Bella(4)]

General Case

In general you can only use a common sorting implementation if you're willing to give up concrete types and use interface types instead.

Create the interface type you want your slice to hold:

type Animal interface {
    Name() string
    Age() int
}

You can have a common implementation of this:

type animal struct {
    name string
    age  int
}

func (a *animal) Name() string  { return a.name }
func (a *animal) Age() int      { return a.age }
func (a animal) String() string { return fmt.Sprintf("%s(%d)", a.name, a.age) }

Your specific animal types:

type Dog struct {
    animal  // Embed animal (its methods and fields)
}

type Cat struct {
    animal // Embed animal (its methods and fields)
}

You implement sort.Interface on SortAnim:

type SortAnim []Animal

func (c SortAnim) Len() int           { return len(c) }
func (c SortAnim) Swap(i, j int)      { c[i], c[j] = c[j], c[i] }
func (c SortAnim) Less(i, j int) bool { return c[i].Age() < c[j].Age() }

Using it:

dogs := SortAnim{&Dog{animal{"Max", 4}}, &Dog{animal{"Buddy", 3}}}
cats := SortAnim{&Cat{animal{"Bella", 4}}, &Cat{animal{"Kitty", 3}}}

fmt.Println(dogs)
sort.Sort(SortAnim(dogs))
fmt.Println(dogs)

fmt.Println(cats)
sort.Sort(SortAnim(cats))
fmt.Println(cats)

Output (Go Playground):

[Max(4) Buddy(3)]
[Buddy(3) Max(4)]
[Bella(4) Kitty(3)]
[Kitty(3) Bella(4)]

Consistence

Answer 3

The best practice for this case would be to define

type Animal struct{
    Species,Name string
    Age int
}

as suggested by twotwotwo. If cat and dog are similar enough to be sorted in the same way, they are also similar enough to be the same struct. If they are different in some way, then you should reimplement the interface for each type.

An alternative could be to copy all pointers from your []*Cat slice into a []SortableByAge slice of the same size. If you are going to sort the slice, that will take O(n*log(n)) so an extra O(n) shouldn't be a performance issue.

A third alternative, in the rare event that you have many types that for some reason have to be distinct but still have very simple sorting functions, you can look at autogenerating them with go generate.

Condescendence

Thanks @johan, I am interested in go generate, too! Could you elaborate a little bit more about how we can use go generate in this case please? – Concordat

Answer 4

In Go 1.21, they have added a new package slices. It contains functions to deal with slices of generic types.

slices.SortFunc() might simplify things for you. It is faster and officially preferable over sort.Sort().

package main

import (
    "cmp"
    "fmt"
    "slices"
)

type Dog struct {
    Name  string
    Breed string
    Age   int
}

type Cat struct {
    Name         string
    FavoriteFood string
    Age          int
}

func CmpDog(a, b Dog) int {
    return cmp.Compare(a.Age, b.Age)
}

func CmpCat(a, b Cat) int {
    return cmp.Compare(a.Age, b.Age)
}

func main() {
    dogs := []Dog{
        {"Candice", "Poodle", 13},
        {"Alice", "Dalmation", 4},
        {"Bob", "Labrador", 8},
    }

    cats := []Cat{
        {"Betty", "Fish", 108},
        {"Brittany", "Fish", 99},
        {"Karen", "Fish", 81},
    }

    slices.SortFunc(dogs, CmpDog)
    slices.SortFunc(cats, CmpCat)
}

Note that slices.SortFunc() is not stable. For stable sorting, you can use slices.SortStableFunc(), which has the same signature as slices.SortFunc().

Gourami