search.go

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

package dijkstra

// search.go holds the integer-indexed, allocation-reusing internals of
// the Dijkstra / A* relaxation pass. It is the performance core that
// the exported DijkstraSearch / DijkstraRun / AStarSearch* methods drive.
//
// Why a separate scratch space at all?
//
// The exported StVertex fields (Weight, Visited, Parent) and the per-edge
// isShort flag are part of the documented post-search contract: DijkstraRun
// promises to populate them on every reachable vertex, and ShowDijkstra /
// the path walk read them back. But touching those fields through the
// name-indexed accessors (vertexGetWeightLocked, maskShortEdgeLocked, ...)
// means a map lookup per access, and the inner relaxation loop performs
// several per edge. That string-keyed map traffic -- not allocation, which
// is already low -- is the dominant cost on large graphs.
//
// stSearch caches contiguous, integer-indexed slices (dist, parent,
// visited, ...) on the graph and reuses them across searches. The
// relaxation loop runs entirely on those slices and on g.vertex[i] by
// index, so the hot path does zero map lookups and zero per-search
// allocation once the scratch has grown to the graph's size. A single
// generation counter (gen) invalidates the per-vertex working state in
// O(1) instead of clearing every slot each call. At the end of a search
// the cached results are reconciled back into the exported StVertex fields
// so the documented behaviour is preserved exactly.
//
// Concurrency: stSearch lives on the StGraph and is mutated only while the
// caller holds g.mu for writing (every search path takes g.mu.Lock).
// Concurrent searches on one graph therefore serialise -- exactly as
// before -- and remain race-free; the cache adds no new shared state that
// is read or written outside the write lock.

// stSearch is the reusable, integer-indexed working state for one graph's
// searches. All slices are indexed by vertex slice position (the same
// index VertexFind returns) and are grown lazily to len(g.vertex).
type stSearch struct {
	// gen is the current search generation. Bumping it logically clears
	// dist / visited / inHeap without touching their contents: a slot is
	// "set this search" iff its companion stamp == gen.
	gen uint32

	// Per-vertex working state, indexed by vertex slice position. dist,
	// parent and parentEdge are written only when a vertex is *finalised*,
	// and finalised vertices are listed in `touched`; the reconcile reads
	// them back from there, so they need no per-slot generation stamp.
	// Only visGn needs a stamp: it answers "visited this search?" in O(1)
	// without an O(V) clear (== gen means finalised this generation).
	dist       []float64 // final g-cost to each finalised vertex this search
	parent     []int32   // predecessor index in the SP tree, -1 for the source
	parentEdge []int32   // edge index in g.vertex[parent[i]].Edges, -1 for source
	visGn      []uint32  // gen at which vertex i was finalised (== gen means visited)
	gnLen      int       // length of visGn known free of stale stamps

	// touched lists every vertex finalised during the current search, so
	// the post-search reconcile into the exported StVertex fields visits
	// only those rather than scanning all V.
	touched []int32

	heap stIntHeap // reusable binary min-heap over vertex indices

	// Integer-indexed adjacency (CSR layout) cached across searches. The
	// graph stores edges by destination *name*; resolving each name to an
	// index every relaxation is the main per-edge cost. We resolve once
	// per topology change into edgeHead/edgeTo/edgeW and reuse it while
	// topoSeen == g.topoVer.
	//
	//   for vertex i, its edges occupy edge* indices [edgeHead[i], edgeHead[i+1])
	//   edgeTo[k] = destination vertex index (-1 if the name is dangling)
	//   edgeW[k]  = edge weight
	//
	// The position of edge k within g.vertex[i].Edges (needed to set
	// isShort) is simply k - edgeHead[i], so it is not stored separately.
	topoSeen uint64
	edgeHead []int32
	edgeTo   []int32
	edgeW    []float64

	// blocked[i] == blkGen means vertex i is currently blocked. Rebuilt
	// each search (cheaply: only the blocked names are stamped) so dynamic
	// blocking still takes effect immediately, with O(1) integer tests in
	// the hot loop instead of a name-keyed map lookup per edge.
	blkStamp []uint32
	blkGen   uint32
	blkLen   int // length of blkStamp known to be free of stale stamps
}

