priority_test.go

package queue_test

import (
	"bytes"
	"encoding/json"
	"errors"
	"reflect"
	"runtime"
	"sort"
	"testing"
	"time"

	"github.com/adrianbrad/queue"
)

func lessInt(elem, elemAfter int) bool {
	return elem < elemAfter
}

func TestPriority(t *testing.T) {
	t.Parallel()

	t.Run("NilLessFunc", testPriorityNilLessFunc)
	t.Run("CapacityLesserThanLenElems", testPriorityCapacityLesserThanLenElems)
	t.Run("Offer", testPriorityOffer)
	t.Run("Get", testPriorityGet)
	t.Run("Clear", testPriorityClear)
	t.Run("Contains", testPriorityContains)
	t.Run("Iterator", testPriorityIterator)
	t.Run("IsEmpty", testPriorityIsEmpty)
	t.Run("Peek", testPriorityPeek)
	t.Run("Reset", testPriorityReset)
	t.Run("MarshalJSON", testPriorityMarshalJSON)
	t.Run("NegativeCapacity", testPriorityNegativeCapacity)
	t.Run("ResetReleasesExtras", testPriorityResetReleasesExtras)
}

func testPriorityResetReleasesExtras(t *testing.T) {
	t.Parallel()

	type payload struct{ id int }

	var pq *queue.Priority[*payload]

	finalized := make(chan struct{}, 5)

	lessByID := func(a, b *payload) bool { return a.id < b.id }

	func() {
		// 2 initial elems, then Offer 5 more with finalizers. Reset
		// should make the extras reclaimable.
		pq = queue.NewPriority(
			[]*payload{{id: 1}, {id: 2}},
			lessByID,
		)

		for i := 3; i <= 7; i++ {
			p := &payload{id: i}
			runtime.SetFinalizer(p, func(*payload) {
				finalized <- struct{}{}
			})

			if err := pq.Offer(p); err != nil {
				t.Fatalf("offer: %v", err)
			}
		}

		pq.Reset()
	}()

	deadline := time.After(time.Second)

	count := 0
	for count < 5 {
		runtime.GC() //nolint:revive // explicit GC needed to drive finalizer

		select {
		case <-finalized:
			count++
		case <-deadline:
			runtime.KeepAlive(pq)
			t.Fatalf("only %d/5 extra payloads finalized after Reset", count)
		default:
			time.Sleep(10 * time.Millisecond)
		}
	}

	runtime.KeepAlive(pq)
}

func testPriorityNegativeCapacity(t *testing.T) {
	t.Parallel()

	defer func() {
		p := recover()
		if p == nil {
			t.Fatal("expected panic for negative capacity")
		}

		msg, ok := p.(string)
		if !ok || msg != negativeCapacityPanic {
			t.Fatalf("expected panic %q, got %v", negativeCapacityPanic, p)
		}
	}()

	_ = queue.NewPriority([]int{1, 2}, lessInt, queue.WithCapacity(-1))
}

func testPriorityNilLessFunc(t *testing.T) {
	defer func() {
		p := recover()
		if p != "nil less func" {
			t.Fatalf("expected panic to be 'nil less func', got %v", p)
		}
	}()

	queue.NewPriority[any](nil, nil)
}

func testPriorityCapacityLesserThanLenElems(t *testing.T) {
	t.Parallel()

	elems := []int{4, 1, 2}

	priorityQueue := queue.NewPriority(elems, lessInt, queue.WithCapacity(2))

	size := priorityQueue.Size()

	if priorityQueue.Size() != 2 {
		t.Fatalf("expected size to be 2, got %d with elements: %v", size, priorityQueue.Clear())
	}

	elems = priorityQueue.Clear()
	expectedElems := []int{1, 2}

	if !reflect.DeepEqual([]int{1, 2}, elems) {
		t.Fatalf("expected elements to be %v, got %v", expectedElems, elems)
	}
}

