-
Notifications
You must be signed in to change notification settings - Fork 0
/
sort.go
80 lines (64 loc) · 2.38 KB
/
sort.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
////////////////////////////////////////////////////////////////////////////////
// Copyright (c) 2017 by Fabian Kohn
//
// This source code is licensed under the Apache License, Version 2.0, found in
// the LICENSE file in the root directory of this source tree.
////////////////////////////////////////////////////////////////////////////////
package topo
import (
"fmt"
"reflect"
"github.com/fako1024/topo/graph"
)
// Type defines a generic data type
type Type interface{}
// Dependency represents a dependency between one Type and another
type Dependency struct {
Child Type
Parent Type
}
// String tries to stringify a dependency. If the type of the dependency fulfills
// the Stringer interface, it will use its String() method, otherwise it will try
// to format the variable otherwise
func (d Dependency) String() string {
return fmt.Sprint(d.Child) + " depends upon " + fmt.Sprint(d.Parent)
}
// Sort performs a topological sort on a slice using a functional approach to generalize
// the input data, constructs a directed graph (using the dependency constraints) and
// finally converts back the resulting object list to the original slice (sort in place)
func Sort(data interface{}, deps []Dependency, getter func(i int) Type, setter func(i int, val Type)) (err error) {
// In case there are no dependencies, return immediately without action
if len(deps) == 0 {
return nil
}
// Obtain the number of elements in the original data slice using reflection
nObj := reflect.ValueOf(data).Len()
// Instantiate a new (empty) graph
gr := graph.NewGraph()
// Add all vertices (based on slice indices) using the 1st class getter function
for i := 0; i < nObj; i++ {
gr.AddVertex(getter(i))
}
// Add all dependencies (based on the enforced struct fields)
for i := 0; i < len(deps); i++ {
if err = gr.AddArc(deps[i].Child, deps[i].Parent); err != nil {
return
}
}
// Perform topological sorting, return error if e.g. a cycle is found
var result graph.ObjectList
if result, err = gr.SortTopological(); err != nil {
return
}
// Sanity check to make sure the resulting slice contains the same number of
// elements as the original data
if len(result) != nObj {
panic("Unexpected mismatch between original and sorted data")
}
// Convert the generic data back to the original slice type using the 1st class
// setter function
for i, val := range result {
setter(i, val)
}
return
}