// stHeapItem is one priority-queue entry, keyed by integer vertex indices
// instead of strings. It also carries the already-resolved tree edge
// (fromEdge, the position in g.vertex[from].Edges) and the cumulative
// g-cost g to reach `to` via that edge, both computed at enqueue time --
// so the dequeue side needs no edge re-scan or weight re-lookup, unlike
// the name-keyed path it replaces. pri is the ordering key (g for
// Dijkstra, g+h for A*). seq preserves FIFO order within equal priorities
// (matching the exported StPriorityQueue's tie-break).
type stHeapItem struct {
	from     int32
	to       int32
	fromEdge int32
	g        float64
	pri      float64
	seq      uint64
}

// stIntHeap is an ascending binary min-heap of stHeapItem whose backing
// array is reused across searches (reset to length 0, capacity retained).
type stIntHeap struct {
	a   []stHeapItem
	seq uint64
}

func (h *stIntHeap) reset() {
	h.a = h.a[:0]
	h.seq = 0
}

func (h *stIntHeap) len() int { return len(h.a) }

func (h *stIntHeap) less(i, j int) bool {
	if h.a[i].pri != h.a[j].pri {
		return h.a[i].pri < h.a[j].pri
	}
	return h.a[i].seq < h.a[j].seq
}

func (h *stIntHeap) push(from, to, fromEdge int32, g, pri float64) {
	h.a = append(h.a, stHeapItem{from: from, to: to, fromEdge: fromEdge, g: g, pri: pri, seq: h.seq})
	h.seq++
	// sift up
	i := len(h.a) - 1
	for i > 0 {
		parent := (i - 1) / 2
		if !h.less(i, parent) {
			break
		}
		h.a[i], h.a[parent] = h.a[parent], h.a[i]
		i = parent
	}
}

func (h *stIntHeap) pop() (stHeapItem, bool) {
	n := len(h.a)
	if n == 0 {
		return stHeapItem{}, false
	}
	top := h.a[0]
	last := n - 1
	h.a[0] = h.a[last]
	h.a = h.a[:last]
	if last > 0 {
		h.down(0)
	}
	return top, true
}

func (h *stIntHeap) down(i int) {
	n := len(h.a)
	for {
		left := 2*i + 1
		if left >= n {
			break
		}
		smallest := left
		if right := left + 1; right < n && h.less(right, left) {
			smallest = right
		}
		if !h.less(smallest, i) {
			break
		}
		h.a[i], h.a[smallest] = h.a[smallest], h.a[i]
		i = smallest
	}
}

// begin starts a new search generation, growing the per-vertex scratch to
// at least n slots, and returns the search scratch ready for use. The
// generation counter makes the logical clear O(1); the only O(n) work is
// the one-time grow when the graph got bigger. Caller holds g.mu.
func (g *StGraph) searchBegin(n int) *stSearch {
	s := &g.search
	if cap(s.dist) < n {
		// Grow once with headroom; reused on subsequent searches. make
		// zero-initialises visGn, so no slot can falsely match gen.
		s.dist = make([]float64, n)
		s.parent = make([]int32, n)
		s.parentEdge = make([]int32, n)
		s.visGn = make([]uint32, n)
		s.gnLen = n
	} else {
		s.dist = s.dist[:n]
		s.parent = s.parent[:n]
		s.parentEdge = s.parentEdge[:n]
		s.visGn = s.visGn[:n]
		// Zero any stamp slots that have just re-entered range after the
		// graph grew; otherwise they could hold a stale value equal to the
		// current gen and be misread as "visited this search". Growth-only.
		for i := s.gnLen; i < n; i++ {
			s.visGn[i] = 0
		}
		if n > s.gnLen {
			s.gnLen = n
		}
	}

	s.gen++
	if s.gen == 0 {
		// Wrapped after ~4 billion searches: stamps could collide with a
		// stale slot. Zero them once so the fresh gen (1) is unambiguous.
		for i := range s.visGn {
			s.visGn[i] = 0
		}
		s.gen = 1
	}

	s.touched = s.touched[:0]
	s.heap.reset()

	g.buildAdjacencyLocked()
	g.buildBlockedLocked()
	return s
}

