Select Git revision
target-phpunit.mk
-
Volker Schukai authoredVolker Schukai authored
topological-sort.go 2.28 KiB
package jobqueue
import "container/heap"
// idPriority is a type that holds a JobID and a Priority
type idPriority struct {
id JobID
priority Priority
}
// idPriorityQueue is a type that holds a slice of idPriority
type idPriorityQueue []idPriority
// Len implements heap.Interface.Len
func (pq *idPriorityQueue) Len() int { return len(*pq) }
// Less implements heap.Interface.Less
func (pq *idPriorityQueue) Less(i, j int) bool {
return (*pq)[i].priority > (*pq)[j].priority
}
// Swap implements heap.Interface.Swap
func (pq *idPriorityQueue) Swap(i, j int) {
(*pq)[i], (*pq)[j] = (*pq)[j], (*pq)[i]
}
// Push implements heap.Interface.Push
func (pq *idPriorityQueue) Push(x interface{}) {
item := x.(idPriority)
*pq = append(*pq, item)
}
// Pop implements heap.Interface.Pop
func (pq *idPriorityQueue) Pop() interface{} {
old := *pq
n := len(old)
item := old[n-1]
*pq = old[0 : n-1]
return item
}
// topologicalSortJobs returns a slice of JobIDs in the order they should be executed
// if there is a cycle, it returns ErrCycleDetected
// if there is a missing dependency, it returns ErrMissingDependency
func topologicalSortJobs(jobs []GenericJob) ([]JobID, error) {
inDegrees := make(map[JobID]int)
jobMap := make(map[JobID]GenericJob)
dependents := make(map[JobID][]JobID)
for _, job := range jobs {
jobID := job.GetID()
inDegrees[jobID] = 0
jobMap[jobID] = job
}
for _, job := range jobs {
jobID := job.GetID()
for _, depID := range job.GetDependencies() {
if _, ok := jobMap[depID]; !ok {
return nil, ErrMissingDependency
}
inDegrees[jobID]++
dependents[depID] = append(dependents[depID], jobID)
}
}
pq := make(idPriorityQueue, 0)
heap.Init(&pq)
for id, inDegree := range inDegrees {
if inDegree == 0 {
heap.Push(&pq, idPriority{id: id, priority: jobMap[id].GetPriority()})
}
}
result := make([]JobID, 0)
for len(pq) > 0 {
idPrio := heap.Pop(&pq).(idPriority)
jobID := idPrio.id
result = append(result, jobID)
for _, dependent := range dependents[jobID] {
inDegrees[dependent]--
if inDegrees[dependent] == 0 {
heap.Push(&pq, idPriority{id: dependent, priority: jobMap[dependent].GetPriority()})
}
}
}
for _, inDegree := range inDegrees {
if inDegree > 0 {
return nil, ErrCycleDetected
}
}
return result, nil
}