ordered.go

     1  // run
     2  
     3  // Copyright 2021 The Go Authors. All rights reserved.
     4  // Use of this source code is governed by a BSD-style
     5  // license that can be found in the LICENSE file.
     6  
     7  package main
     8  
     9  import (
    10  	"fmt"
    11  	"math"
    12  	"sort"
    13  )
    14  
    15  type Ordered interface {
    16  	~int | ~int8 | ~int16 | ~int32 | ~int64 |
    17  		~uint | ~uint8 | ~uint16 | ~uint32 | ~uint64 | ~uintptr |
    18  		~float32 | ~float64 |
    19  		~string
    20  }
    21  
    22  type orderedSlice[Elem Ordered] []Elem
    23  
    24  func (s orderedSlice[Elem]) Len() int { return len(s) }
    25  func (s orderedSlice[Elem]) Less(i, j int) bool {
    26  	if s[i] < s[j] {
    27  		return true
    28  	}
    29  	isNaN := func(f Elem) bool { return f != f }
    30  	if isNaN(s[i]) && !isNaN(s[j]) {
    31  		return true
    32  	}
    33  	return false
    34  }
    35  func (s orderedSlice[Elem]) Swap(i, j int) { s[i], s[j] = s[j], s[i] }
    36  
    37  func _OrderedSlice[Elem Ordered](s []Elem) {
    38  	sort.Sort(orderedSlice[Elem](s))
    39  }
    40  
    41  var ints = []int{74, 59, 238, -784, 9845, 959, 905, 0, 0, 42, 7586, -5467984, 7586}
    42  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}
    43  var strings = []string{"", "Hello", "foo", "bar", "foo", "f00", "%*&^*&^&", "***"}
    44  
    45  func TestSortOrderedInts() bool {
    46  	return testOrdered("ints", ints, sort.Ints)
    47  }
    48  
    49  func TestSortOrderedFloat64s() bool {
    50  	return testOrdered("float64s", float64s, sort.Float64s)
    51  }
    52  
    53  func TestSortOrderedStrings() bool {
    54  	return testOrdered("strings", strings, sort.Strings)
    55  }
    56  
    57  func testOrdered[Elem Ordered](name string, s []Elem, sorter func([]Elem)) bool {
    58  	s1 := make([]Elem, len(s))
    59  	copy(s1, s)
    60  	s2 := make([]Elem, len(s))
    61  	copy(s2, s)
    62  	_OrderedSlice(s1)
    63  	sorter(s2)
    64  	ok := true
    65  	if !sliceEq(s1, s2) {
    66  		fmt.Printf("%s: got %v, want %v", name, s1, s2)
    67  		ok = false
    68  	}
    69  	for i := len(s1) - 1; i > 0; i-- {
    70  		if s1[i] < s1[i-1] {
    71  			fmt.Printf("%s: element %d (%v) < element %d (%v)", name, i, s1[i], i-1, s1[i-1])
    72  			ok = false
    73  		}
    74  	}
    75  	return ok
    76  }
    77  
    78  func sliceEq[Elem Ordered](s1, s2 []Elem) bool {
    79  	for i, v1 := range s1 {
    80  		v2 := s2[i]
    81  		if v1 != v2 {
    82  			isNaN := func(f Elem) bool { return f != f }
    83  			if !isNaN(v1) || !isNaN(v2) {
    84  				return false
    85  			}
    86  		}
    87  	}
    88  	return true
    89  }
    90  
    91  func main() {
    92  	if !TestSortOrderedInts() || !TestSortOrderedFloat64s() || !TestSortOrderedStrings() {
    93  		panic("failure")
    94  	}
    95  }
    96
View as plain text