hashcode2020/sorts.go at master · ethanjjjjjjj/hashcode2020 · GitHub

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
package main

func radixSortBooksNoGo(books []Book, i int) []Book {
	if i < 0 {
		return books
	}
	var ones = make([]Book, 0)
	var zeros = make([]Book, 0)
	for _, n := range books {
		if (n.bookID>>i)&0x1 == 0x1 {
			ones = append(ones, n)
		} else {
			zeros = append(zeros, n)
		}
	}
	if i%8 == 0 {
		c1 := make(chan []Book)
		c2 := make(chan []Book)
		go radixSortBooks(ones, i-1, c1)
		go radixSortBooks(zeros, i-1, c2)
		return append(<-c1, (<-c2)...)
	} else {
		ones = radixSortBooksNoGo(ones, i-1)
		zeros = radixSortBooksNoGo(zeros, i-1)
		return append(ones, zeros...)
	}
}

func radixSortBooks(books []Book, i int, out chan []Book) {
	if i < 0 {
		out <- books
		return
	}
	var ones = make([]Book, 0)
	var zeros = make([]Book, 0)
	for _, n := range books {
		if (n.bookID>>i)&0x1 == 0x1 {
			ones = append(ones, n)
		} else {
			zeros = append(zeros, n)
		}
	}
	if i%8 == 0 {
		c1 := make(chan []Book)
		c2 := make(chan []Book)
		go radixSortBooks(ones, i-1, c1)
		go radixSortBooks(zeros, i-1, c2)
		out <- append(<-c1, (<-c2)...)
	} else {
		ones = radixSortBooksNoGo(ones, i-1)
		zeros = radixSortBooksNoGo(zeros, i-1)
		out <- append(ones, zeros...)
	}
}

func radixSortLibrariesNoGo(libraries []Library, i int) []Library {
	if i < 0 {
		return libraries
	}
	var ones = make([]Library, 0)
	var zeros = make([]Library, 0)
	for _, n := range libraries {
		if (n.sumScore>>i)&0x1 == 0x1 {
			ones = append(ones, n)
		} else {
			zeros = append(zeros, n)
		}
	}
	if i%8 == 0 {
		c1 := make(chan []Library)
		c2 := make(chan []Library)
		go radixSortLibraries(ones, i-1, c1)
		go radixSortLibraries(zeros, i-1, c2)
		return append(<-c1, (<-c2)...)
	} else {
		ones = radixSortLibrariesNoGo(ones, i-1)
		zeros = radixSortLibrariesNoGo(zeros, i-1)
		return append(ones, zeros...)
	}
}

func radixSortLibraries(libraries []Library, i int, out chan []Library) {
	if i < 0 {
		out <- libraries
		return
	}
	var ones = make([]Library, 0)
	var zeros = make([]Library, 0)
	for _, n := range libraries {
		if (n.sumScore>>i)&0x1 == 0x1 {
			ones = append(ones, n)
		} else {
			zeros = append(zeros, n)
		}
	}
	if i%8 == 0 {
		c1 := make(chan []Library)
		c2 := make(chan []Library)
		go radixSortLibraries(ones, i-1, c1)
		go radixSortLibraries(zeros, i-1, c2)
		out <- append(<-c1, (<-c2)...)
	} else {
		ones = radixSortLibrariesNoGo(ones, i-1)
		zeros = radixSortLibrariesNoGo(zeros, i-1)
		out <- append(ones, zeros...)
	}
}