|
1 package hudson.model;
2
3 import java.util.ArrayList  ;
4 import java.util.Collection ;
5 import java.util.Collections ;
6 import java.util.Comparator ;
7 import java.util.HashMap ;
8 import java.util.List ;
9 import java.util.Map ;
10 import java.util.Set ;
11 import java.util.HashSet ;
12 import java.util.Stack ;
13 import java.util.Map.Entry;
14
15
35 public final class DependencyGraph {
36
37 private Map <AbstractProject, List <AbstractProject>> forward = new HashMap <AbstractProject, List <AbstractProject>>();
38 private Map <AbstractProject, List <AbstractProject>> backward = new HashMap <AbstractProject, List <AbstractProject>>();
39
40 private boolean built;
41
42
45 public DependencyGraph() {
46 for( AbstractProject p : Hudson.getInstance().getAllItems(AbstractProject.class) )
47 p.buildDependencyGraph(this);
48
49 forward = finalize(forward);
50 backward = finalize(backward);
51
52 built = true;
53 }
54
55
58 private DependencyGraph(boolean dummy) {
59 forward = backward = Collections.emptyMap();
60 built = true;
61 }
62
63
69 public List <AbstractProject> getDownstream(AbstractProject p) {
70 return get(forward,p);
71 }
72
73
79 public List <AbstractProject> getUpstream(AbstractProject p) {
80 return get(backward,p);
81 }
82
83 private List <AbstractProject> get(Map <AbstractProject, List <AbstractProject>> map, AbstractProject src) {
84 List <AbstractProject> v = map.get(src);
85 if(v!=null) return v;
86 else return Collections.emptyList();
87 }
88
89
92 public void addDependency(AbstractProject from, AbstractProject to) {
93 if(built)
94 throw new IllegalStateException ();
95 add(forward,from,to);
96 add(backward,to,from);
97 }
98
99 public void addDependency(AbstractProject from, Collection <? extends AbstractProject> to) {
100 for (AbstractProject p : to)
101 addDependency(from,p);
102 }
103
104 public void addDependency(Collection <? extends AbstractProject> from, AbstractProject to) {
105 for (AbstractProject p : from)
106 addDependency(p,to);
107 }
108
109
115 public boolean hasIndirectDependencies(AbstractProject src, AbstractProject dst) {
116 Set <AbstractProject> visited = new HashSet <AbstractProject>();
117 Stack <AbstractProject> queue = new Stack <AbstractProject>();
118
119 queue.addAll(getDownstream(src));
120 queue.remove(dst);
121
122 while(!queue.isEmpty()) {
123 AbstractProject p = queue.pop();
124 if(p==dst)
125 return true;
126 if(visited.add(p))
127 queue.addAll(getDownstream(p));
128 }
129
130 return false;
131 }
132
133
136 public Set <AbstractProject> getTransitiveUpstream(AbstractProject src) {
137 return getTransitive(backward,src);
138 }
139
140
143 public Set <AbstractProject> getTransitiveDownstream(AbstractProject src) {
144 return getTransitive(forward,src);
145 }
146
147 private Set <AbstractProject> getTransitive(Map <AbstractProject, List <AbstractProject>> direction, AbstractProject src) {
148 Set <AbstractProject> visited = new HashSet <AbstractProject>();
149 Stack <AbstractProject> queue = new Stack <AbstractProject>();
150
151 queue.add(src);
152
153 while(!queue.isEmpty()) {
154 AbstractProject p = queue.pop();
155
156 for (AbstractProject child : get(direction,p)) {
157 if(visited.add(child))
158 queue.add(child);
159 }
160 }
161
162 return visited;
163 }
164
165 private void add(Map <AbstractProject, List <AbstractProject>> map, AbstractProject src, AbstractProject dst) {
166 List <AbstractProject> set = map.get(src);
167 if(set==null) {
168 set = new ArrayList <AbstractProject>();
169 map.put(src,set);
170 }
171 set.add(dst);
172 }
173
174 private Map <AbstractProject, List <AbstractProject>> finalize(Map <AbstractProject, List <AbstractProject>> m) {
175 for (Entry<AbstractProject, List <AbstractProject>> e : m.entrySet()) {
176 Collections.sort( e.getValue(), NAME_COMPARATOR );
177 e.setValue( Collections.unmodifiableList(e.getValue()) );
178 }
179 return Collections.unmodifiableMap(m);
180 }
181
182 private static final Comparator <AbstractProject> NAME_COMPARATOR = new Comparator <AbstractProject>() {
183 public int compare(AbstractProject lhs, AbstractProject rhs) {
184 return lhs.getName().compareTo(rhs.getName());
185 }
186 };
187
188 public static final DependencyGraph EMPTY = new DependencyGraph(false);
189 }
190 |
Popular Tags |
Java API By Example, From Geeks To Geeks.