diff options
author | Ian Lance Taylor <ian@gcc.gnu.org> | 2013-07-16 06:54:42 +0000 |
---|---|---|
committer | Ian Lance Taylor <ian@gcc.gnu.org> | 2013-07-16 06:54:42 +0000 |
commit | be47d6eceffd2c5dbbc1566d5eea490527fb2bd4 (patch) | |
tree | 0e8fda573576bb4181dba29d0e88380a8c38fafd /libgo/go/sort | |
parent | efb30cdeb003fd7c585ee0d7657340086abcbd9e (diff) | |
download | gcc-be47d6eceffd2c5dbbc1566d5eea490527fb2bd4.zip gcc-be47d6eceffd2c5dbbc1566d5eea490527fb2bd4.tar.gz gcc-be47d6eceffd2c5dbbc1566d5eea490527fb2bd4.tar.bz2 |
libgo: Update to Go 1.1.1.
From-SVN: r200974
Diffstat (limited to 'libgo/go/sort')
-rw-r--r-- | libgo/go/sort/example_keys_test.go | 96 | ||||
-rw-r--r-- | libgo/go/sort/example_multi_test.go | 132 | ||||
-rw-r--r-- | libgo/go/sort/example_reverse_test.go | 30 | ||||
-rw-r--r-- | libgo/go/sort/example_test.go | 7 | ||||
-rw-r--r-- | libgo/go/sort/search_test.go | 27 | ||||
-rw-r--r-- | libgo/go/sort/sort.go | 66 | ||||
-rw-r--r-- | libgo/go/sort/sort_test.go | 41 |
7 files changed, 338 insertions, 61 deletions
diff --git a/libgo/go/sort/example_keys_test.go b/libgo/go/sort/example_keys_test.go new file mode 100644 index 0000000..a8e47e4 --- /dev/null +++ b/libgo/go/sort/example_keys_test.go @@ -0,0 +1,96 @@ +// Copyright 2013 The Go Authors. All rights reserved. +// Use of this source code is governed by a BSD-style +// license that can be found in the LICENSE file. + +package sort_test + +import ( + "fmt" + "sort" +) + +// A couple of type definitions to make the units clear. +type earthMass float64 +type au float64 + +// A Planet defines the properties of a solar system object. +type Planet struct { + name string + mass earthMass + distance au +} + +// By is the type of a "less" function that defines the ordering of its Planet arguments. +type By func(p1, p2 *Planet) bool + +// Sort is a method on the function type, By, that sorts the argument slice according to the function. +func (by By) Sort(planets []Planet) { + ps := &planetSorter{ + planets: planets, + by: by, // The Sort method's receiver is the function (closure) that defines the sort order. + } + sort.Sort(ps) +} + +// planetSorter joins a By function and a slice of Planets to be sorted. +type planetSorter struct { + planets []Planet + by func(p1, p2 *Planet) bool // Closure used in the Less method. +} + +// Len is part of sort.Interface. +func (s *planetSorter) Len() int { + return len(s.planets) +} + +// Swap is part of sort.Interface. +func (s *planetSorter) Swap(i, j int) { + s.planets[i], s.planets[j] = s.planets[j], s.planets[i] +} + +// Less is part of sort.Interface. It is implemented by calling the "by" closure in the sorter. +func (s *planetSorter) Less(i, j int) bool { + return s.by(&s.planets[i], &s.planets[j]) +} + +var planets = []Planet{ + {"Mercury", 0.055, 0.4}, + {"Venus", 0.815, 0.7}, + {"Earth", 1.0, 1.0}, + {"Mars", 0.107, 1.5}, +} + +// ExampleSortKeys demonstrates a technique for sorting a struct type using programmable sort criteria. +func Example_sortKeys() { + // Closures that order the Planet structure. + name := func(p1, p2 *Planet) bool { + return p1.name < p2.name + } + mass := func(p1, p2 *Planet) bool { + return p1.mass < p2.mass + } + distance := func(p1, p2 *Planet) bool { + return p1.distance < p2.distance + } + decreasingDistance := func(p1, p2 *Planet) bool { + return !distance(p1, p2) + } + + // Sort the planets by the various criteria. + By(name).Sort(planets) + fmt.Println("By name:", planets) + + By(mass).Sort(planets) + fmt.Println("By mass:", planets) + + By(distance).Sort(planets) + fmt.Println("By distance:", planets) + + By(decreasingDistance).Sort(planets) + fmt.Println("By decreasing distance:", planets) + + // Output: By name: [{Earth 1 1} {Mars 0.107 1.5} {Mercury 0.055 0.4} {Venus 0.815 0.7}] + // By mass: [{Mercury 0.055 0.4} {Mars 0.107 1.5} {Venus 0.815 0.7} {Earth 1 1}] + // By distance: [{Mercury 0.055 0.4} {Venus 0.815 0.7} {Earth 1 1} {Mars 0.107 1.5}] + // By decreasing distance: [{Mars 0.107 1.5} {Earth 1 1} {Venus 0.815 0.7} {Mercury 0.055 0.4}] +} diff --git a/libgo/go/sort/example_multi_test.go b/libgo/go/sort/example_multi_test.go new file mode 100644 index 0000000..d0a9e7d --- /dev/null +++ b/libgo/go/sort/example_multi_test.go @@ -0,0 +1,132 @@ +// Copyright 2013 The Go Authors. All rights reserved. +// Use of this source code is governed by a BSD-style +// license that can be found in the LICENSE file. + +package sort_test + +import ( + "fmt" + "sort" +) + +// A Change is a record of source code changes, recording user, language, and delta size. +type Change struct { + user string + language string + lines int +} + +type lessFunc func(p1, p2 *Change) bool + +// multiSorter implements the Sort interface, sorting the changes within. +type multiSorter struct { + changes []Change + less []lessFunc +} + +// Sort sorts the argument slice according to the less functions passed to OrderedBy. +func (ms *multiSorter) Sort(changes []Change) { + sort.Sort(ms) +} + +// OrderedBy returns a Sorter that sorts using the less functions, in order. +// Call its Sort method to sort the data. +func OrderedBy(less ...lessFunc) *multiSorter { + return &multiSorter{ + changes: changes, + less: less, + } +} + +// Len is part of sort.Interface. +func (ms *multiSorter) Len() int { + return len(ms.changes) +} + +// Swap is part of sort.Interface. +func (ms *multiSorter) Swap(i, j int) { + ms.changes[i], ms.changes[j] = ms.changes[j], ms.changes[i] +} + +// Less is part of sort.Interface. It is implemented by looping along the +// less functions until it finds a comparison that is either Less or +// !Less. Note that it can call the less functions twice per call. We +// could change the functions to return -1, 0, 1 and reduce the +// number of calls for greater efficiency: an exercise for the reader. +func (ms *multiSorter) Less(i, j int) bool { + p, q := &ms.changes[i], &ms.changes[j] + // Try all but the last comparison. + var k int + for k = 0; k < len(ms.less)-1; k++ { + less := ms.less[k] + switch { + case less(p, q): + // p < q, so we have a decision. + return true + case less(q, p): + // p > q, so we have a decision. + return false + } + // p == q; try the next comparison. + } + // All comparisons to here said "equal", so just return whatever + // the final comparison reports. + return ms.less[k](p, q) +} + +var changes = []Change{ + {"gri", "Go", 100}, + {"ken", "C", 150}, + {"glenda", "Go", 200}, + {"rsc", "Go", 200}, + {"r", "Go", 100}, + {"ken", "Go", 200}, + {"dmr", "C", 100}, + {"r", "C", 150}, + {"gri", "Smalltalk", 80}, +} + +// ExampleMultiKeys demonstrates a technique for sorting a struct type using different +// sets of multiple fields in the comparison. We chain together "Less" functions, each of +// which compares a single field. +func Example_sortMultiKeys() { + // Closures that order the Change structure. + user := func(c1, c2 *Change) bool { + return c1.user < c2.user + } + language := func(c1, c2 *Change) bool { + return c1.language < c2.language + } + increasingLines := func(c1, c2 *Change) bool { + return c1.lines < c2.lines + } + decreasingLines := func(c1, c2 *Change) bool { + return c1.lines > c2.lines // Note: > orders downwards. + } + + // Simple use: Sort by user. + OrderedBy(user).Sort(changes) + fmt.Println("By user:", changes) + + // multiSorter implements the Sort interface, so we can also do this. + sort.Sort(OrderedBy(user, increasingLines)) + fmt.Println("By user,<lines:", changes) + + // More examples. + OrderedBy(user, decreasingLines).Sort(changes) + fmt.Println("By user,>lines:", changes) + + OrderedBy(language, increasingLines).Sort(changes) + fmt.Println("By language,<lines:", changes) + + OrderedBy(language, increasingLines, user).Sort(changes) + fmt.Println("By language,<lines,user:", changes) + + // Output: + //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}] + //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}] + //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}] + //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}] + //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}] + +} diff --git a/libgo/go/sort/example_reverse_test.go b/libgo/go/sort/example_reverse_test.go deleted file mode 100644 index 7c7f05b..0000000 --- a/libgo/go/sort/example_reverse_test.go +++ /dev/null @@ -1,30 +0,0 @@ -// Copyright 2011 The Go Authors. All rights reserved. -// Use of this source code is governed by a BSD-style -// license that can be found in the LICENSE file. - -package sort_test - -import ( - "fmt" - "sort" -) - -// Reverse embeds a sort.Interface value and implements a reverse sort over -// that value. -type Reverse struct { - // This embedded Interface permits Reverse to use the methods of - // another Interface implementation. - sort.Interface -} - -// Less returns the opposite of the embedded implementation's Less method. -func (r Reverse) Less(i, j int) bool { - return r.Interface.Less(j, i) -} - -func ExampleInterface_reverse() { - s := []int{5, 2, 6, 3, 1, 4} // unsorted - sort.Sort(Reverse{sort.IntSlice(s)}) - fmt.Println(s) - // Output: [6 5 4 3 2 1] -} diff --git a/libgo/go/sort/example_test.go b/libgo/go/sort/example_test.go index f57d025..f7372be 100644 --- a/libgo/go/sort/example_test.go +++ b/libgo/go/sort/example_test.go @@ -15,3 +15,10 @@ func ExampleInts() { fmt.Println(s) // Output: [1 2 3 4 5 6] } + +func ExampleReverse() { + s := []int{5, 2, 6, 3, 1, 4} // unsorted + sort.Sort(sort.Reverse(sort.IntSlice(s))) + fmt.Println(s) + // Output: [6 5 4 3 2 1] +} diff --git a/libgo/go/sort/search_test.go b/libgo/go/sort/search_test.go index 07295ff..80b9abd 100644 --- a/libgo/go/sort/search_test.go +++ b/libgo/go/sort/search_test.go @@ -5,6 +5,7 @@ package sort_test import ( + "runtime" . "sort" "testing" ) @@ -117,6 +118,32 @@ func TestSearchWrappers(t *testing.T) { } } +func runSearchWrappers() { + SearchInts(data, 11) + SearchFloat64s(fdata, 2.1) + SearchStrings(sdata, "") + IntSlice(data).Search(0) + Float64Slice(fdata).Search(2.0) + StringSlice(sdata).Search("x") +} + +func TestSearchWrappersDontAlloc(t *testing.T) { + if runtime.GOMAXPROCS(0) > 1 { + t.Skip("skipping; GOMAXPROCS>1") + } + t.Skip("skipping alloc test for gccgo") + allocs := testing.AllocsPerRun(100, runSearchWrappers) + if allocs != 0 { + t.Errorf("expected no allocs for runSearchWrappers, got %v", allocs) + } +} + +func BenchmarkSearchWrappers(b *testing.B) { + for i := 0; i < b.N; i++ { + runSearchWrappers() + } +} + // Abstract exhaustive test: all sizes up to 100, // all possible return values. If there are any small // corner cases, this test exercises them. diff --git a/libgo/go/sort/sort.go b/libgo/go/sort/sort.go index 62a4d55..d3092e8 100644 --- a/libgo/go/sort/sort.go +++ b/libgo/go/sort/sort.go @@ -6,8 +6,6 @@ // collections. package sort -import "math" - // A type, typically a collection, that satisfies sort.Interface can be // sorted by the routines in this package. The methods require that the // elements of the collection be enumerated by an integer index. @@ -124,26 +122,31 @@ func doPivot(data Interface, lo, hi int) (midlo, midhi int) { // into the middle of the slice. pivot := lo a, b, c, d := lo+1, lo+1, hi, hi - for b < c { - if data.Less(b, pivot) { // data[b] < pivot - b++ - continue - } - if !data.Less(pivot, b) { // data[b] = pivot - data.Swap(a, b) - a++ - b++ - continue + for { + for b < c { + if data.Less(b, pivot) { // data[b] < pivot + b++ + } else if !data.Less(pivot, b) { // data[b] = pivot + data.Swap(a, b) + a++ + b++ + } else { + break + } } - if data.Less(pivot, c-1) { // data[c-1] > pivot - c-- - continue + for b < c { + if data.Less(pivot, c-1) { // data[c-1] > pivot + c-- + } else if !data.Less(c-1, pivot) { // data[c-1] = pivot + data.Swap(c-1, d-1) + c-- + d-- + } else { + break + } } - if !data.Less(c-1, pivot) { // data[c-1] = pivot - data.Swap(c-1, d-1) - c-- - d-- - continue + if b >= c { + break } // data[b] > pivot; data[c-1] < pivot data.Swap(b, c-1) @@ -197,6 +200,22 @@ func Sort(data Interface) { quickSort(data, 0, n, maxDepth) } +type reverse struct { + // This embedded Interface permits Reverse to use the methods of + // another Interface implementation. + Interface +} + +// Less returns the opposite of the embedded implementation's Less method. +func (r reverse) Less(i, j int) bool { + return r.Interface.Less(j, i) +} + +// Reverse returns the reverse order for data. +func Reverse(data Interface) Interface { + return &reverse{data} +} + // IsSorted reports whether data is sorted. func IsSorted(data Interface) bool { n := data.Len() @@ -224,9 +243,14 @@ func (p IntSlice) Sort() { Sort(p) } type Float64Slice []float64 func (p Float64Slice) Len() int { return len(p) } -func (p Float64Slice) Less(i, j int) bool { return p[i] < p[j] || math.IsNaN(p[i]) && !math.IsNaN(p[j]) } +func (p Float64Slice) Less(i, j int) bool { return p[i] < p[j] || isNaN(p[i]) && !isNaN(p[j]) } func (p Float64Slice) Swap(i, j int) { p[i], p[j] = p[j], p[i] } +// isNaN is a copy of math.IsNaN to avoid a dependency on the math package. +func isNaN(f float64) bool { + return f != f +} + // Sort is a convenience method. func (p Float64Slice) Sort() { Sort(p) } diff --git a/libgo/go/sort/sort_test.go b/libgo/go/sort/sort_test.go index ee8a9d0..5daf848 100644 --- a/libgo/go/sort/sort_test.go +++ b/libgo/go/sort/sort_test.go @@ -92,6 +92,23 @@ func TestSortLarge_Random(t *testing.T) { } } +func TestReverseSortIntSlice(t *testing.T) { + data := ints + data1 := ints + a := IntSlice(data[0:]) + Sort(a) + r := IntSlice(data1[0:]) + Sort(Reverse(r)) + for i := 0; i < len(data); i++ { + if a[i] != r[len(data)-1-i] { + t.Errorf("reverse sort didn't sort") + } + if i > len(data)/2 { + break + } + } +} + func BenchmarkSortString1K(b *testing.B) { b.StopTimer() for i := 0; i < b.N; i++ { @@ -151,15 +168,18 @@ const ( ) type testingData struct { - desc string - t *testing.T - data []int - maxswap int // number of swaps allowed - nswap int + desc string + t *testing.T + data []int + maxswap int // number of swaps allowed + ncmp, nswap int } -func (d *testingData) Len() int { return len(d.data) } -func (d *testingData) Less(i, j int) bool { return d.data[i] < d.data[j] } +func (d *testingData) Len() int { return len(d.data) } +func (d *testingData) Less(i, j int) bool { + d.ncmp++ + return d.data[i] < d.data[j] +} func (d *testingData) Swap(i, j int) { if d.nswap >= d.maxswap { d.t.Errorf("%s: used %d swaps sorting slice of %d", d.desc, d.nswap, len(d.data)) @@ -192,8 +212,7 @@ func testBentleyMcIlroy(t *testing.T, sort func(Interface)) { dists := []string{"sawtooth", "rand", "stagger", "plateau", "shuffle"} modes := []string{"copy", "reverse", "reverse1", "reverse2", "sort", "dither"} var tmp1, tmp2 [1025]int - for ni := 0; ni < len(sizes); ni++ { - n := sizes[ni] + for _, n := range sizes { for m := 1; m < 2*n; m *= 2 { for dist := 0; dist < _NDist; dist++ { j := 0 @@ -259,8 +278,10 @@ func testBentleyMcIlroy(t *testing.T, sort func(Interface)) { } desc := fmt.Sprintf("n=%d m=%d dist=%s mode=%s", n, m, dists[dist], modes[mode]) - d := &testingData{desc, t, mdata[0:n], n * lg(n) * 12 / 10, 0} + d := &testingData{desc: desc, t: t, data: mdata[0:n], maxswap: n * lg(n) * 12 / 10} sort(d) + // Uncomment if you are trying to improve the number of compares/swaps. + //t.Logf("%s: ncmp=%d, nswp=%d", desc, d.ncmp, d.nswap) // If we were testing C qsort, we'd have to make a copy // of the slice and sort it ourselves and then compare |