// Copyright 2023 schukai GmbH
// SPDX-License-Identifier: AGPL-3.0

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
}