sort.Reverse

April 30, 2019 by George K. MacRorie

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

Reverse Domain Name in Go

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!

© 2018 | Follow on Twitter | Hucore theme & Hugo