Go sort a slice of runes?

Question

I'm having trouble sorting strings by character (to check whether two strings are anagrams, I want to sort both of them, and check for equality).

I can get a []rune representation of the string s like this:

runes := make([]rune, len(s)) 
copy(runes, []rune(s))

And I can sort ints like this

someInts := []int{5, 2, 6, 3, 1, 4} // unsorted
sort.Ints(someInts)

But rune is just an alias for int32 so I should be able to call

sort.Ints(runes) 

However, I get the error:

cannot use runes (type []rune) as type []int in function argument

So... how do I sort a slice of int32, int64, or int*?

EDIT: I did get my runes sorted, but boy, this is ugly.

type RuneSlice []rune

func (p RuneSlice) Len() int           { return len(p) }
func (p RuneSlice) Less(i, j int) bool { return p[i] < p[j] }
func (p RuneSlice) Swap(i, j int)      { p[i], p[j] = p[j], p[i] }

func sorted(s string) string {
    runes := []rune(s)
    sort.Sort(RuneSlice(runes))
    return string(runes)
}

So basically if you have a slice of whatever, you'll have to wrap it in a type that implements sort.Interface. All those implementations will have the exact same method bodies (like sort.IntSlice and sort.Float64Slice). If this is really how ugly this has to be then why didn't they provide these WhateverSlice wrappers in the sort package? The lack of generics start to hurt very badly now. There must be a better way of sorting things.

Solution 1

Use sort.Sort(data Interface) and implement sort.Interface, see the examples on package documentation.

You cannot use rune which is int32 as int. Check the comment of int.

int is a signed integer type that is at least 32 bits in size. It is a distinct type, however, and not an alias for, say, int32.

Solution 2

Note: Go 1.8 will introduce helpers for sorting slices.
See issue 16721 and commit 22a2bdf by Brad Fitzpatrick

var strings = [...]string{"", "Hello", "foo", "bar", "foo", "f00", "%*&^*&^&", "***"}

func TestSlice(t *testing.T) {
    data := strings
    Slice(data[:], func(i, j int) bool {
        return data[i] < data[j]
    })
}

Solution 3

Just as a point of comparison, here's what things might look like if the sort interface were slightly different. That is, rather than the interface being on the container, what would things look like if the interface were on the elements instead?

package main

import (
    "fmt"
    "sort"
)

type Comparable interface {
    LessThan(Comparable) bool
}

type ComparableSlice []Comparable

func (c ComparableSlice) Len() int {
    return len(c)
}

func (c ComparableSlice) Less(i, j int) bool {
    return c[i].LessThan(c[j])
}

func (c ComparableSlice) Swap(i, j int) {
    c[i], c[j] = c[j], c[i]
}

func SortComparables(elts []Comparable) {
    sort.Sort(ComparableSlice(elts))
}

//////////////////////////////////////////////////////////////////////
// Let's try using this:

type ComparableRune rune

func (r1 ComparableRune) LessThan(o Comparable) bool {
    return r1 < o.(ComparableRune)
}

func main() {
    msg := "Hello world!"

    comparables := make(ComparableSlice, len(msg))
    for i, v := range msg {
        comparables[i] = ComparableRune(v)
    }

    SortComparables(comparables)

    sortedRunes := make([]rune, len(msg))
    for i, v := range comparables {
        sortedRunes[i] = rune(v.(ComparableRune))
    }

    fmt.Printf("result: %#v\n", string(sortedRunes))
}

Here, we define a Comparable interface, and we get our type ComparableRune to satisfy it. But because it's an interface, we've got to do the awkward boxing to go from rune to ComparableRune so that dynamic dispatch can kick in:

    comparables := make(ComparableSlice, len(msg))
    for i, v := range msg {
        comparables[i] = ComparableRune(v)
    }

and unboxing to get back our runes:

    sortedRunes := make([]rune, len(msg))
    for i, v := range comparables {
        sortedRunes[i] = rune(v.(ComparableRune))
    }

This approach appears to require us to know how to do typecasts to go back and forth between the interface and the dynamic type of the value. It seems like we would need to use more parts of Go---more mechanics---than the approach that uses the container as the interface.

Solution 4

There is, in fact a soft-generic way to do what you want.

Check out the following package:

https://github.com/BurntSushi/ty/tree/master/fun

