func parent(index int64) int64 {
	return index >> 1
}
parent returns the index of the parent node in the parent level of the tree.
package inmemory
import (
	"errors"
	"fmt"
	"github.com/google/trillian/merkle/hashers"
)
type TreeEntry struct {
	hash []byte
}
func (t TreeEntry) Hash() []byte {
	var newSlice []byte
	return t.HashInto(newSlice)
}
func (t TreeEntry) HashInto(dest []byte) []byte {
	dest = dest[:0]  
	dest = append(dest, t.hash...)
	return dest
}
type TreeEntryDescriptor struct {
	Value  TreeEntry
	XCoord int64  
	YCoord int64  
}
type MerkleTree struct {
	tree            [][]TreeEntry
	leavesProcessed int64
	levelCount      int64
	hasher          hashers.LogHasher
}
func isPowerOfTwoPlusOne(leafCount int64) bool {
	if leafCount == 0 {
		return false
	}
	if leafCount == 1 {
		return true
	}
	return ((leafCount - 1) & (leafCount - 2)) == 0
}
func sibling(leaf int64) int64 {
	if isRightChild(leaf) {
		return leaf - 1
	}
	return leaf + 1
}
func NewMerkleTree(hasher hashers.LogHasher) *MerkleTree {
	return &MerkleTree{hasher: hasher}
}
func (mt *MerkleTree) LeafHash(leaf int64) []byte {
	if leaf == 0 || leaf > mt.LeafCount() {
		return nil
	}
	return mt.tree[0][leaf-1].hash
}
func (mt *MerkleTree) NodeCount(level int64) int64 {
	if mt.lazyLevelCount() <= level {
		panic(fmt.Errorf("lazyLevelCount <= level in nodeCount: %d", mt.lazyLevelCount()))
	}
	return int64(len(mt.tree[level]))
}
func (mt *MerkleTree) LevelCount() int64 {
	return mt.levelCount
}
func (mt *MerkleTree) lazyLevelCount() int64 {
	return int64(len(mt.tree))
}
func (mt *MerkleTree) LeafCount() int64 {
	if len(mt.tree) == 0 {
		return 0
	}
	return mt.NodeCount(0)
}
func (mt *MerkleTree) root() TreeEntry {
	lastLevel := len(mt.tree) - 1
	if len(mt.tree[lastLevel]) > 1 {
		panic(fmt.Errorf("found multiple nodes in root: %d", len(mt.tree[lastLevel])))
	}
	return mt.tree[lastLevel][0]
}
func (mt *MerkleTree) lastNode(level int64) TreeEntry {
	levelNodes := mt.NodeCount(level)
	if levelNodes < 1 {
		panic(fmt.Errorf("no nodes at level %d in lastNode", level))
	}
	return mt.tree[level][levelNodes-1]
}
func (mt *MerkleTree) addLevel() {
	mt.tree = append(mt.tree, []TreeEntry{})
}
func (mt *MerkleTree) pushBack(level int64, treeEntry TreeEntry) {
	if mt.lazyLevelCount() <= level {
		panic(fmt.Errorf("lazyLevelCount <= level in pushBack: %d", mt.lazyLevelCount()))
	}
	mt.tree[level] = append(mt.tree[level], treeEntry)
}
func (mt *MerkleTree) popBack(level int64) {
	if len(mt.tree[level]) < 1 {
		panic(errors.New("no nodes to pop in popBack"))
	}
	mt.tree[level] = mt.tree[level][:len(mt.tree[level])-1]
}
func (mt *MerkleTree) AddLeaf(leafData []byte) (int64, TreeEntry) {
	leafHash := mt.hasher.HashLeaf(leafData)
	leafCount, treeEntry := mt.addLeafHash(leafHash)
	return leafCount, treeEntry
}
func (mt *MerkleTree) addLeafHash(leafData []byte) (int64, TreeEntry) {
	treeEntry := TreeEntry{}
	treeEntry.hash = leafData
	if mt.lazyLevelCount() == 0 {
		mt.addLevel()
		mt.leavesProcessed = 1
	}
	mt.pushBack(0, treeEntry)
	leafCount := mt.LeafCount()
	if isPowerOfTwoPlusOne(leafCount) {
		mt.levelCount++
	}
	return leafCount, treeEntry
}
func (mt *MerkleTree) CurrentRoot() TreeEntry {
	return mt.RootAtSnapshot(mt.LeafCount())
}
func (mt *MerkleTree) RootAtSnapshot(snapshot int64) TreeEntry {
	if snapshot == 0 {
		return TreeEntry{mt.hasher.EmptyRoot()}
	}
	if snapshot > mt.LeafCount() {
		return TreeEntry{nil}
	}
	if snapshot >= mt.leavesProcessed {
		return mt.updateToSnapshot(snapshot)
	}
	return mt.recomputePastSnapshot(snapshot, 0, nil)
}
func (mt *MerkleTree) updateToSnapshot(snapshot int64) TreeEntry {
	if snapshot == 0 {
		return TreeEntry{mt.hasher.EmptyRoot()}
	}
	if snapshot == 1 {
		return mt.tree[0][0]
	}
	if snapshot == mt.leavesProcessed {
		return mt.root()
	}
	if snapshot > mt.LeafCount() {
		panic(errors.New("snapshot size > leaf count in updateToSnapshot"))
	}
	if snapshot <= mt.leavesProcessed {
		panic(errors.New("snapshot size <= leavesProcessed in updateToSnapshot"))
	}
	level := int64(0)
	firstNode := mt.leavesProcessed
	lastNode := snapshot - 1
	for lastNode != 0 {
		if mt.lazyLevelCount() <= level+1 {
			mt.addLevel()
		} else if mt.NodeCount(level+1) == parent(firstNode)+1 {
			mt.popBack(level + 1)
		}
		for j := firstNode &^ 1; j < lastNode; j += 2 {
			mt.pushBack(level+1, TreeEntry{mt.hasher.HashChildren(mt.tree[level][j].hash, mt.tree[level][j+1].hash)})
		}
		if !isRightChild(lastNode) {
			mt.pushBack(level+1, mt.tree[level][lastNode])
		}
		firstNode = parent(firstNode)
		lastNode = parent(lastNode)
		level++
	}
	mt.leavesProcessed = snapshot
	return mt.root()
}
func (mt *MerkleTree) recomputePastSnapshot(snapshot int64, nodeLevel int64, node *TreeEntry) TreeEntry {
	level := int64(0)
	lastNode := snapshot - 1
	if snapshot == mt.leavesProcessed {
		if node != nil && mt.lazyLevelCount() > nodeLevel {
			if nodeLevel > 0 {
				*node = mt.lastNode(nodeLevel)
			} else {
				*node = mt.tree[nodeLevel][lastNode]
			}
		}
		return mt.root()
	}
	if snapshot >= mt.leavesProcessed {
		panic(errors.New("snapshot size >= leavesProcessed in recomputePastSnapshot"))
	}
	for isRightChild(lastNode) {
		if node != nil && nodeLevel == level {
			*node = mt.tree[level][lastNode]
		}
		lastNode = parent(lastNode)
		level++
	}
	subtreeRoot := mt.tree[level][lastNode]
	if node != nil && nodeLevel == level {
		*node = subtreeRoot
	}
	for lastNode != 0 {
		if isRightChild(lastNode) {
			subtreeRoot = TreeEntry{mt.hasher.HashChildren(mt.tree[level][lastNode-1].hash, subtreeRoot.hash)}
		}
		lastNode = parent(lastNode)
		level++
		if node != nil && nodeLevel == level {
			*node = subtreeRoot
		}
	}
	return subtreeRoot
}
func (mt *MerkleTree) PathToCurrentRoot(leaf int64) []TreeEntryDescriptor {
	return mt.PathToRootAtSnapshot(leaf, mt.LeafCount())
}
func (mt *MerkleTree) PathToRootAtSnapshot(leaf int64, snapshot int64) []TreeEntryDescriptor {
	if leaf > snapshot || snapshot > mt.LeafCount() || leaf == 0 {
		return []TreeEntryDescriptor{}
	}
	return mt.pathFromNodeToRootAtSnapshot(leaf-1, 0, snapshot)
}
func (mt *MerkleTree) pathFromNodeToRootAtSnapshot(node int64, level int64, snapshot int64) []TreeEntryDescriptor {
	var path []TreeEntryDescriptor
	if snapshot == 0 {
		return path
	}
	lastNode := (snapshot - 1) >> uint64(level)
	if level >= mt.levelCount || node > lastNode || snapshot > mt.LeafCount() {
		return path
	}
	if snapshot > mt.leavesProcessed {
		mt.updateToSnapshot(snapshot)
	}
	for lastNode != 0 {
		sibling := sibling(node)
		if sibling < lastNode {
			path = append(path, TreeEntryDescriptor{mt.tree[level][sibling], level, sibling})
		} else if sibling == lastNode {
			var recomputeNode TreeEntry
			mt.recomputePastSnapshot(snapshot, level, &recomputeNode)
			path = append(path, TreeEntryDescriptor{recomputeNode, -level, -sibling})
		}
		node = parent(node)
		lastNode = parent(lastNode)
		level++
	}
	return path
}
func (mt *MerkleTree) SnapshotConsistency(snapshot1 int64, snapshot2 int64) []TreeEntryDescriptor {
	var proof []TreeEntryDescriptor
	if snapshot1 == 0 || snapshot1 >= snapshot2 || snapshot2 > mt.LeafCount() {
		return proof
	}
	level := int64(0)
	node := snapshot1 - 1
	for isRightChild(node) {
		node = parent(node)
		level++
	}
	if snapshot2 > mt.leavesProcessed {
		mt.updateToSnapshot(snapshot2)
	}
	if node != 0 {
		proof = append(proof, TreeEntryDescriptor{mt.tree[level][node], level, node})
	}
	path := mt.pathFromNodeToRootAtSnapshot(node, level, snapshot2)
	return append(proof, path...)
}