• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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
5package sort_test
6
7import (
8	"fmt"
9	"sort"
10)
11
12// A Change is a record of source code changes, recording user, language, and delta size.
13type Change struct {
14	user     string
15	language string
16	lines    int
17}
18
19type lessFunc func(p1, p2 *Change) bool
20
21// multiSorter implements the Sort interface, sorting the changes within.
22type multiSorter struct {
23	changes []Change
24	less    []lessFunc
25}
26
27// Sort sorts the argument slice according to the less functions passed to OrderedBy.
28func (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.
35func OrderedBy(less ...lessFunc) *multiSorter {
36	return &multiSorter{
37		less: less,
38	}
39}
40
41// Len is part of sort.Interface.
42func (ms *multiSorter) Len() int {
43	return len(ms.changes)
44}
45
46// Swap is part of sort.Interface.
47func (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.
57func (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
78var 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.
93func 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} {gri Go 100} {r Go 100} {glenda Go 200} {ken 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