Update Go library to r60.

From-SVN: r178910

4 files changed, 83 insertions, 90 deletions

diff --git a/libgo/go/sort/search.go b/libgo/go/sort/search.go
index 6828e19b63b..4f0ce55c3c5 100644
--- a/libgo/go/sort/search.go
+++ b/libgo/go/sort/search.go
@@ -15,7 +15,7 @@ package sort
 // 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
-// a sorted, indexable data structure like an array or slice.
+// a sorted, indexable data structure such as an array or slice.
 // In this case, the argument f, typically a closure, captures the value
 // to be searched for, and how the data structure is indexed and
 // ordered.
@@ -71,40 +71,34 @@ func Search(n int, f func(int) bool) int {
 	return i
 }
 
-
 // Convenience wrappers for common cases.
 
 // SearchInts searches for x in a sorted slice of ints and returns the index
-// as specified by Search. The array must be sorted in ascending order.
+// as specified by Search. 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 array must be sorted in ascending order.
+// as specified by Search. 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 in a sorted slice of strings and returns the index
-// as specified by Search. The array must be sorted in ascending order.
+// 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.
 // 
 func SearchStrings(a []string, x string) int {
 	return Search(len(a), func(i int) bool { return a[i] >= x })
 }
 
-
 // Search returns the result of applying SearchInts to the receiver and x.
-func (p IntArray) Search(x int) int { return SearchInts(p, x) }
-
+func (p IntSlice) Search(x int) int { return SearchInts(p, x) }
 
 // Search returns the result of applying SearchFloat64s to the receiver and x.
-func (p Float64Array) Search(x float64) int { return SearchFloat64s(p, x) }
-
+func (p Float64Slice) Search(x float64) int { return SearchFloat64s(p, x) }
 
 // Search returns the result of applying SearchStrings to the receiver and x.
-func (p StringArray) Search(x string) int { return SearchStrings(p, x) }
+func (p StringSlice) Search(x string) int { return SearchStrings(p, x) }
diff --git a/libgo/go/sort/search_test.go b/libgo/go/sort/search_test.go
index 939f66af380..07295ffa976 100644
--- a/libgo/go/sort/search_test.go
+++ b/libgo/go/sort/search_test.go
@@ -2,10 +2,12 @@
 // Use of this source code is governed by a BSD-style
 // license that can be found in the LICENSE file.
 
-package sort
-
-import "testing"
+package sort_test
 
