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         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 }