func (s *SMT) CacheEntries() int {
	return s.cache.Entries()
}
CacheEntries returns the number of cache entries.
package gosmt
import (
	"bytes"
	"encoding/binary"
	"sort"
)
var (
	Empty = []byte{0x0}
	Set = []byte{0x1}
)
type Trie interface {
	sort.Interface
	Split(s []byte) (l, r Trie)
}
type D [][]byte
func (d D) Len() int           { return len(d) }
func (d D) Swap(i, j int)      { d[i], d[j] = d[j], d[i] }
func (d D) Less(i, j int) bool { return bytes.Compare(d[i], d[j]) == -1 }
func (d D) Split(s []byte) (l, r D) {
	sort.Stable(d)
	i := sort.Search(d.Len(), func(i int) bool {
		return bytes.Compare(d[i], s) >= 0
	})
	return d[:i], d[i:]
}
type Key [][]byte
func (k Key) Len() int           { return len(k) }
func (k Key) Swap(i, j int)      { k[i], k[j] = k[j], k[i] }
func (k Key) Less(i, j int) bool { return bytes.Compare(k[i], k[j]) == -1 }
func (k Key) Split(s []byte) (l, r Key) {
	sort.Stable(k)
	i := sort.Search(k.Len(), func(i int) bool {
		return bytes.Compare(k[i], s) >= 0
	})
	return k[:i], k[i:]
}
type SMT struct {
	c             []byte  
	cache         Cache   
	Base          []byte  
	hash          func(data ...[]byte) []byte
	N             uint64    
	defaultHashes [][]byte  
}
func NewSMT(c []byte, cache Cache, hash func(data ...[]byte) []byte) *SMT {
	s := new(SMT)
	s.cache = cache
	s.hash = hash
	s.c = c
	s.N = uint64(len(hash([]byte("smt"))) * 8)  
	s.Base = make([]byte, s.N/8)
	s.defaultHashes = make([][]byte, s.N+1)
	s.defaultHashes[0] = s.leafHash(Empty, nil)
	for i := 1; i <= int(s.N); i++ {
		s.defaultHashes[i] = hash(s.defaultHashes[i-1], s.defaultHashes[i-1])
	}
	return s
}
func (s *SMT) Update(d D, keys Key, height uint64, base, value []byte) []byte {
	if height == 0 {
		return s.leafHash(value, base)
	}
	split := bitSplit(base, s.N-height)
	ld, rd := d.Split(split)
	lkeys, rkeys := keys.Split(split)
	switch {
	case lkeys.Len() == 0 && rkeys.Len() > 0:
		return s.cache.HashCache(s.RootHash(ld, height-1, base),
			s.Update(rd, keys, height-1, split, value),
			height, base, split, s.interiorHash, s.defaultHashes)
	case lkeys.Len() > 0 && rkeys.Len() == 0:
		return s.cache.HashCache(s.Update(ld, keys, height-1, base, value),
			s.RootHash(rd, height-1, split),
			height, base, split, s.interiorHash, s.defaultHashes)
	default:
		return s.cache.HashCache(s.Update(ld, lkeys, height-1, base, value),
			s.Update(rd, rkeys, height-1, split, value),
			height, base, split, s.interiorHash, s.defaultHashes)
	}
}
func (s *SMT) AuditPath(d D, height uint64, base, key []byte) [][]byte {
	if height == 0 {
		return nil
	}
	split := bitSplit(base, s.N-height)
	l, r := d.Split(split)
	if !bitIsSet(key, s.N-height) {  
		return append(s.AuditPath(l, height-1, base, key),
			s.RootHash(r, height-1, split))
	}
	return append(s.AuditPath(r, height-1, split, key),
		s.RootHash(l, height-1, base))
}
func (s *SMT) VerifyAuditPath(ap [][]byte, key, value, root []byte) bool {
	return bytes.Equal(root,
		s.auditPathCalc(ap, s.N, make([]byte, s.N/8), key, value))
}
func (s *SMT) auditPathCalc(ap [][]byte, height uint64,
	base, key, value []byte) []byte {
	if height == 0 {
		return s.leafHash(value, base)
	}
	split := bitSplit(base, s.N-height)
	if !bitIsSet(key, s.N-height) {  
		return s.interiorHash(s.auditPathCalc(ap, height-1, base, key, value),
			ap[height-1], height, base)
	}
	return s.interiorHash(ap[height-1],
		s.auditPathCalc(ap, height-1, split, key, value), height, base)
}
func (s *SMT) RootHash(d D, height uint64, base []byte) []byte {
	switch {
	case s.cache.Exists(height, base):
		return s.cache.Get(height, base)
	case d.Len() == 0:
		return s.defaultHash(height)
	case d.Len() == 1 && height == 0:
		return s.leafHash(Set, base)
	case d.Len() > 0 && height == 0:
		panic("this should never happen (unsorted D or broken split?)")
	default:
		split := bitSplit(base, s.N-height)
		l, r := d.Split(split)
		return s.interiorHash(s.RootHash(l, height-1, base),
			s.RootHash(r, height-1, split), height, base)
	}
}
func (s *SMT) defaultHash(height uint64) []byte {
	return s.defaultHashes[height]
}
func (s *SMT) leafHash(a, base []byte) []byte {
	if bytes.Equal(a, Empty) {
		return s.hash(s.c)
	}
	return s.hash(s.c, base)
}
func (s *SMT) interiorHash(left, right []byte,
	height uint64, base []byte) []byte {
	if bytes.Equal(left, right) {
		return s.hash(left, right)
	}
	buf := new(bytes.Buffer)
	if binary.Write(buf, binary.BigEndian, height) != nil {
		panic("failed to encode height")
	}
	return s.hash(left, right, base, buf.Bytes())
}