File: multisort_test.go

package info (click to toggle)
golang-github-twotwotwo-sorts 0.0~git20160814.bf5c1f2-2
  • links: PTS, VCS
  • area: main
  • in suites: bookworm, sid
  • size: 172 kB
  • sloc: makefile: 2
file content (109 lines) | stat: -rw-r--r-- 3,164 bytes parent folder | download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
// Copyright 2015 Randall Farmer. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.

package sorts_test

import . "github.com/twotwotwo/sorts"
import . "github.com/twotwotwo/sorts/sortutil"
import "strconv"
import "sort"

// Helpers to sort in different ways: with the quicksort cutoff lowered or
// raised (to exercise radix code more or less), and sorting ints as uints,
// bytes or strings (to exercise those types' sort code).

// varyQSortCutoff runs a function with qSortCutoff set to 1, the default
// value, and 1e9.
func varyQSortCutoff(f func()) {
	f()
	defer SetQSortCutoff(SetQSortCutoff(1))
	f()
	SetQSortCutoff(1e9)
	f()
}

// forceRadix runs a function with qSortCutoff forced to 1
func forceRadix(f func()) {
	defer SetQSortCutoff(SetQSortCutoff(1))
	f()
}

// convertInts turns a []int of only positive numbers into a [][]byte, a
// []string, and a []uint ordered the same way, for exercising all of the
// underlying type-specific sort code.
func convertInts(a []int) ([][]byte, []string, []uint) {
	const l = 20 // length of converted number
	outSpace := make([]byte, l*len(a))
	for i := range outSpace {
		outSpace[i] = '0'
	}

	outBytes := make([][]byte, len(a))
	for i := range a {
		outBytes[i] = outSpace[l*i : l*i+l]
	}

	t := make([]byte, 20)
	for i, v := range a {
		s := strconv.AppendUint(t[:0], uint64(v), 10)
		copy(outBytes[i][l-len(s):], s)
	}

	strSpace := string(outSpace)
	outStrings := make([]string, len(a))
	for i := range a {
		outStrings[i] = strSpace[l*i : l*i+l]
	}

	outUints := make([]uint, len(a))
	for i := range outUints {
		outUints[i] = uint(a[i])
	}

	return outBytes, outStrings, outUints
}

// multiSort sorts incoming integers using integer, []byte, and string sorts.
func multiSort(a []int) {
	asBytes, asStrings, asUints := convertInts(a)
	IntSlice(a).Sort()
	BytesSlice(asBytes).Sort()
	StringSlice(asStrings).Sort()
	UintSlice(asUints).Sort()
}

// manySort sorts integers with all QSort cutoffs and all data types, saving
// the sorted ints back to a and relying on the sorted checks for the other
// sorts.  (It also throws away just tons of RAM but not sure we care.)
func manySort(a []int) {
	aBytes, aStrings, aUints := convertInts(a)

	myInts, myUints, myBytes, myStrings := IntSlice{}, UintSlice{}, BytesSlice{}, StringSlice{}
	varyQSortCutoff(func() {
		myInts = append(myInts[:0], a...)

		// make the parallel qsort extra parallel, as it were
		oldMinOffload := SetMinOffload(2)  // 1 never hits Quicksort insertionSort
		defer SetMinOffload(oldMinOffload) // in case of panic
		Quicksort(myInts)
		SetMinOffload(oldMinOffload) // for other sorts

		myInts = append(myInts[:0], a...)
		myInts.Sort()
		myBytes = append(myBytes[:0], aBytes...)
		myBytes.Sort()
		myStrings = append(myStrings[:0], aStrings...)
		myStrings.Sort()
		myUints = append(myUints[:0], aUints...)
		myUints.Sort()
	})
	// caller wants to see the sorted ints
	copy(a, myInts)
}

// manySortWrapper lets us use testBM with manySort to exercise all the sorts.
func manySortWrapper(d sort.Interface) {
	ints := d.(*testingData).data
	manySort(ints)
}