jobsorter.go

package main

import (
	"errors"
	"fmt"
)

type job struct {
	Name  string
	After []string
}

func main() {
	/*
		Plan jobs parallel execution:
			  0
			   `---- 1 ------------- 4 ------ 7
			   `                     |        |
			   `--- 3                |        |
			   `     `------- 2 -----/        |
			   `     `------- 5 ------------ /
			   `     `------- 6 ----------- /
		       `
				`--- 8
				  	 `------- 9
				 	 `------- 10
				 	 `------- 11
		Expected output (each group means parallel execution):
			[[1 3 8] [2 5 6 9 10 11] [4] [7]]
	*/
	job := []job{
		{Name: "1"},
		{Name: "2", After: []string{"3"}},
		{Name: "3"},
		{Name: "4", After: []string{"1", "2"}},
		{Name: "5", After: []string{"3"}},
		{Name: "6", After: []string{"3"}},
		{Name: "7", After: []string{"4", "5", "6"}},
		{Name: "8"},
		{Name: "9", After: []string{"8"}},
		{Name: "10", After: []string{"8"}},
		{Name: "11", After: []string{"8"}},
	}

	result, err := orderJobs(job)
	if err != nil {
		panic(err)
	}

	fmt.Printf("%v\n", result)
}

func orderJobs(jobs []job) ([][]string, error) {
	var (
		result [][]string
		done   []string
	)

	for range jobs {
		var group []string
		for _, j := range jobs {
			if contains(done, j.Name) {
				continue
			}
			if len(j.After) == 0 || containsAll(done, j.After) {
				group = append(group, j.Name)
			}
		}

		if len(group) == 0 {
			break
		}

		result = append(result, group)
		done = append(done, group...)

		if len(done) == len(jobs) {
			break
		}
	}

	if len(done) != len(jobs) {
		return nil, errors.New("cyclic dependency")
	}
	return result, nil
}

func contains(items []string, find string) bool {
	for _, s := range items {
		if s == find {
			return true
		}
	}
	return false
}

func containsAll(items []string, find []string) bool {
	if len(find) == 0 || len(items) == 0 {
		return false
	}
	for _, s := range find {
		if !contains(items, s) {
			return false
		}
	}
	return true
}