package dijkstra

import (
	"container/heap"
	"math"
	"testing"
)

type Edge struct {
	To     int
	Weight int
}

// Graph is an adjacency list: graph[u] contains all outgoing edges from u.
type Graph map[int][]Edge

// ShortestPaths returns the minimum distance from start to every reachable node.
// Edge weights must be non-negative.
func ShortestPaths(graph Graph, start int) map[int]int {
	dist := map[int]int{start: 0}
	pq := priorityQueue{{node: start, dist: 0}}
	heap.Init(&pq)

	for pq.Len() > 0 {
		cur := heap.Pop(&pq).(item)
		if cur.dist != dist[cur.node] {
			continue // stale queue entry
		}

		for _, edge := range graph[cur.node] {
			nextDist := cur.dist + edge.Weight
			oldDist, seen := dist[edge.To]
			if !seen || nextDist < oldDist {
				dist[edge.To] = nextDist
				heap.Push(&pq, item{node: edge.To, dist: nextDist})
			}
		}
	}

	return dist
}

// ShortestPath returns the shortest distance between start and target.
func ShortestPath(graph Graph, start, target int) (int, bool) {
	dist := ShortestPaths(graph, start)
	d, ok := dist[target]
	return d, ok
}

type item struct {
	node int
	dist int
}

type priorityQueue []item

func (pq priorityQueue) Len() int            { return len(pq) }
func (pq priorityQueue) Less(i, j int) bool  { return pq[i].dist < pq[j].dist }
func (pq priorityQueue) Swap(i, j int)       { pq[i], pq[j] = pq[j], pq[i] }
func (pq *priorityQueue) Push(x any)         { *pq = append(*pq, x.(item)) }
func (pq *priorityQueue) Pop() any {
	old := *pq
	n := len(old)
	x := old[n-1]
	*pq = old[:n-1]
	return x
}

func TestShortestPaths(t *testing.T) {
	graph := Graph{
		0: {{To: 1, Weight: 4}, {To: 2, Weight: 1}},
		1: {{To: 3, Weight: 1}},
		2: {{To: 1, Weight: 2}, {To: 3, Weight: 5}},
		3: nil,
	}

	dist := ShortestPaths(graph, 0)

	want := map[int]int{0: 0, 1: 3, 2: 1, 3: 4}
	for node, expected := range want {
		if dist[node] != expected {
			t.Fatalf("dist[%d] = %d, want %d", node, dist[node], expected)
		}
	}
}

func TestShortestPathUnreachable(t *testing.T) {
	graph := Graph{
		0: {{To: 1, Weight: 7}},
		2: {{To: 3, Weight: 1}},
	}

	dist, ok := ShortestPath(graph, 0, 3)
	if ok {
		t.Fatalf("ShortestPath returned (%d, true), want unreachable", dist)
	}

	dist, ok = ShortestPath(graph, 0, 0)
	if !ok || dist != 0 {
		t.Fatalf("ShortestPath start-to-start = (%d, %v), want (0, true)", dist, ok)
	}
}

func TestShortestPathLargeWeight(t *testing.T) {
	graph := Graph{
		0: {{To: 1, Weight: math.MaxInt / 4}},
		1: {{To: 2, Weight: 3}},
	}

	dist, ok := ShortestPath(graph, 0, 2)
	if !ok || dist != math.MaxInt/4+3 {
		t.Fatalf("ShortestPath = (%d, %v), want (%d, true)", dist, ok, math.MaxInt/4+3)
	}
}