Method sortResult

analysis/stratification.go:183–214

sortResult sorts the strata topologically (ignoring cycles).

(strata []Nodeset, predToStratumMap map[ast.PredicateSym]int)

// sortResult sorts the strata topologically (ignoring cycles).
func (dep depGraph) sortResult(strata []Nodeset, predToStratumMap map[ast.PredicateSym]int) ([]Nodeset, map[ast.PredicateSym]int) {
	var sorted []int
	seen := make(map[int]struct{})
	var visitStratum func(index int)
	visitStratum = func(index int) {
		if _, ok := seen[index]; ok {
			return
		}
		seen[index] = struct{}{}
		for sym := range strata[index] {
			for d := range dep[sym] {
				visitStratum(predToStratumMap[d])
			}
		}
		sorted = append(sorted, index)
	}

	for i := 0; i < len(strata); i++ {
		visitStratum(i)
	}
	newstrata := make([]Nodeset, len(strata), len(strata))
	oldToNew := make(map[int]int)
	for i := 0; i < len(strata); i++ {
		newstrata[i] = strata[sorted[i]]
		oldToNew[sorted[i]] = i
	}
	newPredToStratumMap := make(map[ast.PredicateSym]int, len(predToStratumMap))
	for sym := range predToStratumMap {
		newPredToStratumMap[sym] = oldToNew[predToStratumMap[sym]]
	}
	return newstrata, newPredToStratumMap
}