func TestMergeInBatches(t *testing.T) {
	const numNodes = uint64(220)
	const batch = uint64(13)
	tree, visit := newTree(t, numNodes)
	batches := make([]*Range, 0)
	for i := uint64(0); i < numNodes; i += batch {
		rng := factory.NewEmptyRange(i)
		tree.verifyRange(t, rng, true)
		for node := i; node < i+batch && node < numNodes; node++ {
			visit(NewNodeID(0, node), tree.leaf(node))
			if err := rng.Append(tree.leaf(node), visit); err != nil {
				t.Fatalf("Append: %v", err)
			}
			tree.verifyRange(t, rng, true)
		}
		batches = append(batches, rng)
	}
	total := factory.NewEmptyRange(0)
	for _, batch := range batches {
		if err := total.AppendRange(batch, visit); err != nil {
			t.Fatalf("AppendRange: %v", err)
		}
		tree.verifyRange(t, total, true)
	}
	tree.verifyAllVisited(t, total)
}
Build ranges [0, 13), [13, 26), ... [208,220) by appending single entries to
each. Then append those ranges one by one to [0,0), to get [0,220).
package compact
import (
	"bytes"
	"encoding/base64"
	"errors"
	"fmt"
	"math/bits"
	"math/rand"
	"reflect"
	"strings"
	"testing"
	"github.com/google/go-cmp/cmp"
	"github.com/google/trillian/merkle/rfc6962"
	"github.com/google/trillian/merkle/testonly"
	_ "github.com/golang/glog"  
)
var (
	hashChildren = rfc6962.DefaultHasher.HashChildren
	factory      = &RangeFactory{Hash: hashChildren}
)
func leafData(index uint64) []byte {
	return []byte(fmt.Sprintf("data: %d", index))
}
type treeNode struct {
	hash   []byte  
	visits int     
}
type tree struct {
	size  uint64        
	nodes [][]treeNode  
}
func newTree(t *testing.T, size uint64) (*tree, VisitFn) {
	levels := bits.Len64(size)
	nodes := make([][]treeNode, levels)
	tr := &tree{size: size, nodes: nodes}
	visit := func(id NodeID, hash []byte) {
		if err := tr.visit(id.Level, id.Index, hash); err != nil {
			t.Errorf("visit %+v: %v", id, err)
		}
	}
	for lvl := range nodes {
		nodes[lvl] = make([]treeNode, size>>uint(lvl))
	}
	for i := uint64(0); i < size; i++ {
		nodes[0][i].hash = hashLeaf(leafData(i))
	}
	for lvl := 1; lvl < levels; lvl++ {
		for i := range nodes[lvl] {
			nodes[lvl][i].hash = hashChildren(nodes[lvl-1][i*2].hash, nodes[lvl-1][i*2+1].hash)
		}
	}
	return tr, visit
}
func (tr *tree) rootHash() []byte {
	var hash []byte
	for _, level := range tr.nodes {
		if len(level)%2 == 1 {
			root := level[len(level)-1].hash
			if hash == nil {
				hash = root
			} else {
				hash = hashChildren(root, hash)
			}
		}
	}
	return hash
}
func (tr *tree) leaf(index uint64) []byte {
	return tr.nodes[0][index].hash
}
func (tr *tree) visit(level uint, index uint64, hash []byte) error {
	if level >= uint(len(tr.nodes)) || index >= uint64(len(tr.nodes[level])) {
		return errors.New("node does not exist")
	}
	tr.nodes[level][index].visits++
	if want := tr.nodes[level][index].hash; !bytes.Equal(hash, want) {
		return fmt.Errorf("hash mismatch: got %08x, want %08x", shorten(hash), shorten(want))
	}
	return nil
}
func (tr *tree) verifyRange(t *testing.T, r *Range, wantMatch bool) {
	t.Helper()
	pos := r.Begin()
	if r.End() > tr.size {
		t.Fatalf("range is too long: %d > %d", r.End(), tr.size)
	}
	left, right := Decompose(pos, r.End())
	var hashes [][]byte
	for lvl := uint(0); lvl < 64; lvl++ {
		if left&(1<<lvl) != 0 {
			hashes = append(hashes, tr.nodes[lvl][pos>>lvl].hash)
			pos += 1 << lvl
		}
	}
	for lvl := uint(63); lvl < 64; lvl-- {  
		if right&(1<<lvl) != 0 {
			hashes = append(hashes, tr.nodes[lvl][pos>>lvl].hash)
			pos += 1 << lvl
		}
	}
	if pos != r.End() {
		t.Fatalf("Decompose: range [%d,%d) is not covered; end=%d", r.Begin(), r.End(), pos)
	}
	if match := reflect.DeepEqual(r.Hashes(), hashes); match != wantMatch {
		t.Errorf("hashes match: %v, expected %v", match, wantMatch)
	}
}
func (tr *tree) verifyAllVisited(t *testing.T, r *Range) {
	t.Helper()
	if r.Begin() != 0 || r.End() != tr.size {
		t.Errorf("range mismatch: got [%d,%d), want [%d,%d)", r.Begin(), r.End(), 0, tr.size)
	}
	for lvl, level := range tr.nodes {
		for index, node := range level {
			if got, want := node.visits, 1; got != want {
				t.Errorf("Node (%d,%d) visited %d times, want %d", lvl, index, got, want)
			}
		}
	}
}
func TestAppend(t *testing.T) {
	var sizes []uint64
	for size := uint64(0); size <= 256; size++ {
		sizes = append(sizes, size)
	}
	sizes = append(sizes, 555, 1040, 5431)
	for _, size := range sizes {
		t.Run(fmt.Sprintf("size:%d", size), func(t *testing.T) {
			tree, visit := newTree(t, size)
			cr := factory.NewEmptyRange(0)
			tree.verifyRange(t, cr, true)
			for i := uint64(0); i < size; i++ {
				visit(NewNodeID(0, i), tree.leaf(i))
				if err := cr.Append(tree.leaf(i), visit); err != nil {
					t.Errorf("Append()=%v", err)
				}
				tree.verifyRange(t, cr, true)
			}
			tree.verifyAllVisited(t, cr)
		})
	}
}
func TestGoldenRanges(t *testing.T) {
	inputs := testonly.LeafInputs()
	roots := testonly.RootHashes()
	hashes := testonly.CompactTrees()
	for size, ln := 0, len(inputs); size <= ln; size++ {
		t.Run(fmt.Sprintf("size:%d", size), func(t *testing.T) {
			cr := factory.NewEmptyRange(0)
			for i := 0; i < size; i++ {
				if err := cr.Append(hashLeaf(inputs[i]), nil); err != nil {
					t.Fatalf("Append: %v", err)
				}
			}
			hash, err := cr.GetRootHash(nil)
			if err != nil {
				t.Fatalf("GetRootHash: %v", err)
			}
			if size == 0 {
				if hash != nil {
					t.Errorf("Expected nil hash, got %x", hash)
				}
				hash = rfc6962.DefaultHasher.EmptyRoot()
			}
			if want := roots[size]; !bytes.Equal(hash, want) {
				t.Errorf("root hash mismatch: got %x, want %x", hash, want)
			}
			if diff := cmp.Diff(cr.Hashes(), hashes[size]); diff != "" {
				t.Errorf("hashes mismatch:\n%v", diff)
			}
		})
	}
}
func TestMergeBackwards(t *testing.T) {
	const numNodes = uint64(340)
	tree, visit := newTree(t, numNodes)
	rng := factory.NewEmptyRange(numNodes)
	tree.verifyRange(t, rng, true)
	for i := numNodes; i > 0; i-- {
		visit(NewNodeID(0, i-1), tree.leaf(i-1))
		prepend := factory.NewEmptyRange(i - 1)
		tree.verifyRange(t, prepend, true)
		if err := prepend.Append(tree.leaf(i-1), visit); err != nil {
			t.Errorf("Append()=%v", err)
		}
		tree.verifyRange(t, prepend, true)
		if err := prepend.AppendRange(rng, visit); err != nil {
			t.Fatalf("AppendRange: %v", err)
		}
		rng = prepend
		tree.verifyRange(t, rng, true)
	}
	tree.verifyAllVisited(t, rng)
}