New function coll.Sort, expanding on strings.Sort

Signed-off-by: Dave Henderson <dhenderson@gmail.com>

2 files changed, 258 insertions, 0 deletions

diff --git a/coll/coll.go b/coll/coll.go
index 40d2e9d5..9fff2396 100644
--- a/coll/coll.go
+++ b/coll/coll.go
@@ -176,3 +176,82 @@ func Merge(dst map[string]interface{}, srcs ...map[string]interface{}) (map[stri
 	}
 	return dst, nil
 }
+
+// Sort a given array or slice. Uses natural sort order if possible. If a
+// non-empty key is given and the list elements are maps, this will attempt to
+// sort by the values of those entries.
+//
+// Does not modify the input list.
+func Sort(key string, list interface{}) (out []interface{}, err error) {
+	if list == nil {
+		return nil, nil
+	}
+
+	ia, err := interfaceSlice(list)
+	if err != nil {
+		return nil, err
+	}
+	// if the types are all the same, we can sort the slice
+	if sameTypes(ia) {
+		s := make([]interface{}, len(ia))
+		// make a copy so the original is unmodified
+		copy(s, ia)
+		sort.SliceStable(s, func(i, j int) bool {
+			return lessThan(key)(s[i], s[j])
+		})
+		return s, nil
+	}
+	return ia, nil
+}
+
+// lessThan - compare two values of the same type
+func lessThan(key string) func(left, right interface{}) bool {
+	return func(left, right interface{}) bool {
+		val := reflect.Indirect(reflect.ValueOf(left))
+		rval := reflect.Indirect(reflect.ValueOf(right))
+		switch val.Kind() {
+		case reflect.Int8, reflect.Int16, reflect.Int32, reflect.Int64, reflect.Int:
+			return val.Int() < rval.Int()
+		case reflect.Uint8, reflect.Uint16, reflect.Uint32, reflect.Uint, reflect.Uint64:
+			return val.Uint() < rval.Uint()
+		case reflect.Float32, reflect.Float64:
+			return val.Float() < rval.Float()
+		case reflect.String:
+			return val.String() < rval.String()
+		case reflect.MapOf(
+			reflect.TypeOf(reflect.String),
+			reflect.TypeOf(reflect.Interface),
+		).Kind():
+			kval := reflect.ValueOf(key)
+			if !val.MapIndex(kval).IsValid() {
+				return false
+			}
+			newleft := val.MapIndex(kval).Interface()
+			newright := rval.MapIndex(kval).Interface()
+			return lessThan("")(newleft, newright)
+		case reflect.Struct:
+			if !val.FieldByName(key).IsValid() {
+				return false
+			}
+			newleft := val.FieldByName(key).Interface()
+			newright := rval.FieldByName(key).Interface()
+			return lessThan("")(newleft, newright)
+		default:
+			// it's not really comparable, so...
+			return false
+		}
+	}
+}
+
+func sameTypes(a []interface{}) bool {
+	var t reflect.Type
+	for _, v := range a {
+		if t == nil {
+			t = reflect.TypeOf(v)
+		}
+		if reflect.ValueOf(v).Kind() != t.Kind() {
+			return false
+		}
+	}
+	return true
+}
diff --git a/coll/coll_test.go b/coll/coll_test.go
index db6d4d51..6313c420 100644
--- a/coll/coll_test.go
+++ b/coll/coll_test.go
@@ -1,6 +1,7 @@
 package coll
 
 import (
+	"fmt"
 	"testing"
 
 	"github.com/stretchr/testify/assert"
@@ -228,3 +229,181 @@ func TestMerge(t *testing.T) {
 	assert.NoError(t, err)
 	assert.EqualValues(t, expected, out)
 }
+
+type coords struct {
+	X, Y int
+}
+
+func TestSameTypes(t *testing.T) {
+	data := []struct {
+		in  []interface{}
+		out bool
+	}{
+		{[]interface{}{}, true},
+		{[]interface{}{"a", "b"}, true},
+		{[]interface{}{1.0, 3.14}, true},
+		{[]interface{}{1, 3}, true},
+		{[]interface{}{true, false}, true},
+		{[]interface{}{1, 3.0}, false},
+		{[]interface{}{"a", nil}, false},
+		{[]interface{}{"a", true}, false},
+		{[]interface{}{coords{2, 3}, coords{3, 4}}, true},
+		{[]interface{}{coords{2, 3}, &coords{3, 4}}, false},
+	}
+
+	for _, d := range data {
+		assert.Equal(t, d.out, sameTypes(d.in))
+	}
+}
+
+func TestLessThan(t *testing.T) {
+	data := []struct {
+		key         string
+		left, right interface{}
+		out         bool
+	}{
+		{"", nil, nil, false},
+		{"", "a", "b", true},
+		{"", "a", "a", false},
+		{"", "b", "a", false},
+		{"", 1.00, 3.14, true},
+		{"", 'a', 'A', false},
+		{"", 'a', 'b', true},
+		{"", uint(0xff), uint(0x32), false},
+		{"", 1, 3, true},
+		{"", true, false, false},
+		{"", map[string]interface{}{"foo": 1}, map[string]interface{}{"foo": 2}, false},
+		{"foo", map[string]interface{}{"foo": 1}, map[string]interface{}{"foo": 2}, true},
+		{"bar", map[string]interface{}{"foo": 1}, map[string]interface{}{"foo": 2}, false},
+		{"X", coords{}, coords{-1, 2}, false},
+		{"Y", &coords{1, 1}, &coords{-1, 2}, true},
+		{"", &coords{1, 1}, &coords{-1, 2}, false},
+		{"foo", &coords{1, 1}, &coords{-1, 2}, false},
+	}
+
+	for _, d := range data {
+		t.Run(fmt.Sprintf(`LessThan("%s")(<%T>%#v,%#v)==%v`, d.key, d.left, d.left, d.right, d.out), func(t *testing.T) {
+			assert.Equal(t, d.out, lessThan(d.key)(d.left, d.right))
+		})
+	}
+}
+
+func TestSort(t *testing.T) {
+	out, err := Sort("", 42)
+	assert.Error(t, err)
+	assert.Nil(t, out)
+
+	data := []struct {
+		key string
+		in  interface{}
+		out []interface{}
+	}{
+		{
+			key: "",
+			in:  []string{"b", "c", "a", "d"},
+			out: []interface{}{"a", "b", "c", "d"},
+		},
+		{
+			key: "",
+			in:  []interface{}{"b", "c", "a", "d"},
+			out: []interface{}{"a", "b", "c", "d"},
+		},
+		{
+			key: "",
+			in:  []interface{}{"c", "a", "b", 3, 1, 2},
+			out: []interface{}{"c", "a", "b", 3, 1, 2},
+		},
+		{
+			key: "",
+			in:  nil,
+			out: nil,
+		},
+
+		{
+			key: "",
+			in: []map[string]interface{}{
+				{"name": "Bart", "age": 12},
+				{"age": 1, "name": "Maggie"},
+				{"name": "Lisa", "age": 6},
+			},
+			out: []interface{}{
+				map[string]interface{}{"name": "Bart", "age": 12},
+				map[string]interface{}{"age": 1, "name": "Maggie"},
+				map[string]interface{}{"name": "Lisa", "age": 6},
+			},
+		},
+		{
+			key: "name",
+			in: []map[string]interface{}{
+				{"name": "Bart", "age": 12},
+				{"age": 1, "name": "Maggie"},
+				{"name": "Lisa", "age": 6},
+			},
+			out: []interface{}{
+				map[string]interface{}{"name": "Bart", "age": 12},
+				map[string]interface{}{"name": "Lisa", "age": 6},
+				map[string]interface{}{"age": 1, "name": "Maggie"},
+			},
+		},
+		{
+			key: "age",
+			in: []map[string]interface{}{
+				{"name": "Bart", "age": 12},
+				{"age": 1, "name": "Maggie"},
+				{"name": "Lisa", "age": 6},
+			},
+			out: []interface{}{
+				map[string]interface{}{"age": 1, "name": "Maggie"},
+				map[string]interface{}{"name": "Lisa", "age": 6},
+				map[string]interface{}{"name": "Bart", "age": 12},
+			},
+		},
+		{
+			key: "y",
+			in: []map[string]int{
+				{"x": 54, "y": 6},
+				{"x": 13, "y": -8},
+				{"x": 1, "y": 0},
+			},
+			out: []interface{}{
+				map[string]int{"x": 13, "y": -8},
+				map[string]int{"x": 1, "y": 0},
+				map[string]int{"x": 54, "y": 6},
+			},
+		},
+		{
+			key: "X",
+			in: []coords{
+				{2, 4},
+				{3, 3},
+				{1, 5},
+			},
+			out: []interface{}{
+				coords{1, 5},
+				coords{2, 4},
+				coords{3, 3},
+			},
+		},
+		{
+			key: "X",
+			in: []*coords{
+				{2, 4},
+				{3, 3},
+				{1, 5},
+			},
+			out: []interface{}{
+				&coords{1, 5},
+				&coords{2, 4},
+				&coords{3, 3},
+			},
+		},
+	}
+
+	for _, d := range data {
+		t.Run(fmt.Sprintf(`Sort("%s",<%T>)==%#v`, d.key, d.in, d.out), func(t *testing.T) {
+			out, err := Sort(d.key, d.in)
+			assert.NoError(t, err)
+			assert.EqualValues(t, d.out, out)
+		})
+	}
+}