abrolgo/container/heap_test.go

package container

import (
	"testing"
)

// TestPush tests the Push method of the Heap.
func TestPush(t *testing.T) {
	heap := NewHeap[int, int](true) // Testing a min heap
	heap.Push(3, 3)
	heap.Push(1, 1)
	heap.Push(2, 2)

	expected := []int{1, 3, 2} // The expected min-heap state after pushing elements
	for i, v := range heap.elements {
		if v.Value != expected[i] {
			t.Errorf("Push() test failed: expected %v at index %d, got %v", expected[i], i, v)
		}
	}
}

// TestPop tests the Pop method of the Heap.
func TestPop(t *testing.T) {
	heap := NewHeap[int, int](true)
	heap.Push(3, 3)
	heap.Push(1, 1)
	heap.Push(2, 2)

	if val := heap.Pop(); val != 1 {
		t.Errorf("Pop() test failed: expected 1, got %v", val)
	}

	if val := heap.Pop(); val != 2 {
		t.Errorf("Pop() test failed: expected 2, got %v", val)
	}
}

// TestPeek tests the Peek method of the Heap.
func TestPeek(t *testing.T) {
	heap := NewHeap[int, int](true)
	heap.Push(3, 3)
	heap.Push(1, 1)
	heap.Push(2, 2)

	if val := heap.Peek(); val != 1 {
		t.Errorf("Peek() test failed: expected 1, got %v", val)
	}

	// Check if Peek() doesn't remove the element
	if val := heap.Pop(); val != 1 {
		t.Errorf("Peek() test failed: Peek() should not remove the element")
	}
}

// TestHeapProperty tests if the heap maintains its property after operations.
func TestHeapProperty(t *testing.T) {
	heap := NewHeap[int, int](true) // Testing a min heap
	heap.Push(5, 5)
	heap.Push(3, 3)
	heap.Push(8, 8)
	heap.Push(1, 1)
	heap.Push(7, 7)

	// After every Pop(), the next smallest element should come out
	expectedOrder := []int{1, 3, 5, 7, 8}
	for _, expected := range expectedOrder {
		if val := heap.Pop(); val != expected {
			t.Errorf("Heap property test failed: expected %v, got %v", expected, val)
		}
	}
}

// TestNewHeap tests the NewHeap function.
func TestNewHeap(t *testing.T) {
	// Test creating a min heap
	minHeap := NewHeap[int, int](true)
	if minHeap == nil {
		t.Error("NewHeap() test failed: expected a non-nil heap")
	}
	if minHeap != nil && !minHeap.isMinHeap {
		t.Error("NewHeap() test failed: expected a min heap")
	}

	// Test creating a max heap
	maxHeap := NewHeap[int, int](false)
	if maxHeap == nil {
		t.Error("NewHeap() test failed: expected a non-nil heap")
	}
	if minHeap != nil && maxHeap.isMinHeap {
		t.Error("NewHeap() test failed: expected a max heap")
	}
}

// TestHeapifyUp tests the heapifyUp method of the Heap.
func TestHeapifyUp(t *testing.T) {
	heap := NewHeap[int, int](true)
	heap.elements = []HeapItem[int, int]{{2, 2}, {3, 3}, {1, 1}}

	heap.heapifyUp()

	expected := []int{1, 3, 2} // The expected min-heap state after heapifyUp
	for i, v := range heap.elements {
		if v.Value != expected[i] {
			t.Errorf("heapifyUp() test failed: expected %v at index %d, got %v", expected[i], i, v)
		}
	}
}

// TestHeapifyUpEmptyHeap tests the heapifyUp method of an empty Heap.
func TestHeapifyUpEmptyHeap(t *testing.T) {
	heap := NewHeap[int, int](true)

	heap.heapifyUp()

	if len(heap.elements) != 0 {
		t.Errorf("heapifyUp() test failed: expected empty heap, got %v", heap.elements)
	}
}

// TestHeapifyUpSingleElement tests the heapifyUp method of a Heap with a single element.
func TestHeapifyUpSingleElement(t *testing.T) {
	heap := NewHeap[int, int](true)
	heap.elements = []HeapItem[int, int]{{1, 1}}

	heap.heapifyUp()

	if len(heap.elements) != 1 || heap.elements[0].Value != 1 {
		t.Errorf("heapifyUp() test failed: expected [1], got %v", heap.elements)
	}
}

// TestHeapifyDown tests the heapifyDown method of the Heap.
func TestHeapifyDown(t *testing.T) {
	heap := NewHeap[int, int](true)
	heap.elements = []HeapItem[int, int]{{8, 8}, {1, 1}, {3, 3}, {5, 5}, {7, 7}}

	heap.heapifyDown()

	expected := []int{1, 5, 3, 8, 7} // The expected heap state after heapifyDown
	for i, v := range heap.elements {
		if v.Value != expected[i] {
			t.Errorf("heapifyDown() test failed: expected %v at index %d, got %v", expected[i], i, v)
		}
	}
}