I recently edited my first wikipedia entry. I was learning about how Google indexes websites with BigQuery and stumbled across the page for reverse domain name notation. It makes sense when creating and index of URLs to do so in reverse domain order. This is the process of flipping the constituent parts of a URL like so:
www.google.com
becomes com.google.www
and george.macro.re
becomes re.macro.george
and so on.I was delighted to see all examples of reversing a list in different programming languages. So I quickly scrolled to my language of choice Go to check out the suggestion.
What I found was the following:
func reverseDomain(domain string) string {
s := strings.Split(domain, ".")
sort.Sort(sort.Reverse(sort.StringSlice(s)))
return strings.Join(s, ".")
}
Check this out on the Go Playground.
You will find it fails to reverse
www.google.com
into com.google.www
. In fact it does nothing to this particular input string and www.google.com
is returned.The reason I spotted this is because I was familiar with the
sort.Sort(sort.Interface)
function used in the original implementation. I asked myself, why does it sort the result of calling sort.Reverse
?So my first gut instinct was perhaps they just need to drop the
sort.Sort
and just call sort.Reverse
instead. sort.Reverse
to me sounds as if it reverses the input right? I assume that is what the original author was also expecting.Well that is not actually the case. Looking closer at the documentation:
func Reverse(data Interface) Interface
Reverse returns the reverse order for data.
First interpretation of this documentation is the same conclusion I had before. It returns the reverse order of the data.
I see the function takes an
Interface
and returns an Interface
. So perhaps it doesn't mutate the state but return a newly allocated reversed result. However, what is that Interface
type? First pass I just see it and assume it is interface{}
but that is not the same thing. This is an exported type from the same package called Interface
.type Interface interface {
// Len is the number of elements in the collection.
Len() int
// Less reports whether the element with
// index i should sort before the element with index j.
Less(i, j int) bool
// Swap swaps the elements with indexes i and j.
Swap(i, j int)
}
This is a special interface which must be implemented by a slice type in order for the
sort
package to be able to sort the contents of the slice. This is the crux of the sort package and the sort.Sort
family of functions.
So what actually is sort.Reverse
because the signature is sort.Reverse(Interface) Interface
. It takes one of these types and returns another implementation. This is a clue. It decorates the interface. The reality is the result of calling sort.Reverse
is no actual manipulation of the order at that point in time. Rather it changes the behaviour of the Less(i, j int) bool
implementation which it decorates.type reverse struct {
// This embedded Interface permits Reverse to use the methods of
// another Interface implementation.
Interface
}
// Less returns the opposite of the embedded implementation's Less method.
func (r reverse) Less(i, j int) bool {
return r.Interface.Less(j, i)
}
// Reverse returns the reverse order for data.
func Reverse(data Interface) Interface {
return &reverse{data}
}
This is taken directly from the Go standard library. Notice that the new unexported type
*reverse
is returned, which embeds the wrapped implementation and implements its own version of the Less
function. This implementation delegates a call to the embedded Interface
type and does something rather subtle. It swaps the parameters i
and j
around. The result of which means the newly decorated implementation of the sort.Interface
is returned and it will be sorted in reverse order. It won't perform a reversal operation, but rather it will manipulate a later call to sort.Sort
such that it produces a reversed order result.This is really neat and in some cases optimal. It is often more efficient to sort something into reverse order rather than sort it and then reverse it afterwards. However, it is misleading for those reading the documentation. I see
sort.Reverse
and assume it reverses the thing I give it.Returning to the original input
www.google.com
you will notice when delimited by .
you get the resulting parts www
, google
and com
. Which when sorted lexicographically in reverse order produces the same result (w > g > c). Which is why the original example produces the same result as the input string.As far as I can tell there is no way to lean on the
sort
package in order to perform a reversal of an arbitrarily typed slice. Nor have I seen another package which does this. Which is why in my implementation I chose to simply swap the elements of the slice from outside to in. The handy multiple assignment statement here is your friend.func reverseDomain(domain string) string {
s := strings.Split(domain, ".")
for left := 0; left < (len(s)/2)+1; left++ {
right := len(s)-left-1
s[left], s[right] = s[right], s[left]
}
return strings.Join(s, ".")
}
UPDATE
@arussellsaw just pointed out a neat little solution which does use
sort.Slice
:func reverseDomain(domain string) string {
s := strings.Split(domain, ".")
sort.Slice(s, func(i, j int) bool {
return i > j
})
return strings.Join(s, ".")
}
This compares the indexes rather than the values, which means the result of calling
sort.Slice
is it just reverses the order of the contents. Nice!