func walkLinks(t *testing.T, d *Deque, f func(n *node)) {
	t.Helper()
	fail := func(what string, got, want interface{}) {
		t.Errorf("link invariant %s fail; got %v want %v", what, got, want)
	}
	n := d.head
	for {
		if n.n.p != n {
			fail("node.n.p == node", n.n.p, n)
		}
		if n.p.n != n {
			fail("node.p.n == node", n.p.n, n)
		}
		f(n)
		n = n.n
		if n == d.head {
			break
		}
	}
}
walkLinks calls f for each node in the linked list.
It also checks link invariants:
package deque
import (
	"fmt"
	"testing"
)
const (
	refillCount = 3
	pushCount   = maxInternalSliceSize * 3  
)
func TestNewShouldReturnInitiazedInstanceOfDeque(t *testing.T) {
	d := New()
	assertInvariants(t, d, nil)
}
func TestInvariantsWhenEmptyInMiddleOfSlice(t *testing.T) {
	d := new(Deque)
	d.PushBack(0)
	assertInvariants(t, d, nil)
	d.PushBack(1)
	assertInvariants(t, d, nil)
	d.PopFront()
	assertInvariants(t, d, nil)
	d.PopFront()
	assertInvariants(t, d, nil)
}
func TestPushFrontPopBackShouldHaveAllInternalLinksInARing(t *testing.T) {
	d := New()
	pushValue, extraAddedItems, spareLinks := 0, 0, 0
	expectedHeadSliceSize := firstSliceSize
	for i := 1; i <= maxFirstSliceSize; i++ {
		pushValue++
		d.PushFront(pushValue)
		checkLinks(t, d, pushValue, expectedHeadSliceSize, expectedHeadSliceSize, spareLinks, d.head, d.head, d.head, d.head)
		if pushValue >= expectedHeadSliceSize {
			expectedHeadSliceSize *= sliceGrowthFactor
		}
	}
	pushValue++
	d.PushFront(pushValue)
	extraAddedItems++
	checkLinks(t, d, pushValue, maxInternalSliceSize, maxFirstSliceSize, spareLinks, d.tail, d.tail, d.head, d.head)
	for i := 1; i <= maxInternalSliceSize-1; i++ {
		pushValue++
		d.PushFront(pushValue)
		checkLinks(t, d, pushValue, maxInternalSliceSize, maxFirstSliceSize, spareLinks, d.tail, d.tail, d.head, d.head)
	}
	pushValue++
	d.PushFront(pushValue)
	checkLinks(t, d, pushValue, maxInternalSliceSize, maxFirstSliceSize, spareLinks, d.tail.p, d.tail, d.head, d.head.n)
	if d.head.n.n != d.tail {
		t.Error("Expected: d.head.n.n == d.tail; Got: d.head.n.n != d.tail")
	}
	if d.head.n.p != d.head {
		t.Error("Expected: d.head.n.p == d.head; Got: d.head.n.p != d.head")
	}
	if d.Len() != maxFirstSliceSize+maxInternalSliceSize+extraAddedItems {
		t.Errorf("Expected: %d; Got: %d", maxFirstSliceSize+maxInternalSliceSize+extraAddedItems, d.Len())
	}
	popValue := 1
	for i := 1; i <= maxFirstSliceSize-1; i++ {
		if v, ok := d.PopBack(); !ok || v.(int) != popValue {
			t.Errorf("Expected: %d; Got: %d", popValue, v)
		}
		popValue++
		checkLinks(t, d, pushValue-popValue+extraAddedItems, maxInternalSliceSize, maxFirstSliceSize, spareLinks, d.tail.p, d.tail, d.head, d.head.n)
		if d.head.n.n != d.tail {
			t.Error("Expected: d.head.n.n == d.tail; Got: d.head.n.n != d.tail")
		}
		if d.head.n.p != d.head {
			t.Error("Expected: d.head.n.p == d.head; Got: d.head.n.p != d.head")
		}
	}
	if v, ok := d.PopBack(); !ok || v.(int) != popValue {
		t.Errorf("Expected: %d; Got: %d", popValue, v)
	}
	spareLinks++
	popValue++
	checkLinks(t, d, pushValue-popValue+extraAddedItems, maxInternalSliceSize, maxInternalSliceSize, spareLinks, d.tail, d.tail.n, d.head.p, d.head)
	if d.head.p.n != d.head {
		t.Error("Expected: d.head.p.n == d.head; Got: d.head.p.n != d.head")
	}
	if d.head.p.p != d.tail {
		t.Error("Expected: d.head.p.p == d.tail; Got: d.head.p.p != d.tail")
	}
	for i := 1; i <= maxInternalSliceSize-1; i++ {
		if v, ok := d.PopBack(); !ok || v.(int) != popValue {
			t.Errorf("Expected: %d; Got: %d", popValue, v)
		}
		popValue++
		checkLinks(t, d, pushValue-popValue+extraAddedItems, maxInternalSliceSize, maxInternalSliceSize, spareLinks, d.tail, d.tail.n, d.head.p, d.head)
		if d.head.p.n != d.head {
			t.Error("Expected: d.head.p.n == d.head; Got: d.head.p.n != d.head")
		}
		if d.head.p.p != d.tail {
			t.Error("Expected: d.head.p.p == d.tail; Got: d.head.p.p != d.tail")
		}
	}
	if v, ok := d.PopBack(); !ok || v.(int) != popValue {
		t.Errorf("Expected: %d; Got: %d", popValue, v)
	}
	spareLinks++
	checkLinks(t, d, pushValue-popValue, maxInternalSliceSize, maxInternalSliceSize, spareLinks, d.tail.p.p, d.tail.p, d.tail.p.p, d.tail.p)
	if d.head.n.n != d.tail.p {
		t.Error("Expected: d.head.n.n == d.tail.p; Got: d.head.n.n != d.tail.p")
	}
	if d.head.n.p != d.head {
		t.Error("Expected: d.head.n.p == d.head; Got: d.head.n.p != d.head")
	}
	if d.head.p.n != d.head {
		t.Error("Expected: d.head.p.n == d.head; Got: d.head.p.n != d.head")
	}
	if d.head.p.p != d.tail.n {
		t.Error("Expected: d.head.p.p == d.tail.n; Got: d.head.p.p != d.tail.n")
	}
	popValue++
	if v, ok := d.PopBack(); !ok || v.(int) != popValue {
		t.Errorf("Expected: %d; Got: %d", popValue, v)
	}
	checkLinks(t, d, pushValue-popValue, maxInternalSliceSize, maxInternalSliceSize, spareLinks, d.tail.p.p, d.tail.p, d.tail.p.p, d.tail.p)
	if d.head.n.n != d.tail.p {
		t.Error("Expected: d.head.n.n == d.tail.p; Got: d.head.n.n != d.tail.p")
	}
	if d.head.n.p != d.head {
		t.Error("Expected: d.head.n.p == d.head; Got: d.head.n.p != d.head")
	}
	if d.head.p.n != d.head {
		t.Error("Expected: d.head.p.n == d.head; Got: d.head.p.n != d.head")
	}
	if d.head.p.p != d.tail.n {
		t.Error("Expected: d.head.p.p == d.tail.n; Got: d.head.p.p != d.tail.n")
	}
	if d.Len() != 0 {
		t.Errorf("Expected: %d; Got: %d", 0, d.Len())
	}
	if _, ok := d.Back(); ok {
		t.Error("Expected: false; Got: true")
	}
	if _, ok := d.Front(); ok {
		t.Error("Expected: false; Got: true")
	}
	if len(d.head.v) != maxInternalSliceSize {
		t.Errorf("Expected: %d; Got: %d", maxInternalSliceSize, len(d.head.v))
	}
	if len(d.tail.v) != maxInternalSliceSize {
		t.Errorf("Expected: %d; Got: %d", maxInternalSliceSize, len(d.tail.v))
	}
	if d.head != d.tail {
		t.Error("Expected: d.head == d.tail; Got: d.head != d.tail")
	}
	if d.tp != maxInternalSliceSize-1 {
		t.Errorf("Expected: %d; Got: %d", 0, d.tp)
	}
	if d.hp != maxInternalSliceSize-1 {
		t.Errorf("Expected: %d; Got: %d", 0, d.hp)
	}
	if d.spareLinks != spareLinks {
		t.Errorf("Expected: %d; Got: %d", spareLinks, d.spareLinks)
	}
}
func TestPushFrontPopFrontShouldHaveAllInternalLinksInARing(t *testing.T) {
	d := New()
	pushValue, spareLinks := 0, 0
	for i := 1; i <= maxFirstSliceSize+maxInternalSliceSize+1; i++ {
		pushValue++
		d.PushFront(pushValue)
	}
	popValue := pushValue
	if v, ok := d.PopFront(); !ok || v.(int) != popValue {
		t.Errorf("Expected: %d; Got: %d", popValue, v)
	}
	spareLinks++
	popValue--
	checkLinks(t, d, popValue, maxInternalSliceSize, maxFirstSliceSize, spareLinks, d.tail, d.tail.n, d.head.p, d.head)
	if d.head.p.n != d.head {
		t.Error("Expected: d.head.p.n == d.head; Got: d.head.p.n != d.head")
	}
	if d.head.p.p != d.tail {
		t.Error("Expected: d.head.p.p == d.tail; Got: d.head.p.p != d.tail")
	}
	for i := 1; i <= maxInternalSliceSize-1; i++ {
		if v, ok := d.PopFront(); !ok || v.(int) != popValue {
			t.Errorf("Expected: %d; Got: %d", popValue, v)
		}
		popValue--
		checkLinks(t, d, popValue, maxInternalSliceSize, maxFirstSliceSize, spareLinks, d.tail, d.tail.n, d.head.p, d.head)
		if d.head.p.n != d.head {
			t.Error("Expected: d.head.p.n == d.head; Got: d.head.p.n != d.head")
		}
		if d.head.p.p != d.tail {
			t.Error("Expected: d.head.p.p == d.tail; Got: d.head.p.p != d.tail")
		}
	}
	if v, ok := d.PopFront(); !ok || v.(int) != popValue {
		t.Errorf("Expected: %d; Got: %d", popValue, v)
	}
	spareLinks++
	popValue--
	checkLinks(t, d, popValue, maxFirstSliceSize, maxFirstSliceSize, spareLinks, d.tail.p.p, d.tail.p, d.head.p.p, d.head.p)
	if d.head.p.p.n != d.head.p {
		t.Error("Expected: d.head.p.p.n == d.head.p; Got: d.head.p.p.n != d.head.p")
	}
	if d.head.p.p.p != d.tail {
		t.Error("Expected: d.head.p.p.p == d.tail; Got: d.head.p.p.p != d.tail")
	}
	if d.head.p.n != d.head {
		t.Error("Expected: d.head.p.n == d.head; Got: d.head.p.n != d.head")
	}
	if d.head.p.p != d.tail.n {
		t.Error("Expected: d.head.p.p == d.tail.n; Got: d.head.p.p != d.tail.n")
	}
	for i := 1; i <= maxFirstSliceSize; i++ {
		if v, ok := d.PopFront(); !ok || v.(int) != popValue {
			t.Errorf("Expected: %d; Got: %d", popValue, v)
		}
		popValue--
		checkLinks(t, d, popValue, maxFirstSliceSize, maxFirstSliceSize, spareLinks, d.tail.p.p, d.tail.p, d.head.p.p, d.head.p)
		if d.head.p.p.n != d.head.p {
			t.Error("Expected: d.head.p.p.n == d.head.p; Got: d.head.p.p.n != d.head.p")
		}
		if d.head.p.p.p != d.tail {
			t.Error("Expected: d.head.p.p.p == d.tail; Got: d.head.p.p.p != d.tail")
		}
		if d.head.p.n != d.head {
			t.Error("Expected: d.head.p.n == d.head; Got: d.head.p.n != d.head")
		}
		if d.head.p.p != d.tail.n {
			t.Error("Expected: d.head.p.p == d.tail.n; Got: d.head.p.p != d.tail.n")
		}
	}
	if d.Len() != 0 {
		t.Errorf("Expected: %d; Got: %d", 0, d.Len())
	}
	if _, ok := d.Back(); ok {
		t.Error("Expected: false; Got: true")
	}
	if _, ok := d.Front(); ok {
		t.Error("Expected: false; Got: true")
	}
	if len(d.head.v) != maxFirstSliceSize {
		t.Errorf("Expected: %d; Got: %d", maxFirstSliceSize, len(d.head.v))
	}
	if len(d.tail.v) != maxFirstSliceSize {
		t.Errorf("Expected: %d; Got: %d", maxFirstSliceSize, len(d.tail.v))
	}
	if d.head != d.tail {
		t.Error("Expected: d.head == d.tail; Got: d.head != d.tail")
	}
	if d.tp != maxFirstSliceSize-1 {
		t.Errorf("Expected: %d; Got: %d", maxFirstSliceSize-1, d.tp)
	}
	if d.hp != maxFirstSliceSize-1 {
		t.Errorf("Expected: %d; Got: %d", maxFirstSliceSize-1, d.hp)
	}
	if d.spareLinks != spareLinks {
		t.Errorf("Expected: %d; Got: %d", spareLinks, d.spareLinks)
	}
}
func TestPushBackPopBackShouldHaveAllInternalLinksInARing(t *testing.T) {
	d := New()
	pushValue, extraAddedItems, spareLinks := 0, 0, 0
	expectedHeadSliceSize := firstSliceSize
	for i := 1; i <= maxFirstSliceSize; i++ {
		pushValue++
		d.PushBack(pushValue)
		checkLinks(t, d, pushValue, expectedHeadSliceSize, expectedHeadSliceSize, spareLinks, d.head, d.head, d.head, d.head)
		if pushValue >= expectedHeadSliceSize {
			expectedHeadSliceSize *= sliceGrowthFactor
		}
	}
	pushValue++
	d.PushBack(pushValue)
	extraAddedItems++
	checkLinks(t, d, pushValue, maxFirstSliceSize, maxInternalSliceSize, spareLinks, d.tail, d.tail, d.head, d.head)
	for i := 1; i <= maxInternalSliceSize-1; i++ {
		pushValue++
		d.PushBack(pushValue)
		checkLinks(t, d, pushValue, maxFirstSliceSize, maxInternalSliceSize, spareLinks, d.tail, d.tail, d.head, d.head)
	}
	pushValue++
	d.PushBack(pushValue)
	checkLinks(t, d, pushValue, maxFirstSliceSize, maxInternalSliceSize, spareLinks, d.tail.p, d.tail, d.head, d.head.n)
	if d.head.n.n != d.tail {
		t.Error("Expected: d.head.n.n == d.tail; Got: d.head.n.n != d.tail")
	}
	if d.head.n.p != d.head {
		t.Error("Expected: d.head.n.p == d.head; Got: d.head.n.p != d.head")
	}
	if d.Len() != maxFirstSliceSize+maxInternalSliceSize+extraAddedItems {
		t.Errorf("Expected: %d; Got: %d", maxFirstSliceSize+maxInternalSliceSize+extraAddedItems, d.Len())
	}
	popValue := d.Len()
	if v, ok := d.PopBack(); !ok || v.(int) != popValue {
		t.Errorf("Expected: %d; Got: %d", popValue, v)
	}
	spareLinks++
	popValue--
	checkLinks(t, d, popValue, maxFirstSliceSize, maxInternalSliceSize, spareLinks, d.tail, d.tail.n, d.head.p, d.head)
	if d.head.p.n != d.head {
		t.Error("Expected: d.head.p.n == d.head; Got: d.head.p.n != d.head")
	}
	if d.head.p.p != d.tail {
		t.Error("Expected: d.head.p.p == d.tail; Got: d.head.p.p != d.tail")
	}
	for i := 1; i <= maxInternalSliceSize-1; i++ {
		if v, ok := d.PopBack(); !ok || v.(int) != popValue {
			t.Errorf("Expected: %d; Got: %d", popValue, v)
		}
		popValue--
		checkLinks(t, d, popValue, maxFirstSliceSize, maxInternalSliceSize, spareLinks, d.tail, d.tail.n, d.head.p, d.head)
		if d.head.p.n != d.head {
			t.Error("Expected: d.head.p.n == d.head; Got: d.head.p.n != d.head")
		}
		if d.head.p.p != d.tail {
			t.Error("Expected: d.head.p.p == d.tail; Got: d.head.p.p != d.tail")
		}
	}
	if v, ok := d.PopBack(); !ok || v.(int) != popValue {
		t.Errorf("Expected: %d; Got: %d", popValue, v)
	}
	popValue--
	spareLinks++
	checkLinks(t, d, popValue, maxFirstSliceSize, maxFirstSliceSize, spareLinks, d.tail.p.p, d.tail.p, d.tail.p.p, d.tail.p)
	if d.head.n.n != d.tail.p {
		t.Error("Expected: d.head.n.n == d.tail.p; Got: d.head.n.n != d.tail.p")
	}
	if d.head.n.p != d.head {
		t.Error("Expected: d.head.n.p == d.head; Got: d.head.n.p != d.head")
	}
	if d.head.p.n != d.head {
		t.Error("Expected: d.head.p.n == d.head; Got: d.head.p.n != d.head")
	}
	if d.head.p.p != d.tail.n {
		t.Error("Expected: d.head.p.p == d.tail.n; Got: d.head.p.p != d.tail.n")
	}
	for i := 1; i <= maxFirstSliceSize; i++ {
		if v, ok := d.PopBack(); !ok || v.(int) != popValue {
			t.Errorf("Expected: %d; Got: %d", popValue, v)
		}
		popValue--
		checkLinks(t, d, popValue, maxFirstSliceSize, maxFirstSliceSize, spareLinks, d.tail.p.p, d.tail.p, d.tail.p.p, d.tail.p)
		if d.head.n.n != d.tail.p {
			t.Error("Expected: d.head.n.n == d.tail.p; Got: d.head.n.n != d.tail.p")
		}
		if d.head.n.p != d.head {
			t.Error("Expected: d.head.n.p == d.head; Got: d.head.n.p != d.head")
		}
		if d.head.p.n != d.head {
			t.Error("Expected: d.head.p.n == d.head; Got: d.head.p.n != d.head")
		}
		if d.head.p.p != d.tail.n {
			t.Error("Expected: d.head.p.p == d.tail.n; Got: d.head.p.p != d.tail.n")
		}
	}
	if d.Len() != 0 {
		t.Errorf("Expected: %d; Got: %d", 0, d.Len())
	}
	if _, ok := d.Back(); ok {
		t.Error("Expected: false; Got: true")
	}
	if _, ok := d.Front(); ok {
		t.Error("Expected: false; Got: true")
	}
	if len(d.head.v) != maxFirstSliceSize {
		t.Errorf("Expected: %d; Got: %d", maxFirstSliceSize, len(d.head.v))
	}
	if len(d.tail.v) != maxFirstSliceSize {
		t.Errorf("Expected: %d; Got: %d", maxFirstSliceSize, len(d.tail.v))
	}
	if d.head.n == d.tail.p {
		t.Error("Expected: d.head.n != d.tail.p; Got: d.head.n == d.tail.p")
	}
	if d.tp != 0 {
		t.Errorf("Expected: %d; Got: %d", -1, d.tp)
	}
	if d.hp != 0 {
		t.Errorf("Expected: %d; Got: %d", 0, d.hp)
	}
	if d.spareLinks != spareLinks {
		t.Errorf("Expected: %d; Got: %d", spareLinks, d.spareLinks)
	}
}
func TestPushBackPopFrontShouldHaveAllInternalLinksInARing(t *testing.T) {
	d := New()
	pushValue, spareLinks := 0, 0
	for i := 1; i <= maxFirstSliceSize+maxInternalSliceSize+1; i++ {
		pushValue++
		d.PushBack(pushValue)
	}
	popValue := 0
	for i := 1; i <= maxFirstSliceSize-1; i++ {
		popValue++
		if v, ok := d.PopFront(); !ok || v.(int) != popValue {
			t.Errorf("Expected: %d; Got: %d", popValue, v)
		}
		checkLinks(t, d, pushValue-popValue, maxFirstSliceSize, maxInternalSliceSize, spareLinks, d.tail.p, d.tail, d.head, d.head.n)
		if d.head.n.n != d.tail {
			t.Error("Expected: d.head.n.n == d.tail; Got: d.head.n.n != d.tail")
		}
		if d.head.n.p != d.head {
			t.Error("Expected: d.head.n.p == d.head; Got: d.head.n.p != d.head")
		}
	}
	popValue++
	if v, ok := d.PopFront(); !ok || v.(int) != popValue {
		t.Errorf("Expected: %d; Got: %d", popValue, v)
	}
	spareLinks++
	checkLinks(t, d, pushValue-popValue, maxInternalSliceSize, maxInternalSliceSize, spareLinks, d.tail, d.tail.n, d.head.p, d.head)
	if d.head.p.n != d.head {
		t.Error("Expected: d.head.p.n == d.head; Got: d.head.p.n != d.head")
	}
	if d.head.p.p != d.tail {
		t.Error("Expected: d.head.p.p == d.tail; Got: d.head.p.p != d.tail")
	}
	for i := 1; i <= maxInternalSliceSize-1; i++ {
		popValue++
		if v, ok := d.PopFront(); !ok || v.(int) != popValue {
			t.Errorf("Expected: %d; Got: %d", popValue, v)
		}
		checkLinks(t, d, pushValue-popValue, maxInternalSliceSize, maxInternalSliceSize, spareLinks, d.tail, d.tail.n, d.head.p, d.head)
		if d.head.p.n != d.head {
			t.Error("Expected: d.head.p.n == d.head; Got: d.head.p.n != d.head")
		}
		if d.head.p.p != d.tail {
			t.Error("Expected: d.head.p.p == d.tail; Got: d.head.p.p != d.tail")
		}
	}
	popValue++
	spareLinks++
	if v, ok := d.PopFront(); !ok || v.(int) != popValue {
		t.Errorf("Expected: %d; Got: %d", popValue, v)
	}
	checkLinks(t, d, pushValue-popValue, maxInternalSliceSize, maxInternalSliceSize, spareLinks, d.tail.p.p, d.tail.p, d.head.p.p, d.head.p)
	if d.head.n.n != d.head.p {
		t.Error("Expected: d.head.n.n == d.head.p; Got: d.head.n.n != d.head.p")
	}
	if d.head.n.p != d.tail {
		t.Error("Expected: d.head.n.p == d.tail; Got: d.head.n.p != d.tail")
	}
	if d.head.p.n != d.tail {
		t.Error("Expected: d.head.p.n == d.tail; Got: d.head.p.n != d.tail")
	}
	if d.head.p.p != d.tail.n {
		t.Error("Expected: d.head.p.p == d.tail.n; Got: d.head.p.p != d.tail.n")
	}
	popValue++
	if v, ok := d.PopFront(); !ok || v.(int) != popValue {
		t.Errorf("Expected: %d; Got: %d", popValue, v)
	}
	checkLinks(t, d, pushValue-popValue, maxInternalSliceSize, maxInternalSliceSize, spareLinks, d.tail.p.p, d.tail.p, d.head.p.p, d.head.p)
	if d.head.n.n != d.head.p {
		t.Error("Expected: d.head.n.n == d.head.p; Got: d.head.n.n != d.head.p")
	}
	if d.head.n.p != d.tail {
		t.Error("Expected: d.head.n.p == d.tail; Got: d.head.n.p != d.tail")
	}
	if d.head.p.n != d.tail {
		t.Error("Expected: d.head.p.n == d.tail; Got: d.head.p.n != d.tail")
	}
	if d.head.p.p != d.tail.n {
		t.Error("Expected: d.head.p.p == d.tail.n; Got: d.head.p.p != d.tail.n")
	}
	if d.Len() != 0 {
		t.Errorf("Expected: %d; Got: %d", 0, d.Len())
	}
	if _, ok := d.Back(); ok {
		t.Error("Expected: false; Got: true")
	}
	if _, ok := d.Front(); ok {
		t.Error("Expected: false; Got: true")
	}
	if len(d.head.v) != maxInternalSliceSize {
		t.Errorf("Expected: %d; Got: %d", maxInternalSliceSize, len(d.head.v))
	}
	if len(d.tail.v) != maxInternalSliceSize {
		t.Errorf("Expected: %d; Got: %d", maxInternalSliceSize, len(d.tail.v))
	}
	if d.head.p != d.tail.p {
		t.Error("Expected: d.head.p == d.tail.p; Got: d.head.p != d.tail.p")
	}
	if d.tp != 1 {
		t.Errorf("Expected: %d; Got: %d", 0, d.tp)
	}
	if d.hp != 1 {
		t.Errorf("Expected: %d; Got: %d", 1, d.hp)
	}
	if d.spareLinks != spareLinks {
		t.Errorf("Expected: %d; Got: %d", spareLinks, d.spareLinks)
	}
}
func TestPushFrontShouldReuseSpareLinks(t *testing.T) {
	d := New()
	count := maxInternalSliceSize * 3
	for i := 0; i < count; i++ {
		d.PushFront(i)
	}
	for i := 0; i < maxInternalSliceSize; i++ {
		d.PopFront()
	}
	if d.spareLinks != 1 {
		t.Errorf("Expected: %d; Got: %d", 1, d.spareLinks)
	}
	for i := 0; i < count; i++ {
		d.PushFront(i)
	}
	if d.spareLinks != 0 {
		t.Errorf("Expected: %d; Got: %d", 0, d.spareLinks)
	}
}
func TestPushFrontPopBackStableShouldReuseHeadSlice(t *testing.T) {
	d := New()
	for i := 0; i < pushCount; i++ {
		d.PushFront(i)
		v, ok := d.PopBack()
		if !ok || v == nil || v.(int) != i {
			t.Errorf("Expected: %d; Got: %d", i, v)
		}
	}
	if d.head != d.tail || d.head.n != d.tail || d.head.p != d.tail {
		t.Error("Expected to have only one head slice")
	}
	if d.spareLinks != 0 {
		t.Errorf("Expected: %d spareLinks; Got: %d", maxSpareLinks, d.spareLinks)
	}
}
func TestPushBackShouldReuseSpareLinks(t *testing.T) {
	d := New()
	count := maxInternalSliceSize * 3
	for i := 0; i < count; i++ {
		d.PushBack(i)
	}
	for i := 0; i < maxInternalSliceSize; i++ {
		d.PopBack()
	}
	if d.spareLinks != 1 {
		t.Errorf("Expected: %d; Got: %d", 1, d.spareLinks)
	}
	for i := 0; i < count; i++ {
		d.PushBack(i)
	}
	if d.spareLinks != 0 {
		t.Errorf("Expected: %d; Got: %d", 0, d.spareLinks)
	}
}
func TestPopFrontWithRefillShouldKeepMaxSpareLinks(t *testing.T) {
	d := New()
	count := maxInternalSliceSize * (maxSpareLinks + 2)
	for i := 0; i < refillCount; i++ {
		for j := 0; j < count; j++ {
			d.PushBack(j)
		}
		for j := 0; j < count; j++ {
			if v, ok := d.PopFront(); !ok || v.(int) != j {
				t.Errorf("Expected: %d; Got: %d", j, v)
			}
			if d.spareLinks > maxSpareLinks {
				t.Fatalf("Too many spare links : got %d; want <= %d", d.spareLinks, maxSpareLinks)
			}
		}
		actualSpareLinks := 0
		tmp := d.head.n  
		for tmp != nil {
			if tmp != d.tail {
				actualSpareLinks++
			} else {
				break
			}
			tmp = tmp.n
		}
		if actualSpareLinks != maxSpareLinks {
			t.Errorf("Expected: %d; Got: %d", d.spareLinks, actualSpareLinks)
		}
	}
}
func TestPopBackWithRefillShouldKeepMaxSpareLinks(t *testing.T) {
	d := New()
	count := maxInternalSliceSize * (maxSpareLinks + 2)
	for i := 0; i < refillCount; i++ {
		for j := 0; j < count; j++ {
			d.PushFront(j)
		}
		for j := 0; j < count; j++ {
			if v, ok := d.PopBack(); !ok || v.(int) != j {
				t.Errorf("Expected: %d; Got: %d", j, v)
			}
			if d.spareLinks > maxSpareLinks {
				t.Fatalf("Too many spare links : got %d; want <= %d", d.spareLinks, maxSpareLinks)
			}
		}
		actualSpareLinks := 0
		tmp := d.head.n  
		for tmp != nil {
			if tmp != d.tail {
				actualSpareLinks++
			} else {
				break
			}
			tmp = tmp.n
		}
		if actualSpareLinks != maxSpareLinks {
			t.Errorf("Expected: %d; Got: %d", maxSpareLinks, actualSpareLinks)
		}
	}
}
func checkLinks(t *testing.T, d *Deque, length, headSliceSize, tailSliceSize, spareLinks int, headNext, headPrevious, tailNext, tailPrevious *node) {
	t.Helper()
	if d.Len() != length {
		t.Errorf("unexpected length; Expected: %d; Got: %d", length, d.Len())
	}
	if len(d.head.v) != headSliceSize {
		t.Errorf("unexpected head size; Expected: %d; Got: %d", headSliceSize, len(d.head.v))
	}
	if d.head.n != headNext {
		t.Error("unexpected head node; Expected: d.head.n == headNext; Got: d.head.n != headNext")
	}
	if d.head.p != headPrevious {
		t.Error("unexpected head; Expected: d.head.p == headPrevious; Got: d.head.p != headPrevious")
	}
	if d.tail.n != tailNext {
		t.Error("unexpected tailNext; Expected: d.tail.n == tailNext; Got: d.tail.n != tailNext")
	}
	if d.tail.p != tailPrevious {
		t.Error("unexpected tailPrevious; Expected: d.tail.p == tailPrevious; Got: d.tail.p != tailPrevious")
	}
	if len(d.tail.v) != tailSliceSize {
		t.Errorf("unexpected tail size; Expected: %d; Got: %d", tailSliceSize, len(d.tail.v))
	}
	if d.spareLinks != spareLinks {
		t.Errorf("unexpected spare link count; Expected: %d; Got: %d", spareLinks, d.spareLinks)
	}
	if t.Failed() {
		t.FailNow()
	}
}
func assertInvariants(t *testing.T, d *Deque, val func(i int) interface{}) {
	t.Helper()
	fail := func(what string, got, want interface{}) {
		t.Errorf("invariant fail: %s; got %v want %v", what, got, want)
	}
	if d == nil {
		fail("non-nil Deque", d, "non-nil")
	}
	if d.head == nil {
		if d.tail != nil {
			fail("nil tail when zero", d.tail, nil)
		}
		if d.len != 0 {
			fail("zero length when zero", d.len, 0)
		}
		if d.hp != 0 {
			fail("zero hp when zero", d.hp, 0)
		}
		if d.tp != 0 {
			fail("zero tp when zero", d.tp, 0)
		}
		if d.spareLinks != 0 {
			fail("no spare links when zero", d.spareLinks, 0)
		}
		return
	}
	if d.hp < 0 {
		fail("head index non-negative", d.hp, 0)
	}
	if d.hp > len(d.head.v) {
		fail("head index out of range", d.hp, len(d.head.v))
	}
	if d.tp < 0 {
		fail("tail index non-negative", d.tp, 0)
	}
	if d.tp > len(d.tail.v) {
		fail("head index out of range", d.tp, len(d.tail.v))
	}
	if d.head == d.tail {
		if d.tp-d.hp != d.len {
			fail("tail index - head index == len", d.tp-d.hp, d.len)
		}
	}
	spareLinkCount := 0
	inQueue := true
	elemCount := 0
	smallNodeCount := 0
	index := 0
	walkLinks(t, d, func(n *node) {
		if len(n.v) < maxInternalSliceSize {
			smallNodeCount++
			if len(n.v) > maxFirstSliceSize {
				fail("first node within bounds", len(n.v), maxFirstSliceSize)
			}
		}
		if len(n.v) > maxInternalSliceSize {
			fail("slice too big", len(n.v), maxInternalSliceSize)
		}
		for i, v := range n.v {
			failElem := func(what string, got, want interface{}) {
				fail(fmt.Sprintf("at elem %d, node %p, %s", i, n, what), got, want)
				t.FailNow()
			}
			if !inQueue {
				if v != nil {
					failElem("all values outside queue nil", v, nil)
				}
				continue
			}
			elemInQueue := inQueue
			switch {
			case n == d.head && n == d.tail:
				elemInQueue = i >= d.hp && i < d.tp
			case n == d.head:
				elemInQueue = i >= d.hp
			case n == d.tail:
				elemInQueue = i < d.tp
			}
			if elemInQueue {
				if v == nil {
					failElem("all values inside queue non-nil", v, "non-nil")
				}
			} else {
				if v != nil {
					failElem("all values outside queue nil", v, nil)
				}
			}
			if v != nil {
				if val != nil {
					want := val(index)
					if want != v {
						failElem(fmt.Sprintf("element %d has expected value", index), v, want)
					}
				}
				elemCount++
				index++
			}
		}
		if !inQueue {
			spareLinkCount++
		}
		if n == d.tail {
			inQueue = false
		}
	})
	if inQueue {
		t.Errorf("tail does not point to element in list")
	}
	if spareLinkCount > maxSpareLinks {
		fail("spare link count <= maxSpareLinks", spareLinkCount, maxSpareLinks)
	}
	if elemCount != d.len {
		fail("element count == d.len", elemCount, d.len)
	}
	if smallNodeCount > 1 {
		fail("only one first node", smallNodeCount, 1)
	}
	if t.Failed() {
		t.FailNow()
	}
}