Home | History | Annotate | Download | only in sort 
      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 is either Less or
     53 // !Less. Note that it can call the less functions twice per call. We
     54 // could change the functions to return -1, 0, 1 and reduce the
     55 // number of calls for greater efficiency: an exercise for the reader.
     56 func (ms *multiSorter) Less(i, j int) bool {
     57 	p, q := &ms.changes[i], &ms.changes[j]
     58 	// Try all but the last comparison.
     59 	var k int
     60 	for k = 0; k < len(ms.less)-1; k++ {
     61 		less := ms.less[k]
     62 		switch {
     63 		case less(p, q):
     64 			// p < q, so we have a decision.
     65 			return true
     66 		case less(q, p):
     67 			// p > q, so we have a decision.
     68 			return false
     69 		}
     70 		// p == q; try the next comparison.
     71 	}
     72 	// All comparisons to here said "equal", so just return whatever
     73 	// the final comparison reports.
     74 	return ms.less[k](p, q)
     75 }
     76 
     77 var changes = []Change{
     78 	{"gri", "Go", 100},
     79 	{"ken", "C", 150},
     80 	{"glenda", "Go", 200},
     81 	{"rsc", "Go", 200},
     82 	{"r", "Go", 100},
     83 	{"ken", "Go", 200},
     84 	{"dmr", "C", 100},
     85 	{"r", "C", 150},
     86 	{"gri", "Smalltalk", 80},
     87 }
     88 
     89 // ExampleMultiKeys demonstrates a technique for sorting a struct type using different
     90 // sets of multiple fields in the comparison. We chain together "Less" functions, each of
     91 // which compares a single field.
     92 func Example_sortMultiKeys() {
     93 	// Closures that order the Change structure.
     94 	user := func(c1, c2 *Change) bool {
     95 		return c1.user < c2.user
     96 	}
     97 	language := func(c1, c2 *Change) bool {
     98 		return c1.language < c2.language
     99 	}
    100 	increasingLines := func(c1, c2 *Change) bool {
    101 		return c1.lines < c2.lines
    102 	}
    103 	decreasingLines := func(c1, c2 *Change) bool {
    104 		return c1.lines > c2.lines // Note: > orders downwards.
    105 	}
    106 
    107 	// Simple use: Sort by user.
    108 	OrderedBy(user).Sort(changes)
    109 	fmt.Println("By user:", changes)
    110 
    111 	// More examples.
    112 	OrderedBy(user, increasingLines).Sort(changes)
    113 	fmt.Println("By user,<lines:", changes)
    114 
    115 	OrderedBy(user, decreasingLines).Sort(changes)
    116 	fmt.Println("By user,>lines:", changes)
    117 
    118 	OrderedBy(language, increasingLines).Sort(changes)
    119 	fmt.Println("By language,<lines:", changes)
    120 
    121 	OrderedBy(language, increasingLines, user).Sort(changes)
    122 	fmt.Println("By language,<lines,user:", changes)
    123 
    124 	// Output:
    125 	// By user: [{dmr C 100} {glenda Go 200} {gri Smalltalk 80} {gri Go 100} {ken Go 200} {ken C 150} {r Go 100} {r C 150} {rsc Go 200}]
    126 	// 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}]
    127 	// 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}]
    128 	// By language,<lines: [{dmr C 100} {ken C 150} {r C 150} {gri Go 100} {r Go 100} {ken Go 200} {glenda Go 200} {rsc Go 200} {gri Smalltalk 80}]
    129 	// 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}]
    130 
    131 }
    132