From 7943430749a22e6f26aa16ca2c48e97e9277998f Mon Sep 17 00:00:00 2001
From: Thibaut Horel <thibaut.horel@gmail.com>
Date: Wed, 4 May 2016 15:54:19 -0400
Subject: Initial commit

---
 utils.go | 36 ++++++++++++++++++++++++++++++++++++
 1 file changed, 36 insertions(+)
 create mode 100644 utils.go

(limited to 'utils.go')

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
+}
-- 
cgit v1.2.3-70-g09d2