blob: fe176504061aa9314986f6c4429ecbcf344877dd (
plain)
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
|
package main
import (
"math/rand"
"sort"
)
// floor of log(x) (i.e MSB for positive integers)
func Log(x int64) int64 {
var r int64 = 0
for ; x > 1; x >>= 1 {
r++
}
return r
}
// squared exponentiation
func Pow(x int64, n int64) int64 {
var r int64 = 1
for i := n; i > 0; i >>= 1 {
if i&1 == 1 {
r *= x
}
x *= x
}
return r
}
// convert BFS order to DF-post-order, dark magic
func Post(size int64, height int64, id int64) int64 {
id += 1
s := int64(1) << uint64(height-Log(id)) // size of the substree rooted at id
r := s - 2
for ; id > 1; id >>= 1 {
if id&1 == 1 { // right child
r += s - 1
}
s <<= 1
}
return r
}
func Shuffle(data sort.Interface) {
var j int
for i := data.Len() - 1; i > 0; i-- {
j = rand.Intn(i + 1)
data.Swap(i, j)
}
}
|
