One of the termui tests was failing; this fixes the `numbered.Less()` function.

Something in sorting was broken at some point, maybe during a Go version
upgrade? That code hasn't changed in a while. While fixing the code, I rewrote
the `numbered.Less()` function. It's shorter, and I think it's clearer, but in
addition to being correct now it's also about 10% faster than the original.

2 files changed, 86 insertions, 48 deletions

diff --git a/termui/linegraph.go b/termui/linegraph.go
index 941183f..17ec1ae 100644
--- a/termui/linegraph.go
+++ b/termui/linegraph.go
@@ -171,57 +171,63 @@ type numbered []string
 
 func (n numbered) Len() int      { return len(n) }
 func (n numbered) Swap(i, j int) { n[i], n[j] = n[j], n[i] }
+
 func (n numbered) Less(i, j int) bool {
-	a := n[i]
-	b := n[j]
-	for i := 0; i < len(a); i++ {
-		ac := a[i]
-		if unicode.IsDigit(rune(ac)) {
-			j := i + 1
-			for ; j < len(a); j++ {
-				if !unicode.IsDigit(rune(a[j])) {
-					break
-				}
-				if j >= len(b) {
-					return false
-				}
-				if !unicode.IsDigit(rune(b[j])) {
-					return false
-				}
-			}
-			an, err := strconv.Atoi(a[i:j])
-			if err != nil {
+	ars := n[i]
+	brs := n[j]
+	// iterate over the runes in string A
+	var ai int
+	for ai = 0; ai < len(ars); ai++ {
+		ar := ars[ai]
+		// if brs has been equal to ars so far, but is shorter, than brs is less
+		if ai >= len(brs) {
+			return false
+		}
+		br := brs[ai]
+		// handle numbers if we find them
+		if unicode.IsDigit(rune(ar)) {
+			// if ar is a digit and br isn't, then ars is less
+			if !unicode.IsDigit(rune(brs[ai])) {
 				return true
 			}
-			if j > len(b) {
-				return false
+			// now get the range for the full numbers, which is the sequence of consecutive digits from each
+			ae := ai + 1
+			be := ae
+			for ; ae < len(ars) && unicode.IsDigit(rune(ars[ae])); ae++ {
 			}
-			for ; j < len(b); j++ {
-				if !unicode.IsDigit(rune(b[j])) {
-					break
-				}
+			for ; be < len(brs) && unicode.IsDigit(rune(brs[be])); be++ {
 			}
-			bn, err := strconv.Atoi(b[i:j])
+			if be < ae {
+				return false
+			}
+			adigs, err := strconv.Atoi(string(ars[ai:ae]))
 			if err != nil {
 				return true
 			}
-			if an < bn {
+			bdigs, err := strconv.Atoi(string(brs[ai:be]))
+			if err != nil {
 				return true
-			} else if bn < an {
-				return false
 			}
-			i = j
-		}
-		if i >= len(a) {
-			return true
-		} else if i >= len(b) {
+			// The numbers are equal; continue with the rest of the string
+			if adigs == bdigs {
+				ai = ae - 1
+				continue
+			}
+			return adigs < bdigs
+		} else if unicode.IsDigit(rune(br)) {
 			return false
 		}
-		if ac < b[i] {
+		if ar == br {
+			continue
+		}
+		// No digits, so compare letters
+		if ar < br {
 			return true
-		} else if b[i] < ac {
-			return false
 		}
+		return false
+	}
+	if ai <= len(brs) {
+		return true
 	}
-	return true
+	return false
 }
diff --git a/termui/linegraph_test.go b/termui/linegraph_test.go
index e8f8a6a..562c5ce 100644
--- a/termui/linegraph_test.go
+++ b/termui/linegraph_test.go
@@ -1,7 +1,10 @@
 package termui
 
-import "testing"
-import "sort"
+import (
+	"github.com/stretchr/testify/assert"
+	"sort"
+	"testing"
+)
 
 func TestLess(t *testing.T) {
 	tests := []struct {
@@ -16,6 +19,10 @@ func TestLess(t *testing.T) {
 		{a: "a2", b: "2", e: false},
 		{a: "a2", b: "a10", e: true},
 		{a: "a20", b: "a2", e: false},
+		{a: "abc", b: "abc20", e: true},
+		{a: "a1", b: "abc", e: true},
+		{a: "a20", b: "abc", e: true},
+		{a: "abc20", b: "abc", e: false},
 		{a: "abc20", b: "def2", e: true},
 		{a: "abc20", b: "abc2", e: false},
 		{a: "abc20", b: "abc20", e: true},
@@ -29,9 +36,7 @@ func TestLess(t *testing.T) {
 	for _, k := range tests {
 		n := numbered([]string{k.a, k.b})
 		g := n.Less(0, 1)
-		if g != k.e {
-			t.Errorf("%s < %s: expected %v, got %v", k.a, k.b, k.e, g)
-		}
+		assert.Equal(t, k.e, g, "%s < %s %t", k.a, k.b, g)
 	}
 }
 
@@ -40,7 +45,7 @@ func TestSort(t *testing.T) {
 		in, ex numbered
 	}{
 		{
-			in: numbered{"abc", "def", "abc", "abc", "def", "abc", "1", "10", "1", "2", "a2", "2", "a2", "a10", "a20", "a2", "abc20", "def2", "abc20", "abc2", "abc20", "abc20", "abc30", "abc20", "abc20a", "abc20", "abc20", "abc20a", "abc20", "abc2a"},
+			in: numbered{"abc", "def", "abc", "def", "abc", "1", "10", "1", "2", "a2", "2", "a2", "a10", "a20", "a2", "abc20", "def2", "abc20", "abc2", "abc20", "abc20", "abc30", "abc20", "abc20a", "abc20", "abc20", "abc20a", "abc20", "abc2a", "abc"},
 			ex: numbered{"1", "1", "2", "2", "10", "a2", "a2", "a2", "a10", "a20", "abc", "abc", "abc", "abc", "abc2", "abc2a", "abc20", "abc20", "abc20", "abc20", "abc20", "abc20", "abc20", "abc20", "abc20a", "abc20a", "abc30", "def", "def", "def2"},
 		},
 		{
@@ -51,10 +56,37 @@ func TestSort(t *testing.T) {
 
 	for _, k := range tests {
 		sort.Sort(k.in)
-		for i, v := range k.in {
-			if v != k.ex[i] {
-				t.Errorf("failed to properly sort\n\texpected: %v\n\tgot:      %v", k.ex, k.in)
-			}
+		assert.Equal(t, k.ex, k.in)
+	}
+}
+
+func BenchmarkLess(b *testing.B) {
+	tests := []numbered{
+		numbered([]string{"abc", "def"}),
+		numbered([]string{"abc", "abc"}),
+		numbered([]string{"def", "abc"}),
+		numbered([]string{"1", "10"}),
+		numbered([]string{"1", "2"}),
+		numbered([]string{"a2", "2"}),
+		numbered([]string{"a2", "a10"}),
+		numbered([]string{"a20", "a2"}),
+		numbered([]string{"abc", "abc20"}),
+		numbered([]string{"a1", "abc"}),
+		numbered([]string{"a20", "abc"}),
+		numbered([]string{"abc20", "abc"}),
+		numbered([]string{"abc20", "def2"}),
+		numbered([]string{"abc20", "abc2"}),
+		numbered([]string{"abc20", "abc20"}),
+		numbered([]string{"abc30", "abc20"}),
+		numbered([]string{"abc20a", "abc20"}),
+		numbered([]string{"abc20", "abc20a"}),
+		numbered([]string{"abc20", "abc2a"}),
+		numbered([]string{"abc20", "abc3a"}),
+		numbered([]string{"abc20", "abc2abc"}),
+	}
+	for i := 0; i < b.N; i++ {
+		for _, t := range tests {
+			t.Less(0, 1)
 		}
 	}
 }