sort points (structs) by different dimensions in go lang

Question

I have a list of multidimensional points of type Points.

I've implemented the sort.Sort interface and can now sort by y value.

e.g.

type Points []*Point

func (points Points) Len() int {
    return len(points)
}
func (points Points) Less(i, j int) bool {
    return points[i].y < points[j].y
}
func (points Points) Swap(i, j int) {
    points[i], points[j] = points[j], points[i]
}

type Point struct {
    x int
    y int
    country_id int
}

Now I want to sort my points by x value instead of y value.

My idea is to use an if statement with a global flag (which can be switched on or off before sorting):

func (points Points) Less(i, j int) bool {
    if SORT_BY_X {
        return points[i].x < points[j].x
    }
    return points[i].y < points[j].y
}

Is there a better way of doing this? Should I be implementing Less multiple times? What if I was sorting tables of data by columns for example?

Answer 1

Ah, this is interesting: sort.Sort() expects the type to define an ordering and some array operations. You can have "X-sortable point list" and "Y-sortable point list" types, but making them share the array ops works differently from in other languages because Go doesn't use inheritance.

The first way I thought of is to create XSortablePoints and YSortablePoints types that each independently implement sort.Interface, and convert your Points instance to whichever one you need at the moment--see here: http://play.golang.org/p/9V3WlKjOwX.

Then nemo had a better way: type embedding allows XSortablePoints and YSortablePoints to share the functions for array operations. Also, nemo doesn't save the sortable types in a variable, which makes sense as they only exist for this one sort call. Here's adjusted sample code: http://play.golang.org/p/wNm-ilM18n

Note that neither of these approaches actually copies your point data when you cast, just the slice header. You can see that by looking at the pointer addresses printed out by the first example.

You can get fancier: there's a Points.Sort taking an arbitrary comparison function at http://play.golang.org/p/4PmJVi2_7D. I think the brute-force approach of just defining more types is fine as long as you only have two or three orderings, but situations vary. Note that for types much bigger than the points here, you might want to define the comparer to take pointers rather than values, to avoid copying.

re: SORT_BY_X: I'd generally avoid global mode-setting variables that you update as the program runs, because there are lots of ways those can come back to bite you. For example, maybe you'll have two parallel goroutines someday and then trouble happens when they both access the global at once. Or maybe some code will work when the initial value of SORT_BY_X is false, then someday fail because it was left true after another task ran. If you do find yourself needing a mode variable, figure out if, instead of it being global, you could make it a function parameter or attach it to an object.

Finally, there might be a package that already provides some of the higher-level functionality you want. For example, there are some packages related to geographic data listed here: https://code.google.com/p/go-wiki/wiki/Projects#GIS

Answer 2

In addition to user2714852's answer, you can use the same technique as is already used for reversing sorting in the sort package: shadowing the Less() definition.

While this is similar to what was already proposed, the way of getting there is a bit different (example on play). You define your points:

type Points []Point

func (points Points) Swap(i, j int) {
    points[i], points[j] = points[j], points[i]
}

func (points Points) Len() int {
    return len(points)
}

And for each sorting method you implement your own type which embeds your Points type:

type XPoints struct {
    Points
}

func (points XPoints) Less(i,j int) bool {
    return points.Points[i].x < points.Points[j].x
}

type YPoints struct {
    Points
}

func (points YPoints) Less(i, j int) bool {
    return points.Points[i].y < points.Points[j].y
}

Now you can use the different sorting methods like this:

pts := Points{{1, 2, 3}, {2, 1, 3}}

sort.Sort(XPoints{pts})
fmt.Println("X-sorted points:", pts)

sort.Sort(YPoints{pts})
fmt.Println("Y-sorted points:", pts)