KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > org > eclipse > core > internal > resources > ComputeProjectOrder


1 /*******************************************************************************
2  * Copyright (c) 2000, 2005 IBM Corporation and others.
3  * All rights reserved. This program and the accompanying materials
4  * are made available under the terms of the Eclipse Public License v1.0
5  * which accompanies this distribution, and is available at
6  * http://www.eclipse.org/legal/epl-v10.html
7  *
8  * Contributors:
9  * IBM Corporation - initial API and implementation
10  *******************************************************************************/
11
12 package org.eclipse.core.internal.resources;
13
14 import java.util.*;
15 import org.eclipse.core.resources.IProject;
16 import org.eclipse.core.resources.IWorkspace;
17
18 /**
19  * Implementation of a sort algorithm for computing the project order. This
20  * algorithm handles cycles in the project reference graph in a reasonable way.
21  *
22  * @since 2.1
23  */
24 class ComputeProjectOrder {
25
26     /*
27      * Prevent class from being instantiated.
28      */
29     private ComputeProjectOrder() {
30         // not allowed
31 }
32
33     /**
34      * A directed graph. Once the vertexes and edges of the graph have been
35      * defined, the graph can be queried for the depth-first finish time of each
36      * vertex.
37      * <p>
38      * Ref: Cormen, Leiserson, and Rivest <it>Introduction to Algorithms</it>,
39      * McGraw-Hill, 1990. The depth-first search algorithm is in section 23.3.
40      * </p>
41      */
42     private static class Digraph {
43         /**
44          * struct-like object for representing a vertex along with various
45          * values computed during depth-first search (DFS).
46          */
47         public static class Vertex {
48             /**
49              * White is for marking vertexes as unvisited.
50              */
51             public static final String JavaDoc WHITE = "white"; //$NON-NLS-1$
52
53             /**
54              * Grey is for marking vertexes as discovered but visit not yet
55              * finished.
56              */
57             public static final String JavaDoc GREY = "grey"; //$NON-NLS-1$
58
59             /**
60              * Black is for marking vertexes as visited.
61              */
62             public static final String JavaDoc BLACK = "black"; //$NON-NLS-1$
63
64             /**
65              * Color of the vertex. One of <code>WHITE</code> (unvisited),
66              * <code>GREY</code> (visit in progress), or <code>BLACK</code>
67              * (visit finished). <code>WHITE</code> initially.
68              */
69             public String JavaDoc color = WHITE;
70
71             /**
72              * The DFS predecessor vertex, or <code>null</code> if there is no
73              * predecessor. <code>null</code> initially.
74              */
75             public Vertex predecessor = null;
76
77             /**
78              * Timestamp indicating when the vertex was finished (became BLACK)
79              * in the DFS. Finish times are between 1 and the number of
80              * vertexes.
81              */
82             public int finishTime;
83
84             /**
85              * The id of this vertex.
86              */
87             public Object JavaDoc id;
88
89             /**
90              * Ordered list of adjacent vertexes. In other words, "this" is the
91              * "from" vertex and the elements of this list are all "to"
92              * vertexes.
93              *
94              * Element type: <code>Vertex</code>
95              */
96             public List adjacent = new ArrayList(3);
97
98             /**
99              * Creates a new vertex with the given id.
100              *
101              * @param id the vertex id
102              */
103             public Vertex(Object JavaDoc id) {
104                 this.id = id;
105             }
106         }
107
108         /**
109          * Ordered list of all vertexes in this graph.
110          *
111          * Element type: <code>Vertex</code>
112          */
113         private List vertexList = new ArrayList(100);
114
115         /**
116          * Map from id to vertex.
117          *
118          * Key type: <code>Object</code>; value type: <code>Vertex</code>
119          */
120         private Map vertexMap = new HashMap(100);
121
122         /**
123          * DFS visit time. Non-negative.
124          */
125         private int time;
126
127         /**
128          * Indicates whether the graph has been initialized. Initially
129          * <code>false</code>.
130          */
131         private boolean initialized = false;
132
133         /**
134          * Indicates whether the graph contains cycles. Initially
135          * <code>false</code>.
136          */
137         private boolean cycles = false;
138
139         /**
140          * Creates a new empty directed graph object.
141          * <p>
142          * After this graph's vertexes and edges are defined with
143          * <code>addVertex</code> and <code>addEdge</code>, call
144          * <code>freeze</code> to indicate that the graph is all there, and then
145          * call <code>idsByDFSFinishTime</code> to read off the vertexes ordered
146          * by DFS finish time.
147          * </p>
148          */
149         public Digraph() {
150             super();
151         }
152
153         /**
154          * Freezes this graph. No more vertexes or edges can be added to this
155          * graph after this method is called. Has no effect if the graph is
156          * already frozen.
157          */
158         public void freeze() {
159             if (!initialized) {
160                 initialized = true;
161                 // only perform depth-first-search once
162 DFS();
163             }
164         }
165
166         /**
167          * Defines a new vertex with the given id. The depth-first search is
168          * performed in the relative order in which vertexes were added to the
169          * graph.
170          *
171          * @param id the id of the vertex
172          * @exception IllegalArgumentException if the vertex id is
173          * already defined or if the graph is frozen
174          */
175         public void addVertex(Object JavaDoc id) throws IllegalArgumentException JavaDoc {
176             if (initialized) {
177                 throw new IllegalArgumentException JavaDoc();
178             }
179             Vertex vertex = new Vertex(id);
180             Object JavaDoc existing = vertexMap.put(id, vertex);
181             // nip problems with duplicate vertexes in the bud
182 if (existing != null) {
183                 throw new IllegalArgumentException JavaDoc();
184             }
185             vertexList.add(vertex);
186         }
187
188         /**
189          * Adds a new directed edge between the vertexes with the given ids.
190          * Vertexes for the given ids must be defined beforehand with
191          * <code>addVertex</code>. The depth-first search is performed in the
192          * relative order in which adjacent "to" vertexes were added to a given
193          * "from" index.
194          *
195          * @param fromId the id of the "from" vertex
196          * @param toId the id of the "to" vertex
197          * @exception IllegalArgumentException if either vertex is undefined or
198          * if the graph is frozen
199          */
200         public void addEdge(Object JavaDoc fromId, Object JavaDoc toId) throws IllegalArgumentException JavaDoc {
201             if (initialized) {
202                 throw new IllegalArgumentException JavaDoc();
203             }
204             Vertex fromVertex = (Vertex) vertexMap.get(fromId);
205             Vertex toVertex = (Vertex) vertexMap.get(toId);
206             // nip problems with bogus vertexes in the bud
207 if (fromVertex == null) {
208                 throw new IllegalArgumentException JavaDoc();
209             }
210             if (toVertex == null) {
211                 throw new IllegalArgumentException JavaDoc();
212             }
213             fromVertex.adjacent.add(toVertex);
214         }
215
216         /**
217          * Returns the ids of the vertexes in this graph ordered by depth-first
218          * search finish time. The graph must be frozen.
219          *
220          * @param increasing <code>true</code> if objects are to be arranged
221          * into increasing order of depth-first search finish time, and
222          * <code>false</code> if objects are to be arranged into decreasing
223          * order of depth-first search finish time
224          * @return the list of ids ordered by depth-first search finish time
225          * (element type: <code>Object</code>)
226          * @exception IllegalArgumentException if the graph is not frozen
227          */
228         public List idsByDFSFinishTime(boolean increasing) {
229             if (!initialized) {
230                 throw new IllegalArgumentException JavaDoc();
231             }
232             int len = vertexList.size();
233             Object JavaDoc[] r = new Object JavaDoc[len];
234             for (Iterator allV = vertexList.iterator(); allV.hasNext();) {
235                 Vertex vertex = (Vertex) allV.next();
236                 int f = vertex.finishTime;
237                 // note that finish times start at 1, not 0
238 if (increasing) {
239                     r[f - 1] = vertex.id;
240                 } else {
241                     r[len - f] = vertex.id;
242                 }
243             }
244             return Arrays.asList(r);
245         }
246
247         /**
248          * Returns whether the graph contains cycles. The graph must be frozen.
249          *
250          * @return <code>true</code> if this graph contains at least one cycle,
251          * and <code>false</code> if this graph is cycle free
252          * @exception IllegalArgumentException if the graph is not frozen
253          */
254         public boolean containsCycles() {
255             if (!initialized) {
256                 throw new IllegalArgumentException JavaDoc();
257             }
258             return cycles;
259         }
260
261         /**
262          * Returns the non-trivial components of this graph. A non-trivial
263          * component is a set of 2 or more vertexes that were traversed
264          * together. The graph must be frozen.
265          *
266          * @return the possibly empty list of non-trivial components, where
267          * each component is an array of ids (element type:
268          * <code>Object[]</code>)
269          * @exception IllegalArgumentException if the graph is not frozen
270          */
271         public List nonTrivialComponents() {
272             if (!initialized) {
273                 throw new IllegalArgumentException JavaDoc();
274             }
275             // find the roots of each component
276 // Map<Vertex,List<Object>> components
277 Map components = new HashMap();
278             for (Iterator it = vertexList.iterator(); it.hasNext();) {
279                 Vertex vertex = (Vertex) it.next();
280                 if (vertex.predecessor == null) {
281                     // this vertex is the root of a component
282 // if component is non-trivial we will hit a child
283 } else {
284                     // find the root ancestor of this vertex
285 Vertex root = vertex;
286                     while (root.predecessor != null) {
287                         root = root.predecessor;
288                     }
289                     List component = (List) components.get(root);
290                     if (component == null) {
291                         component = new ArrayList(2);
292                         component.add(root.id);
293                         components.put(root, component);
294                     }
295                     component.add(vertex.id);
296                 }
297             }
298             List result = new ArrayList(components.size());
299             for (Iterator it = components.values().iterator(); it.hasNext();) {
300                 List component = (List) it.next();
301                 if (component.size() > 1) {
302                     result.add(component.toArray());
303                 }
304             }
305             return result;
306         }
307
308         // /**
309 // * Performs a depth-first search of this graph and records interesting
310 // * info with each vertex, including DFS finish time. Employs a recursive
311 // * helper method <code>DFSVisit</code>.
312 // * <p>
313 // * Although this method is not used, it is the basis of the
314 // * non-recursive <code>DFS</code> method.
315 // * </p>
316 // */
317 // private void recursiveDFS() {
318 // // initialize
319 // // all vertex.color initially Vertex.WHITE;
320 // // all vertex.predecessor initially null;
321 // time = 0;
322 // for (Iterator allV = vertexList.iterator(); allV.hasNext();) {
323 // Vertex nextVertex = (Vertex) allV.next();
324 // if (nextVertex.color == Vertex.WHITE) {
325 // DFSVisit(nextVertex);
326 // }
327 // }
328 // }
329 //
330 // /**
331 // * Helper method. Performs a depth first search of this graph.
332 // *
333 // * @param vertex the vertex to visit
334 // */
335 // private void DFSVisit(Vertex vertex) {
336 // // mark vertex as discovered
337 // vertex.color = Vertex.GREY;
338 // List adj = vertex.adjacent;
339 // for (Iterator allAdjacent=adj.iterator(); allAdjacent.hasNext();) {
340 // Vertex adjVertex = (Vertex) allAdjacent.next();
341 // if (adjVertex.color == Vertex.WHITE) {
342 // // explore edge from vertex to adjVertex
343 // adjVertex.predecessor = vertex;
344 // DFSVisit(adjVertex);
345 // } else if (adjVertex.color == Vertex.GREY) {
346 // // back edge (grey vertex means visit in progress)
347 // cycles = true;
348 // }
349 // }
350 // // done exploring vertex
351 // vertex.color = Vertex.BLACK;
352 // time++;
353 // vertex.finishTime = time;
354 // }
355
356         /**
357          * Performs a depth-first search of this graph and records interesting
358          * info with each vertex, including DFS finish time. Does not employ
359          * recursion.
360          */
361         private void DFS() {
362             // state machine rendition of the standard recursive DFS algorithm
363 int state;
364             final int NEXT_VERTEX = 1;
365             final int START_DFS_VISIT = 2;
366             final int NEXT_ADJACENT = 3;
367             final int AFTER_NEXTED_DFS_VISIT = 4;
368             // use precomputed objects to avoid garbage
369 final Integer JavaDoc NEXT_VERTEX_OBJECT = new Integer JavaDoc(NEXT_VERTEX);
370             final Integer JavaDoc AFTER_NEXTED_DFS_VISIT_OBJECT = new Integer JavaDoc(AFTER_NEXTED_DFS_VISIT);
371             // initialize
372 // all vertex.color initially Vertex.WHITE;
373 // all vertex.predecessor initially null;
374 time = 0;
375             // for a stack, append to the end of an array-based list
376 List stack = new ArrayList(Math.max(1, vertexList.size()));
377             Iterator allAdjacent = null;
378             Vertex vertex = null;
379             Iterator allV = vertexList.iterator();
380             state = NEXT_VERTEX;
381             nextStateLoop: while (true) {
382                 switch (state) {
383                     case NEXT_VERTEX :
384                         // on entry, "allV" contains vertexes yet to be visited
385 if (!allV.hasNext()) {
386                             // all done
387 break nextStateLoop;
388                         }
389                         Vertex nextVertex = (Vertex) allV.next();
390                         if (nextVertex.color == Vertex.WHITE) {
391                             stack.add(NEXT_VERTEX_OBJECT);
392                             vertex = nextVertex;
393                             state = START_DFS_VISIT;
394                             continue nextStateLoop;
395                         }
396                         //else
397 state = NEXT_VERTEX;
398                         continue nextStateLoop;
399                     case START_DFS_VISIT :
400                         // on entry, "vertex" contains the vertex to be visited
401 // top of stack is return code
402 // mark the vertex as discovered
403 vertex.color = Vertex.GREY;
404                         allAdjacent = vertex.adjacent.iterator();
405                         state = NEXT_ADJACENT;
406                         continue nextStateLoop;
407                     case NEXT_ADJACENT :
408                         // on entry, "allAdjacent" contains adjacent vertexes to
409 // be visited; "vertex" contains vertex being visited
410 if (allAdjacent.hasNext()) {
411                             Vertex adjVertex = (Vertex) allAdjacent.next();
412                             if (adjVertex.color == Vertex.WHITE) {
413                                 // explore edge from vertex to adjVertex
414 adjVertex.predecessor = vertex;
415                                 stack.add(allAdjacent);
416                                 stack.add(vertex);
417                                 stack.add(AFTER_NEXTED_DFS_VISIT_OBJECT);
418                                 vertex = adjVertex;
419                                 state = START_DFS_VISIT;
420                                 continue nextStateLoop;
421                             }
422                             if (adjVertex.color == Vertex.GREY) {
423                                 // back edge (grey means visit in progress)
424 cycles = true;
425                             }
426                             state = NEXT_ADJACENT;
427                             continue nextStateLoop;
428                         }
429                         //else done exploring vertex
430 vertex.color = Vertex.BLACK;
431                         time++;
432                         vertex.finishTime = time;
433                         state = ((Integer JavaDoc) stack.remove(stack.size() - 1)).intValue();
434                         continue nextStateLoop;
435                     case AFTER_NEXTED_DFS_VISIT :
436                         // on entry, stack contains "vertex" and "allAjacent"
437 vertex = (Vertex) stack.remove(stack.size() - 1);
438                         allAdjacent = (Iterator) stack.remove(stack.size() - 1);
439                         state = NEXT_ADJACENT;
440                         continue nextStateLoop;
441                 }
442             }
443         }
444
445     }
446
447     /**
448      * Sorts the given list of probject in a manner that honors the given
449      * project reference relationships. That is, if project A references project
450      * B, then the resulting order will list B before A if possible. For graphs
451      * that do not contain cycles, the result is the same as a conventional
452      * topological sort. For graphs containing cycles, the order is based on
453      * ordering the strongly connected components of the graph. This has the
454      * effect of keeping each knot of projects together without otherwise
455      * affecting the order of projects not involved in a cycle. For a graph G,
456      * the algorithm performs in O(|G|) space and time.
457      * <p>
458      * When there is an arbitrary choice, vertexes are ordered as supplied.
459      * Arranged projects in descending alphabetical order generally results in
460      * an order that builds "A" before "Z" when there are no other constraints.
461      * </p>
462      * <p> Ref: Cormen, Leiserson, and Rivest <it>Introduction to
463      * Algorithms</it>, McGraw-Hill, 1990. The strongly-connected-components
464      * algorithm is in section 23.5.
465      * </p>
466      *
467      * @param projects a list of projects (element type:
468      * <code>IProject</code>)
469      * @param references a list of project references [A,B] meaning that A
470      * references B (element type: <code>IProject[]</code>)
471      * @return an object describing the resulting project order
472      */
473     static IWorkspace.ProjectOrder computeProjectOrder(SortedSet projects, List references) {
474
475         // Step 1: Create the graph object.
476 final Digraph g1 = new Digraph();
477         // add vertexes
478 for (Iterator it = projects.iterator(); it.hasNext();) {
479             IProject project = (IProject) it.next();
480             g1.addVertex(project);
481         }
482         // add edges
483 for (Iterator it = references.iterator(); it.hasNext();) {
484             IProject[] ref = (IProject[]) it.next();
485             IProject p = ref[0];
486             IProject q = ref[1];
487             // p has a project reference to q
488 // therefore create an edge from q to p
489 // to cause q to come before p in eventual result
490 g1.addEdge(q, p);
491         }
492         g1.freeze();
493
494         // Step 2: Create the transposed graph. This time, define the vertexes
495 // in decreasing order of depth-first finish time in g1
496 // interchange "to" and "from" to reverse edges from g1
497 final Digraph g2 = new Digraph();
498         // add vertexes
499 List resortedVertexes = g1.idsByDFSFinishTime(false);
500         for (Iterator it = resortedVertexes.iterator(); it.hasNext();) {
501             final IProject project = (IProject) it.next();
502             g2.addVertex(project);
503         }
504         // add edges
505 for (Iterator it = references.iterator(); it.hasNext();) {
506             IProject[] ref = (IProject[]) it.next();
507             IProject p = ref[0];
508             IProject q = ref[1];
509             // p has a project reference to q
510 // therefore create an edge from p to q
511 // N.B. this is the reverse of step 1
512 g2.addEdge(p, q);
513         }
514         g2.freeze();
515
516         // Step 3: Return the vertexes in increasing order of depth-first finish
517 // time in g2
518 List sortedProjectList = g2.idsByDFSFinishTime(true);
519         IProject[] orderedProjects = new IProject[sortedProjectList.size()];
520         sortedProjectList.toArray(orderedProjects);
521         IProject[][] knots;
522         boolean hasCycles = g2.containsCycles();
523         if (hasCycles) {
524             List knotList = g2.nonTrivialComponents();
525             knots = new IProject[knotList.size()][];
526             // cannot use knotList.toArray(knots) because each knot is Object[]
527 // and we need each to be an IProject[]
528 int k = 0;
529             for (Iterator it = knotList.iterator(); it.hasNext();) {
530                 Object JavaDoc[] knot = (Object JavaDoc[]) it.next();
531                 IProject[] knotCopy = new IProject[knot.length];
532                 for (int i = 0; i < knot.length; i++) {
533                     knotCopy[i] = (IProject) knot[i];
534                 }
535                 knots[k] = knotCopy;
536                 k++;
537             }
538         } else {
539             knots = new IProject[][] {};
540         }
541         return new IWorkspace.ProjectOrder(orderedProjects, hasCycles, knots);
542     }
543 }
544
Popular Tags