Imported Upstream version 1.1~hg20130304upstream/1.1_hg20130304

7 files changed, 210 insertions, 65 deletions

diff --git a/src/pkg/sort/example_keys_test.go b/src/pkg/sort/example_keys_test.go
new file mode 100644
index 000000000..a8e47e492
--- /dev/null
+++ b/src/pkg/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/src/pkg/sort/example_reverse_test.go b/src/pkg/sort/example_reverse_test.go
deleted file mode 100644
index 7c7f05bf3..000000000
--- a/src/pkg/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/src/pkg/sort/example_test.go b/src/pkg/sort/example_test.go
index f57d02546..f7372bec3 100644
--- a/src/pkg/sort/example_test.go
+++ b/src/pkg/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/src/pkg/sort/search.go b/src/pkg/sort/search.go
index 4f0ce55c3..8a2c1c33b 100644
--- a/src/pkg/sort/search.go
+++ b/src/pkg/sort/search.go
@@ -7,11 +7,13 @@
 package sort
 
 // Search uses binary search to find and return the smallest index i
-// in [0, n) at which f(i) is true, assuming that on the range [0, n), 
+// in [0, n) at which f(i) is true, assuming that on the range [0, n),
 // f(i) == true implies f(i+1) == true.  That is, Search requires that
 // f is false for some (possibly empty) prefix of the input range [0, n)
 // and then true for the (possibly empty) remainder; Search returns
 // the first true index.  If there is no such index, Search returns n.
+// (Note that the "not found" return value is not -1 as in, for instance,
+// strings.Index).
 // Search calls f(i) only for i in the range [0, n).
 //
 // A common use of Search is to find the index i for a value x in
@@ -74,22 +76,28 @@ func Search(n int, f func(int) bool) int {
 // Convenience wrappers for common cases.
 
 // SearchInts searches for x in a sorted slice of ints and returns the index
-// as specified by Search. The slice must be sorted in ascending order.
+// as specified by Search. The return value is the index to insert x if x is
+// not present (it could be len(a)).
+// The slice must be sorted in ascending order.
 //
 func SearchInts(a []int, x int) int {
 	return Search(len(a), func(i int) bool { return a[i] >= x })
 }
 
 // SearchFloat64s searches for x in a sorted slice of float64s and returns the index
-// as specified by Search. The slice must be sorted in ascending order.
-// 
+// as specified by Search.  The return value is the index to insert x if x is not
+// present (it could be len(a)).
+// The slice must be sorted in ascending order.
+//
 func SearchFloat64s(a []float64, x float64) int {
 	return Search(len(a), func(i int) bool { return a[i] >= x })
 }
 
-// SearchStrings searches for x slice a sorted slice of strings and returns the index
-// as specified by Search. The slice must be sorted in ascending order.
-// 
+// SearchStrings searches for x in a sorted slice of strings and returns the index
+// as specified by Search.  The return value is the index to insert x if x is not
+// present (it could be len(a)).
+// The slice must be sorted in ascending order.
+//
 func SearchStrings(a []string, x string) int {
 	return Search(len(a), func(i int) bool { return a[i] >= x })
 }
diff --git a/src/pkg/sort/search_test.go b/src/pkg/sort/search_test.go
index 07295ffa9..4d8d6d930 100644
--- a/src/pkg/sort/search_test.go
+++ b/src/pkg/sort/search_test.go
@@ -117,6 +117,28 @@ 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) {
+	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/src/pkg/sort/sort.go b/src/pkg/sort/sort.go
index 62a4d55e7..e10961992 100644
--- a/src/pkg/sort/sort.go
+++ b/src/pkg/sort/sort.go
@@ -124,26 +124,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 +202,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()
diff --git a/src/pkg/sort/sort_test.go b/src/pkg/sort/sort_test.go
index ee8a9d0e8..5daf8482b 100644
--- a/src/pkg/sort/sort_test.go
+++ b/src/pkg/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