func testPriorityOffer(t *testing.T) {
	t.Parallel()

	t.Run("Success", func(t *testing.T) {
		t.Parallel()

		elems := []int{4, 1, 2}

		priorityQueue := queue.NewPriority(elems, lessInt)

		if err := priorityQueue.Offer(5); err != nil {
			t.Fatalf("expected no error, got %v", err)
		}

		size := priorityQueue.Size()

		if size != 4 {
			t.Fatalf("expected size to be 4, got %d", size)
		}

		queueElems := priorityQueue.Clear()
		expectedElems := []int{1, 2, 4, 5}

		if !reflect.DeepEqual(expectedElems, queueElems) {
			t.Fatalf("expected elements to be %v, got %v", expectedElems, queueElems)
		}

		newElems := make([]int, 10)

		for j := 19; j >= 10; j-- {
			newElems[j%10] = j

			if err := priorityQueue.Offer(j); err != nil {
				t.Fatalf("expected no error, got %v", err)
			}
		}

		queueElems = priorityQueue.Clear()
		if !reflect.DeepEqual(newElems, queueElems) {
			t.Fatalf("expected elements to be %v, got %v", newElems, queueElems)
		}
	})

	t.Run("ErrQueueIsFull", func(t *testing.T) {
		t.Parallel()

		elems := []int{1}

		priorityQueue := queue.NewPriority(
			elems, lessInt,
			queue.WithCapacity(1),
		)

		if err := priorityQueue.Offer(2); !errors.Is(err, queue.ErrQueueIsFull) {
			t.Fatalf("expected error to be %v, got %v", queue.ErrQueueIsFull, err)
		}
	})
}

func testPriorityGet(t *testing.T) {
	t.Parallel()

	t.Run("Success", func(t *testing.T) {
		t.Parallel()

		elems := []int{4, 1, 2}

		priorityQueue := queue.NewPriority(elems, lessInt)

		elem, err := priorityQueue.Get()
		if err != nil {
			t.Fatalf("expected no error, got %v", err)
		}

		if elem != 1 {
			t.Fatalf("expected elem to be 1, got %d", elem)
		}

		size := priorityQueue.Size()

		if size != 2 {
			t.Fatalf("expected size to be 2, got %d", size)
		}
	})

	t.Run("ErrNoElementsAvailable", func(t *testing.T) {
		t.Parallel()

		priorityQueue := queue.NewPriority([]int{}, func(_, _ int) bool { return false })

		if _, err := priorityQueue.Get(); !errors.Is(err, queue.ErrNoElementsAvailable) {
			t.Fatalf("expected error to be %v, got %v", queue.ErrNoElementsAvailable, err)
		}
	})
}

func testPriorityClear(t *testing.T) {
	t.Parallel()

	t.Run("Success", func(t *testing.T) {
		t.Parallel()

		elems := []int{1, 2, 3}

		priorityQueue := queue.NewPriority(elems, lessInt)

		queueElems := priorityQueue.Clear()

		if !reflect.DeepEqual(elems, queueElems) {
			t.Fatalf("expected elements to be %v, got %v", elems, queueElems)
		}
	})

	t.Run("Empty", func(t *testing.T) {
		t.Parallel()

		priorityQueue := queue.NewPriority([]int{}, lessInt)

		queueElems := priorityQueue.Clear()

		if len(queueElems) != 0 {
			t.Fatalf("expected elements to be empty, got %v", queueElems)
		}
	})
}

func testPriorityContains(t *testing.T) {
	t.Parallel()

	t.Run("True", func(t *testing.T) {
		t.Parallel()

		elems := []int{1, 2, 3}

		priorityQueue := queue.NewPriority(elems, lessInt)

		if !priorityQueue.Contains(2) {
			t.Fatal("expected queue to contain 2")
		}
	})

	t.Run("False", func(t *testing.T) {
		t.Parallel()

		elems := []int{1, 2, 3}

		priorityQueue := queue.NewPriority(elems, lessInt)

		if priorityQueue.Contains(4) {
			t.Fatal("expected queue to not contain 4")
		}
	})
}

