Imported Upstream version 1.4upstream/1.4

1 files changed, 0 insertions, 112 deletions

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) }