common_test.go raw

   1  package treap
   2  
   3  import (
   4  	"encoding/binary"
   5  	"math/rand"
   6  	"reflect"
   7  	"testing"
   8  )
   9  
  10  // fromHex converts the passed hex string into a byte slice and will panic if there is an error. This is only provided
  11  // for the hard-coded constants so errors in the source code can be detected. It will only (and must only) be called for
  12  // initialization purposes.
  13  //
  14  // func fromHex(// 	s string) []byte {
  15  // 	r, e := hex.DecodeString(s)
  16  // 	if e != nil  {
  17  // 		panic("invalid hex in source file: " + s)
  18  // 	}
  19  // 	return r
  20  // }
  21  
  22  // serializeUint32 returns the big-endian encoding of the passed uint32.
  23  func serializeUint32(ui uint32) []byte {
  24  	var ret [4]byte
  25  	binary.BigEndian.PutUint32(ret[:], ui)
  26  	return ret[:]
  27  }
  28  
  29  // TestParentStack ensures the treapParentStack functionality works as intended.
  30  func TestParentStack(t *testing.T) {
  31  	t.Parallel()
  32  	tests := []struct {
  33  		numNodes int
  34  	}{
  35  		{numNodes: 1},
  36  		{numNodes: staticDepth},
  37  		{numNodes: staticDepth + 1}, // Test dynamic code paths
  38  	}
  39  testLoop:
  40  	for i, test := range tests {
  41  		nodes := make([]*treapNode, 0, test.numNodes)
  42  		for j := 0; j < test.numNodes; j++ {
  43  			var key [4]byte
  44  			binary.BigEndian.PutUint32(key[:], uint32(j))
  45  			node := newTreapNode(key[:], key[:], 0)
  46  			nodes = append(nodes, node)
  47  		}
  48  		// Push all of the nodes onto the parent stack while testing various stack properties.
  49  		stack := &parentStack{}
  50  		for j, node := range nodes {
  51  			stack.Push(node)
  52  			// Ensure the stack length is the expected value.
  53  			if stack.Len() != j+1 {
  54  				t.Errorf("Len #%d (%d): unexpected stack "+
  55  					"length - got %d, want %d", i, j,
  56  					stack.Len(), j+1,
  57  				)
  58  				continue testLoop
  59  			}
  60  			// Ensure the node at each index is the expected one.
  61  			for k := 0; k <= j; k++ {
  62  				atNode := stack.At(j - k)
  63  				if !reflect.DeepEqual(atNode, nodes[k]) {
  64  					t.Errorf("At #%d (%d): mismatched node "+
  65  						"- got %v, want %v", i, j-k,
  66  						atNode, nodes[k],
  67  					)
  68  					continue testLoop
  69  				}
  70  			}
  71  		}
  72  		// Ensure each popped node is the expected one.
  73  		for j := 0; j < len(nodes); j++ {
  74  			node := stack.Pop()
  75  			expected := nodes[len(nodes)-j-1]
  76  			if !reflect.DeepEqual(node, expected) {
  77  				t.Errorf("At #%d (%d): mismatched node - "+
  78  					"got %v, want %v", i, j, node, expected,
  79  				)
  80  				continue testLoop
  81  			}
  82  		}
  83  		// Ensure the stack is now empty.
  84  		if stack.Len() != 0 {
  85  			t.Errorf("Len #%d: stack is not empty - got %d", i,
  86  				stack.Len(),
  87  			)
  88  			continue testLoop
  89  		}
  90  		// Ensure attempting to retrieve a node at an index beyond the stack's length returns nil.
  91  		if node := stack.At(2); node != nil {
  92  			t.Errorf("At #%d: did not give back nil - got %v", i,
  93  				node,
  94  			)
  95  			continue testLoop
  96  		}
  97  		// Ensure attempting to pop a node from an empty stack returns nil.
  98  		if node := stack.Pop(); node != nil {
  99  			t.Errorf("Pop #%d: did not give back nil - got %v", i,
 100  				node,
 101  			)
 102  			continue testLoop
 103  		}
 104  	}
 105  }
 106  func init() {
 107  	
 108  	// Force the same pseudo random numbers for each test run.
 109  	rand.Seed(0)
 110  }
 111