a geicko-2 based round robin ranking system designed to test c++ battleship submissions
battleship.dunkirk.sh
dunkirk.sh
1// Copyright 2021 The Go Authors. All rights reserved.
2// Use of this source code is governed by a BSD-style
3// license that can be found in the LICENSE file.
4
5// Package slices defines various functions useful with slices of any type.
6package slices
7
8import (
9 "unsafe"
10
11 "golang.org/x/exp/constraints"
12)
13
14// Equal reports whether two slices are equal: the same length and all
15// elements equal. If the lengths are different, Equal returns false.
16// Otherwise, the elements are compared in increasing index order, and the
17// comparison stops at the first unequal pair.
18// Floating point NaNs are not considered equal.
19func Equal[S ~[]E, E comparable](s1, s2 S) bool {
20 if len(s1) != len(s2) {
21 return false
22 }
23 for i := range s1 {
24 if s1[i] != s2[i] {
25 return false
26 }
27 }
28 return true
29}
30
31// EqualFunc reports whether two slices are equal using an equality
32// function on each pair of elements. If the lengths are different,
33// EqualFunc returns false. Otherwise, the elements are compared in
34// increasing index order, and the comparison stops at the first index
35// for which eq returns false.
36func EqualFunc[S1 ~[]E1, S2 ~[]E2, E1, E2 any](s1 S1, s2 S2, eq func(E1, E2) bool) bool {
37 if len(s1) != len(s2) {
38 return false
39 }
40 for i, v1 := range s1 {
41 v2 := s2[i]
42 if !eq(v1, v2) {
43 return false
44 }
45 }
46 return true
47}
48
49// Compare compares the elements of s1 and s2, using [cmp.Compare] on each pair
50// of elements. The elements are compared sequentially, starting at index 0,
51// until one element is not equal to the other.
52// The result of comparing the first non-matching elements is returned.
53// If both slices are equal until one of them ends, the shorter slice is
54// considered less than the longer one.
55// The result is 0 if s1 == s2, -1 if s1 < s2, and +1 if s1 > s2.
56func Compare[S ~[]E, E constraints.Ordered](s1, s2 S) int {
57 for i, v1 := range s1 {
58 if i >= len(s2) {
59 return +1
60 }
61 v2 := s2[i]
62 if c := cmpCompare(v1, v2); c != 0 {
63 return c
64 }
65 }
66 if len(s1) < len(s2) {
67 return -1
68 }
69 return 0
70}
71
72// CompareFunc is like [Compare] but uses a custom comparison function on each
73// pair of elements.
74// The result is the first non-zero result of cmp; if cmp always
75// returns 0 the result is 0 if len(s1) == len(s2), -1 if len(s1) < len(s2),
76// and +1 if len(s1) > len(s2).
77func CompareFunc[S1 ~[]E1, S2 ~[]E2, E1, E2 any](s1 S1, s2 S2, cmp func(E1, E2) int) int {
78 for i, v1 := range s1 {
79 if i >= len(s2) {
80 return +1
81 }
82 v2 := s2[i]
83 if c := cmp(v1, v2); c != 0 {
84 return c
85 }
86 }
87 if len(s1) < len(s2) {
88 return -1
89 }
90 return 0
91}
92
93// Index returns the index of the first occurrence of v in s,
94// or -1 if not present.
95func Index[S ~[]E, E comparable](s S, v E) int {
96 for i := range s {
97 if v == s[i] {
98 return i
99 }
100 }
101 return -1
102}
103
104// IndexFunc returns the first index i satisfying f(s[i]),
105// or -1 if none do.
106func IndexFunc[S ~[]E, E any](s S, f func(E) bool) int {
107 for i := range s {
108 if f(s[i]) {
109 return i
110 }
111 }
112 return -1
113}
114
115// Contains reports whether v is present in s.
116func Contains[S ~[]E, E comparable](s S, v E) bool {
117 return Index(s, v) >= 0
118}
119
120// ContainsFunc reports whether at least one
121// element e of s satisfies f(e).
122func ContainsFunc[S ~[]E, E any](s S, f func(E) bool) bool {
123 return IndexFunc(s, f) >= 0
124}
125
126// Insert inserts the values v... into s at index i,
127// returning the modified slice.
128// The elements at s[i:] are shifted up to make room.
129// In the returned slice r, r[i] == v[0],
130// and r[i+len(v)] == value originally at r[i].
131// Insert panics if i is out of range.
132// This function is O(len(s) + len(v)).
133func Insert[S ~[]E, E any](s S, i int, v ...E) S {
134 m := len(v)
135 if m == 0 {
136 return s
137 }
138 n := len(s)
139 if i == n {
140 return append(s, v...)
141 }
142 if n+m > cap(s) {
143 // Use append rather than make so that we bump the size of
144 // the slice up to the next storage class.
145 // This is what Grow does but we don't call Grow because
146 // that might copy the values twice.
147 s2 := append(s[:i], make(S, n+m-i)...)
148 copy(s2[i:], v)
149 copy(s2[i+m:], s[i:])
150 return s2
151 }
152 s = s[:n+m]
153
154 // before:
155 // s: aaaaaaaabbbbccccccccdddd
156 // ^ ^ ^ ^
157 // i i+m n n+m
158 // after:
159 // s: aaaaaaaavvvvbbbbcccccccc
160 // ^ ^ ^ ^
161 // i i+m n n+m
162 //
163 // a are the values that don't move in s.
164 // v are the values copied in from v.
165 // b and c are the values from s that are shifted up in index.
166 // d are the values that get overwritten, never to be seen again.
167
168 if !overlaps(v, s[i+m:]) {
169 // Easy case - v does not overlap either the c or d regions.
170 // (It might be in some of a or b, or elsewhere entirely.)
171 // The data we copy up doesn't write to v at all, so just do it.
172
173 copy(s[i+m:], s[i:])
174
175 // Now we have
176 // s: aaaaaaaabbbbbbbbcccccccc
177 // ^ ^ ^ ^
178 // i i+m n n+m
179 // Note the b values are duplicated.
180
181 copy(s[i:], v)
182
183 // Now we have
184 // s: aaaaaaaavvvvbbbbcccccccc
185 // ^ ^ ^ ^
186 // i i+m n n+m
187 // That's the result we want.
188 return s
189 }
190
191 // The hard case - v overlaps c or d. We can't just shift up
192 // the data because we'd move or clobber the values we're trying
193 // to insert.
194 // So instead, write v on top of d, then rotate.
195 copy(s[n:], v)
196
197 // Now we have
198 // s: aaaaaaaabbbbccccccccvvvv
199 // ^ ^ ^ ^
200 // i i+m n n+m
201
202 rotateRight(s[i:], m)
203
204 // Now we have
205 // s: aaaaaaaavvvvbbbbcccccccc
206 // ^ ^ ^ ^
207 // i i+m n n+m
208 // That's the result we want.
209 return s
210}
211
212// clearSlice sets all elements up to the length of s to the zero value of E.
213// We may use the builtin clear func instead, and remove clearSlice, when upgrading
214// to Go 1.21+.
215func clearSlice[S ~[]E, E any](s S) {
216 var zero E
217 for i := range s {
218 s[i] = zero
219 }
220}
221
222// Delete removes the elements s[i:j] from s, returning the modified slice.
223// Delete panics if j > len(s) or s[i:j] is not a valid slice of s.
224// Delete is O(len(s)-i), so if many items must be deleted, it is better to
225// make a single call deleting them all together than to delete one at a time.
226// Delete zeroes the elements s[len(s)-(j-i):len(s)].
227func Delete[S ~[]E, E any](s S, i, j int) S {
228 _ = s[i:j:len(s)] // bounds check
229
230 if i == j {
231 return s
232 }
233
234 oldlen := len(s)
235 s = append(s[:i], s[j:]...)
236 clearSlice(s[len(s):oldlen]) // zero/nil out the obsolete elements, for GC
237 return s
238}
239
240// DeleteFunc removes any elements from s for which del returns true,
241// returning the modified slice.
242// DeleteFunc zeroes the elements between the new length and the original length.
243func DeleteFunc[S ~[]E, E any](s S, del func(E) bool) S {
244 i := IndexFunc(s, del)
245 if i == -1 {
246 return s
247 }
248 // Don't start copying elements until we find one to delete.
249 for j := i + 1; j < len(s); j++ {
250 if v := s[j]; !del(v) {
251 s[i] = v
252 i++
253 }
254 }
255 clearSlice(s[i:]) // zero/nil out the obsolete elements, for GC
256 return s[:i]
257}
258
259// Replace replaces the elements s[i:j] by the given v, and returns the
260// modified slice. Replace panics if s[i:j] is not a valid slice of s.
261// When len(v) < (j-i), Replace zeroes the elements between the new length and the original length.
262func Replace[S ~[]E, E any](s S, i, j int, v ...E) S {
263 _ = s[i:j] // verify that i:j is a valid subslice
264
265 if i == j {
266 return Insert(s, i, v...)
267 }
268 if j == len(s) {
269 return append(s[:i], v...)
270 }
271
272 tot := len(s[:i]) + len(v) + len(s[j:])
273 if tot > cap(s) {
274 // Too big to fit, allocate and copy over.
275 s2 := append(s[:i], make(S, tot-i)...) // See Insert
276 copy(s2[i:], v)
277 copy(s2[i+len(v):], s[j:])
278 return s2
279 }
280
281 r := s[:tot]
282
283 if i+len(v) <= j {
284 // Easy, as v fits in the deleted portion.
285 copy(r[i:], v)
286 if i+len(v) != j {
287 copy(r[i+len(v):], s[j:])
288 }
289 clearSlice(s[tot:]) // zero/nil out the obsolete elements, for GC
290 return r
291 }
292
293 // We are expanding (v is bigger than j-i).
294 // The situation is something like this:
295 // (example has i=4,j=8,len(s)=16,len(v)=6)
296 // s: aaaaxxxxbbbbbbbbyy
297 // ^ ^ ^ ^
298 // i j len(s) tot
299 // a: prefix of s
300 // x: deleted range
301 // b: more of s
302 // y: area to expand into
303
304 if !overlaps(r[i+len(v):], v) {
305 // Easy, as v is not clobbered by the first copy.
306 copy(r[i+len(v):], s[j:])
307 copy(r[i:], v)
308 return r
309 }
310
311 // This is a situation where we don't have a single place to which
312 // we can copy v. Parts of it need to go to two different places.
313 // We want to copy the prefix of v into y and the suffix into x, then
314 // rotate |y| spots to the right.
315 //
316 // v[2:] v[:2]
317 // | |
318 // s: aaaavvvvbbbbbbbbvv
319 // ^ ^ ^ ^
320 // i j len(s) tot
321 //
322 // If either of those two destinations don't alias v, then we're good.
323 y := len(v) - (j - i) // length of y portion
324
325 if !overlaps(r[i:j], v) {
326 copy(r[i:j], v[y:])
327 copy(r[len(s):], v[:y])
328 rotateRight(r[i:], y)
329 return r
330 }
331 if !overlaps(r[len(s):], v) {
332 copy(r[len(s):], v[:y])
333 copy(r[i:j], v[y:])
334 rotateRight(r[i:], y)
335 return r
336 }
337
338 // Now we know that v overlaps both x and y.
339 // That means that the entirety of b is *inside* v.
340 // So we don't need to preserve b at all; instead we
341 // can copy v first, then copy the b part of v out of
342 // v to the right destination.
343 k := startIdx(v, s[j:])
344 copy(r[i:], v)
345 copy(r[i+len(v):], r[i+k:])
346 return r
347}
348
349// Clone returns a copy of the slice.
350// The elements are copied using assignment, so this is a shallow clone.
351func Clone[S ~[]E, E any](s S) S {
352 // Preserve nil in case it matters.
353 if s == nil {
354 return nil
355 }
356 return append(S([]E{}), s...)
357}
358
359// Compact replaces consecutive runs of equal elements with a single copy.
360// This is like the uniq command found on Unix.
361// Compact modifies the contents of the slice s and returns the modified slice,
362// which may have a smaller length.
363// Compact zeroes the elements between the new length and the original length.
364func Compact[S ~[]E, E comparable](s S) S {
365 if len(s) < 2 {
366 return s
367 }
368 i := 1
369 for k := 1; k < len(s); k++ {
370 if s[k] != s[k-1] {
371 if i != k {
372 s[i] = s[k]
373 }
374 i++
375 }
376 }
377 clearSlice(s[i:]) // zero/nil out the obsolete elements, for GC
378 return s[:i]
379}
380
381// CompactFunc is like [Compact] but uses an equality function to compare elements.
382// For runs of elements that compare equal, CompactFunc keeps the first one.
383// CompactFunc zeroes the elements between the new length and the original length.
384func CompactFunc[S ~[]E, E any](s S, eq func(E, E) bool) S {
385 if len(s) < 2 {
386 return s
387 }
388 i := 1
389 for k := 1; k < len(s); k++ {
390 if !eq(s[k], s[k-1]) {
391 if i != k {
392 s[i] = s[k]
393 }
394 i++
395 }
396 }
397 clearSlice(s[i:]) // zero/nil out the obsolete elements, for GC
398 return s[:i]
399}
400
401// Grow increases the slice's capacity, if necessary, to guarantee space for
402// another n elements. After Grow(n), at least n elements can be appended
403// to the slice without another allocation. If n is negative or too large to
404// allocate the memory, Grow panics.
405func Grow[S ~[]E, E any](s S, n int) S {
406 if n < 0 {
407 panic("cannot be negative")
408 }
409 if n -= cap(s) - len(s); n > 0 {
410 // TODO(https://go.dev/issue/53888): Make using []E instead of S
411 // to workaround a compiler bug where the runtime.growslice optimization
412 // does not take effect. Revert when the compiler is fixed.
413 s = append([]E(s)[:cap(s)], make([]E, n)...)[:len(s)]
414 }
415 return s
416}
417
418// Clip removes unused capacity from the slice, returning s[:len(s):len(s)].
419func Clip[S ~[]E, E any](s S) S {
420 return s[:len(s):len(s)]
421}
422
423// Rotation algorithm explanation:
424//
425// rotate left by 2
426// start with
427// 0123456789
428// split up like this
429// 01 234567 89
430// swap first 2 and last 2
431// 89 234567 01
432// join first parts
433// 89234567 01
434// recursively rotate first left part by 2
435// 23456789 01
436// join at the end
437// 2345678901
438//
439// rotate left by 8
440// start with
441// 0123456789
442// split up like this
443// 01 234567 89
444// swap first 2 and last 2
445// 89 234567 01
446// join last parts
447// 89 23456701
448// recursively rotate second part left by 6
449// 89 01234567
450// join at the end
451// 8901234567
452
453// TODO: There are other rotate algorithms.
454// This algorithm has the desirable property that it moves each element exactly twice.
455// The triple-reverse algorithm is simpler and more cache friendly, but takes more writes.
456// The follow-cycles algorithm can be 1-write but it is not very cache friendly.
457
458// rotateLeft rotates b left by n spaces.
459// s_final[i] = s_orig[i+r], wrapping around.
460func rotateLeft[E any](s []E, r int) {
461 for r != 0 && r != len(s) {
462 if r*2 <= len(s) {
463 swap(s[:r], s[len(s)-r:])
464 s = s[:len(s)-r]
465 } else {
466 swap(s[:len(s)-r], s[r:])
467 s, r = s[len(s)-r:], r*2-len(s)
468 }
469 }
470}
471func rotateRight[E any](s []E, r int) {
472 rotateLeft(s, len(s)-r)
473}
474
475// swap swaps the contents of x and y. x and y must be equal length and disjoint.
476func swap[E any](x, y []E) {
477 for i := 0; i < len(x); i++ {
478 x[i], y[i] = y[i], x[i]
479 }
480}
481
482// overlaps reports whether the memory ranges a[0:len(a)] and b[0:len(b)] overlap.
483func overlaps[E any](a, b []E) bool {
484 if len(a) == 0 || len(b) == 0 {
485 return false
486 }
487 elemSize := unsafe.Sizeof(a[0])
488 if elemSize == 0 {
489 return false
490 }
491 // TODO: use a runtime/unsafe facility once one becomes available. See issue 12445.
492 // Also see crypto/internal/alias/alias.go:AnyOverlap
493 return uintptr(unsafe.Pointer(&a[0])) <= uintptr(unsafe.Pointer(&b[len(b)-1]))+(elemSize-1) &&
494 uintptr(unsafe.Pointer(&b[0])) <= uintptr(unsafe.Pointer(&a[len(a)-1]))+(elemSize-1)
495}
496
497// startIdx returns the index in haystack where the needle starts.
498// prerequisite: the needle must be aliased entirely inside the haystack.
499func startIdx[E any](haystack, needle []E) int {
500 p := &needle[0]
501 for i := range haystack {
502 if p == &haystack[i] {
503 return i
504 }
505 }
506 // TODO: what if the overlap is by a non-integral number of Es?
507 panic("needle not found")
508}
509
510// Reverse reverses the elements of the slice in place.
511func Reverse[S ~[]E, E any](s S) {
512 for i, j := 0, len(s)-1; i < j; i, j = i+1, j-1 {
513 s[i], s[j] = s[j], s[i]
514 }
515}