// buildAdjacencyLocked (re)builds the integer-indexed CSR adjacency from
// the name-keyed edges, but only when the graph's topology has changed
// since the last build. On an unchanged graph -- the common repeated-query
// case -- it is a single comparison and returns immediately, so searches
// pay the name->index resolution exactly once per structural edit instead
// of once per edge per search. Caller holds g.mu.
func (g *StGraph) buildAdjacencyLocked() {
	s := &g.search
	if s.edgeHead != nil && s.topoSeen == g.topoVer {
		return
	}

	n := len(g.vertex)
	totalEdges := 0
	for i := range g.vertex {
		totalEdges += len(g.vertex[i].Edges)
	}

	if cap(s.edgeHead) < n+1 {
		s.edgeHead = make([]int32, n+1)
	} else {
		s.edgeHead = s.edgeHead[:n+1]
	}
	if cap(s.edgeTo) < totalEdges {
		s.edgeTo = make([]int32, totalEdges)
		s.edgeW = make([]float64, totalEdges)
	} else {
		s.edgeTo = s.edgeTo[:totalEdges]
		s.edgeW = s.edgeW[:totalEdges]
	}

	k := 0
	for i := range g.vertex {
		s.edgeHead[i] = int32(k)
		for j := range g.vertex[i].Edges {
			e := &g.vertex[i].Edges[j]
			to := int32(-1)
			if idx, ok := g.index[e.ToVertexName]; ok {
				to = int32(idx)
			}
			s.edgeTo[k] = to
			s.edgeW[k] = e.Weight
			k++
		}
	}
	s.edgeHead[n] = int32(k)
	s.topoSeen = g.topoVer
}

// buildBlockedLocked stamps the integer indices of currently blocked
// vertices for this search so the relaxation loop can test "is this
// neighbour blocked" with an O(1) integer compare instead of a name-keyed
// map lookup. Only the blocked names are touched (the set is typically
// small), and it is rebuilt every search so blocking/unblocking still
// takes effect on the very next search. Caller holds g.mu.
func (g *StGraph) buildBlockedLocked() {
	s := &g.search
	n := len(g.vertex)
	if cap(s.blkStamp) < n {
		s.blkStamp = make([]uint32, n) // zero-initialised
		s.blkLen = n
	} else {
		s.blkStamp = s.blkStamp[:n]
		// Slots that have just come back into range (because the graph
		// grew since this slice was last zeroed) may hold stale stamps
		// from an earlier era; zero them so they cannot falsely match
		// blkGen. This runs only on growth, not every search.
		for i := s.blkLen; i < n; i++ {
			s.blkStamp[i] = 0
		}
		if n > s.blkLen {
			s.blkLen = n
		}
	}
	// Always advance blkGen so any stamps left by a previous search (when
	// different vertices may have been blocked) are now stale and read as
	// unblocked; an empty blocked set then leaves nothing stamped == blkGen.
	s.blkGen++
	if s.blkGen == 0 {
		for i := range s.blkStamp {
			s.blkStamp[i] = 0
		}
		s.blkGen = 1
	}
	for name := range g.blocked {
		if idx, ok := g.index[name]; ok {
			s.blkStamp[idx] = s.blkGen
		}
	}
}

// isBlocked reports whether vertex index i was blocked for this search.
func (s *stSearch) isBlocked(i int32) bool {
	return s.blkStamp[i] == s.blkGen
}

// visited reports whether vertex i has been finalised this generation.
func (s *stSearch) visited(i int32) bool { return s.visGn[i] == s.gen }

// finalise records vertex i as settled this search with the given g-cost,
// predecessor index and the edge (in g.vertex[parent].Edges) that reached
// it, and appends it to the touched list for the reconcile. parent/edge
// are -1 for the source vertex. Each vertex is finalised at most once.
func (s *stSearch) finalise(i, parent, edge int32, g float64) {
	s.visGn[i] = s.gen
	s.dist[i] = g
	s.parent[i] = parent
	s.parentEdge[i] = edge
	s.touched = append(s.touched, i)
}

