package dijkstra

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

// Edge represents a weighted directed edge to another node.
type Edge struct {
	To     string
	Weight int
}

// Graph is an adjacency-list representation of a weighted graph.
type Graph map[string][]Edge

// ShortestPath returns the shortest distance and path from start to target.
// It reports false when target is unreachable.
func ShortestPath(g Graph, start, target string) (int, []string, bool) {
	dist := map[string]int{start: 0}
	prev := map[string]string{}
	pq := priorityQueue{{node: start, distance: 0}}
	heap.Init(&pq)

	for pq.Len() > 0 {
		current := heap.Pop(&pq).(item)

		if current.distance != dist[current.node] {
			continue
		}
		if current.node == target {
			return current.distance, buildPath(prev, start, target), true
		}

		for _, edge := range g[current.node] {
			if edge.Weight < 0 {
				panic("dijkstra requires non-negative edge weights")
			}

			nextDistance := current.distance + edge.Weight
			if known, ok := dist[edge.To]; !ok || nextDistance < known {
				dist[edge.To] = nextDistance
				prev[edge.To] = current.node
				heap.Push(&pq, item{node: edge.To, distance: nextDistance})
			}
		}
	}

	return math.MaxInt, nil, false
}

func buildPath(prev map[string]string, start, target string) []string {
	path := []string{target}
	for path[len(path)-1] != start {
		path = append(path, prev[path[len(path)-1]])
	}

	for i, j := 0, len(path)-1; i < j; i, j = i+1, j-1 {
		path[i], path[j] = path[j], path[i]
	}
	return path
}

type item struct {
	node     string
	distance int
}

type priorityQueue []item

func (pq priorityQueue) Len() int           { return len(pq) }
func (pq priorityQueue) Less(i, j int) bool { return pq[i].distance < pq[j].distance }
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 TestShortestPath(t *testing.T) {
	g := Graph{
		"A": {{To: "B", Weight: 4}, {To: "C", Weight: 1}},
		"B": {{To: "D", Weight: 1}},
		"C": {{To: "B", Weight: 2}, {To: "D", Weight: 5}},
		"D": nil,
	}

	distance, path, ok := ShortestPath(g, "A", "D")
	if !ok {
		t.Fatal("expected path to exist")
	}
	if distance != 4 {
		t.Fatalf("distance = %d, want 4", distance)
	}
	if want := []string{"A", "C", "B", "D"}; !reflect.DeepEqual(path, want) {
		t.Fatalf("path = %v, want %v", path, want)
	}
}

func TestShortestPathUnreachable(t *testing.T) {
	g := Graph{
		"A": {{To: "B", Weight: 1}},
		"C": nil,
	}

	_, path, ok := ShortestPath(g, "A", "C")
	if ok {
		t.Fatal("expected target to be unreachable")
	}
	if path != nil {
		t.Fatalf("path = %v, want nil", path)
	}
}