especially the following file:

https://github.com/BurntSushi/ty/blob/master/fun/sort_test.go

Example of how it is used:

tosort := []int{10, 3, 5, 1, 15, 6}

fun.Sort(func(a, b int) bool {
    return b < a
}, tosort)

There are lots of other interesting fun generic algorithms implemented through reflection in that package.

All credits go to @BurntSushi.

Solution 5

As of November 2020 at least, https://golang.org/pkg/sort/ offers to use a custom Less function passed as a closure. The code below has the desired effect:

package main

import (
    "fmt"
    "sort"
)

func main() {

    s1 := "eidbaooo"

    runeSlice := []rune(s1)

    fmt.Println(string(runeSlice))

    sort.Slice(runeSlice, func(i, j int) bool {
        return runeSlice[i] < runeSlice[j]
    })
    
    fmt.Println(string(runeSlice))
}

Output:

eidbaooo
abdeiooo

This can spare you the full interface implementation.

View more solutions

Comments

[andras]

Yes, it is a horrendous violation of DRY. I mean having the exact same code replicated as many times as there are basic types is pretty bad. Generic sort algorithms that work on basic types without any extra stitching is pretty much what you expect in ANY language. But having to teach the compiler how to get the length of a slice 20 times is just unreal.

[zzzz]

You're missing the point completely. The generic sort algorithm works not only for slices, but for anything satisfying sort.Interface. Now, how do you propose to automagically get the Len and friends of anything you know nothing about in advance (at compile time)??? IOW, your rant is not rational.

[andras]

I don't expect the compiler to be able sort BucketOfFish instances out of the box. sort.Interface seems like a nice abstraction for these cases (although I probably want to keep my Fishes in slices as well, instead of some custom container). I just find it strange that such a basic use case (slice of a basic type) is not covered by the standard library.

[Brad Ackerman]

Your make statement should use utf8.RuneCountInString (from unicode/utf8) rather than len; len counts the number of bytes, not the number of runes.

[Phrozen]

Actually typecasting works too! len([]rune(someString)) yields the same as utf8.RuneCountString (less imports) but for an anagram solver it won't matter in 99% of the cases. A colision where all utf8 character's bytes are the same is highly unlikely (although possible).

[andras]

I checked sort.go, and this is what I ended up doing, but COME ON! Do I really have to implement RuneSlice, ByteSlice, Int32Slice, UintSlice, etc etc? These are just the same 3 methods with the exact same method bodies! If this is really the only way to sort slices other than int and float64 slices then why didn't they implement these WhateverSlice types in sort.go? I will end up implementing them in my utils anyway. Is this because of the lack of generics? Come on, there must be a better way.

[Grzegorz Żur]

@andras That is a good question. I would put it on StackOverflow.

[andras]

@jnml thanks, that's something at least. Might wanna post an answer so that I can accept it. BTW, I googled "golang sort util" but did not find this package. How do you look for golang packages?

[andras]

thanks dyoo! This is helpful (although still not actually usable:). At least I see how you would do it in Java style. Still, the lack of generics (a basket of apples is not a basket of fruits) makes the solution unfeasible.

[dyoo]

andras: code.google.com/p/go-wiki/wiki/Projects seems to be a good place to find quality third-party packages.

[dyoo]

Yup! But let's keep the note about generics out of this, at least for now. Otherwise, the question can likely devolve into "Why doesn't Go support generics?!", which is something we can't answer effectively. It would be very nice if it did (maybe), but the proposed solutions here appear to be the right ways to use the very general sort.Sort routine and how Go's current type system affects its use.

[andras]

You're right about this, and I didn't mean this as a rant like "Why isn't Go like X language?". I'd like to learn idiomatic Go, but having to implement sort.Interface for basic types felt so weird that I thought I must be doing something wrong. Maybe in time I'll learn the way of Go and this issue won't bother me that much:)

[andras]

Thanks, this looks useful. It seems that it enforces type safety during runtime using reflection? (or black magic, for that matter, as I can't wrap my head around the source code yet:)

[andras]

@dyoo thanks, although I really hope that compiling a list of quality Go libraries by hand will become quickly unfeasible as Go gets more popular:)

[John Drinane]

The question is asking about runes not ints.

[Tao Starbow]

Until generics get out of beta, this is the best answer.