CODEWITHSUNDEEP
sortinginterfacego
Jeroen Dirks
Jeroen Dirks

Reputation: 7887

Is there a way to avoid the implementation of the full sort.Interface for slices of structs?

If I have an array/slice of structs in Go and want to sort them using the sort package it seems to me that I need to implement the whole sort interface which contains 3 methods:

It seems that Len and Swap should always have the same implementation no matter the type of struct is in the array.

Is there a way to avoid having the implement Len and Swap every time or is this just a limitation from the lack of Generics in Go?

Upvotes: 6

Views: 2880

Answers (4)

alltom
alltom

Reputation: 3252

If you want to sort slices (for which Len and Swap always have the same implementation), the sort package now has a function that only requires an implementation of Less:

func Slice(slice interface{}, less func(i, j int) bool)

Upvotes: 2

Dave C
Dave C

Reputation: 7896

Although this is an old question, I'd like to point out the github.com/bradfitz/slice package. But as an example or proof of concept only, I would not recommend this actually be used (it's documented with the word "gross"):

It uses gross, low-level operations to make it easy to sort arbitrary slices with only a less function, without defining a new type with Len and Swap operations.

In actual code, I find it completely trivial, quick, short, readable, and non-distracting to just do something like:

type points []point

func (p []points) Len() int      { return len(p) }
func (p []points) Swap(i, j int) { p[i], p[j] = p[j], p[i] }
func (p []points) Less(i, j int) bool {
        // custom, often multi-line, comparison code here
}

Here gofmt insists on a blank line between the type and func lines but it has no problem with multiple one-line functions with no blank lines and it nicely lines up the function bodies. I find this a nice readable compact form for such things.

As for your comment that:

It seems that Len and Swap should always have the same implementation no matter the type of struct is in the [slice]

just the other week I need a sort that kept pairs of elements in a slice together (for input to strings.NewReplacer) that required a trivial variation like:

type pairByLen []string

func (p pairByLen) Len() int           { return len(p) / 2 }
func (p pairByLen) Less(i, j int) bool { return len(p[i*2]) > len(p[j*2]) }
func (p pairByLen) Swap(i, j int) {
        p[i*2], p[j*2] = p[j*2], p[i*2]
        p[i*2+1], p[j*2+1] = p[j*2+1], p[i*2+1]
}

This is not supported by an interface like the one in github.com/bradfitz/slice. Again, I find this layout easy, compact, and readable. Although (perhaps more so in this case), others may disagree.

Upvotes: 0

rog
rog

Reputation: 6700

If you are implementing several different comparison operations on the same slice type, you can use embedding to avoid redefining Len and Swap each time. You can also use this technique to add parameters to the sort, for example to sort in reverse or not depending on some run-time value.

e.g.

package main

import (
    "sort"
)

type T struct {
    Foo int
    Bar int
}

// TVector is our basic vector type.
type TVector []T

func (v TVector) Len() int {
    return len(v)
}

func (v TVector) Swap(i, j int) {
    v[i], v[j] = v[j], v[i]
}

// default comparison.
func (v TVector) Less(i, j int) bool {
    return v[i].Foo < v[j].Foo
}

// TVectorBarOrdered embeds TVector and overrides
// its Less method so that it is ordered by the Bar field.
type TVectorBarOrdered struct {
    TVector
}

func (v TVectorBarOrdered) Less(i, j int) bool {
    return v.TVector[i].Bar < v.TVector[j].Bar
}

// TVectorArbitraryOrdered sorts in normal or reversed
// order depending on the order of its Reversed field.
type TVectorArbitraryOrdered struct {
    Reversed bool
    TVector
}

func (v TVectorArbitraryOrdered) Less(i, j int) bool {
    if v.Reversed {
        i, j = j, i
    }
    return v.TVector[i].Foo < v.TVector[j].Foo
}

func main() {
    v := []T{{1, 3}, {0, 6}, {3, 2}, {8, 7}}
    sort.Sort(TVector(v))
    sort.Sort(TVectorBarOrdered{v})
    sort.Sort(TVectorArbitraryOrdered{true, v})
}

Upvotes: 8

themue
themue

Reputation: 7850

Your own answer is right. In your case of an array or slice the implementations of Len() and Swap() are simple. Like len() Go could provide a native swap() here. But the interface which is used now can also be used for more complex data structures like BTrees. It still allows the Sort() function to work (like my parallel quicksort, which uses the same sort interface).

Upvotes: 5

Related Questions