Debugging Grimoire

Generic Stack Implementation and Testing in Go

genstack.go

// A package to implement a generic stack in Go

package genstack

import "fmt"

type Stack[T any] struct {
	vals []interface{}
}

func (s *Stack[T]) Push(val interface{}) {
	s.vals = append(s.vals, val)
}

func (s *Stack[T]) isEmpty() bool {
	return len(s.vals) == 0
}

func (s *Stack[T]) Pop() (val interface{}, err error) {
	if s.isEmpty() {
		var zero T
		return zero, fmt.Errorf("Stack is empty")
	}
	val = s.vals[len(s.vals)-1]
	s.vals = s.vals[:len(s.vals)-1]
	return val, nil
}

func (s *Stack[T]) Top() (val interface{}, err error) {
	if s.isEmpty() {
		var zero T
		return zero, fmt.Errorf("stack is empty")
	}
	return s.vals[len(s.vals)-1], nil
}

// Fill the stack from a slice
func (s *Stack[T]) CopyFromSlice(slice []interface{}) {
	for _, val := range slice {
		s.Push(val)
	}
}

// Pops the stack contents into a slice
func (s *Stack[T]) CopyToSlice() []interface{} {
	var slice []interface{}
	for !s.isEmpty() {
		val, err := s.Pop()
		if err != nil {
			break
		}
		slice = append(slice, val)
	}
	return slice
}

func main() {
	fmt.Println("Stacks")
	var intStack Stack[int]
	fmt.Println(intStack)
	intStack.Push(15)
	intStack.Push("dog")
	intStack.Push(25)
	fmt.Println(intStack)
	fmt.Println(intStack.isEmpty())

	// Copy stack contents to a slice
	slice := intStack.CopyToSlice()
	fmt.Println("Slice:", slice)
	fmt.Println("Stack after CopyToSlice:", intStack)
	intStack.CopyFromSlice(slice)
	fmt.Println("Stack after CopyFromSlice:", intStack)
}

genstack_test.go

// Running unit tests for genstack package

package genstack

import (
	"testing"
)

func TestPushPop(t *testing.T) {
	stack := Stack[int]{}

	stack.Push(10)
	stack.Push(20)

	val, err := stack.Pop()
	if err != nil {
		t.Errorf("Unexpected error: %v", err)
	}
	if val != 20 {
		t.Errorf("Expected 20, got %v", val)
	}

	val2, err2 := stack.Pop()
	if err2 != nil {
		t.Errorf("Unexpected error: %v", err)
	}
	if val2 != 10 {
		t.Errorf("Expected 10, got %v", val2)
	}

	_, err = stack.Pop()
	if err == nil {
		t.Errorf("Expected error, got nil")
	}
}

func TestIsEmpty(t *testing.T) {
	stack := Stack[int]{}

	if !stack.isEmpty() {
		t.Errorf("Expected stack to be empty")
	}

	stack.Push(10)
	if stack.isEmpty() {
		t.Errorf("Expected stack to be non-empty")
	}

	stack.Pop()
	if !stack.isEmpty() {
		t.Errorf("Expected stack to be empty")
	}
}

Key Concepts in Go

1. Generics

   • The stack is defined as Stack[T any], using Go’s generics to allow for stacks of any type.
   • This provides flexibility and type safety, a major feature added in Go 1.18+.

2. Interfaces and Type Flexibility

   • Internally, the stack stores values as []interface{}. This enables pushing different types onto the stack, but means type assertions or checks may be necessary when popping.

3. Idiomatic Error Handling

   • Both Pop() and Top() return an error if the stack is empty, following Go’s convention of explicit error returns rather than exceptions.

4. Testing with the testing Package

   • Testing in Go is simple and built-in: functions beginning with Test in a *_test.go file are automatically discovered and run with go test.

Overview of the Program

• genstack.go implements a generic stack, supporting:
  • Pushing and popping elements
  • Checking if the stack is empty
  • Copying stack contents to/from slices
• genstack_test.go provides unit tests to verify core stack behavior, ensuring reliability and correctness.

Test File Explanation (genstack_test.go)

• TestPushPop

  • Pushes integers onto the stack, pops them, and checks order (LIFO: last-in, first-out).
  • Ensures errors are correctly raised when popping from an empty stack.

• TestIsEmpty

  • Verifies that the stack correctly reports empty and non-empty states as elements are pushed and popped.

Example:

func TestPushPop(t *testing.T) {
	stack := Stack[int]{}
	stack.Push(10)
	stack.Push(20)
	val, err := stack.Pop()
	if val != 20 { /* ... */ }
	// ... further checks ...
}

How to Run the Tests

1. Ensure both genstack.go and genstack_test.go are in the same directory/package.
2. Run:

   go test
   

3. Output:

   ok  	theflyoccultist/hello-go/genstack	0.002s
   

Real-World Use Cases

• Testing in Go:

  • Automated tests are crucial for reliability, especially when implementing generic data structures.
  • Go's testing framework is simple, fast, and integrates with tools for continuous integration and code coverage.

• Generic Data Structures:

  • Stacks are used in parsing, algorithms, interpreter runtimes, undo/redo features, and much more.

Extensions

• Type Safety:
  • Consider using []T instead of []interface{} for stricter type guarantees (now possible with Go generics).
• More Operations:
  • Add Peek, Size, or Clear methods for a more complete stack implementation.
• More Tests:
  • Add tests for copying to/from slices, pushing mixed types, or concurrent usage.