Terraria ModLoader  0.10.1.5
A framework for Terraria mods
Terraria.ModLoader.TopoSort< T > Class Template Reference
+ Collaboration diagram for Terraria.ModLoader.TopoSort< T >:

Classes

class  SortingException
 

Public Member Functions

 TopoSort (IEnumerable< T > elements, Func< T, IEnumerable< T >> dependencies=null, Func< T, IEnumerable< T >> dependents=null)
 
void AddEntry (T dependency, T dependent)
 
ISet< T > AllDependencies (T t)
 
ISet< T > AllDependendents (T t)
 
List< T > Dependencies (T t)
 
List< T > Dependents (T t)
 
List< T > Sort ()
 

Public Attributes

readonly ReadOnlyCollection< T > list
 

Static Private Member Functions

static void BuildSet (T t, IDictionary< T, List< T >> dict, ISet< T > set)
 

Private Attributes

IDictionary< T, List< T > > dependencyDict = new Dictionary<T, List<T>>()
 
IDictionary< T, List< T > > dependentDict = new Dictionary<T, List<T>>()
 

Detailed Description

Definition at line 8 of file TopoSort.cs.

Constructor & Destructor Documentation

Terraria.ModLoader.TopoSort< T >.TopoSort ( IEnumerable< T >  elements,
Func< T, IEnumerable< T >>  dependencies = null,
Func< T, IEnumerable< T >>  dependents = null 
)

Definition at line 29 of file TopoSort.cs.

29  {
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  }
readonly ReadOnlyCollection< T > list
Definition: TopoSort.cs:25
void AddEntry(T dependency, T dependent)
Definition: TopoSort.cs:42

Member Function Documentation

void Terraria.ModLoader.TopoSort< T >.AddEntry ( dependency,
dependent 
)

Definition at line 42 of file TopoSort.cs.

42  {
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  }
IDictionary< T, List< T > > dependentDict
Definition: TopoSort.cs:27
readonly ReadOnlyCollection< T > list
Definition: TopoSort.cs:25
IDictionary< T, List< T > > dependencyDict
Definition: TopoSort.cs:26
ISet<T> Terraria.ModLoader.TopoSort< T >.AllDependencies ( t)

Definition at line 71 of file TopoSort.cs.

71  {
72  var set = new HashSet<T>();
73  BuildSet(t, dependencyDict, set);
74  return set;
75  }
static void BuildSet(T t, IDictionary< T, List< T >> dict, ISet< T > set)
Definition: TopoSort.cs:51
IDictionary< T, List< T > > dependencyDict
Definition: TopoSort.cs:26
ISet<T> Terraria.ModLoader.TopoSort< T >.AllDependendents ( t)

Definition at line 77 of file TopoSort.cs.

77  {
78  var set = new HashSet<T>();
79  BuildSet(t, dependentDict, set);
80  return set;
81  }
static void BuildSet(T t, IDictionary< T, List< T >> dict, ISet< T > set)
Definition: TopoSort.cs:51
IDictionary< T, List< T > > dependentDict
Definition: TopoSort.cs:27
static void Terraria.ModLoader.TopoSort< T >.BuildSet ( t,
IDictionary< T, List< T >>  dict,
ISet< T >  set 
)
staticprivate

Definition at line 51 of file TopoSort.cs.

51  {
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  }
static void BuildSet(T t, IDictionary< T, List< T >> dict, ISet< T > set)
Definition: TopoSort.cs:51
readonly ReadOnlyCollection< T > list
Definition: TopoSort.cs:25
List<T> Terraria.ModLoader.TopoSort< T >.Dependencies ( t)

Definition at line 61 of file TopoSort.cs.

61  {
62  List<T> list;
63  return dependencyDict.TryGetValue(t, out list) ? list : new List<T>();
64  }
readonly ReadOnlyCollection< T > list
Definition: TopoSort.cs:25
IDictionary< T, List< T > > dependencyDict
Definition: TopoSort.cs:26
List<T> Terraria.ModLoader.TopoSort< T >.Dependents ( t)

Definition at line 66 of file TopoSort.cs.

66  {
67  List<T> list;
68  return dependentDict.TryGetValue(t, out list) ? list : new List<T>();
69  }
IDictionary< T, List< T > > dependentDict
Definition: TopoSort.cs:27
readonly ReadOnlyCollection< T > list
Definition: TopoSort.cs:25
List<T> Terraria.ModLoader.TopoSort< T >.Sort ( )

Definition at line 83 of file TopoSort.cs.

83  {
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  }
List< T > Dependencies(T t)
Definition: TopoSort.cs:61
readonly ReadOnlyCollection< T > list
Definition: TopoSort.cs:25

Member Data Documentation

IDictionary<T, List<T> > Terraria.ModLoader.TopoSort< T >.dependencyDict = new Dictionary<T, List<T>>()
private

Definition at line 26 of file TopoSort.cs.

IDictionary<T, List<T> > Terraria.ModLoader.TopoSort< T >.dependentDict = new Dictionary<T, List<T>>()
private

Definition at line 27 of file TopoSort.cs.

readonly ReadOnlyCollection<T> Terraria.ModLoader.TopoSort< T >.list

Definition at line 25 of file TopoSort.cs.