sortable_stack_test.go

package pqueue

import (
	"math/rand"
	"sort"
	"testing"
)

func TestSStack(t *testing.T) {
	// Create some initial data
	size := 16 * blockSize
	data := make([]*item, size)
	for i := 0; i < size; i++ {
		data[i] = &item{rand.Int(), rand.Float32()}
	}

	stack := newSstack()
	for rep := 0; rep < 2; rep++ {
		// Push all the data into stack, Pop out every even index
		even := []*item{}
		for i := range data {
			stack.Push(data[i])
			if i%2 == 0 {
				even = append(even, stack.Pop().(*item))
			}
		}

		rest := []*item{}

		for i := 0; stack.Len() > 0; i++ {
			rest = append(rest, stack.Pop().(*item))
		}

		// Make sure the contents of resulting slices are ok
		for i := range data {
			if i%2 == 0 && data[i] != even[i/2] {
				t.Errorf("push/pop mismatch: have %v, want %v.", even[i/2], data[i])
			}

			if i%2 == 1 && data[i] != rest[len(rest)-i/2-1] {
				t.Errorf("push/pop mismatch: have %v, want %v.", rest[len(rest)-i/2-1], data[i])
			}
		}
	}
}

func TestSStack_Sort(t *testing.T) {
	// Create some initial data
	size := 16 * blockSize
	data := make([]*item, size)
	for i := 0; i < size; i++ {
		data[i] = &item{rand.Int(), float32(i)}
	}
	// Push all the data into the stack
	stack := newSstack()
	for _, val := range data {
		stack.Push(val)
	}
	// Sort and pop the stack contents (should reverse the order)
	sort.Sort(stack)
	for _, val := range data {
		out := stack.Pop()
		if out != val {
			t.Errorf("push/pop mismatch after sort: have %v, want %v.", out, val)
		}
	}
}

func TestSStack_Reset(t *testing.T) {
	// Create some initial data
	size := 16 * blockSize
	data := make([]*item, size)
	for i := 0; i < size; i++ {
		data[i] = &item{rand.Int(), rand.Float32()}
	}
	stack := newSstack()
	for rep := 0; rep < 2; rep++ {
		// Push all the data into the stack, pop out every second
		secs := []*item{}
		for i := 0; i < size; i++ {
			stack.Push(data[i])
			if i%2 == 0 {
				secs = append(secs, stack.Pop().(*item))
			}
		}
		// Reset and verify both pulled and stack contents
		stack.Reset()
		if stack.Len() != 0 {
			t.Errorf("stack not empty after reset: %v", stack)
		}
		for i := 0; i < size; i++ {
			if i%2 == 0 && data[i] != secs[i/2] {
				t.Errorf("push/pop mismatch: have %v, want %v.", secs[i/2], data[i])
			}
		}
	}
}