...

Source file src/sort/example_multi_test.go

Documentation: 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 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} {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  

View as plain text