libgo/go/sort/example_multi_test.go

   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         sort.Sort(ms)
  30 }
  31
  32 // OrderedBy returns a Sorter that sorts using the less functions, in order.
  33 // Call its Sort method to sort the data.
  34 func OrderedBy(less ...lessFunc) *multiSorter {
  35         return &multiSorter{
  36                 changes: changes,
  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         // multiSorter implements the Sort interface, so we can also do this.
 112         sort.Sort(OrderedBy(user, increasingLines))
 113         fmt.Println("By user,<lines:", changes)
 114
 115         // More examples.
 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 Smalltalk 80} {gri Go 100} {ken Go 200} {ken C 150} {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} {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 }