Terraria ModLoader  0.11.7.8
A mod to make and play Terraria mods
TopoSort.cs
Go to the documentation of this file.
1 using System;
2 using System.Collections.Generic;
3 using System.Collections.ObjectModel;
4 using System.Linq;
5 
6 namespace Terraria.ModLoader
7 {
8  public class TopoSort<T>
9  {
10  public class SortingException : Exception
11  {
12  public ISet<T> set = new HashSet<T>();
13  public IList<List<T>> cycles = new List<List<T>>();
14 
15  private string CycleToString(List<T> cycle) => "Dependency Cycle: " + string.Join(" -> ", cycle);
16  public override string Message => string.Join(Environment.NewLine, cycles.Select(CycleToString));
17 
18  public void Add(List<T> cycle) {
19  cycles.Add(cycle);
20  foreach (var e in cycle)
21  set.Add(e);
22  }
23  }
24 
25  public readonly ReadOnlyCollection<T> list;
26  private IDictionary<T, List<T>> dependencyDict = new Dictionary<T, List<T>>();
27  private IDictionary<T, List<T>> dependentDict = new Dictionary<T, List<T>>();
28 
29  public TopoSort(IEnumerable<T> elements, Func<T, IEnumerable<T>> dependencies = null, Func<T, IEnumerable<T>> dependents = null) {
30  list = elements.ToList().AsReadOnly();
31  if (dependencies != null)
32  foreach (var t in list)
33  foreach (var dependency in dependencies(t))
34  AddEntry(dependency, t);
35 
36  if (dependents != null)
37  foreach (var t in list)
38  foreach (var dependent in dependents(t))
39  AddEntry(t, dependent);
40  }
41 
42  public void AddEntry(T dependency, T dependent) {
43  List<T> list;
44  if (!dependencyDict.TryGetValue(dependent, out list)) dependencyDict[dependent] = list = new List<T>();
45  list.Add(dependency);
46 
47  if (!dependentDict.TryGetValue(dependency, out list)) dependentDict[dependency] = list = new List<T>();
48  list.Add(dependent);
49  }
50 
51  private static void BuildSet(T t, IDictionary<T, List<T>> dict, ISet<T> set) {
52  List<T> list;
53  if (!dict.TryGetValue(t, out list))
54  return;
55 
56  foreach (var entry in dict[t])
57  if (set.Add(entry))
58  BuildSet(entry, dict, set);
59  }
60 
61  public List<T> Dependencies(T t) {
62  List<T> list;
63  return dependencyDict.TryGetValue(t, out list) ? list : new List<T>();
64  }
65 
66  public List<T> Dependents(T t) {
67  List<T> list;
68  return dependentDict.TryGetValue(t, out list) ? list : new List<T>();
69  }
70 
71  public ISet<T> AllDependencies(T t) {
72  var set = new HashSet<T>();
73  BuildSet(t, dependencyDict, set);
74  return set;
75  }
76 
77  public ISet<T> AllDependendents(T t) {
78  var set = new HashSet<T>();
79  BuildSet(t, dependentDict, set);
80  return set;
81  }
82 
83  public List<T> Sort() {
84  var ex = new SortingException();
85  var visiting = new Stack<T>();
86  var sorted = new List<T>();
87 
88  Action<T> Visit = null;
89  Visit = t => {
90  if (sorted.Contains(t) || ex.set.Contains(t))
91  return;
92 
93  visiting.Push(t);
94  foreach (var dependency in Dependencies(t)) {
95  if (visiting.Contains(dependency)) {//walk down the visiting stack to extract the dependency cycle
96  var cycle = new List<T>();
97  cycle.Add(dependency);
98  cycle.AddRange(visiting.TakeWhile(entry => !EqualityComparer<T>.Default.Equals(entry, dependency)));
99  cycle.Add(dependency);
100  cycle.Reverse();//items at top of the stack (start of the list) are deepest in the dependency tree
101  ex.Add(cycle);
102  continue;
103  }
104 
105  Visit(dependency);
106  }
107  visiting.Pop();
108  sorted.Add(t);
109  };
110 
111  foreach (var t in list)
112  Visit(t);
113 
114  if (ex.set.Count > 0)
115  throw ex;
116 
117  return sorted;
118  }
119  }
120 }
static void BuildSet(T t, IDictionary< T, List< T >> dict, ISet< T > set)
Definition: TopoSort.cs:51
ISet< T > AllDependendents(T t)
Definition: TopoSort.cs:77
List< T > Dependencies(T t)
Definition: TopoSort.cs:61
readonly ReadOnlyCollection< T > list
Definition: TopoSort.cs:25
ISet< T > AllDependencies(T t)
Definition: TopoSort.cs:71
Sandstorm, Hell, Above surface during Eclipse, Space
void AddEntry(T dependency, T dependent)
Definition: TopoSort.cs:42
TopoSort(IEnumerable< T > elements, Func< T, IEnumerable< T >> dependencies=null, Func< T, IEnumerable< T >> dependents=null)
Definition: TopoSort.cs:29
List< T > Dependents(T t)
Definition: TopoSort.cs:66