← Back to branch summary

~halega/+junk/sharpdevelop

« back to all changes in this revision

Viewing changes to src/AddIns/BackendBindings/CppBinding/CppBinding/Project/DependencyRelation.cs

  • Committer: sk
  • Date: 2011-09-10 05:17:57 UTC
  • Revision ID: halega@halega.com-20110910051757-qfouz1llya9m6boy
4.1.0.7915 Release Candidate 1

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/AddIns/BackendBindings/CppBinding/CppBinding/Project/DependencyRelation.cs
 
1
// Copyright (c) AlphaSierraPapa for the SharpDevelop Team (for details please see \doc\copyright.txt)
 
2
// This code is distributed under the GNU LGPL (for details please see \doc\license.txt)
 
3
 
 
4
using System;
 
5
using System.Collections.Generic;
 
6
using System.Linq;
 
7
using System.Text;
 
8
using System.Diagnostics;
 
9
 
 
10
namespace ICSharpCode.CppBinding.Project
 
11
{
 
12
        /// <summary>
 
13
        /// Dependency relation between arbitrary types.
 
14
        /// </summary>
 
15
        public class DependencyRelation<T1, T2>
 
16
        {
 
17
                public DependencyRelation()
 
18
                        : this(new MultiDictionary<T1, T2>())
 
19
                { }
 
20
 
 
21
                public DependencyRelation(IMultiDictionary<T1, T2> innerDep)
 
22
                {
 
23
                        dep = innerDep;
 
24
 
 
25
                        revDep = new MultiDictionary<T2, T1>();
 
26
                        foreach (KeyValuePair<T1, T2> item in dep)
 
27
                                revDep.Add(item.Value, item.Key);
 
28
                }
 
29
 
 
30
                /// <summary>
 
31
                /// Adds an information that <paramref name="item"/> does depend on <paramref name="dependency"/>
 
32
                /// </summary>
 
33
                public void Add(T1 item, T2 dependency)
 
34
                {
 
35
                        dep.Add(item, dependency);
 
36
                        revDep.Add(dependency, item);
 
37
                }
 
38
 
 
39
                /// <summary>
 
40
                /// Removes a dependency between <paramref name="item"/> and <paramref name="dependency"/>.
 
41
                /// </summary>
 
42
                public bool Remove(T1 item, T2 dependency)
 
43
                {
 
44
                        if (dep.Remove(item, dependency))
 
45
                        {
 
46
                                Debug.Assert(revDep.Remove(dependency, item));
 
47
                                return true;
 
48
                        }
 
49
                        return false;
 
50
                }
 
51
 
 
52
                /// <summary>
 
53
                /// Returns a list of items given element directly depend on.
 
54
                /// If there is no element in the dependency relation, returns an empty list.
 
55
                /// </summary>
 
56
                public IList<T2> DependOn(T1 element)
 
57
                {
 
58
                        if (dep.ContainsKey(element))
 
59
                                return dep[element];
 
60
                        return new List<T2>();
 
61
                }
 
62
 
 
63
                /// <summary>
 
64
                /// Enumerates all items given element depend on including those that
 
65
                /// depend indirectly. If type parameters <typeparamref name="T1"/> and <typeparamref name="T2"/>
 
66
                /// are not equal then the result is the same as from DependOn method.
 
67
                /// </summary>
 
68
                /// <remarks>
 
69
                /// The enumeration may contain the <paramref name="element"/> if there is 
 
70
                /// a cyclic dependency. It is guaranteed that the enumaration contains an item
 
71
                /// at most once.
 
72
                /// </remarks>
 
73
                public IEnumerable<T2> DependencyTreeFrom(T1 element)
 
74
                {
 
75
                        if (typeof(T1) != typeof(T2)) return DependOn(element);
 
76
 
 
77
                        //this solves the case when T1 == T2
 
78
                        return DependencyTree(dep, element).Cast<T2>();
 
79
                }
 
80
 
 
81
                /// <summary>
 
82
                /// Returns a list of elements that depend on given element.
 
83
                /// If the is no item that depend on given element, returns an empty list.
 
84
                /// </summary>
 
85
                /// <returns></returns>
 
86
                public IList<T1> DependingOn(T2 element)
 
87
                {
 
88
                        if (revDep.ContainsKey(element))
 
89
                                return revDep[element];
 
90
                        return new List<T1>();
 
91
                }
 
92
 
 
93
                /// <summary>
 
94
                /// Enumerates all items that are depending on given element including those 
 
95
                /// depending indirectly. If type parameters <typeparamref name="T1"/> and <typeparamref name="T2"/>
 
96
                /// are not equal then the result is the same as from DependingOn method.
 
97
                /// </summary>
 
98
                /// <remarks>
 
99
                /// The enumeration may contain the <paramref name="element"/> if there is 
 
100
                /// a cyclic dependency. It is guaranteed that the enumaration contains an item
 
101
                /// at most once.
 
102
                /// </remarks>
 
103
                public IEnumerable<T1> DependencyTreeTo(T2 element)
 
104
                {
 
105
                        if (typeof(T1) != typeof(T2)) return DependingOn(element);
 
106
 
 
107
                        //this solves the case when T1 == T2
 
108
                        return DependencyTree(revDep, element).Cast<T1>();
 
109
                }
 
110
 
 
111
                IEnumerable<T> DependencyTree<T, U>(IMultiDictionary<T, U> rel, T startItem)
 
112
                {
 
113
                        HashSet<T> visited = new HashSet<T>();
 
114
                        Stack<T> pendingItems = new Stack<T>();
 
115
 
 
116
                        pendingItems.Push(startItem);
 
117
                        while (pendingItems.Count > 0)
 
118
                        {
 
119
                                T currentItem = pendingItems.Pop();
 
120
                                if (rel.ContainsKey(currentItem))
 
121
                                        foreach (T depend in rel[currentItem].Cast<T>())
 
122
                                                if (!visited.Contains(depend))
 
123
                                                {
 
124
                                                        visited.Add(depend);
 
125
                                                        pendingItems.Push(depend);
 
126
                                                        yield return depend;
 
127
                                                }
 
128
                        }
 
129
                }
 
130
 
 
131
                //dependency relation
 
132
                IMultiDictionary<T1, T2> dep;
 
133
 
 
134
                //reverse dependency relation
 
135
                IMultiDictionary<T2, T1> revDep;
 
136
        }
 
137
}