before/after ordering test

order_test.go

package main

import (
	"errors"
	"fmt"
	"testing"
)

type App struct {
	Name   string
	Before []string
	After  []string
}

func (a *App) IsBefore(name string) bool {
	if len(a.Before) > 0 &&
		ListContains(a.Before, name) {
		return true
	}
	return false
}

func (a *App) IsAfter(name string) bool {
	if len(a.After) > 0 &&
		ListContains(a.After, name) {
		return true
	}
	return false
}

// ListContains determines whether the given string is contained in the
// given list of strings.
func ListContains(list []string, str string) bool {
	for _, k := range list {
		if k == str {
			return true
		}
	}
	return false
}

// maybeOrderBeforeAfter does naiive ordering of apps using Before/After
// criteria, Returned a list of ordered apps needs verification if dependencies
// of each app were satisfied.
func maybeOrderBeforeAfter(apps []App) []App {
	ord := make([]App, len(apps))
	copy(ord, apps)
	// ord := apps

	for i := range ord {
		for j := range ord {
			if j == i {
				continue
			}
			var swap bool
			if !swap && i < j && ord[i].IsAfter(ord[j].Name) {
				swap = true
			}
			if !swap && i > j && ord[i].IsBefore(ord[j].Name) {
				swap = true
			}
			if !swap && j < i && ord[j].IsAfter(ord[i].Name) {
				swap = true
			}
			if !swap && j > i && ord[j].IsBefore(ord[i].Name) {
				swap = true
			}
			if swap {
				tmp := ord[i]
				ord[i] = ord[j]
				ord[j] = tmp
			}

		}
	}
	return ord
}

// orderBeforeAfterBubbleSort orders apps according to Before/After conditions.
// If the dependencies cannot be satisfied, returns the error and a partially
// ordered list.
func orderBeforeAfterBubbleSort(apps []App) ([]App, error) {

	ordered := maybeOrderBeforeAfter(apps)

	appsListContains := func(apps []App, names ...string) bool {
		for _, name := range names {
			var found bool
			for _, app := range apps {
				if app.Name == name {
					found = true
					break
				}
			}
			if !found {
				return false
			}
		}
		return true
	}

	for i := range ordered {
		after := appsListContains(ordered[0:i], ordered[i].After...)
		before := appsListContains(ordered[i+1:], ordered[i].Before...)
		if !after || !before {
			return ordered, fmt.Errorf("dependencies not satisfied for %v", ordered[i].Name)
		}
	}
	return ordered, nil
}

// maybeOrderBeforeAfter does naiive ordering of apps using Before/After
// criteria, Returned a list of ordered apps needs verification if dependencies
// of each app were satisfied.
func orderBeforeAfterKahn(apps []App) ([]App, error) {
	graph := make([]App, len(apps))
	copy(graph, apps)
	out := make([]App, 0, len(apps))

	indegrees := map[string]int{}
	graphAppMap := map[string]*App{}
	appMap := map[string]App{}
	edges := 0

	// prepare some helpers
	for i := range graph {
		graphAppMap[graph[i].Name] = &graph[i]
		appMap[graph[i].Name] = graph[i]
	}

	for i := range graph {
		// convert afters to befores
		for _, after := range graph[i].After {
			if !ListContains(graphAppMap[after].Before, graph[i].Name) {
				graphAppMap[after].Before = append(graphAppMap[after].Before,
					graph[i].Name)
			}
		}
		graph[i].After = nil
	}

	for i := range graph {
		// 'before' count as indegree of other appOther
		// appOther <--- app (app is before)
		for _, other := range graph[i].Before {
			indegrees[other] += 1
			edges += 1
		}
	}

	queue := make([]App, 0, len(graph))
	for i := 0; i < len(graph); i++ {
		app := graph[i]
		if indegrees[app.Name] == 0 {
			queue = append(queue, app)
		}
	}

	// Kahn:
	// - queue: nodes without incoming edges
	// - out: sorted nodes
	//
	// Nodes without incoming edges are 'top' nodes and are appended to
	// 'out'. On each iteration, take the next 'top' node, and decrease each
	// adjecent node's indegree (count of incoming edges). Once that
	// adjecent node's indegree is 0 (no incoming edges) is can become a
	// 'top' node and is put on the queue.
	for len(queue) > 0 {
		u := queue[0]
		queue = queue[1:]
		out = append(out, u)
		for _, before := range u.Before {
			indegrees[before] -= 1
			edges -= 1
			if indegrees[before] == 0 {
				queue = append(queue, *graphAppMap[before])
			}
		}
	}

	// fixup the output so that we return 'unmodified' entries
	for i := range out {
		out[i] = appMap[out[i].Name]
	}

	if edges != 0 {
		return out, errors.New("cycle detected")
	}
	return out, nil
}

