topological-sort_test.go

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

package jobqueue

import (
	"reflect"
	"testing"
)

func TestTopologicalSortJobs(t *testing.T) {
	// Create a sample set of jobs with dependencies and priorities

	job1 := &Job[string]{id: "1", priority: PriorityDefault}
	job2 := &Job[string]{id: "2", priority: PriorityHigh, dependencies: []JobID{"1"}}
	job3 := &Job[string]{id: "3", priority: PriorityLow, dependencies: []JobID{"1"}}
	job4 := &Job[string]{id: "4", priority: PriorityCritical, dependencies: []JobID{"3"}}
	job5 := &Job[string]{id: "5", dependencies: []JobID{"2", "4"}}

	jobs := []GenericJob{
		job1,
		job2,
		job3,
		job4,
		job5,
	}

	// Call the function to get the sorted job IDs
	sortedJobIDs, err := topologicalSortJobs(jobs)
	if err != nil {
		t.Errorf("Error in sorting jobs: %v", err)
	}

	// Define the expected order
	expectedOrder := []JobID{"1", "2", "3", "4", "5"}

	// Check if the result matches the expected order
	if !reflect.DeepEqual(sortedJobIDs, expectedOrder) {
		t.Errorf("Expected order %v, but got %v", expectedOrder, sortedJobIDs)
	}
}

func TestTopologicalSortJobs2(t *testing.T) {
	// Create a sample set of jobs with dependencies and priorities

	job1 := &Job[string]{id: "1", priority: PriorityHigh}
	job2 := &Job[string]{id: "2", priority: PriorityHigh, dependencies: []JobID{"1"}}
	job3 := &Job[string]{id: "3", priority: PriorityLow, dependencies: []JobID{"1"}}
	job4 := &Job[string]{id: "4", priority: PriorityCritical, dependencies: []JobID{"3"}}
	job5 := &Job[string]{id: "5", dependencies: []JobID{"2", "4"}}

	jobs := []GenericJob{
		job1,
		job2,
		job3,
		job4,
		job5,
	}

	// Call the function to get the sorted job IDs
	sortedJobIDs, err := topologicalSortJobs(jobs)
	if err != nil {
		t.Errorf("Error in sorting jobs: %v", err)
	}

	// Define the expected order
	expectedOrder := []JobID{"1", "2", "3", "4", "5"}

	// Check if the result matches the expected order
	if !reflect.DeepEqual(sortedJobIDs, expectedOrder) {
		t.Errorf("Expected order %v, but got %v", expectedOrder, sortedJobIDs)
	}
}

func TestTopologicalSortJobsNodePendencies(t *testing.T) {
	// Create a sample set of jobs with no dependencies
	job1 := &Job[string]{id: "1"}
	job2 := &Job[string]{id: "2"}
	job3 := &Job[string]{id: "3"}

	jobs := []GenericJob{
		job1,
		job2,
		job3,
	}

	// Call the function to get the sorted job IDs
	sortedJobIDs, err := topologicalSortJobs(jobs)
	if err != nil {
		t.Errorf("Error in sorting jobs: %v", err)
	}

	// Define the expected order (in any order because they have no dependencies)
	expectedOrder := []JobID{"3", "2", "1"}

	// Check if the result contains the same elements as the expected order
	if len(sortedJobIDs) != len(expectedOrder) {
		t.Errorf("Expected order %v, but got %v", expectedOrder, sortedJobIDs)
	}
}

func TestTopologicalSortJobs_EmptyMap(t *testing.T) {
	jobs := []GenericJob{}
	sortedJobIDs, err := topologicalSortJobs(jobs)
	if err != nil {
		t.Errorf("Error in sorting jobs: %v", err)
	}
	if len(sortedJobIDs) != 0 {
		t.Errorf("Expected empty slice, got %v", sortedJobIDs)
	}
}

func TestTopologicalSortJobs_CycleDetected(t *testing.T) {
	// Creating a cycle 1 -> 2 -> 3 -> 1
	job1 := &Job[string]{id: "1", dependencies: []JobID{"3"}}
	job2 := &Job[string]{id: "2", dependencies: []JobID{"1"}}
	job3 := &Job[string]{id: "3", dependencies: []JobID{"2"}}

	jobs := []GenericJob{
		job1,
		job2,
		job3,
	}

	_, err := topologicalSortJobs(jobs)
	if err != ErrCycleDetected {
		t.Errorf("Expected ErrCycleDetected, got %v", err)
	}
}