func testPriorityIterator(t *testing.T) {
	t.Parallel()

	elems := []int{1, 2, 3}

	priorityQueue := queue.NewPriority(elems, lessInt)

	iterCh := priorityQueue.Iterator()

	if !priorityQueue.IsEmpty() {
		t.Fatal("expected queue to be empty")
	}

	iterElems := make([]int, 0, len(elems))

	for e := range iterCh {
		iterElems = append(iterElems, e)
	}

	if !reflect.DeepEqual(elems, iterElems) {
		t.Fatalf("expected elements to be %v, got %v", elems, iterElems)
	}
}

func testPriorityIsEmpty(t *testing.T) {
	t.Parallel()

	t.Run("True", func(t *testing.T) {
		t.Parallel()

		priorityQueue := queue.NewPriority([]int{}, lessInt)

		if !priorityQueue.IsEmpty() {
			t.Fatal("expected queue to be empty")
		}
	})

	t.Run("False", func(t *testing.T) {
		t.Parallel()

		priorityQueue := queue.NewPriority([]int{1}, lessInt)

		if priorityQueue.IsEmpty() {
			t.Fatal("expected queue to not be empty")
		}
	})
}

func testPriorityPeek(t *testing.T) {
	t.Parallel()

	t.Run("Success", testPriorityPeekSuccess)

	t.Run("ErrNoElementsAvailable", func(t *testing.T) {
		t.Parallel()

		priorityQueue := queue.NewPriority([]int{}, func(_, _ int) bool { return false })

		if _, err := priorityQueue.Peek(); !errors.Is(err, queue.ErrNoElementsAvailable) {
			t.Fatalf("expected error to be %v, got %v", queue.ErrNoElementsAvailable, err)
		}
	})
}

func testPriorityPeekSuccess(t *testing.T) {
	t.Parallel()

	elems := []int{4, 1, 2}

	priorityQueue := queue.NewPriority(elems, lessInt)

	elem, err := priorityQueue.Peek()
	if err != nil {
		t.Fatalf("expected no error, got %v", err)
	}

	size := priorityQueue.Size()

	if size != 3 {
		t.Fatalf("expected size to be 3, got %d", size)
	}

	if elem != 1 {
		t.Fatalf("expected elem to be 1, got %d", elem)
	}

	elem, err = priorityQueue.Get()
	if err != nil {
		t.Fatalf("expected no error, got %v", err)
	}

	if elem != 1 {
		t.Fatalf("expected elem to be 1, got %d", elem)
	}

	elem, err = priorityQueue.Peek()
	if err != nil {
		t.Fatalf("expected no error, got %v", err)
	}

	size = priorityQueue.Size()

	if size != 2 {
		t.Fatalf("expected size to be 2, got %d", size)
	}

	if elem != 2 {
		t.Fatalf("expected elem to be 2, got %d", elem)
	}

	elem, err = priorityQueue.Get()
	if err != nil {
		t.Fatalf("expected no error, got %v", err)
	}

	if elem != 2 {
		t.Fatalf("expected elem to be 2, got %d", elem)
	}
}

func testPriorityReset(t *testing.T) {
	t.Run("SizeGreaterThanInitialElems", func(t *testing.T) {
		t.Parallel()

		elems := []int{1}

		priorityQueue := queue.NewPriority(elems, lessInt)

		err := priorityQueue.Offer(2)
		if err != nil {
			t.Fatalf("expected no error, got %v", err)
		}

		priorityQueue.Reset()

		if priorityQueue.Size() != 1 {
			t.Fatalf("expected size to be 1, got %d", priorityQueue.Size())
		}
	})

	t.Run("SizeLesserThanInitialElems", func(t *testing.T) {
		t.Parallel()

		elems := []int{1, 2}

		priorityQueue := queue.NewPriority(elems, lessInt)

		if _, err := priorityQueue.Get(); err != nil {
			t.Fatalf("expected no error, got %v", err)
		}

		priorityQueue.Reset()

		if priorityQueue.Size() != 2 {
			t.Fatalf("expected size to be 2, got %d", priorityQueue.Size())
		}
	})
}

