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} {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  }
	 133
View as plain text