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

TopoSort()

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.

                                                                                                                                         {
            list = elements.ToList().AsReadOnly();
            if (dependencies != null)
                foreach (var t in list)
                    foreach (var dependency in dependencies(t))
                        AddEntry(dependency, t);
 
            if (dependents != null)
                foreach (var t in list)
                    foreach (var dependent in dependents(t))
                        AddEntry(t, dependent);
        }

References Terraria.ModLoader.TopoSort< T >.AddEntry(), and Terraria.ModLoader.TopoSort< T >.list.

Here is the call graph for this function:

Member Function Documentation

AddEntry()

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

Definition at line 42 of file TopoSort.cs.

                                                        {
            List<T> list;
            if (!dependencyDict.TryGetValue(dependent, out list)) dependencyDict[dependent] = list = new List<T>();
            list.Add(dependency);
 
            if (!dependentDict.TryGetValue(dependency, out list)) dependentDict[dependency] = list = new List<T>();
            list.Add(dependent);
        }

References Terraria.ModLoader.TopoSort< T >.dependencyDict, Terraria.ModLoader.TopoSort< T >.dependentDict, and Terraria.ModLoader.TopoSort< T >.list.

Referenced by Terraria.ModLoader.TopoSort< T >.TopoSort().

Here is the caller graph for this function:

AllDependencies()

ISet< T > Terraria.ModLoader.TopoSort< T >.AllDependencies

(

T

t

)

Definition at line 71 of file TopoSort.cs.

                                            {
            var set = new HashSet<T>();
            BuildSet(t, dependencyDict, set);
            return set;
        }

References Terraria.ModLoader.TopoSort< T >.BuildSet(), and Terraria.ModLoader.TopoSort< T >.dependencyDict.

Here is the call graph for this function:

AllDependendents()

ISet< T > Terraria.ModLoader.TopoSort< T >.AllDependendents

(

T

t

)

Definition at line 77 of file TopoSort.cs.

                                             {
            var set = new HashSet<T>();
            BuildSet(t, dependentDict, set);
            return set;
        }

References Terraria.ModLoader.TopoSort< T >.BuildSet(), and Terraria.ModLoader.TopoSort< T >.dependentDict.

Here is the call graph for this function:

BuildSet()

static void Terraria.ModLoader.TopoSort< T >.BuildSet ( T  t, IDictionary< T, List< T > >  dict, ISet< T >  set  )

staticprivate

Definition at line 51 of file TopoSort.cs.

                                                                                     {
            List<T> list;
            if (!dict.TryGetValue(t, out list))
                return;
 
            foreach (var entry in dict[t])
                if (set.Add(entry))
                    BuildSet(entry, dict, set);
        }

References Terraria.ModLoader.TopoSort< T >.BuildSet(), and Terraria.ModLoader.TopoSort< T >.list.

Referenced by Terraria.ModLoader.TopoSort< T >.AllDependencies(), Terraria.ModLoader.TopoSort< T >.AllDependendents(), and Terraria.ModLoader.TopoSort< T >.BuildSet().

Here is the call graph for this function:

Here is the caller graph for this function:

Dependencies()

List< T > Terraria.ModLoader.TopoSort< T >.Dependencies

(

T

t

)

Definition at line 61 of file TopoSort.cs.

                                         {
            List<T> list;
            return dependencyDict.TryGetValue(t, out list) ? list : new List<T>();
        }

References Terraria.ModLoader.TopoSort< T >.dependencyDict, and Terraria.ModLoader.TopoSort< T >.list.

Referenced by Terraria.ModLoader.TopoSort< T >.Sort().

Here is the caller graph for this function:

Dependents()

List< T > Terraria.ModLoader.TopoSort< T >.Dependents

(

T

t

)

Definition at line 66 of file TopoSort.cs.

                                       {
            List<T> list;
            return dependentDict.TryGetValue(t, out list) ? list : new List<T>();
        }

References Terraria.ModLoader.TopoSort< T >.dependentDict, and Terraria.ModLoader.TopoSort< T >.list.

Sort()

List< T > Terraria.ModLoader.TopoSort< T >.Sort

(

)

Definition at line 83 of file TopoSort.cs.

                              {
            var ex = new SortingException();
            var visiting = new Stack<T>();
            var sorted = new List<T>();
 
            Action<T> Visit = null;
            Visit = t => {
                if (sorted.Contains(t) || ex.set.Contains(t))
                    return;
 
                visiting.Push(t);
                foreach (var dependency in Dependencies(t)) {
                    if (visiting.Contains(dependency)) {//walk down the visiting stack to extract the dependency cycle
                        var cycle = new List<T>();
                        cycle.Add(dependency);
                        cycle.AddRange(visiting.TakeWhile(entry => !EqualityComparer<T>.Default.Equals(entry, dependency)));
                        cycle.Add(dependency);
                        cycle.Reverse();//items at top of the stack (start of the list) are deepest in the dependency tree
                        ex.Add(cycle);
                        continue;
                    }
 
                    Visit(dependency);
                }
                visiting.Pop();
                sorted.Add(t);
            };
 
            foreach (var t in list)
                Visit(t);
 
            if (ex.set.Count > 0)
                throw ex;
 
            return sorted;
        }

References Terraria.ModLoader.TopoSort< T >.Dependencies(), and Terraria.ModLoader.TopoSort< T >.list.

Here is the call graph for this function:

Member Data Documentation

dependencyDict

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

private

Definition at line 26 of file TopoSort.cs.

Referenced by Terraria.ModLoader.TopoSort< T >.AddEntry(), Terraria.ModLoader.TopoSort< T >.AllDependencies(), and Terraria.ModLoader.TopoSort< T >.Dependencies().

dependentDict

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

private

Definition at line 27 of file TopoSort.cs.

Referenced by Terraria.ModLoader.TopoSort< T >.AddEntry(), Terraria.ModLoader.TopoSort< T >.AllDependendents(), and Terraria.ModLoader.TopoSort< T >.Dependents().

list

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

Definition at line 25 of file TopoSort.cs.

Referenced by Terraria.ModLoader.TopoSort< T >.TopoSort(), Terraria.ModLoader.TopoSort< T >.AddEntry(), Terraria.ModLoader.TopoSort< T >.BuildSet(), Terraria.ModLoader.TopoSort< T >.Dependencies(), Terraria.ModLoader.TopoSort< T >.Dependents(), and Terraria.ModLoader.TopoSort< T >.Sort().