1 // Copyright 2013 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 file. 4 5 package sort_test 6 7 import ( 8 "fmt" 9 "sort" 10 ) 11 12 // A Change is a record of source code changes, recording user, language, and delta size. 13 type Change struct { 14 user string 15 language string 16 lines int 17 } 18 19 type lessFunc func(p1, p2 *Change) bool 20 21 // multiSorter implements the Sort interface, sorting the changes within. 22 type multiSorter struct { 23 changes []Change 24 less []lessFunc 25 } 26 27 // Sort sorts the argument slice according to the less functions passed to OrderedBy. 28 func (ms *multiSorter) Sort(changes []Change) { 29 ms.changes = changes 30 sort.Sort(ms) 31 } 32 33 // OrderedBy returns a Sorter that sorts using the less functions, in order. 34 // Call its Sort method to sort the data. 35 func OrderedBy(less ...lessFunc) *multiSorter { 36 return &multiSorter{ 37 less: less, 38 } 39 } 40 41 // Len is part of sort.Interface. 42 func (ms *multiSorter) Len() int { 43 return len(ms.changes) 44 } 45 46 // Swap is part of sort.Interface. 47 func (ms *multiSorter) Swap(i, j int) { 48 ms.changes[i], ms.changes[j] = ms.changes[j], ms.changes[i] 49 } 50 51 // Less is part of sort.Interface. It is implemented by looping along the 52 // less functions until it finds a comparison that discriminates between 53 // the two items (one is less than the other). Note that it can call the 54 // less functions twice per call. We could change the functions to return 55 // -1, 0, 1 and reduce the number of calls for greater efficiency: an 56 // exercise for the reader. 57 func (ms *multiSorter) Less(i, j int) bool { 58 p, q := &ms.changes[i], &ms.changes[j] 59 // Try all but the last comparison. 60 var k int 61 for k = 0; k < len(ms.less)-1; k++ { 62 less := ms.less[k] 63 switch { 64 case less(p, q): 65 // p < q, so we have a decision. 66 return true 67 case less(q, p): 68 // p > q, so we have a decision. 69 return false 70 } 71 // p == q; try the next comparison. 72 } 73 // All comparisons to here said "equal", so just return whatever 74 // the final comparison reports. 75 return ms.less[k](p, q) 76 } 77 78 var changes = []Change{ 79 {"gri", "Go", 100}, 80 {"ken", "C", 150}, 81 {"glenda", "Go", 200}, 82 {"rsc", "Go", 200}, 83 {"r", "Go", 100}, 84 {"ken", "Go", 200}, 85 {"dmr", "C", 100}, 86 {"r", "C", 150}, 87 {"gri", "Smalltalk", 80}, 88 } 89 90 // ExampleMultiKeys demonstrates a technique for sorting a struct type using different 91 // sets of multiple fields in the comparison. We chain together "Less" functions, each of 92 // which compares a single field. 93 func Example_sortMultiKeys() { 94 // Closures that order the Change structure. 95 user := func(c1, c2 *Change) bool { 96 return c1.user < c2.user 97 } 98 language := func(c1, c2 *Change) bool { 99 return c1.language < c2.language 100 } 101 increasingLines := func(c1, c2 *Change) bool { 102 return c1.lines < c2.lines 103 } 104 decreasingLines := func(c1, c2 *Change) bool { 105 return c1.lines > c2.lines // Note: > orders downwards. 106 } 107 108 // Simple use: Sort by user. 109 OrderedBy(user).Sort(changes) 110 fmt.Println("By user:", changes) 111 112 // More examples. 113 OrderedBy(user, increasingLines).Sort(changes) 114 fmt.Println("By user,<lines:", changes) 115 116 OrderedBy(user, decreasingLines).Sort(changes) 117 fmt.Println("By user,>lines:", changes) 118 119 OrderedBy(language, increasingLines).Sort(changes) 120 fmt.Println("By language,<lines:", changes) 121 122 OrderedBy(language, increasingLines, user).Sort(changes) 123 fmt.Println("By language,<lines,user:", changes) 124 125 // Output: 126 // By user: [{dmr C 100} {glenda Go 200} {gri Go 100} {gri Smalltalk 80} {ken C 150} {ken Go 200} {r Go 100} {r C 150} {rsc Go 200}] 127 // By user,<lines: [{dmr C 100} {glenda Go 200} {gri Smalltalk 80} {gri Go 100} {ken C 150} {ken Go 200} {r Go 100} {r C 150} {rsc Go 200}] 128 // By user,>lines: [{dmr C 100} {glenda Go 200} {gri Go 100} {gri Smalltalk 80} {ken Go 200} {ken C 150} {r C 150} {r Go 100} {rsc Go 200}] 129 // By language,<lines: [{dmr C 100} {ken C 150} {r C 150} {r Go 100} {gri Go 100} {ken Go 200} {glenda Go 200} {rsc Go 200} {gri Smalltalk 80}] 130 // By language,<lines,user: [{dmr C 100} {ken C 150} {r C 150} {gri Go 100} {r Go 100} {glenda Go 200} {ken Go 200} {rsc Go 200} {gri Smalltalk 80}] 131 132 } 133
