search_test.go

// SPDX-License-Identifier: MIT
// Copyright (c) 2026 MaIII Themd

package dijkstra

import (
	"fmt"
	"testing"
)

// TestSearchScratchReuseAcrossGrowth exercises the reusable per-vertex
// scratch and the generation/blocked stamps across a sequence of searches
// that grow and shrink the graph. It guards the stamp-reuse hazards the
// optimisation has to handle: a slot that re-enters range after the graph
// grows must not carry a stale "visited"/"blocked" stamp from an earlier
// era, and a cleared blocked set must not leave any vertex reading blocked.
func TestSearchScratchReuseAcrossGrowth(t *testing.T) {
	var g StGraph

	// Start with a 6x6 grid, run a search (warms a large scratch), then
	// rebuild as a smaller graph reusing the same StGraph value via removes,
	// then grow again. Each phase asserts a known-correct path.
	side := 6
	name := func(r, c int) string { return fmt.Sprintf("r%dc%d", r, c) }
	for r := 0; r < side; r++ {
		for c := 0; c < side; c++ {
			var edges []StEdge
			if r > 0 {
				edges = append(edges, StEdge{ToVertexName: name(r-1, c), Weight: 1})
			}
			if r < side-1 {
				edges = append(edges, StEdge{ToVertexName: name(r+1, c), Weight: 1})
			}
			if c > 0 {
				edges = append(edges, StEdge{ToVertexName: name(r, c-1), Weight: 1})
			}
			if c < side-1 {
				edges = append(edges, StEdge{ToVertexName: name(r, c+1), Weight: 1})
			}
			g.VertexAdd(name(r, c), float64(c), float64(r), 0, edges...)
		}
	}
	if ok, p := g.DijkstraSearch("r0c0", "r5c5"); !ok || lastCost(p) != 10 {
		t.Fatalf("6x6 corner: ok=%v cost=%v, want cost 10", ok, lastCost(p))
	}

	// Block then unblock and re-search: a cleared blocked set must not
	// leave stale "blocked" stamps from the warm scratch.
	g.VertexBLock("r0c1")
	g.VertexBLock("r1c0")
	if ok, _ := g.DijkstraSearch("r0c0", "r5c5"); ok {
		t.Fatal("both exits from r0c0 blocked: expected no path")
	}
	g.VertexBLockClear()
	if ok, p := g.DijkstraSearch("r0c0", "r5c5"); !ok || lastCost(p) != 10 {
		t.Fatalf("after unblock: ok=%v cost=%v, want cost 10", ok, lastCost(p))
	}

	// Shrink the graph (remove a whole row of vertices), forcing the index
	// to be rebuilt and reused vertex slots, then search the smaller graph.
	for c := 0; c < side; c++ {
		g.VertexRemove(name(5, c))
	}
	if ok, p := g.DijkstraSearch("r0c0", "r4c4"); !ok || lastCost(p) != 8 {
		t.Fatalf("after shrink: ok=%v cost=%v, want cost 8", ok, lastCost(p))
	}

	// Grow it back: new vertices land in slots that previously held stamps
	// from the larger graph. They must not read as visited/blocked.
	for c := 0; c < side; c++ {
		var edges []StEdge
		edges = append(edges, StEdge{ToVertexName: name(4, c), Weight: 1})
		if c > 0 {
			edges = append(edges, StEdge{ToVertexName: name(5, c-1), Weight: 1})
		}
		if c < side-1 {
			edges = append(edges, StEdge{ToVertexName: name(5, c+1), Weight: 1})
		}
		g.VertexAdd(name(5, c), float64(c), 5, 0, edges...)
		g.VertexAddEdge(name(4, c), name(5, c), 1, false)
	}
	if ok, p := g.DijkstraSearch("r0c0", "r5c5"); !ok || lastCost(p) != 10 {
		t.Fatalf("after regrow: ok=%v cost=%v, want cost 10", ok, lastCost(p))
	}
}

// TestRepeatedSearchesDeterministic runs many searches on one warm graph
// from different sources and confirms each is independently correct, i.e.
// the O(1) generation reset fully invalidates the previous run's scratch.
func TestRepeatedSearchesDeterministic(t *testing.T) {
	g := buildGrid(10)
	type qc struct {
		from, to string
		cost     float64
	}
	cases := []qc{
		{"r0c0", "r9c9", 18},
		{"r9c9", "r0c0", 18},
		{"r0c0", "r0c9", 9},
		{"r5c5", "r5c5", 0},
		{"r2c3", "r7c1", 7},
	}
	// Interleave repeatedly so each query runs against scratch left dirty
	// by a different previous query.
	for iter := 0; iter < 20; iter++ {
		for _, c := range cases {
			ok, p := g.DijkstraSearch(c.from, c.to)
			if !ok {
				t.Fatalf("iter %d %s->%s: no path", iter, c.from, c.to)
			}
			if lastCost(p) != c.cost {
				t.Fatalf("iter %d %s->%s: cost=%v, want %v", iter, c.from, c.to, lastCost(p), c.cost)
			}
		}
	}
}