func TestTopologicalSortJobs_SingleNode(t *testing.T) {
	job1 := &Job[string]{id: "1"}

	jobs := []GenericJob{
		job1,
	}

	sortedJobIDs, err := topologicalSortJobs(jobs)
	if err != nil {
		t.Errorf("Error in sorting jobs: %v", err)
	}
	if !reflect.DeepEqual(sortedJobIDs, []JobID{"1"}) {
		t.Errorf("Expected [\"1\"], got %v", sortedJobIDs)
	}
}

func TestTopologicalSortJobs_MissingDependency(t *testing.T) {
	job1 := &Job[string]{id: "1"}
	job2 := &Job[string]{id: "2", dependencies: []JobID{"3"}}

	jobs := []GenericJob{
		job1,
		job2,
	}

	_, err := topologicalSortJobs(jobs)
	if err != nil && err != ErrMissingDependency {
		t.Errorf("Expected ErrMissingDependency, got %v", err)
	}
}

func TestTopologicalSortJobs_SelfDependency(t *testing.T) {
	// job 1 depends on itself
	job1 := &Job[string]{id: "1", dependencies: []JobID{"1"}}

	jobs := []GenericJob{
		job1,
	}

	_, err := topologicalSortJobs(jobs)
	if err != ErrCycleDetected {
		t.Errorf("Expected ErrCycleDetected, got %v", err)
	}
}

func TestTopologicalSortJobs_MultipleEdges(t *testing.T) {
	// job 3 and job 4 both depend on job 2
	job1 := &Job[string]{id: "1"}
	job2 := &Job[string]{id: "2", dependencies: []JobID{"1"}}
	job3 := &Job[string]{id: "3", dependencies: []JobID{"2"}}
	job4 := &Job[string]{id: "4", dependencies: []JobID{"2"}}

	jobs := []GenericJob{
		job1,
		job2,
		job3,
		job4,
	}

	sortedJobIDs, err := topologicalSortJobs(jobs)
	if err != nil {
		t.Errorf("Error in sorting jobs: %v", err)
	}
	if !reflect.DeepEqual(sortedJobIDs, []JobID{"1", "2", "3", "4"}) && !reflect.DeepEqual(sortedJobIDs, []JobID{"1", "2", "4", "3"}) {
		t.Errorf("Unexpected order: %v", sortedJobIDs)
	}
}

func TestTopologicalSortJobs_Multipledependencies(t *testing.T) {
	// job 3 depends on both job 1 and job 2
	job1 := &Job[string]{id: "1"}
	job2 := &Job[string]{id: "2"}
	job3 := &Job[string]{id: "3", dependencies: []JobID{"1", "2"}}

	jobs := []GenericJob{
		job1,
		job2,
		job3,
	}

	sortedJobIDs, err := topologicalSortJobs(jobs)
	if err != nil {
		t.Errorf("Error in sorting jobs: %v", err)
	}
	if !reflect.DeepEqual(sortedJobIDs, []JobID{"1", "2", "3"}) && !reflect.DeepEqual(sortedJobIDs, []JobID{"2", "1", "3"}) {
		t.Errorf("Unexpected order: %v", sortedJobIDs)
	}
}

func TestTopologicalSortJobs_PriorityIgnoredInCycle(t *testing.T) {
	// Cycle exists even if one job has high priority
	job1 := &Job[string]{id: "1", priority: PriorityHigh, dependencies: []JobID{"2"}}
	job2 := &Job[string]{id: "2", dependencies: []JobID{"1"}}

	jobs := []GenericJob{
		job1,
		job2,
	}

	_, err := topologicalSortJobs(jobs)
	if err != ErrCycleDetected {
		t.Errorf("Expected ErrCycleDetected, got %v", err)
	}
}

func TestTopologicalSortJobs_IsNotAvailable(t *testing.T) {
	// Cycle exists even if one job has high priority
	job1 := &Job[string]{id: "1", priority: PriorityHigh, dependencies: []JobID{"3"}}
	job2 := &Job[string]{id: "2"}

	jobs := []GenericJob{
		job1,
		job2,
	}

	_, err := topologicalSortJobs(jobs)
	if err != ErrMissingDependency {
		t.Errorf("Expected ErrMissingDependency, got %v", err)
	}
}