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)
	}
}