// Week 8 – Priority queue: with an unsorted slice, and with the container/heap package
// Run: go run ./w08/priorityqueue
package main

import (
	"container/heap"
	"fmt"
)

type Task struct {
	Name     string
	Priority int
}

// SimplePQ: insertion O(1), removal O(n) (minimum search)
type SimplePQ struct{ items []Task }

func (p *SimplePQ) Insert(t Task) { p.items = append(p.items, t) }

func (p *SimplePQ) RemoveMin() Task {
	min := 0
	for i := range p.items {
		if p.items[i].Priority < p.items[min].Priority {
			min = i
		}
	}
	t := p.items[min]
	last := len(p.items) - 1
	p.items[min] = p.items[last]
	p.items = p.items[:last]
	return t
}

// TaskHeap: implementing container/heap.Interface – O(log n) operations (week 15)
type TaskHeap []Task

func (h TaskHeap) Len() int           { return len(h) }
func (h TaskHeap) Less(i, j int) bool { return h[i].Priority < h[j].Priority }
func (h TaskHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
func (h *TaskHeap) Push(x any)        { *h = append(*h, x.(Task)) }
func (h *TaskHeap) Pop() any {
	old := *h
	n := len(old)
	x := old[n-1]
	*h = old[:n-1]
	return x
}

func main() {
	tasks := []Task{{"e-mail", 3}, {"server down", 1}, {"coffee", 5}, {"prepare lecture", 2}, {"lunch", 4}}

	var p SimplePQ
	for _, t := range tasks {
		p.Insert(t)
	}
	fmt.Print("SimplePQ order: ")
	for len(p.items) > 0 {
		t := p.RemoveMin()
		fmt.Printf("%s(%d) ", t.Name, t.Priority)
	}
	fmt.Println()

	h := &TaskHeap{}
	for _, t := range tasks {
		heap.Push(h, t)
	}
	fmt.Print("heap order:     ")
	for h.Len() > 0 {
		t := heap.Pop(h).(Task)
		fmt.Printf("%s(%d) ", t.Name, t.Priority)
	}
	fmt.Println()
}