// runSearchLocked performs one integer-indexed relaxation from start.
//
// It is the shared core of Dijkstra and A*: the only differences are the
// priority used to order the heap (pri) and the optional goal early-exit.
//   - heuristic == nil  -> Dijkstra: pri = g.
//   - heuristic != nil  -> A*:       pri = g + heuristic(neighbour, goal).
//
// goal < 0 disables the early exit (full single-source tree, as Dijkstra
// needs); goal >= 0 stops as soon as that vertex is finalised (A*).
//
// Results land in the scratch (dist / parent / parentEdge / visGn /
// touched); reconcileLocked then mirrors them into the exported StVertex
// fields. Caller holds g.mu. The boolean return matches the legacy
// helpers (always true once the start exists, which the callers verify).
func (g *StGraph) runSearchLocked(start int32, goal int32, heuristic func(toIdx int32) float64) {
	s := &g.search

	startG := 0.0
	startPri := startG
	if heuristic != nil {
		startPri = heuristic(start)
	}
	// The source has no incoming tree edge: from = -1, fromEdge = -1.
	s.heap.push(-1, start, -1, startG, startPri)

	for s.heap.len() > 0 {
		it, _ := s.heap.pop()
		to := it.to
		if s.visited(to) {
			continue
		}
		s.finalise(to, it.from, it.fromEdge, it.g)

		if to == goal {
			return
		}

		gCur := it.g
		base := s.edgeHead[to]
		end := s.edgeHead[to+1]
		for k := base; k < end; k++ {
			nb := s.edgeTo[k]
			if nb < 0 { // dangling edge (target name not a vertex)
				continue
			}
			if s.visited(nb) || s.isBlocked(nb) {
				continue
			}
			gNext := gCur + s.edgeW[k]
			pri := gNext
			if heuristic != nil {
				pri = gNext + heuristic(nb)
			}
			s.heap.push(to, nb, k-base, gNext, pri)
		}
	}
}

// reconcileLocked mirrors the scratch results of the most recent
// runSearchLocked into the exported StVertex fields and per-edge isShort
// flags, reproducing exactly the post-search state that the legacy
// DijkstraRun / aStarRun left behind:
//
//   - every vertex reset to Visited=false, MaskSearch=false, Weight=0,
//     Parent="" and every edge to isShort=false, then
//   - every finalised vertex set to Visited=true, Weight=its g-cost,
//     Parent=its predecessor's name, with the tree edge (and its reverse,
//     when two-way) marked isShort.
//
// The reset is the unavoidable O(V+E) part of the documented contract
// (unreached vertices must read back as Weight 0 / unvisited); the search
// itself no longer pays it. Caller holds g.mu.
func (g *StGraph) reconcileLocked() {
	s := &g.search

	for i := range g.vertex {
		v := &g.vertex[i]
		v.Visited = false
		v.MaskSearch = false
		v.Weight = 0
		v.Parent = ""
		for j := range v.Edges {
			v.Edges[j].isShort = false
		}
	}

	for _, ti := range s.touched {
		v := &g.vertex[ti]
		v.Visited = true
		v.Weight = s.dist[ti]
		p := s.parent[ti]
		if p < 0 {
			continue // source vertex: no parent, no tree edge
		}
		pv := &g.vertex[p]
		v.Parent = pv.Name
		// Forward tree edge parent -> child.
		pe := s.parentEdge[ti]
		if pe >= 0 && int(pe) < len(pv.Edges) {
			pv.Edges[pe].isShort = true
		}
		// Reverse edge child -> parent is also part of the tree when it
		// exists and is two-way (used by the legacy ShowDijkstra view).
		for j := range v.Edges {
			if v.Edges[j].ToVertexName == pv.Name {
				if !v.Edges[j].IsOneWay {
					v.Edges[j].isShort = true
				}
				break
			}
		}
	}
}