+import (
+	. "sort"
+	"testing"
+)
 
 func f(a []int, x int) func(int) bool {
 	return func(i int) bool {
@@ -13,7 +15,6 @@ func f(a []int, x int) func(int) bool {
 	}
 }
 
-
 var data = []int{0: -10, 1: -5, 2: 0, 3: 1, 4: 2, 5: 3, 6: 5, 7: 7, 8: 11, 9: 100, 10: 100, 11: 100, 12: 1000, 13: 10000}
 
 var tests = []struct {
@@ -46,7 +47,6 @@ var tests = []struct {
 	{"overflow", 2e9, func(i int) bool { return false }, 2e9},
 }
 
-
 func TestSearch(t *testing.T) {
 	for _, e := range tests {
 		i := Search(e.n, e.f)
@@ -56,7 +56,6 @@ func TestSearch(t *testing.T) {
 	}
 }
 
-
 // log2 computes the binary logarithm of x, rounded up to the next integer.
 // (log2(0) == 0, log2(1) == 0, log2(2) == 1, log2(3) == 2, etc.)
 //
@@ -70,7 +69,6 @@ func log2(x int) int {
 	return n
 }
 
-
 func TestSearchEfficiency(t *testing.T) {
 	n := 100
 	step := 1
@@ -93,7 +91,6 @@ func TestSearchEfficiency(t *testing.T) {
 	}
 }
 
-
 // Smoke tests for convenience wrappers - not comprehensive.
 
 var fdata = []float64{0: -3.14, 1: 0, 2: 1, 3: 2, 4: 1000.7}
@@ -107,12 +104,11 @@ var wrappertests = []struct {
 	{"SearchInts", SearchInts(data, 11), 8},
 	{"SearchFloat64s", SearchFloat64s(fdata, 2.1), 4},
 	{"SearchStrings", SearchStrings(sdata, ""), 0},
-	{"IntArray.Search", IntArray(data).Search(0), 2},
-	{"Float64Array.Search", Float64Array(fdata).Search(2.0), 3},
-	{"StringArray.Search", StringArray(sdata).Search("x"), 3},
+	{"IntSlice.Search", IntSlice(data).Search(0), 2},
+	{"Float64Slice.Search", Float64Slice(fdata).Search(2.0), 3},
+	{"StringSlice.Search", StringSlice(sdata).Search("x"), 3},
 }
 
-
 func TestSearchWrappers(t *testing.T) {
 	for _, e := range wrappertests {
 		if e.result != e.i {
@@ -121,7 +117,6 @@ func TestSearchWrappers(t *testing.T) {
 	}
 }
 
-
 // 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 30b1819af2d..0a4a4375f05 100644
--- a/libgo/go/sort/sort.go
+++ b/libgo/go/sort/sort.go
@@ -2,10 +2,12 @@
 // Use of this source code is governed by a BSD-style
 // license that can be found in the LICENSE file.
 
-// Package sort provides primitives for sorting arrays and user-defined
+// Package sort provides primitives for sorting slices and user-defined
 // 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.
@@ -82,7 +84,7 @@ func doPivot(data Interface, lo, hi int) (midlo, midhi int) {
 	//	data[d <= i < hi] = pivot
 	//
 	// Once b meets c, can swap the "= pivot" sections
-	// into the middle of the array.
+	// into the middle of the slice.
 	pivot := lo
 	a, b, c, d := lo+1, lo+1, hi, hi
 	for b < c {
@@ -141,7 +143,6 @@ func quickSort(data Interface, a, b int) {
 
 func Sort(data Interface) { quickSort(data, 0, data.Len()) }
 
-
 func IsSorted(data Interface) bool {
 	n := data.Len()
 	for i := n - 1; i > 0; i-- {
@@ -152,55 +153,50 @@ func IsSorted(data Interface) bool {
 	return true
 }
 
-
 // Convenience types for common cases
 
-// IntArray attaches the methods of Interface to []int, sorting in increasing order.
-type IntArray []int
+// IntSlice attaches the methods of Interface to []int, sorting in increasing order.
+type IntSlice []int
 
-func (p IntArray) Len() int           { return len(p) }
-func (p IntArray) Less(i, j int) bool { return p[i] < p[j] }
-func (p IntArray) Swap(i, j int)      { p[i], p[j] = p[j], p[i] }
+func (p IntSlice) Len() int           { return len(p) }
+func (p IntSlice) Less(i, j int) bool { return p[i] < p[j] }
+func (p IntSlice) Swap(i, j int)      { p[i], p[j] = p[j], p[i] }
 
 // Sort is a convenience method.
-func (p IntArray) Sort() { Sort(p) }
-
+func (p IntSlice) Sort() { Sort(p) }
 
-// Float64Array attaches the methods of Interface to []float64, sorting in increasing order.
-type Float64Array []float64
+// Float64Slice attaches the methods of Interface to []float64, sorting in increasing order.
+type Float64Slice []float64
 
-func (p Float64Array) Len() int           { return len(p) }
-func (p Float64Array) Less(i, j int) bool { return p[i] < p[j] }
-func (p Float64Array) Swap(i, j int)      { p[i], p[j] = p[j], p[i] }
+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) Swap(i, j int)      { p[i], p[j] = p[j], p[i] }
 
 // Sort is a convenience method.
-func (p Float64Array) Sort() { Sort(p) }
+func (p Float64Slice) Sort() { Sort(p) }
 
+// StringSlice attaches the methods of Interface to []string, sorting in increasing order.
+type StringSlice []string
 
-// StringArray attaches the methods of Interface to []string, sorting in increasing order.
-type StringArray []string
-
-func (p StringArray) Len() int           { return len(p) }
-func (p StringArray) Less(i, j int) bool { return p[i] < p[j] }
-func (p StringArray) Swap(i, j int)      { p[i], p[j] = p[j], p[i] }
+func (p StringSlice) Len() int           { return len(p) }
+func (p StringSlice) Less(i, j int) bool { return p[i] < p[j] }
+func (p StringSlice) Swap(i, j int)      { p[i], p[j] = p[j], p[i] }
 
 // Sort is a convenience method.
-func (p StringArray) Sort() { Sort(p) }
-
+func (p StringSlice) Sort() { Sort(p) }
 
 // Convenience wrappers for common cases
 
-// SortInts sorts an array of ints in increasing order.
-func SortInts(a []int) { Sort(IntArray(a)) }
-// SortFloat64s sorts an array of float64s in increasing order.
-func SortFloat64s(a []float64) { Sort(Float64Array(a)) }
-// SortStrings sorts an array of strings in increasing order.
-func SortStrings(a []string) { Sort(StringArray(a)) }
-
-
-// IntsAreSorted tests whether an array of ints is sorted in increasing order.
-func IntsAreSorted(a []int) bool { return IsSorted(IntArray(a)) }
-// Float64sAreSorted tests whether an array of float64s is sorted in increasing order.
-func Float64sAreSorted(a []float64) bool { return IsSorted(Float64Array(a)) }
-// StringsAreSorted tests whether an array of strings is sorted in increasing order.
-func StringsAreSorted(a []string) bool { return IsSorted(StringArray(a)) }
+// Ints sorts a slice of ints in increasing order.
+func Ints(a []int) { Sort(IntSlice(a)) }
+// Float64s sorts a slice of float64s in increasing order.
+func Float64s(a []float64) { Sort(Float64Slice(a)) }
+// Strings sorts a slice of strings in increasing order.
+func Strings(a []string) { Sort(StringSlice(a)) }
+
+// IntsAreSorted tests whether a slice of ints is sorted in increasing order.
+func IntsAreSorted(a []int) bool { return IsSorted(IntSlice(a)) }
+// Float64sAreSorted tests whether a slice of float64s is sorted in increasing order.
+func Float64sAreSorted(a []float64) bool { return IsSorted(Float64Slice(a)) }
+// StringsAreSorted tests whether a slice of strings is sorted in increasing order.
+func StringsAreSorted(a []string) bool { return IsSorted(StringSlice(a)) }
diff --git a/libgo/go/sort/sort_test.go b/libgo/go/sort/sort_test.go
index 3d7337fd010..5007a92a562 100644
--- a/libgo/go/sort/sort_test.go
+++ b/libgo/go/sort/sort_test.go
@@ -2,23 +2,24 @@
 // Use of this source code is governed by a BSD-style
 // license that can be found in the LICENSE file.
 
-package sort
+package sort_test
 
 import (
 	"fmt"
+	"math"
 	"rand"
+	. "sort"
 	"strconv"
 	"testing"
 )
 
-
 var ints = [...]int{74, 59, 238, -784, 9845, 959, 905, 0, 0, 42, 7586, -5467984, 7586}
-var float64s = [...]float64{74.3, 59.0, 238.2, -784.0, 2.3, 9845.768, -959.7485, 905, 7.8, 7.8}
+var float64s = [...]float64{74.3, 59.0, math.Inf(1), 238.2, -784.0, 2.3, math.NaN(), math.NaN(), math.Inf(-1), 9845.768, -959.7485, 905, 7.8, 7.8}
 var strings = [...]string{"", "Hello", "foo", "bar", "foo", "f00", "%*&^*&^&", "***"}
 
-func TestSortIntArray(t *testing.T) {
+func TestSortIntSlice(t *testing.T) {
 	data := ints
-	a := IntArray(data[0:])
+	a := IntSlice(data[0:])
 	Sort(a)
 	if !IsSorted(a) {
 		t.Errorf("sorted %v", ints)
@@ -26,9 +27,9 @@ func TestSortIntArray(t *testing.T) {
 	}
 }
 
-func TestSortFloat64Array(t *testing.T) {
+func TestSortFloat64Slice(t *testing.T) {
 	data := float64s
-	a := Float64Array(data[0:])
+	a := Float64Slice(data[0:])
 	Sort(a)
 	if !IsSorted(a) {
 		t.Errorf("sorted %v", float64s)
@@ -36,9 +37,9 @@ func TestSortFloat64Array(t *testing.T) {
 	}
 }
 
-func TestSortStringArray(t *testing.T) {
+func TestSortStringSlice(t *testing.T) {
 	data := strings
-	a := StringArray(data[0:])
+	a := StringSlice(data[0:])
 	Sort(a)
 	if !IsSorted(a) {
 		t.Errorf("sorted %v", strings)
@@ -46,27 +47,27 @@ func TestSortStringArray(t *testing.T) {
 	}
 }
 
-func TestSortInts(t *testing.T) {
+func TestInts(t *testing.T) {
 	data := ints
-	SortInts(data[0:])
+	Ints(data[0:])
 	if !IntsAreSorted(data[0:]) {
 		t.Errorf("sorted %v", ints)
 		t.Errorf("   got %v", data)
 	}
 }
 
-func TestSortFloat64s(t *testing.T) {
+func TestFloat64s(t *testing.T) {
 	data := float64s
-	SortFloat64s(data[0:])
+	Float64s(data[0:])
 	if !Float64sAreSorted(data[0:]) {
 		t.Errorf("sorted %v", float64s)
 		t.Errorf("   got %v", data)
 	}
 }
 
-func TestSortStrings(t *testing.T) {
+func TestStrings(t *testing.T) {
 	data := strings
-	SortStrings(data[0:])
+	Strings(data[0:])
 	if !StringsAreSorted(data[0:]) {
 		t.Errorf("sorted %v", strings)
 		t.Errorf("   got %v", data)
@@ -85,7 +86,7 @@ func TestSortLarge_Random(t *testing.T) {
 	if IntsAreSorted(data) {
 		t.Fatalf("terrible rand.rand")
 	}
-	SortInts(data)
+	Ints(data)
 	if !IntsAreSorted(data) {
 		t.Errorf("sort didn't sort - 1M ints")
 	}
@@ -99,7 +100,7 @@ func BenchmarkSortString1K(b *testing.B) {
 			data[i] = strconv.Itoa(i ^ 0x2cc)
 		}
 		b.StartTimer()
-		SortStrings(data)
+		Strings(data)
 		b.StopTimer()
 	}
 }
@@ -112,7 +113,7 @@ func BenchmarkSortInt1K(b *testing.B) {
 			data[i] = i ^ 0x2cc
 		}
 		b.StartTimer()
-		SortInts(data)
+		Ints(data)
 		b.StopTimer()
 	}
 }
@@ -125,7 +126,7 @@ func BenchmarkSortInt64K(b *testing.B) {
 			data[i] = i ^ 0xcccc
 		}
 		b.StartTimer()
-		SortInts(data)
+		Ints(data)
 		b.StopTimer()
 	}
 }
@@ -161,7 +162,7 @@ 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) Swap(i, j int) {
 	if d.nswap >= d.maxswap {
-		d.t.Errorf("%s: used %d swaps sorting array of %d", d.desc, d.nswap, len(d.data))
+		d.t.Errorf("%s: used %d swaps sorting slice of %d", d.desc, d.nswap, len(d.data))
 		d.t.FailNow()
 	}
 	d.nswap++
@@ -241,9 +242,9 @@ func TestBentleyMcIlroy(t *testing.T) {
 						for i := 0; i < n; i++ {
 							mdata[i] = data[i]
 						}
-						// SortInts is known to be correct
+						// Ints is known to be correct
 						// because mode Sort runs after mode _Copy.
-						SortInts(mdata)
+						Ints(mdata)
 					case _Dither:
 						for i := 0; i < n; i++ {
 							mdata[i] = data[i] + i%5
@@ -255,13 +256,13 @@ func TestBentleyMcIlroy(t *testing.T) {
 					Sort(d)
 
 					// If we were testing C qsort, we'd have to make a copy
-					// of the array and sort it ourselves and then compare
+					// of the slice and sort it ourselves and then compare
 					// x against it, to ensure that qsort was only permuting
 					// the data, not (for example) overwriting it with zeros.
 					//
 					// In go, we don't have to be so paranoid: since the only
 					// mutating method Sort can call is TestingData.swap,
-					// it suffices here just to check that the final array is sorted.
+					// it suffices here just to check that the final slice is sorted.
 					if !IntsAreSorted(mdata) {
 						t.Errorf("%s: ints not sorted", desc)
 						t.Errorf("\t%v", mdata)
@@ -272,3 +273,10 @@ func TestBentleyMcIlroy(t *testing.T) {
 		}
 	}
 }
+
+func min(a, b int) int {
+	if a < b {
+		return a
+	}
+	return b
+}