aboutsummaryrefslogtreecommitdiff
path: root/libgo/go/sort
diff options
context:
space:
mode:
authorIan Lance Taylor <ian@gcc.gnu.org>2013-07-16 06:54:42 +0000
committerIan Lance Taylor <ian@gcc.gnu.org>2013-07-16 06:54:42 +0000
commitbe47d6eceffd2c5dbbc1566d5eea490527fb2bd4 (patch)
tree0e8fda573576bb4181dba29d0e88380a8c38fafd /libgo/go/sort
parentefb30cdeb003fd7c585ee0d7657340086abcbd9e (diff)
downloadgcc-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.go96
-rw-r--r--libgo/go/sort/example_multi_test.go132
-rw-r--r--libgo/go/sort/example_reverse_test.go30
-rw-r--r--libgo/go/sort/example_test.go7
-rw-r--r--libgo/go/sort/search_test.go27
-rw-r--r--libgo/go/sort/sort.go66
-rw-r--r--libgo/go/sort/sort_test.go41
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