summaryrefslogtreecommitdiff
path: root/src/pkg/sort
diff options
context:
space:
mode:
Diffstat (limited to 'src/pkg/sort')
-rw-r--r--src/pkg/sort/example_interface_test.go44
-rw-r--r--src/pkg/sort/example_keys_test.go96
-rw-r--r--src/pkg/sort/example_multi_test.go131
-rw-r--r--src/pkg/sort/example_test.go24
-rw-r--r--src/pkg/sort/example_wrapper_test.go77
-rw-r--r--src/pkg/sort/export_test.go9
-rw-r--r--src/pkg/sort/search.go112
-rw-r--r--src/pkg/sort/search_test.go161
-rw-r--r--src/pkg/sort/sort.go474
-rw-r--r--src/pkg/sort/sort_test.go553
10 files changed, 0 insertions, 1681 deletions
diff --git a/src/pkg/sort/example_interface_test.go b/src/pkg/sort/example_interface_test.go
deleted file mode 100644
index 442204ea9..000000000
--- a/src/pkg/sort/example_interface_test.go
+++ /dev/null
@@ -1,44 +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"
-)
-
-type Person struct {
- Name string
- Age int
-}
-
-func (p Person) String() string {
- return fmt.Sprintf("%s: %d", p.Name, p.Age)
-}
-
-// ByAge implements sort.Interface for []Person based on
-// the Age field.
-type ByAge []Person
-
-func (a ByAge) Len() int { return len(a) }
-func (a ByAge) Swap(i, j int) { a[i], a[j] = a[j], a[i] }
-func (a ByAge) Less(i, j int) bool { return a[i].Age < a[j].Age }
-
-func Example() {
- people := []Person{
- {"Bob", 31},
- {"John", 42},
- {"Michael", 17},
- {"Jenny", 26},
- }
-
- fmt.Println(people)
- sort.Sort(ByAge(people))
- fmt.Println(people)
-
- // Output:
- // [Bob: 31 John: 42 Michael: 17 Jenny: 26]
- // [Michael: 17 Jenny: 26 Bob: 31 John: 42]
-}
diff --git a/src/pkg/sort/example_keys_test.go b/src/pkg/sort/example_keys_test.go
deleted file mode 100644
index a8e47e492..000000000
--- a/src/pkg/sort/example_keys_test.go
+++ /dev/null
@@ -1,96 +0,0 @@
-// 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_multi_test.go b/src/pkg/sort/example_multi_test.go
deleted file mode 100644
index ac316540f..000000000
--- a/src/pkg/sort/example_multi_test.go
+++ /dev/null
@@ -1,131 +0,0 @@
-// 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) {
- ms.changes = changes
- 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{
- 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)
-
- // More examples.
- OrderedBy(user, increasingLines).Sort(changes)
- fmt.Println("By user,<lines:", changes)
-
- 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/src/pkg/sort/example_test.go b/src/pkg/sort/example_test.go
deleted file mode 100644
index f7372bec3..000000000
--- a/src/pkg/sort/example_test.go
+++ /dev/null
@@ -1,24 +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"
-)
-
-func ExampleInts() {
- s := []int{5, 2, 6, 3, 1, 4} // unsorted
- sort.Ints(s)
- 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/example_wrapper_test.go b/src/pkg/sort/example_wrapper_test.go
deleted file mode 100644
index cf6d74cf7..000000000
--- a/src/pkg/sort/example_wrapper_test.go
+++ /dev/null
@@ -1,77 +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"
-)
-
-type Grams int
-
-func (g Grams) String() string { return fmt.Sprintf("%dg", int(g)) }
-
-type Organ struct {
- Name string
- Weight Grams
-}
-
-type Organs []*Organ
-
-func (s Organs) Len() int { return len(s) }
-func (s Organs) Swap(i, j int) { s[i], s[j] = s[j], s[i] }
-
-// ByName implements sort.Interface by providing Less and using the Len and
-// Swap methods of the embedded Organs value.
-type ByName struct{ Organs }
-
-func (s ByName) Less(i, j int) bool { return s.Organs[i].Name < s.Organs[j].Name }
-
-// ByWeight implements sort.Interface by providing Less and using the Len and
-// Swap methods of the embedded Organs value.
-type ByWeight struct{ Organs }
-
-func (s ByWeight) Less(i, j int) bool { return s.Organs[i].Weight < s.Organs[j].Weight }
-
-func Example_sortWrapper() {
- s := []*Organ{
- {"brain", 1340},
- {"heart", 290},
- {"liver", 1494},
- {"pancreas", 131},
- {"prostate", 62},
- {"spleen", 162},
- }
-
- sort.Sort(ByWeight{s})
- fmt.Println("Organs by weight:")
- printOrgans(s)
-
- sort.Sort(ByName{s})
- fmt.Println("Organs by name:")
- printOrgans(s)
-
- // Output:
- // Organs by weight:
- // prostate (62g)
- // pancreas (131g)
- // spleen (162g)
- // heart (290g)
- // brain (1340g)
- // liver (1494g)
- // Organs by name:
- // brain (1340g)
- // heart (290g)
- // liver (1494g)
- // pancreas (131g)
- // prostate (62g)
- // spleen (162g)
-}
-
-func printOrgans(s []*Organ) {
- for _, o := range s {
- fmt.Printf("%-8s (%v)\n", o.Name, o.Weight)
- }
-}
diff --git a/src/pkg/sort/export_test.go b/src/pkg/sort/export_test.go
deleted file mode 100644
index b6e30ceb5..000000000
--- a/src/pkg/sort/export_test.go
+++ /dev/null
@@ -1,9 +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
-
-func Heapsort(data Interface) {
- heapSort(data, 0, data.Len())
-}
diff --git a/src/pkg/sort/search.go b/src/pkg/sort/search.go
deleted file mode 100644
index 8a2c1c33b..000000000
--- a/src/pkg/sort/search.go
+++ /dev/null
@@ -1,112 +0,0 @@
-// Copyright 2010 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.
-
-// This file implements binary search.
-
-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),
-// 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
-// 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.
-//
-// For instance, given a slice data sorted in ascending order,
-// the call Search(len(data), func(i int) bool { return data[i] >= 23 })
-// returns the smallest index i such that data[i] >= 23. If the caller
-// wants to find whether 23 is in the slice, it must test data[i] == 23
-// separately.
-//
-// Searching data sorted in descending order would use the <=
-// operator instead of the >= operator.
-//
-// To complete the example above, the following code tries to find the value
-// x in an integer slice data sorted in ascending order:
-//
-// x := 23
-// i := sort.Search(len(data), func(i int) bool { return data[i] >= x })
-// if i < len(data) && data[i] == x {
-// // x is present at data[i]
-// } else {
-// // x is not present in data,
-// // but i is the index where it would be inserted.
-// }
-//
-// As a more whimsical example, this program guesses your number:
-//
-// func GuessingGame() {
-// var s string
-// fmt.Printf("Pick an integer from 0 to 100.\n")
-// answer := sort.Search(100, func(i int) bool {
-// fmt.Printf("Is your number <= %d? ", i)
-// fmt.Scanf("%s", &s)
-// return s != "" && s[0] == 'y'
-// })
-// fmt.Printf("Your number is %d.\n", answer)
-// }
-//
-func Search(n int, f func(int) bool) int {
- // Define f(-1) == false and f(n) == true.
- // Invariant: f(i-1) == false, f(j) == true.
- i, j := 0, n
- for i < j {
- h := i + (j-i)/2 // avoid overflow when computing h
- // i ≤ h < j
- if !f(h) {
- i = h + 1 // preserves f(i-1) == false
- } else {
- j = h // preserves f(j) == true
- }
- }
- // i == j, f(i-1) == false, and f(j) (= f(i)) == true => answer is i.
- 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 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 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 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 })
-}
-
-// Search returns the result of applying SearchInts to the receiver and 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 Float64Slice) Search(x float64) int { return SearchFloat64s(p, x) }
-
-// Search returns the result of applying SearchStrings to the receiver and x.
-func (p StringSlice) Search(x string) int { return SearchStrings(p, x) }
diff --git a/src/pkg/sort/search_test.go b/src/pkg/sort/search_test.go
deleted file mode 100644
index 29b8d62df..000000000
--- a/src/pkg/sort/search_test.go
+++ /dev/null
@@ -1,161 +0,0 @@
-// Copyright 2010 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 (
- "runtime"
- . "sort"
- "testing"
-)
-
-func f(a []int, x int) func(int) bool {
- return func(i int) bool {
- return a[i] >= x
- }
-}
-
-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 {
- name string
- n int
- f func(int) bool
- i int
-}{
- {"empty", 0, nil, 0},
- {"1 1", 1, func(i int) bool { return i >= 1 }, 1},
- {"1 true", 1, func(i int) bool { return true }, 0},
- {"1 false", 1, func(i int) bool { return false }, 1},
- {"1e9 991", 1e9, func(i int) bool { return i >= 991 }, 991},
- {"1e9 true", 1e9, func(i int) bool { return true }, 0},
- {"1e9 false", 1e9, func(i int) bool { return false }, 1e9},
- {"data -20", len(data), f(data, -20), 0},
- {"data -10", len(data), f(data, -10), 0},
- {"data -9", len(data), f(data, -9), 1},
- {"data -6", len(data), f(data, -6), 1},
- {"data -5", len(data), f(data, -5), 1},
- {"data 3", len(data), f(data, 3), 5},
- {"data 11", len(data), f(data, 11), 8},
- {"data 99", len(data), f(data, 99), 9},
- {"data 100", len(data), f(data, 100), 9},
- {"data 101", len(data), f(data, 101), 12},
- {"data 10000", len(data), f(data, 10000), 13},
- {"data 10001", len(data), f(data, 10001), 14},
- {"descending a", 7, func(i int) bool { return []int{99, 99, 59, 42, 7, 0, -1, -1}[i] <= 7 }, 4},
- {"descending 7", 1e9, func(i int) bool { return 1e9-i <= 7 }, 1e9 - 7},
- {"overflow", 2e9, func(i int) bool { return false }, 2e9},
-}
-
-func TestSearch(t *testing.T) {
- for _, e := range tests {
- i := Search(e.n, e.f)
- if i != e.i {
- t.Errorf("%s: expected index %d; got %d", e.name, e.i, i)
- }
- }
-}
-
-// 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.)
-//
-func log2(x int) int {
- n := 0
- for p := 1; p < x; p += p {
- // p == 2**n
- n++
- }
- // p/2 < x <= p == 2**n
- return n
-}
-
-func TestSearchEfficiency(t *testing.T) {
- n := 100
- step := 1
- for exp := 2; exp < 10; exp++ {
- // n == 10**exp
- // step == 10**(exp-2)
- max := log2(n)
- for x := 0; x < n; x += step {
- count := 0
- i := Search(n, func(i int) bool { count++; return i >= x })
- if i != x {
- t.Errorf("n = %d: expected index %d; got %d", n, x, i)
- }
- if count > max {
- t.Errorf("n = %d, x = %d: expected <= %d calls; got %d", n, x, max, count)
- }
- }
- n *= 10
- step *= 10
- }
-}
-
-// Smoke tests for convenience wrappers - not comprehensive.
-
-var fdata = []float64{0: -3.14, 1: 0, 2: 1, 3: 2, 4: 1000.7}
-var sdata = []string{0: "f", 1: "foo", 2: "foobar", 3: "x"}
-
-var wrappertests = []struct {
- name string
- result int
- i int
-}{
- {"SearchInts", SearchInts(data, 11), 8},
- {"SearchFloat64s", SearchFloat64s(fdata, 2.1), 4},
- {"SearchStrings", SearchStrings(sdata, ""), 0},
- {"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 {
- t.Errorf("%s: expected index %d; got %d", e.name, e.i, e.result)
- }
- }
-}
-
-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 testing.Short() {
- t.Skip("skipping malloc count in short mode")
- }
- if runtime.GOMAXPROCS(0) > 1 {
- t.Skip("skipping; GOMAXPROCS>1")
- }
- 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.
-func TestSearchExhaustive(t *testing.T) {
- for size := 0; size <= 100; size++ {
- for targ := 0; targ <= size; targ++ {
- i := Search(size, func(i int) bool { return i >= targ })
- if i != targ {
- t.Errorf("Search(%d, %d) = %d", size, targ, i)
- }
- }
- }
-}
diff --git a/src/pkg/sort/sort.go b/src/pkg/sort/sort.go
deleted file mode 100644
index e980c295c..000000000
--- a/src/pkg/sort/sort.go
+++ /dev/null
@@ -1,474 +0,0 @@
-// Copyright 2009 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 provides primitives for sorting slices and user-defined
-// collections.
-package sort
-
-// 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.
-type Interface interface {
- // Len is the number of elements in the collection.
- Len() int
- // Less reports whether the element with
- // index i should sort before the element with index j.
- Less(i, j int) bool
- // Swap swaps the elements with indexes i and j.
- Swap(i, j int)
-}
-
-func min(a, b int) int {
- if a < b {
- return a
- }
- return b
-}
-
-// Insertion sort
-func insertionSort(data Interface, a, b int) {
- for i := a + 1; i < b; i++ {
- for j := i; j > a && data.Less(j, j-1); j-- {
- data.Swap(j, j-1)
- }
- }
-}
-
-// siftDown implements the heap property on data[lo, hi).
-// first is an offset into the array where the root of the heap lies.
-func siftDown(data Interface, lo, hi, first int) {
- root := lo
- for {
- child := 2*root + 1
- if child >= hi {
- break
- }
- if child+1 < hi && data.Less(first+child, first+child+1) {
- child++
- }
- if !data.Less(first+root, first+child) {
- return
- }
- data.Swap(first+root, first+child)
- root = child
- }
-}
-
-func heapSort(data Interface, a, b int) {
- first := a
- lo := 0
- hi := b - a
-
- // Build heap with greatest element at top.
- for i := (hi - 1) / 2; i >= 0; i-- {
- siftDown(data, i, hi, first)
- }
-
- // Pop elements, largest first, into end of data.
- for i := hi - 1; i >= 0; i-- {
- data.Swap(first, first+i)
- siftDown(data, lo, i, first)
- }
-}
-
-// Quicksort, following Bentley and McIlroy,
-// ``Engineering a Sort Function,'' SP&E November 1993.
-
-// medianOfThree moves the median of the three values data[a], data[b], data[c] into data[a].
-func medianOfThree(data Interface, a, b, c int) {
- m0 := b
- m1 := a
- m2 := c
- // bubble sort on 3 elements
- if data.Less(m1, m0) {
- data.Swap(m1, m0)
- }
- if data.Less(m2, m1) {
- data.Swap(m2, m1)
- }
- if data.Less(m1, m0) {
- data.Swap(m1, m0)
- }
- // now data[m0] <= data[m1] <= data[m2]
-}
-
-func swapRange(data Interface, a, b, n int) {
- for i := 0; i < n; i++ {
- data.Swap(a+i, b+i)
- }
-}
-
-func doPivot(data Interface, lo, hi int) (midlo, midhi int) {
- m := lo + (hi-lo)/2 // Written like this to avoid integer overflow.
- if hi-lo > 40 {
- // Tukey's ``Ninther,'' median of three medians of three.
- s := (hi - lo) / 8
- medianOfThree(data, lo, lo+s, lo+2*s)
- medianOfThree(data, m, m-s, m+s)
- medianOfThree(data, hi-1, hi-1-s, hi-1-2*s)
- }
- medianOfThree(data, lo, m, hi-1)
-
- // Invariants are:
- // data[lo] = pivot (set up by ChoosePivot)
- // data[lo <= i < a] = pivot
- // data[a <= i < b] < pivot
- // data[b <= i < c] is unexamined
- // data[c <= i < d] > pivot
- // data[d <= i < hi] = pivot
- //
- // Once b meets c, can swap the "= pivot" sections
- // into the middle of the slice.
- pivot := lo
- a, b, c, d := lo+1, lo+1, hi, hi
- 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
- }
- }
- 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 b >= c {
- break
- }
- // data[b] > pivot; data[c-1] < pivot
- data.Swap(b, c-1)
- b++
- c--
- }
-
- n := min(b-a, a-lo)
- swapRange(data, lo, b-n, n)
-
- n = min(hi-d, d-c)
- swapRange(data, c, hi-n, n)
-
- return lo + b - a, hi - (d - c)
-}
-
-func quickSort(data Interface, a, b, maxDepth int) {
- for b-a > 7 {
- if maxDepth == 0 {
- heapSort(data, a, b)
- return
- }
- maxDepth--
- mlo, mhi := doPivot(data, a, b)
- // Avoiding recursion on the larger subproblem guarantees
- // a stack depth of at most lg(b-a).
- if mlo-a < b-mhi {
- quickSort(data, a, mlo, maxDepth)
- a = mhi // i.e., quickSort(data, mhi, b)
- } else {
- quickSort(data, mhi, b, maxDepth)
- b = mlo // i.e., quickSort(data, a, mlo)
- }
- }
- if b-a > 1 {
- insertionSort(data, a, b)
- }
-}
-
-// Sort sorts data.
-// It makes one call to data.Len to determine n, and O(n*log(n)) calls to
-// data.Less and data.Swap. The sort is not guaranteed to be stable.
-func Sort(data Interface) {
- // Switch to heapsort if depth of 2*ceil(lg(n+1)) is reached.
- n := data.Len()
- maxDepth := 0
- for i := n; i > 0; i >>= 1 {
- maxDepth++
- }
- maxDepth *= 2
- 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()
- for i := n - 1; i > 0; i-- {
- if data.Less(i, i-1) {
- return false
- }
- }
- return true
-}
-
-// Convenience types for common cases
-
-// IntSlice attaches the methods of Interface to []int, sorting in increasing order.
-type IntSlice []int
-
-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 IntSlice) Sort() { Sort(p) }
-
-// Float64Slice attaches the methods of Interface to []float64, sorting in increasing order.
-type Float64Slice []float64
-
-func (p Float64Slice) Len() int { return len(p) }
-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) }
-
-// StringSlice attaches the methods of Interface to []string, sorting in increasing order.
-type StringSlice []string
-
-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 StringSlice) Sort() { Sort(p) }
-
-// Convenience wrappers for common cases
-
-// 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)) }
-
-// Notes on stable sorting:
-// The used algorithms are simple and provable correct on all input and use
-// only logarithmic additional stack space. They perform well if compared
-// experimentally to other stable in-place sorting algorithms.
-//
-// Remarks on other algorithms evaluated:
-// - GCC's 4.6.3 stable_sort with merge_without_buffer from libstdc++:
-// Not faster.
-// - GCC's __rotate for block rotations: Not faster.
-// - "Practical in-place mergesort" from Jyrki Katajainen, Tomi A. Pasanen
-// and Jukka Teuhola; Nordic Journal of Computing 3,1 (1996), 27-40:
-// The given algorithms are in-place, number of Swap and Assignments
-// grow as n log n but the algorithm is not stable.
-// - "Fast Stable In-Plcae Sorting with O(n) Data Moves" J.I. Munro and
-// V. Raman in Algorithmica (1996) 16, 115-160:
-// This algorithm either needs additional 2n bits or works only if there
-// are enough different elements available to encode some permutations
-// which have to be undone later (so not stable an any input).
-// - All the optimal in-place sorting/merging algorithms I found are either
-// unstable or rely on enough different elements in each step to encode the
-// performed block rearrangements. See also "In-Place Merging Algorithms",
-// Denham Coates-Evely, Department of Computer Science, Kings College,
-// January 2004 and the reverences in there.
-// - Often "optimal" algorithms are optimal in the number of assignments
-// but Interface has only Swap as operation.
-
-// Stable sorts data while keeping the original order of equal elements.
-//
-// It makes one call to data.Len to determine n, O(n*log(n)) calls to
-// data.Less and O(n*log(n)*log(n)) calls to data.Swap.
-func Stable(data Interface) {
- n := data.Len()
- blockSize := 20
- a, b := 0, blockSize
- for b <= n {
- insertionSort(data, a, b)
- a = b
- b += blockSize
- }
- insertionSort(data, a, n)
-
- for blockSize < n {
- a, b = 0, 2*blockSize
- for b <= n {
- symMerge(data, a, a+blockSize, b)
- a = b
- b += 2 * blockSize
- }
- symMerge(data, a, a+blockSize, n)
- blockSize *= 2
- }
-}
-
-// SymMerge merges the two sorted subsequences data[a:m] and data[m:b] using
-// the SymMerge algorithm from Pok-Son Kim and Arne Kutzner, "Stable Minimum
-// Storage Merging by Symmetric Comparisons", in Susanne Albers and Tomasz
-// Radzik, editors, Algorithms - ESA 2004, volume 3221 of Lecture Notes in
-// Computer Science, pages 714-723. Springer, 2004.
-//
-// Let M = m-a and N = b-n. Wolog M < N.
-// The recursion depth is bound by ceil(log(N+M)).
-// The algorithm needs O(M*log(N/M + 1)) calls to data.Less.
-// The algorithm needs O((M+N)*log(M)) calls to data.Swap.
-//
-// The paper gives O((M+N)*log(M)) as the number of assignments assuming a
-// rotation algorithm which uses O(M+N+gcd(M+N)) assignments. The argumentation
-// in the paper carries through for Swap operations, especially as the block
-// swapping rotate uses only O(M+N) Swaps.
-func symMerge(data Interface, a, m, b int) {
- if a >= m || m >= b {
- return
- }
-
- mid := a + (b-a)/2
- n := mid + m
- start := 0
- if m > mid {
- start = n - b
- r, p := mid, n-1
- for start < r {
- c := start + (r-start)/2
- if !data.Less(p-c, c) {
- start = c + 1
- } else {
- r = c
- }
- }
- } else {
- start = a
- r, p := m, n-1
- for start < r {
- c := start + (r-start)/2
- if !data.Less(p-c, c) {
- start = c + 1
- } else {
- r = c
- }
- }
- }
- end := n - start
- rotate(data, start, m, end)
- symMerge(data, a, start, mid)
- symMerge(data, mid, end, b)
-}
-
-// Rotate two consecutives blocks u = data[a:m] and v = data[m:b] in data:
-// Data of the form 'x u v y' is changed to 'x v u y'.
-// Rotate performs at most b-a many calls to data.Swap.
-func rotate(data Interface, a, m, b int) {
- i := m - a
- if i == 0 {
- return
- }
- j := b - m
- if j == 0 {
- return
- }
-
- if i == j {
- swapRange(data, a, m, i)
- return
- }
-
- p := a + i
- for i != j {
- if i > j {
- swapRange(data, p-i, p, j)
- i -= j
- } else {
- swapRange(data, p-i, p+j-i, i)
- j -= i
- }
- }
- swapRange(data, p-i, p, i)
-}
-
-/*
-Complexity of Stable Sorting
-
-
-Complexity of block swapping rotation
-
-Each Swap puts one new element into its correct, final position.
-Elements which reach their final position are no longer moved.
-Thus block swapping rotation needs |u|+|v| calls to Swaps.
-This is best possible as each element might need a move.
-
-Pay attention when comparing to other optimal algorithms which
-typically count the number of assignments instead of swaps:
-E.g. the optimal algorithm of Dudzinski and Dydek for in-place
-rotations uses O(u + v + gcd(u,v)) assignments which is
-better than our O(3 * (u+v)) as gcd(u,v) <= u.
-
-
-Stable sorting by SymMerge and BlockSwap rotations
-
-SymMerg complexity for same size input M = N:
-Calls to Less: O(M*log(N/M+1)) = O(N*log(2)) = O(N)
-Calls to Swap: O((M+N)*log(M)) = O(2*N*log(N)) = O(N*log(N))
-
-(The following argument does not fuzz over a missing -1 or
-other stuff which does not impact the final result).
-
-Let n = data.Len(). Assume n = 2^k.
-
-Plain merge sort performs log(n) = k iterations.
-On iteration i the algorithm merges 2^(k-i) blocks, each of size 2^i.
-
-Thus iteration i of merge sort performs:
-Calls to Less O(2^(k-i) * 2^i) = O(2^k) = O(2^log(n)) = O(n)
-Calls to Swap O(2^(k-i) * 2^i * log(2^i)) = O(2^k * i) = O(n*i)
-
-In total k = log(n) iterations are performed; so in total:
-Calls to Less O(log(n) * n)
-Calls to Swap O(n + 2*n + 3*n + ... + (k-1)*n + k*n)
- = O((k/2) * k * n) = O(n * k^2) = O(n * log^2(n))
-
-
-Above results should generalize to arbitrary n = 2^k + p
-and should not be influenced by the initial insertion sort phase:
-Insertion sort is O(n^2) on Swap and Less, thus O(bs^2) per block of
-size bs at n/bs blocks: O(bs*n) Swaps and Less during insertion sort.
-Merge sort iterations start at i = log(bs). With t = log(bs) constant:
-Calls to Less O((log(n)-t) * n + bs*n) = O(log(n)*n + (bs-t)*n)
- = O(n * log(n))
-Calls to Swap O(n * log^2(n) - (t^2+t)/2*n) = O(n * log^2(n))
-
-*/
diff --git a/src/pkg/sort/sort_test.go b/src/pkg/sort/sort_test.go
deleted file mode 100644
index 6c36f30e0..000000000
--- a/src/pkg/sort/sort_test.go
+++ /dev/null
@@ -1,553 +0,0 @@
-// Copyright 2009 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"
- "math"
- "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, 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 TestSortIntSlice(t *testing.T) {
- data := ints
- a := IntSlice(data[0:])
- Sort(a)
- if !IsSorted(a) {
- t.Errorf("sorted %v", ints)
- t.Errorf(" got %v", data)
- }
-}
-
-func TestSortFloat64Slice(t *testing.T) {
- data := float64s
- a := Float64Slice(data[0:])
- Sort(a)
- if !IsSorted(a) {
- t.Errorf("sorted %v", float64s)
- t.Errorf(" got %v", data)
- }
-}
-
-func TestSortStringSlice(t *testing.T) {
- data := strings
- a := StringSlice(data[0:])
- Sort(a)
- if !IsSorted(a) {
- t.Errorf("sorted %v", strings)
- t.Errorf(" got %v", data)
- }
-}
-
-func TestInts(t *testing.T) {
- data := ints
- Ints(data[0:])
- if !IntsAreSorted(data[0:]) {
- t.Errorf("sorted %v", ints)
- t.Errorf(" got %v", data)
- }
-}
-
-func TestFloat64s(t *testing.T) {
- data := float64s
- Float64s(data[0:])
- if !Float64sAreSorted(data[0:]) {
- t.Errorf("sorted %v", float64s)
- t.Errorf(" got %v", data)
- }
-}
-
-func TestStrings(t *testing.T) {
- data := strings
- Strings(data[0:])
- if !StringsAreSorted(data[0:]) {
- t.Errorf("sorted %v", strings)
- t.Errorf(" got %v", data)
- }
-}
-
-func TestSortLarge_Random(t *testing.T) {
- n := 1000000
- if testing.Short() {
- n /= 100
- }
- data := make([]int, n)
- for i := 0; i < len(data); i++ {
- data[i] = rand.Intn(100)
- }
- if IntsAreSorted(data) {
- t.Fatalf("terrible rand.rand")
- }
- Ints(data)
- if !IntsAreSorted(data) {
- t.Errorf("sort didn't sort - 1M ints")
- }
-}
-
-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++ {
- data := make([]string, 1<<10)
- for i := 0; i < len(data); i++ {
- data[i] = strconv.Itoa(i ^ 0x2cc)
- }
- b.StartTimer()
- Strings(data)
- b.StopTimer()
- }
-}
-
-func BenchmarkStableString1K(b *testing.B) {
- b.StopTimer()
- for i := 0; i < b.N; i++ {
- data := make([]string, 1<<10)
- for i := 0; i < len(data); i++ {
- data[i] = strconv.Itoa(i ^ 0x2cc)
- }
- b.StartTimer()
- Stable(StringSlice(data))
- b.StopTimer()
- }
-}
-
-func BenchmarkSortInt1K(b *testing.B) {
- b.StopTimer()
- for i := 0; i < b.N; i++ {
- data := make([]int, 1<<10)
- for i := 0; i < len(data); i++ {
- data[i] = i ^ 0x2cc
- }
- b.StartTimer()
- Ints(data)
- b.StopTimer()
- }
-}
-
-func BenchmarkStableInt1K(b *testing.B) {
- b.StopTimer()
- for i := 0; i < b.N; i++ {
- data := make([]int, 1<<10)
- for i := 0; i < len(data); i++ {
- data[i] = i ^ 0x2cc
- }
- b.StartTimer()
- Stable(IntSlice(data))
- b.StopTimer()
- }
-}
-
-func BenchmarkSortInt64K(b *testing.B) {
- b.StopTimer()
- for i := 0; i < b.N; i++ {
- data := make([]int, 1<<16)
- for i := 0; i < len(data); i++ {
- data[i] = i ^ 0xcccc
- }
- b.StartTimer()
- Ints(data)
- b.StopTimer()
- }
-}
-
-func BenchmarkStableInt64K(b *testing.B) {
- b.StopTimer()
- for i := 0; i < b.N; i++ {
- data := make([]int, 1<<16)
- for i := 0; i < len(data); i++ {
- data[i] = i ^ 0xcccc
- }
- b.StartTimer()
- Stable(IntSlice(data))
- b.StopTimer()
- }
-}
-
-const (
- _Sawtooth = iota
- _Rand
- _Stagger
- _Plateau
- _Shuffle
- _NDist
-)
-
-const (
- _Copy = iota
- _Reverse
- _ReverseFirstHalf
- _ReverseSecondHalf
- _Sorted
- _Dither
- _NMode
-)
-
-type testingData struct {
- 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 {
- 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))
- d.t.FailNow()
- }
- d.nswap++
- d.data[i], d.data[j] = d.data[j], d.data[i]
-}
-
-func min(a, b int) int {
- if a < b {
- return a
- }
- return b
-}
-
-func lg(n int) int {
- i := 0
- for 1<<uint(i) < n {
- i++
- }
- return i
-}
-
-func testBentleyMcIlroy(t *testing.T, sort func(Interface), maxswap func(int) int) {
- sizes := []int{100, 1023, 1024, 1025}
- if testing.Short() {
- sizes = []int{100, 127, 128, 129}
- }
- dists := []string{"sawtooth", "rand", "stagger", "plateau", "shuffle"}
- modes := []string{"copy", "reverse", "reverse1", "reverse2", "sort", "dither"}
- var tmp1, tmp2 [1025]int
- for _, n := range sizes {
- for m := 1; m < 2*n; m *= 2 {
- for dist := 0; dist < _NDist; dist++ {
- j := 0
- k := 1
- data := tmp1[0:n]
- for i := 0; i < n; i++ {
- switch dist {
- case _Sawtooth:
- data[i] = i % m
- case _Rand:
- data[i] = rand.Intn(m)
- case _Stagger:
- data[i] = (i*m + i) % n
- case _Plateau:
- data[i] = min(i, m)
- case _Shuffle:
- if rand.Intn(m) != 0 {
- j += 2
- data[i] = j
- } else {
- k += 2
- data[i] = k
- }
- }
- }
-
- mdata := tmp2[0:n]
- for mode := 0; mode < _NMode; mode++ {
- switch mode {
- case _Copy:
- for i := 0; i < n; i++ {
- mdata[i] = data[i]
- }
- case _Reverse:
- for i := 0; i < n; i++ {
- mdata[i] = data[n-i-1]
- }
- case _ReverseFirstHalf:
- for i := 0; i < n/2; i++ {
- mdata[i] = data[n/2-i-1]
- }
- for i := n / 2; i < n; i++ {
- mdata[i] = data[i]
- }
- case _ReverseSecondHalf:
- for i := 0; i < n/2; i++ {
- mdata[i] = data[i]
- }
- for i := n / 2; i < n; i++ {
- mdata[i] = data[n-(i-n/2)-1]
- }
- case _Sorted:
- for i := 0; i < n; i++ {
- mdata[i] = data[i]
- }
- // Ints is known to be correct
- // because mode Sort runs after mode _Copy.
- Ints(mdata)
- case _Dither:
- for i := 0; i < n; i++ {
- mdata[i] = data[i] + i%5
- }
- }
-
- desc := fmt.Sprintf("n=%d m=%d dist=%s mode=%s", n, m, dists[dist], modes[mode])
- d := &testingData{desc: desc, t: t, data: mdata[0:n], maxswap: maxswap(n)}
- 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
- // 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 slice is sorted.
- if !IntsAreSorted(mdata) {
- t.Errorf("%s: ints not sorted", desc)
- t.Errorf("\t%v", mdata)
- t.FailNow()
- }
- }
- }
- }
- }
-}
-
-func TestSortBM(t *testing.T) {
- testBentleyMcIlroy(t, Sort, func(n int) int { return n * lg(n) * 12 / 10 })
-}
-
-func TestHeapsortBM(t *testing.T) {
- testBentleyMcIlroy(t, Heapsort, func(n int) int { return n * lg(n) * 12 / 10 })
-}
-
-func TestStableBM(t *testing.T) {
- testBentleyMcIlroy(t, Stable, func(n int) int { return n * lg(n) * lg(n) / 3 })
-}
-
-// This is based on the "antiquicksort" implementation by M. Douglas McIlroy.
-// See http://www.cs.dartmouth.edu/~doug/mdmspe.pdf for more info.
-type adversaryTestingData struct {
- data []int
- keys map[int]int
- candidate int
-}
-
-func (d *adversaryTestingData) Len() int { return len(d.data) }
-
-func (d *adversaryTestingData) Less(i, j int) bool {
- if _, present := d.keys[i]; !present {
- if _, present := d.keys[j]; !present {
- if i == d.candidate {
- d.keys[i] = len(d.keys)
- } else {
- d.keys[j] = len(d.keys)
- }
- }
- }
-
- if _, present := d.keys[i]; !present {
- d.candidate = i
- return false
- }
- if _, present := d.keys[j]; !present {
- d.candidate = j
- return true
- }
-
- return d.keys[i] >= d.keys[j]
-}
-
-func (d *adversaryTestingData) Swap(i, j int) {
- d.data[i], d.data[j] = d.data[j], d.data[i]
-}
-
-func TestAdversary(t *testing.T) {
- const size = 100
- data := make([]int, size)
- for i := 0; i < size; i++ {
- data[i] = i
- }
-
- d := &adversaryTestingData{data, make(map[int]int), 0}
- Sort(d) // This should degenerate to heapsort.
-}
-
-func TestStableInts(t *testing.T) {
- data := ints
- Stable(IntSlice(data[0:]))
- if !IntsAreSorted(data[0:]) {
- t.Errorf("nsorted %v\n got %v", ints, data)
- }
-}
-
-type intPairs []struct {
- a, b int
-}
-
-// IntPairs compare on a only.
-func (d intPairs) Len() int { return len(d) }
-func (d intPairs) Less(i, j int) bool { return d[i].a < d[j].a }
-func (d intPairs) Swap(i, j int) { d[i], d[j] = d[j], d[i] }
-
-// Record initial order in B.
-func (d intPairs) initB() {
- for i := range d {
- d[i].b = i
- }
-}
-
-// InOrder checks if a-equal elements were not reordered.
-func (d intPairs) inOrder() bool {
- lastA, lastB := -1, 0
- for i := 0; i < len(d); i++ {
- if lastA != d[i].a {
- lastA = d[i].a
- lastB = d[i].b
- continue
- }
- if d[i].b <= lastB {
- return false
- }
- lastB = d[i].b
- }
- return true
-}
-
-func TestStability(t *testing.T) {
- n, m := 100000, 1000
- if testing.Short() {
- n, m = 1000, 100
- }
- data := make(intPairs, n)
-
- // random distribution
- for i := 0; i < len(data); i++ {
- data[i].a = rand.Intn(m)
- }
- if IsSorted(data) {
- t.Fatalf("terrible rand.rand")
- }
- data.initB()
- Stable(data)
- if !IsSorted(data) {
- t.Errorf("Stable didn't sort %d ints", n)
- }
- if !data.inOrder() {
- t.Errorf("Stable wasn't stable on %d ints", n)
- }
-
- // already sorted
- data.initB()
- Stable(data)
- if !IsSorted(data) {
- t.Errorf("Stable shuffeled sorted %d ints (order)", n)
- }
- if !data.inOrder() {
- t.Errorf("Stable shuffeled sorted %d ints (stability)", n)
- }
-
- // sorted reversed
- for i := 0; i < len(data); i++ {
- data[i].a = len(data) - i
- }
- data.initB()
- Stable(data)
- if !IsSorted(data) {
- t.Errorf("Stable didn't sort %d ints", n)
- }
- if !data.inOrder() {
- t.Errorf("Stable wasn't stable on %d ints", n)
- }
-}
-
-var countOpsSizes = []int{1e2, 3e2, 1e3, 3e3, 1e4, 3e4, 1e5, 3e5, 1e6}
-
-func countOps(t *testing.T, algo func(Interface), name string) {
- sizes := countOpsSizes
- if testing.Short() {
- sizes = sizes[:5]
- }
- if !testing.Verbose() {
- t.Skip("Counting skipped as non-verbose mode.")
- }
- for _, n := range sizes {
- td := testingData{
- desc: name,
- t: t,
- data: make([]int, n),
- maxswap: 1<<31 - 1,
- }
- for i := 0; i < n; i++ {
- td.data[i] = rand.Intn(n / 5)
- }
- algo(&td)
- t.Logf("%s %8d elements: %11d Swap, %10d Less", name, n, td.nswap, td.ncmp)
- }
-}
-
-func TestCountStableOps(t *testing.T) { countOps(t, Stable, "Stable") }
-func TestCountSortOps(t *testing.T) { countOps(t, Sort, "Sort ") }
-
-func bench(b *testing.B, size int, algo func(Interface), name string) {
- b.StopTimer()
- data := make(intPairs, size)
- x := ^uint32(0)
- for i := 0; i < b.N; i++ {
- for n := size - 3; n <= size+3; n++ {
- for i := 0; i < len(data); i++ {
- x += x
- x ^= 1
- if int32(x) < 0 {
- x ^= 0x88888eef
- }
- data[i].a = int(x % uint32(n/5))
- }
- data.initB()
- b.StartTimer()
- algo(data)
- b.StopTimer()
- if !IsSorted(data) {
- b.Errorf("%s did not sort %d ints", name, n)
- }
- if name == "Stable" && !data.inOrder() {
- b.Errorf("%s unstable on %d ints", name, n)
- }
- }
- }
-}
-
-func BenchmarkSort1e2(b *testing.B) { bench(b, 1e2, Sort, "Sort") }
-func BenchmarkStable1e2(b *testing.B) { bench(b, 1e2, Stable, "Stable") }
-func BenchmarkSort1e4(b *testing.B) { bench(b, 1e4, Sort, "Sort") }
-func BenchmarkStable1e4(b *testing.B) { bench(b, 1e4, Stable, "Stable") }
-func BenchmarkSort1e6(b *testing.B) { bench(b, 1e6, Sort, "Sort") }
-func BenchmarkStable1e6(b *testing.B) { bench(b, 1e6, Stable, "Stable") }
generated by cgit v1.2.3 (git 2.39.1) at 2025-05-01 19:01:44 +0000