func TestImmutableMemory(t *testing.T) {
	runtime.GC()
	memStats := new(runtime.MemStats)
	runtime.ReadMemStats(memStats)
	initAlloc := memStats.Alloc
	initTotal := memStats.TotalAlloc
	randSource := rand.NewSource(12345)
	numItems := 40960
	numNodes := 128
	nodeTreaps := make([]*Immutable, numNodes)
	testTreap := NewImmutable()
	for i := 0; i < numItems; i++ {
		randomHash := randHash(randSource)
		randHeight := uint32(randSource.Int63())
		testTreap = testTreap.Put(Key(*randomHash),
			&Value{randHeight, randHeight - 1, false, true, false, true})
	}
	nodeTreaps[0] = testTreap
	maxHeight := uint32(0xFFFFFFFF)
	lastTreap := nodeTreaps[0]
	lastTotal := initTotal
	allocsPerNode := make([]uint64, numNodes)
	for i := 1; i < numNodes; i++ {
		treapCopy := lastTreap
		sz := treapCopy.Len()
		winnerIdxs := pickRandWinners(sz, randSource)
		winners, _ := treapCopy.FetchWinnersAndExpired(winnerIdxs, maxHeight)
		for _, k := range winners {
			treapCopy = treapCopy.Delete(*k)
		}
		perBlock := int(chaincfg.MainNetParams.TicketsPerBlock)
		for i := 0; i < perBlock; i++ {
			randomHash := randHash(randSource)
			randHeight := uint32(randSource.Int63())
			treapCopy = treapCopy.Put(Key(*randomHash),
				&Value{randHeight, randHeight - 1, false, true, false, true})
		}
		runtime.ReadMemStats(memStats)
		finalTotal := memStats.TotalAlloc
		allocsPerNode[i] = finalTotal - lastTotal
		lastTotal = finalTotal
		nodeTreaps[i] = treapCopy
		lastTreap = treapCopy
	}
	avgUint64 := func(uis []uint64) uint64 {
		var sum uint64
		for i := range uis {
			sum += uis[i]
		}
		return sum / uint64(len(uis))
	}
	runtime.GC()
	runtime.ReadMemStats(memStats)
	finalAlloc := memStats.Alloc
	t.Logf("Ticket treaps for %v nodes allocated %v many bytes total after GC",
		numNodes, finalAlloc-initAlloc)
	t.Logf("Ticket treaps allocated an average of %v many bytes per node",
		avgUint64(allocsPerNode))
	lenTest := nodeTreaps[0].count == nodeTreaps[0].Len()
	if !lenTest {
		t.Errorf("bad len test")
	}
}
TestImmutableMemory tests the memory for creating n many nodes cloned and
modified in the memory analogous to what is actually seen in the Hypercash
mainnet, then analyzes the relative memory usage with runtime stats.
package tickettreap
import (
	"bytes"
	"crypto/sha256"
	"math/rand"
	"reflect"
	"runtime"
	"testing"
	"github.com/HcashOrg/hcashd/chaincfg"
	"github.com/HcashOrg/hcashd/chaincfg/chainhash"
)
func TestImmutableEmpty(t *testing.T) {
	t.Parallel()
	testTreap := NewImmutable()
	if gotLen := testTreap.Len(); gotLen != 0 {
		t.Fatalf("Len: unexpected length - got %d, want %d", gotLen, 0)
	}
	if gotSize := testTreap.Size(); gotSize != 0 {
		t.Fatalf("Size: unexpected byte size - got %d, want 0",
			gotSize)
	}
	key := uint32ToKey(0)
	if gotVal := testTreap.Has(key); gotVal {
		t.Fatalf("Has: unexpected result - got %v, want false", gotVal)
	}
	if gotVal := testTreap.Get(key); gotVal != nil {
		t.Fatalf("Get: unexpected result - got %v, want nil", gotVal)
	}
	testTreap.Delete(key)
	var numIterated int
	testTreap.ForEach(func(k Key, v *Value) bool {
		numIterated++
		return true
	})
	if numIterated != 0 {
		t.Fatalf("ForEach: unexpected iterate count - got %d, want 0",
			numIterated)
	}
}
func TestImmutableSequential(t *testing.T) {
	t.Parallel()
	expectedSize := uint64(0)
	numItems := 1000
	testTreap := NewImmutable()
	for i := 0; i < numItems; i++ {
		key := uint32ToKey(uint32(i))
		value := &Value{Height: uint32(i)}
		testTreap = testTreap.Put(key, value)
		if gotLen := testTreap.Len(); gotLen != i+1 {
			t.Fatalf("Len #%d: unexpected length - got %d, want %d",
				i, gotLen, i+1)
		}
		if !testTreap.Has(key) {
			t.Fatalf("Has #%d: key %q is not in treap", i, key)
		}
		if gotVal := testTreap.Get(key); !reflect.DeepEqual(gotVal, value) {
			t.Fatalf("Get #%d: unexpected value - got %v, want %v",
				i, gotVal, value)
		}
		expectedSize += (nodeFieldsSize + uint64(len(key)) + nodeValueSize)
		if gotSize := testTreap.Size(); gotSize != expectedSize {
			t.Fatalf("Size #%d: unexpected byte size - got %d, "+
				"want %d", i, gotSize, expectedSize)
		}
	}
	var numIterated int
	testTreap.ForEach(func(k Key, v *Value) bool {
		wantKey := uint32ToKey(uint32(numIterated))
		if !bytes.Equal(k[:], wantKey[:]) {
			t.Fatalf("ForEach #%d: unexpected key - got %x, want %x",
				numIterated, k, wantKey)
		}
		wantValue := &Value{Height: uint32(numIterated)}
		if !reflect.DeepEqual(v, wantValue) {
			t.Fatalf("ForEach #%d: unexpected value - got %v, want %v",
				numIterated, v, wantValue)
		}
		numIterated++
		return true
	})
	if numIterated != numItems {
		t.Fatalf("ForEach: unexpected iterate count - got %d, want %d",
			numIterated, numItems)
	}
	for i := 0; i < numItems; i++ {
		key := uint32ToKey(uint32(i))
		testTreap = testTreap.Delete(key)
		if gotLen := testTreap.Len(); gotLen != numItems-i-1 {
			t.Fatalf("Len #%d: unexpected length - got %d, want %d",
				i, gotLen, numItems-i-1)
		}
		if testTreap.Has(key) {
			t.Fatalf("Has #%d: key %q is in treap", i, key)
		}
		if gotVal := testTreap.Get(key); gotVal != nil {
			t.Fatalf("Get #%d: unexpected value - got %v, want nil",
				i, gotVal)
		}
		expectedSize -= (nodeFieldsSize + uint64(len(key)) + 4)
		if gotSize := testTreap.Size(); gotSize != expectedSize {
			t.Fatalf("Size #%d: unexpected byte size - got %d, "+
				"want %d", i, gotSize, expectedSize)
		}
	}
}
func TestImmutableReverseSequential(t *testing.T) {
	t.Parallel()
	expectedSize := uint64(0)
	numItems := 1000
	testTreap := NewImmutable()
	for i := 0; i < numItems; i++ {
		key := uint32ToKey(uint32(numItems - i - 1))
		value := &Value{Height: uint32(numItems - i - 1)}
		testTreap = testTreap.Put(key, value)
		if gotLen := testTreap.Len(); gotLen != i+1 {
			t.Fatalf("Len #%d: unexpected length - got %d, want %d",
				i, gotLen, i+1)
		}
		if !testTreap.Has(key) {
			t.Fatalf("Has #%d: key %q is not in treap", i, key)
		}
		if gotVal := testTreap.Get(key); !reflect.DeepEqual(gotVal, value) {
			t.Fatalf("Get #%d: unexpected value - got %v, want %v",
				i, gotVal, value)
		}
		expectedSize += (nodeFieldsSize + uint64(len(key)) + 4)
		if gotSize := testTreap.Size(); gotSize != expectedSize {
			t.Fatalf("Size #%d: unexpected byte size - got %d, "+
				"want %d", i, gotSize, expectedSize)
		}
	}
	var numIterated int
	testTreap.ForEach(func(k Key, v *Value) bool {
		wantKey := uint32ToKey(uint32(numIterated))
		if !bytes.Equal(k[:], wantKey[:]) {
			t.Fatalf("ForEach #%d: unexpected key - got %x, want %x",
				numIterated, k, wantKey)
		}
		wantValue := &Value{Height: uint32(numIterated)}
		if !reflect.DeepEqual(v, wantValue) {
			t.Fatalf("ForEach #%d: unexpected value - got %v, want %v",
				numIterated, v, wantValue)
		}
		numIterated++
		return true
	})
	if numIterated != numItems {
		t.Fatalf("ForEach: unexpected iterate count - got %d, want %d",
			numIterated, numItems)
	}
	for i := 0; i < numItems; i++ {
		key := uint32ToKey(uint32(i))
		testTreap = testTreap.Delete(key)
		if gotLen := testTreap.Len(); gotLen != numItems-i-1 {
			t.Fatalf("Len #%d: unexpected length - got %d, want %d",
				i, gotLen, numItems-i-1)
		}
		if testTreap.Has(key) {
			t.Fatalf("Has #%d: key %q is in treap", i, key)
		}
		if gotVal := testTreap.Get(key); gotVal != nil {
			t.Fatalf("Get #%d: unexpected value - got %v, want nil",
				i, gotVal)
		}
		expectedSize -= (nodeFieldsSize + uint64(len(key)) + 4)
		if gotSize := testTreap.Size(); gotSize != expectedSize {
			t.Fatalf("Size #%d: unexpected byte size - got %d, "+
				"want %d", i, gotSize, expectedSize)
		}
	}
}
func TestImmutableUnordered(t *testing.T) {
	t.Parallel()
	expectedSize := uint64(0)
	numItems := 1000
	testTreap := NewImmutable()
	for i := 0; i < numItems; i++ {
		key := Key(sha256.Sum256(serializeUint32(uint32(i))))
		value := &Value{Height: uint32(i)}
		testTreap = testTreap.Put(key, value)
		if gotLen := testTreap.Len(); gotLen != i+1 {
			t.Fatalf("Len #%d: unexpected length - got %d, want %d",
				i, gotLen, i+1)
		}
		if !testTreap.Has(key) {
			t.Fatalf("Has #%d: key %q is not in treap", i, key)
		}
		if gotVal := testTreap.Get(key); !reflect.DeepEqual(gotVal, value) {
			t.Fatalf("Get #%d: unexpected value - got %v, want %v",
				i, gotVal, value)
		}
		expectedSize += nodeFieldsSize + uint64(len(key)) + 4
		if gotSize := testTreap.Size(); gotSize != expectedSize {
			t.Fatalf("Size #%d: unexpected byte size - got %d, "+
				"want %d", i, gotSize, expectedSize)
		}
	}
	for i := 0; i < numItems; i++ {
		key := Key(sha256.Sum256(serializeUint32(uint32(i))))
		testTreap = testTreap.Delete(key)
		if gotLen := testTreap.Len(); gotLen != numItems-i-1 {
			t.Fatalf("Len #%d: unexpected length - got %d, want %d",
				i, gotLen, numItems-i-1)
		}
		if testTreap.Has(key) {
			t.Fatalf("Has #%d: key %q is in treap", i, key)
		}
		if gotVal := testTreap.Get(key); gotVal != nil {
			t.Fatalf("Get #%d: unexpected value - got %v, want nil",
				i, gotVal)
		}
		expectedSize -= (nodeFieldsSize + uint64(len(key)) + 4)
		if gotSize := testTreap.Size(); gotSize != expectedSize {
			t.Fatalf("Size #%d: unexpected byte size - got %d, "+
				"want %d", i, gotSize, expectedSize)
		}
	}
}
func TestImmutableDuplicatePut(t *testing.T) {
	t.Parallel()
	expectedVal := &Value{Height: 10000}
	expectedSize := uint64(0)
	numItems := 1000
	testTreap := NewImmutable()
	for i := 0; i < numItems; i++ {
		key := uint32ToKey(uint32(i))
		value := &Value{Height: uint32(i)}
		testTreap = testTreap.Put(key, value)
		expectedSize += nodeFieldsSize + uint64(len(key)) + 4
		testTreap = testTreap.Put(key, expectedVal)
		if gotVal := testTreap.Has(key); !gotVal {
			t.Fatalf("Has: unexpected result - got %v, want false",
				gotVal)
		}
		if gotVal := testTreap.Get(key); !reflect.DeepEqual(gotVal, expectedVal) {
			t.Fatalf("Get: unexpected result - got %v, want %v",
				gotVal, expectedVal)
		}
		if gotSize := testTreap.Size(); gotSize != expectedSize {
			t.Fatalf("Size: unexpected byte size - got %d, want %d",
				gotSize, expectedSize)
		}
	}
}
func TestImmutableNilValue(t *testing.T) {
	t.Parallel()
	key := uint32ToKey(0)
	testTreap := NewImmutable()
	testTreap = testTreap.Put(key, nil)
	if gotVal := testTreap.Has(key); gotVal {
		t.Fatalf("Has: unexpected result - got %v, want false", gotVal)
	}
	if gotVal := testTreap.Get(key); gotVal != nil {
		t.Fatalf("Get: unexpected result - got %v, want nil", gotVal)
	}
}
func TestImmutableForEachStopIterator(t *testing.T) {
	t.Parallel()
	numItems := 10
	testTreap := NewImmutable()
	for i := 0; i < numItems; i++ {
		key := uint32ToKey(uint32(i))
		value := &Value{Height: uint32(i)}
		testTreap = testTreap.Put(key, value)
	}
	var numIterated int
	testTreap.ForEach(func(k Key, v *Value) bool {
		numIterated++
		return numIterated != numItems/2
	})
	if numIterated != numItems/2 {
		t.Fatalf("ForEach: unexpected iterate count - got %d, want %d",
			numIterated, numItems/2)
	}
}
func TestImmutableSnapshot(t *testing.T) {
	t.Parallel()
	expectedSize := uint64(0)
	numItems := 1000
	testTreap := NewImmutable()
	for i := 0; i < numItems; i++ {
		treapSnap := testTreap
		key := uint32ToKey(uint32(i))
		value := &Value{Height: uint32(i)}
		testTreap = testTreap.Put(key, value)
		if gotLen := treapSnap.Len(); gotLen != i {
			t.Fatalf("Len #%d: unexpected length - got %d, want %d",
				i, gotLen, i)
		}
		if treapSnap.Has(key) {
			t.Fatalf("Has #%d: key %q is in treap", i, key)
		}
		if gotVal := treapSnap.Get(key); gotVal != nil {
			t.Fatalf("Get #%d: unexpected value - got %v, want nil",
				i, gotVal)
		}
		if gotSize := treapSnap.Size(); gotSize != expectedSize {
			t.Fatalf("Size #%d: unexpected byte size - got %d, "+
				"want %d", i, gotSize, expectedSize)
		}
		expectedSize += (nodeFieldsSize + uint64(len(key)) + 4)
	}
	for i := 0; i < numItems; i++ {
		treapSnap := testTreap
		key := uint32ToKey(uint32(i))
		value := &Value{Height: uint32(i)}
		testTreap = testTreap.Delete(key)
		if gotLen := treapSnap.Len(); gotLen != numItems-i {
			t.Fatalf("Len #%d: unexpected length - got %d, want %d",
				i, gotLen, numItems-i)
		}
		if !treapSnap.Has(key) {
			t.Fatalf("Has #%d: key %q is not in treap", i, key)
		}
		if gotVal := treapSnap.Get(key); !reflect.DeepEqual(gotVal, value) {
			t.Fatalf("Get #%d: unexpected value - got %v, want %v",
				i, gotVal, value)
		}
		if gotSize := treapSnap.Size(); gotSize != expectedSize {
			t.Fatalf("Size #%d: unexpected byte size - got %d, "+
				"want %d", i, gotSize, expectedSize)
		}
		expectedSize -= (nodeFieldsSize + uint64(len(key)) + 4)
	}
}
func randHash(r rand.Source) *chainhash.Hash {
	hash := new(chainhash.Hash)
	for i := 0; i < chainhash.HashSize/2; i++ {
		random := uint64(r.Int63())
		randByte1 := random % 255
		randByte2 := (random >> 8) % 255
		hash[i] = uint8(randByte1)
		hash[i+1] = uint8(randByte2)
	}
	return hash
}
func pickRandWinners(sz int, r rand.Source) []int {
	if sz == 0 {
		panic("bad sz!")
	}
	perBlock := int(chaincfg.MainNetParams.TicketsPerBlock)
	winners := make([]int, perBlock)
	for i := 0; i < perBlock; i++ {
		winners[i] = int(r.Int63() % int64(sz))
	}
	return winners
}