var tcs = []struct {
	apps []App
	err  error
	exp  [][]string
}{
	{
		apps: []App{
			{
				Name: "baz",
			},
			{
				Name:   "bar",
				Before: []string{"baz"},
			},
			{
				Name:   "foo",
				Before: []string{"bar"},
			},
			{
				Name:  "zed",
				After: []string{"foo"},
			},
		},
		exp: [][]string{
			{"foo", "bar", "baz", "zed"},
			{"foo", "zed", "bar", "baz"},
			{"foo", "bar", "zed", "baz"},
		},
	},
	{
		apps: []App{
			{
				Name:  "baz",
				After: []string{"bar"},
			},
			{
				Name:   "bar",
				Before: []string{"baz"},
			},
			{
				Name:   "foo",
				Before: []string{"bar"},
			},
			{
				Name:   "zed",
				After:  []string{"foo"},
				Before: []string{"baz", "bar"},
			},
		},
		exp: [][]string{{"foo", "zed", "bar", "baz"}},
	},
	{
		apps: []App{
			{
				Name:  "baz",
				After: []string{"bar"},
			},
			{
				Name:   "bar",
				Before: []string{"baz"},
			},
			{
				Name:   "foo",
				Before: []string{"bar"},
			},
			{
				Name:   "zed",
				After:  []string{"foo"},
				Before: []string{"baz", "bar"},
			},
		},
		exp: [][]string{{"foo", "zed", "bar", "baz"}},
	},
	{
		apps: []App{
			{
				Name:  "baz",
				After: []string{"bar"},
			},
			{
				Name:   "bar",
				Before: []string{"baz"},
			},
			{
				Name:   "foo",
				Before: []string{"zed"},
			},
			{
				Name:   "zed",
				After:  []string{"foo"},
				Before: []string{"baz", "bar"},
			},
		},
		exp: [][]string{{"foo", "zed", "bar", "baz"}},
	},
	{
		apps: []App{
			{
				Name:  "1",
				After: []string{"2"},
			},
			{
				Name:   "2",
				Before: []string{"1"},
			},
		},
		exp: [][]string{{"2", "1"}},
	},
	{
		apps: []App{
			{
				Name:  "1",
				After: []string{"2"},
			},
			{
				Name:  "2",
				After: []string{"1"},
			},
		},
		err: errors.New("foo"),
	},
	{
		// already ordered
		apps: []App{
			{
				Name:   "foo",
				Before: []string{"bar"},
			},
			{
				Name:   "bar",
				Before: []string{"baz"},
			},
			{
				Name: "baz",
			},
			{
				Name:  "zed",
				After: []string{"foo"},
			},
		},
		exp: [][]string{
			{"foo", "bar", "baz", "zed"},
			{"foo", "bar", "zed", "baz"},
		},
	},
	{
		apps: []App{
			{
				Name: "foo",
			},
			{
				Name: "bar",
			},
			{
				Name: "baz",
			},
			{
				Name: "zed",
			},
		},
		exp: [][]string{
			{"foo", "bar", "baz", "zed"},
			{"foo", "bar", "zed", "baz"},
			{"foo", "zed", "bar", "baz"},
			{"foo", "zed", "baz", "bar"},
			{"foo", "zed", "zed", "bar"},
			{"foo", "baz", "bar", "zed"},
			{"zed", "foo", "bar", "baz"},
			{"zed", "foo", "baz", "bar"},
			{"zed", "bar", "foo", "baz"},
			{"zed", "bar", "baz", "foo"},
			{"bar", "zed", "baz", "foo"},
			{"bar", "baz", "zed", "foo"},
			{"bar", "baz", "foo", "zed"},
			{"bar", "foo", "zed", "baz"},
			{"baz", "zed", "bar", "foo"},
			{"baz", "zed", "foo", "bar"},
			{"baz", "foo", "zed", "bar"},
			{"zed", "baz", "foo", "bar"},
		},
	},
	{
		// reverse ordered
		apps: []App{
			{
				Name:  "zed",
				After: []string{"foo"},
			},
			{
				Name: "baz",
			},
			{
				Name:   "bar",
				Before: []string{"baz"},
			},
			{
				Name:   "foo",
				Before: []string{"bar"},
			},
		},
		exp: [][]string{
			{"foo", "bar", "baz", "zed"},
			{"foo", "bar", "zed", "baz"},
			{"foo", "zed", "bar", "baz"},
		},
	},
	{
		// reverse ordered
		apps: []App{
			{
				Name:  "zed",
				After: []string{"foo", "bar", "baz"},
				// Before: []string{"baz"},
			},
			{
				Name: "baz",
			},
			{
				Name:   "bar",
				Before: []string{"baz"},
			},
			{
				Name:  "foo",
				After: []string{"baz"},
			},
		},
		exp: [][]string{{"bar", "baz", "foo", "zed"}},
	},
	{
		apps: []App{
			{
				Name: "zed",
			},
			{
				Name:   "baz",
				Before: []string{"zed"},
			},
			{
				Name:   "bar",
				Before: []string{"baz"},
			},
			{
				Name:   "foo",
				Before: []string{"bar"},
				After:  []string{"zed"},
			},
		},
		err: errors.New("foo"),
	},
	{
		apps: []App{
			{
				Name:  "zed",
				After: []string{"foo", "bar", "baz"},
				// Before: []string{"baz"},
			},
			{
				Name:  "foo",
				After: []string{"baz"},
			},
			{
				Name:   "bar",
				Before: []string{"baz"},
			},
			{
				Name: "baz",
			},
		},
		exp: [][]string{{"bar", "baz", "foo", "zed"}},
	},
}

