1package txn
2
3import (
4	"github.com/10gen/llmgo/bson"
5	"sort"
6)
7
8func tarjanSort(successors map[bson.ObjectId][]bson.ObjectId) [][]bson.ObjectId {
9	// http://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm
10	data := &tarjanData{
11		successors: successors,
12		nodes:      make([]tarjanNode, 0, len(successors)),
13		index:      make(map[bson.ObjectId]int, len(successors)),
14	}
15
16	for id := range successors {
17		id := bson.ObjectId(string(id))
18		if _, seen := data.index[id]; !seen {
19			data.strongConnect(id)
20		}
21	}
22
23	// Sort connected components to stabilize the algorithm.
24	for _, ids := range data.output {
25		if len(ids) > 1 {
26			sort.Sort(idList(ids))
27		}
28	}
29	return data.output
30}
31
32type tarjanData struct {
33	successors map[bson.ObjectId][]bson.ObjectId
34	output     [][]bson.ObjectId
35
36	nodes []tarjanNode
37	stack []bson.ObjectId
38	index map[bson.ObjectId]int
39}
40
41type tarjanNode struct {
42	lowlink int
43	stacked bool
44}
45
46type idList []bson.ObjectId
47
48func (l idList) Len() int           { return len(l) }
49func (l idList) Swap(i, j int)      { l[i], l[j] = l[j], l[i] }
50func (l idList) Less(i, j int) bool { return l[i] < l[j] }
51
52func (data *tarjanData) strongConnect(id bson.ObjectId) *tarjanNode {
53	index := len(data.nodes)
54	data.index[id] = index
55	data.stack = append(data.stack, id)
56	data.nodes = append(data.nodes, tarjanNode{index, true})
57	node := &data.nodes[index]
58
59	for _, succid := range data.successors[id] {
60		succindex, seen := data.index[succid]
61		if !seen {
62			succnode := data.strongConnect(succid)
63			if succnode.lowlink < node.lowlink {
64				node.lowlink = succnode.lowlink
65			}
66		} else if data.nodes[succindex].stacked {
67			// Part of the current strongly-connected component.
68			if succindex < node.lowlink {
69				node.lowlink = succindex
70			}
71		}
72	}
73
74	if node.lowlink == index {
75		// Root node; pop stack and output new
76		// strongly-connected component.
77		var scc []bson.ObjectId
78		i := len(data.stack) - 1
79		for {
80			stackid := data.stack[i]
81			stackindex := data.index[stackid]
82			data.nodes[stackindex].stacked = false
83			scc = append(scc, stackid)
84			if stackindex == index {
85				break
86			}
87			i--
88		}
89		data.stack = data.stack[:i]
90		data.output = append(data.output, scc)
91	}
92
93	return node
94}
95