Initial commit

1 files changed, 36 insertions, 0 deletions

diff --git a/utils.go b/utils.go
new file mode 100644
index 0000000..513786c
--- /dev/null
+++ b/utils.go
@@ -0,0 +1,36 @@
+package main
+
+// 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
+}