func TestMutableReverseSequential(t *testing.T) {
	t.Parallel()
	expectedSize := uint64(0)
	numItems := 1000
	testTreap := NewMutable()
	for i := 0; i < numItems; i++ {
		key := uint32ToKey(uint32(numItems - i - 1))
		value := &Value{Height: uint32(numItems - i - 1)}
		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.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)
		}
	}
}
TestMutableReverseSequential ensures that putting keys into a mutable treap
in reverse sequential order works as expected.
package tickettreap
import (
	"bytes"
	"crypto/sha256"
	"reflect"
	"testing"
)
func TestMutableEmpty(t *testing.T) {
	t.Parallel()
	testTreap := NewMutable()
	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 TestMutableReset(t *testing.T) {
	t.Parallel()
	numItems := 10
	testTreap := NewMutable()
	for i := 0; i < numItems; i++ {
		key := uint32ToKey(uint32(i))
		value := &Value{Height: uint32(i)}
		testTreap.Put(key, value)
	}
	testTreap.Reset()
	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)
	}
	for i := 0; i < numItems; i++ {
		key := uint32ToKey(uint32(i))
		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)
		}
	}
	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 TestMutableSequential(t *testing.T) {
	t.Parallel()
	expectedSize := uint64(0)
	numItems := 1000
	testTreap := NewMutable()
	for i := 0; i < numItems; i++ {
		key := uint32ToKey(uint32(i))
		value := &Value{Height: uint32(i)}
		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.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)
		}
	}
}