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);
        }

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);
        }

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;
        }

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;
        }

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);
        }

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>();
        }

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>();
        }

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;
        }

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.

dependentDict

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

private

Definition at line 27 of file TopoSort.cs.

list

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

Definition at line 25 of file TopoSort.cs.