func nextPerm(p []int) {
	for i := len(p) - 1; i >= 0; i-- {
		if i == 0 || p[i] < len(p)-i-1 {
			p[i]++
			return
		}
		p[i] = 0
	}
}

func permute(orig []App, p []int) []App {
	result := append([]App{}, orig...)
	for i, v := range p {
		result[i], result[i+v] = result[i+v], result[i]
	}
	return result
}

func testValidate(t *testing.T, orderFunc func(apps []App) ([]App, error)) {
	for i := range tcs {
		tc := tcs[i]
		t.Run(fmt.Sprintf("tc %d", i), func(t *testing.T) {
			apps := make([]App, len(tc.apps))
			copy(apps, tc.apps)

			for p := make([]int, len(apps)); p[0] < len(p); nextPerm(p) {
				apps = permute(apps, p)
				ord, err := orderFunc(apps)
				t.Logf("err: %v exp err: %v\n", err, tc.err)
				t.Logf("\nin:  %v\ngot: %v err: %v", apps, ord, err)
				if tc.err != nil {
					if err == nil {
						t.Logf("expected error")
						t.Fail()
					}
				} else {
					if err != nil {
						t.Log("unexpected error")
						t.Fail()
					}

					var mismatch bool
					for _, variant := range tc.exp {
						mismatch = false
						if len(variant) != len(ord) {
							t.Logf("length mismatch, expected %v got %v",
								len(variant), len(ord))
							mismatch = true
							continue
						}
						for i := range variant {
							if variant[i] != ord[i].Name {
								mismatch = true
								break
							}
						}
						if !mismatch {
							break
						}
					}
					if mismatch {
						t.Logf("order mismatch, expected variants: %v\n", tc.exp)
						t.Fail()
					}
				}
			}
		})
	}
}
func benchmarkOrder(b *testing.B, orderFunc func(apps []App) ([]App, error)) {
	for i := range tcs {
		tc := tcs[i]
		b.Run(fmt.Sprintf("tc %d", i), func(b *testing.B) {
			for i := 0; i < b.N; i++ {
				orderFunc(tc.apps)
			}
		})
	}

}

func TestValidateBubbleSort(t *testing.T) {
	testValidate(t, orderBeforeAfterBubbleSort)
}

func BenchmarkOrderBubble(b *testing.B) {
	benchmarkOrder(b, orderBeforeAfterBubbleSort)
}

func TestValidateKahn(t *testing.T) {
	testValidate(t, orderBeforeAfterKahn)
}
func BenchmarkOrderKahn(b *testing.B) {
	benchmarkOrder(b, orderBeforeAfterKahn)
}