]>
Commit | Line | Data |
---|---|---|
107c1cdb ND |
1 | // Copyright 2017, The Go Authors. All rights reserved. |
2 | // Use of this source code is governed by a BSD-style | |
3 | // license that can be found in the LICENSE.md file. | |
4 | ||
5 | package value | |
6 | ||
7 | import ( | |
8 | "fmt" | |
9 | "math" | |
10 | "reflect" | |
11 | "sort" | |
12 | ) | |
13 | ||
14 | // SortKeys sorts a list of map keys, deduplicating keys if necessary. | |
15 | // The type of each value must be comparable. | |
16 | func SortKeys(vs []reflect.Value) []reflect.Value { | |
17 | if len(vs) == 0 { | |
18 | return vs | |
19 | } | |
20 | ||
21 | // Sort the map keys. | |
22 | sort.Sort(valueSorter(vs)) | |
23 | ||
24 | // Deduplicate keys (fails for NaNs). | |
25 | vs2 := vs[:1] | |
26 | for _, v := range vs[1:] { | |
27 | if isLess(vs2[len(vs2)-1], v) { | |
28 | vs2 = append(vs2, v) | |
29 | } | |
30 | } | |
31 | return vs2 | |
32 | } | |
33 | ||
34 | // TODO: Use sort.Slice once Google AppEngine is on Go1.8 or above. | |
35 | type valueSorter []reflect.Value | |
36 | ||
37 | func (vs valueSorter) Len() int { return len(vs) } | |
38 | func (vs valueSorter) Less(i, j int) bool { return isLess(vs[i], vs[j]) } | |
39 | func (vs valueSorter) Swap(i, j int) { vs[i], vs[j] = vs[j], vs[i] } | |
40 | ||
41 | // isLess is a generic function for sorting arbitrary map keys. | |
42 | // The inputs must be of the same type and must be comparable. | |
43 | func isLess(x, y reflect.Value) bool { | |
44 | switch x.Type().Kind() { | |
45 | case reflect.Bool: | |
46 | return !x.Bool() && y.Bool() | |
47 | case reflect.Int, reflect.Int8, reflect.Int16, reflect.Int32, reflect.Int64: | |
48 | return x.Int() < y.Int() | |
49 | case reflect.Uint, reflect.Uint8, reflect.Uint16, reflect.Uint32, reflect.Uint64, reflect.Uintptr: | |
50 | return x.Uint() < y.Uint() | |
51 | case reflect.Float32, reflect.Float64: | |
52 | fx, fy := x.Float(), y.Float() | |
53 | return fx < fy || math.IsNaN(fx) && !math.IsNaN(fy) | |
54 | case reflect.Complex64, reflect.Complex128: | |
55 | cx, cy := x.Complex(), y.Complex() | |
56 | rx, ix, ry, iy := real(cx), imag(cx), real(cy), imag(cy) | |
57 | if rx == ry || (math.IsNaN(rx) && math.IsNaN(ry)) { | |
58 | return ix < iy || math.IsNaN(ix) && !math.IsNaN(iy) | |
59 | } | |
60 | return rx < ry || math.IsNaN(rx) && !math.IsNaN(ry) | |
61 | case reflect.Ptr, reflect.UnsafePointer, reflect.Chan: | |
62 | return x.Pointer() < y.Pointer() | |
63 | case reflect.String: | |
64 | return x.String() < y.String() | |
65 | case reflect.Array: | |
66 | for i := 0; i < x.Len(); i++ { | |
67 | if isLess(x.Index(i), y.Index(i)) { | |
68 | return true | |
69 | } | |
70 | if isLess(y.Index(i), x.Index(i)) { | |
71 | return false | |
72 | } | |
73 | } | |
74 | return false | |
75 | case reflect.Struct: | |
76 | for i := 0; i < x.NumField(); i++ { | |
77 | if isLess(x.Field(i), y.Field(i)) { | |
78 | return true | |
79 | } | |
80 | if isLess(y.Field(i), x.Field(i)) { | |
81 | return false | |
82 | } | |
83 | } | |
84 | return false | |
85 | case reflect.Interface: | |
86 | vx, vy := x.Elem(), y.Elem() | |
87 | if !vx.IsValid() || !vy.IsValid() { | |
88 | return !vx.IsValid() && vy.IsValid() | |
89 | } | |
90 | tx, ty := vx.Type(), vy.Type() | |
91 | if tx == ty { | |
92 | return isLess(x.Elem(), y.Elem()) | |
93 | } | |
94 | if tx.Kind() != ty.Kind() { | |
95 | return vx.Kind() < vy.Kind() | |
96 | } | |
97 | if tx.String() != ty.String() { | |
98 | return tx.String() < ty.String() | |
99 | } | |
100 | if tx.PkgPath() != ty.PkgPath() { | |
101 | return tx.PkgPath() < ty.PkgPath() | |
102 | } | |
103 | // This can happen in rare situations, so we fallback to just comparing | |
104 | // the unique pointer for a reflect.Type. This guarantees deterministic | |
105 | // ordering within a program, but it is obviously not stable. | |
106 | return reflect.ValueOf(vx.Type()).Pointer() < reflect.ValueOf(vy.Type()).Pointer() | |
107 | default: | |
108 | // Must be Func, Map, or Slice; which are not comparable. | |
109 | panic(fmt.Sprintf("%T is not comparable", x.Type())) | |
110 | } | |
111 | } |