// All-shortest-paths enumeration: a reusable single-source minimum-hop
// parent tree (spTree) for hop-minimal single paths, plus the forward-BFS
// + backward-DFS that enumerates every distinct minimum-hop path a..b and
// resolves each path's relationship positions. Split from shortest.go,
// which holds the stage runner, scratch, and single-path search.
package exec

import (
	
	
	
)

// spTree is a single-source minimum-hop parent tree, reused across every
// row sharing that source.
type spTree struct {
	source graph.NodeID
	parent map[graph.NodeID]graph.NodeID
}

// buildSPTree runs one bounded BFS from a, honoring the same filters the
// per-row search uses so reachability and distances are identical. The
// parent map is retained in the stage memo, so it allocates fresh.
func buildSPTree( *eval.Ctx,  graph.NodeID,  *plan.SpStage,  *graph.RelMatcher,  *hopFilter,  *spScratch) *spTree {
	 := map[graph.NodeID]graph.NodeID{}
	spWalk(, , , , , , func(,  graph.NodeID,  uint64) bool {
		[] = 
		return false
	}, nil)
	return &spTree{source: , parent: }
}

// pathTo reads the minimum-hop path source..b off the parent links,
// returned by value.
func ( *spTree) ( *eval.Ctx,  graph.NodeID,  *plan.SpStage,  *graph.RelMatcher,  *hopFilter,  *spScratch) (nodesRels, bool) {
	 := pathFromParents(, .parent, .source, )
	if  == nil {
		return nodesRels{}, false
	}
	return nodesRels{nodes: , rels: pathRelPositions(, , , .Dir, , )}, true
}

// allShortestPaths enumerates every minimum-hop path a..b: a forward BFS
// records each reached node's minimum distance, then a backward DFS from b
// walks predecessor chains strictly descending the distance -- each
// completed chain is a distinct minimum-hop path.
func allShortestPaths( *eval.Ctx, ,  graph.NodeID,  *plan.SpStage,  *graph.RelMatcher,  *hopFilter,  *spScratch) []nodesRels {
	if  ==  {
		 := .nodeSlice(1)
		[0] = 
		return []nodesRels{{nodes: }}
	}
	// spWalk opens the generation; dist entries are valid under its stamp
	// (scr.cur) until the next search begins.
	spWalk(, , , , , , func(,  graph.NodeID,  uint64) bool {
		.dist[] = uint32()
		return false
	}, func() bool {
		return .gen[] == .cur
	})
	if .gen[] != .cur {
		return nil
	}
	 := flipDir(.Dir)
	var  [][]graph.NodeID
	 := []graph.NodeID{}
	if .preds == nil {
		.preds = map[graph.NodeID][]graph.NodeID{}
	} else {
		clear(.preds)
	}
	enumeratePaths(, , , , , , &, &)
	 := make([]nodesRels, len())
	for ,  := range  {
		[] = nodesRels{nodes: , rels: pathRelPositions(, , , .Dir, , )}
	}
	return 
}

// enumeratePaths extends the reversed suffix [b..v] by each predecessor u
// whose stamped distance is dist[v]-1; reaching a completes one path. The
// enumeration is COMPLETE by decision -- a min-hop DAG can fan out
// combinatorially and every path is the operator's contract -- so the
// work is kept output-proportional: each node's predecessor sequence is
// resolved once per enumeration (predsOf) instead of re-scanning its
// adjacency on every path through it, which charged a hub's whole degree
// per path.
func enumeratePaths( *eval.Ctx,  graph.NodeID,  *spScratch,  graph.Direction,  *graph.RelMatcher,  *hopFilter,  *[]graph.NodeID,  *[][]graph.NodeID) {
	 := (*)[len(*)-1]
	if  ==  {
		 := .nodeSlice(len(*))
		copy(, *)
		reverseNodes()
		* = append(*, )
		return
	}
	for ,  := range predsOf(, , , , , ) {
		* = append(*, )
		(, , , , , , , )
		* = (*)[:len(*)-1]
	}
}

// predsOf memoizes v's minimum-hop predecessor sequence for the current
// enumeration, preserving the exact order (and any multigraph duplicates)
// the filtered neighbor walk yields -- the memo must be sequence-
// identical to the walk it replaces, not merely set-equal, so path output
// order is unchanged.
func predsOf( *eval.Ctx,  graph.NodeID,  *spScratch,  graph.Direction,  *graph.RelMatcher,  *hopFilter) []graph.NodeID {
	if ,  := .preds[];  {
		return 
	}
	 := .dist[] - 1
	 := []graph.NodeID{}
	filteredNeighbors(, , , , , func( graph.NodeID) {
		if .gen[] == .cur && .dist[] ==  {
			 = append(, )
		}
	})
	.preds[] = 
	return 
}

// pathRelPositions resolves each consecutive node pair's relationship
// position (the first accepted relationship between them). Each hop reads
// from its lower-degree endpoint -- resolving from the higher-degree side
// pays a hub's whole adjacency, and a path found by never expanding a
// hub's ply must not re-pay the hub here. The read goes through the batch
// seam into the walk scratch's neighbor buffers (an iterator closure per
// hop dominated shortest-path stages' allocations); it runs only after a
// walk completes, so the buffers are free (same rule as
// appendHopNeighbors). Positions read identically from either side (the
// incoming seam maps to stored positions), so the side pick cannot change
// the resolved rel set.
func pathRelPositions( *eval.Ctx,  *spScratch,  []graph.NodeID,  graph.Direction,  *graph.RelMatcher,  *hopFilter) []uint32 {
	 := .relSlice(max(len()-1, 0))[:0]
	 := flipDir()
	for  := 0; +1 < len(); ++ {
		,  := [], [+1]
		, ,  := , , 
		if .G.Degree(, ) < .G.Degree(, ) {
			, ,  = , , 
		}
		.nbNodes, .nbPoss = .G.AppendRelationshipsMatched(.nbNodes[:0], .nbPoss[:0], , , )
		for ,  := range .nbNodes {
			if  ==  && ( == nil || .keep(, .nbPoss[])) {
				 = append(, .nbPoss[])
				break
			}
		}
	}
	return 
}

// reverseNodes reverses a node sequence in place.
func reverseNodes( []graph.NodeID) {
	for ,  := 0, len()-1;  < ; ,  = +1, -1 {
		[], [] = [], []
	}
}