process-order

main.go

package main

import (
	"fmt"
	"time"
)

func main() {

}

type proc struct {
	id  string
	sub string
}

func ProcessOrder(processes []*proc, p int) []string {
	start := time.Now()
	done := map[string]int{}
	output := make([]string, 0, p)

	fmt.Printf("waiting for all processes to complete\n")
	fmt.Printf("start time: %v\n", start)

	timeLeft := time.Until(time.Now().Add(time.Duration(time.Second * 1)))
	fmt.Printf("time left %2v seconds\n", timeLeft)

	elapsed := time.Now().Sub(start)
	// Loop until time runs out.
timeLoop:
	for elapsed < timeLeft {
		elapsed = time.Now().Sub(start)
		fmt.Printf("time elapsed %v\n", elapsed)
		// Loop until all processes are done
		for i, process := range processes {
			if process != nil && process.id == process.sub {
				panic("parent process is equal to child process")
			}

			if process == nil {
				continue
			}

			fmt.Printf("examine %v\n", process.id)
			fmt.Printf("\t%v is waiting on %v\n", process.id, process.sub)
			if find(processes, process.sub) == -1 {
				fmt.Printf("\tsub process %v is done\n", process.sub)
				_, ok := done[process.sub]
				if !ok {
					output = append(output, process.sub)
				}
				processes[i] = nil
				done[process.sub] = 1
			}

			if find(processes, process.id) == -1 {
				fmt.Printf("\tparent process %v is done\n", process.id)
				_, ok := done[process.id]
				if !ok {
					output = append(output, process.id)
				}
				done[process.id] = 1
			}

			if len(output) >= p {
				fmt.Printf("\tall processes are complete\n")
				break timeLoop
			}
		}
	}

	fmt.Printf("output: %v\n", output)

	return output
}

// find return index of item found or -1.
func find(processes []*proc, id string) int {
	rt := -1

	for i, process := range processes {
		if process != nil && process.id == id {
			rt = i
		}
	}

	return rt
}

main_test.go

package main

import (
	"testing"
)

/* P1 -> P2,  P1 -> P4, P2 -> P3, P4 -> P5, 5 }

Output: P2, P3, P5, P4, P1*/

func TestProcessOrder(t *testing.T) {
	cases := []struct {
		name string
		in   []*proc
		pLen int
		out  []string
	}{
		{
			"1",
			[]*proc{
				{"P1", "P2"},
				{"P1", "P4"},
				{"P2", "P3"},
				{"P4", "P5"},
			},
			5,
			[]string{"P2", "P3", " P5", "P4", "P1"},
		},
	}

	for _, c := range cases {
		t.Run(c.name, func(d *testing.T) {
			got := ProcessOrder(c.in, c.pLen)

			for i, g := range got {
				if g != c.out[i] {
					d.Errorf("got %v, want %v\n", g, c.out[i])
					break
				}
				i++
			}
		})
	}
}