Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

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:

  • Len
  • Swap
  • Less

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?

like image 657
Jeroen Dirks Avatar asked Feb 09 '11 15:02

Jeroen Dirks


3 Answers

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})
}
like image 63
rog Avatar answered Oct 28 '22 14:10

rog


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).

like image 22
themue Avatar answered Oct 28 '22 15:10

themue


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)

like image 44
alltom Avatar answered Oct 28 '22 15:10

alltom