func testPriorityMarshalJSON(t *testing.T) {
	t.Parallel()

	// Use an unsorted input large enough that the heap's internal layout
	// differs from priority-sorted order. For a min-heap over
	// [5, 3, 1, 4, 2] with less=<, heap.Init produces [1, 2, 4, 5, 3];
	// draining via heap.Pop must yield [1, 2, 3, 4, 5].
	elems := []int{5, 3, 1, 4, 2}

	priorityQueue := queue.NewPriority(elems, lessInt)

	marshaled, err := json.Marshal(priorityQueue)
	if err != nil {
		t.Fatalf("expected no error, got %v", err)
	}

	expectedMarshaled := []byte(`[1,2,3,4,5]`)
	if !bytes.Equal(expectedMarshaled, marshaled) {
		t.Fatalf("expected marshaled to be %s, got %s", expectedMarshaled, marshaled)
	}
}

func FuzzPriority(f *testing.F) {
	testcases := [][]byte{{2, 10, 8, 4}, {11, 9, 7}, {8, 24, 255}}
	for _, tc := range testcases {
		f.Add(tc)
	}

	lessFunc := func(elem, elemAfter byte) bool {
		return elem < elemAfter
	}

	f.Fuzz(func(t *testing.T, orig []byte) {
		sort.Slice(orig, func(i, j int) bool {
			return orig[i] < orig[j]
		})

		priorityQueue := queue.NewPriority(nil, lessFunc)

		for _, v := range orig {
			err := priorityQueue.Offer(v)
			if err != nil {
				t.Fatalf("expected no error, got %v", err)
			}
		}

		for _, v := range orig {
			peekedVal, err := priorityQueue.Peek()
			if err != nil {
				t.Fatalf("expected no error, got %v", err)
			}

			if v != peekedVal {
				t.Fatalf("expected peeked value to be %d, got %d", v, peekedVal)
			}

			getVal, err := priorityQueue.Get()
			if err != nil {
				t.Fatalf("expected no error, got %v", err)
			}

			if peekedVal != getVal {
				t.Fatalf("expected peeked value to be %d, got %d", peekedVal, getVal)
			}
		}
	})
}

func BenchmarkPriorityQueue(b *testing.B) {
	b.Run("MarshalJSON", func(b *testing.B) {
		priorityQueue := queue.NewPriority[int](
			[]int{2, 3, 1, 5, 4},
			func(elem, otherElem int) bool {
				return elem < otherElem
			},
		)

		b.ReportAllocs()
		b.ResetTimer()

		for i := 0; i <= b.N; i++ {
			_, _ = priorityQueue.MarshalJSON()
		}
	})

	b.Run("Peek", func(b *testing.B) {
		priorityQueue := queue.NewPriority([]int{1}, func(elem, otherElem int) bool {
			return elem < otherElem
		})

		b.ReportAllocs()
		b.ResetTimer()

		for i := 0; i <= b.N; i++ {
			_, _ = priorityQueue.Peek()
		}
	})

	b.Run("Get_Offer", func(b *testing.B) {
		priorityQueue := queue.NewPriority([]int{1}, func(elem, otherElem int) bool {
			return elem < otherElem
		})

		b.ReportAllocs()
		b.ResetTimer()

		for i := 0; i <= b.N; i++ {
			_, _ = priorityQueue.Get()

			_ = priorityQueue.Offer(1)
		}
	})

	b.Run("Offer", func(b *testing.B) {
		priorityQueue := queue.NewPriority[int](nil, func(elem, otherElem int) bool {
			return elem < otherElem
		})

		b.ReportAllocs()
		b.ResetTimer()

		for i := 0; i <= b.N; i++ {
			_ = priorityQueue.Offer(i)
		}
	})
}