001: /*
002: * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
003: *
004: * Copyright 1997-2007 Sun Microsystems, Inc. All rights reserved.
005: *
006: * The contents of this file are subject to the terms of either the GNU
007: * General Public License Version 2 only ("GPL") or the Common
008: * Development and Distribution License("CDDL") (collectively, the
009: * "License"). You may not use this file except in compliance with the
010: * License. You can obtain a copy of the License at
011: * http://www.netbeans.org/cddl-gplv2.html
012: * or nbbuild/licenses/CDDL-GPL-2-CP. See the License for the
013: * specific language governing permissions and limitations under the
014: * License. When distributing the software, include this License Header
015: * Notice in each file and include the License file at
016: * nbbuild/licenses/CDDL-GPL-2-CP. Sun designates this
017: * particular file as subject to the "Classpath" exception as provided
018: * by Sun in the GPL Version 2 section of the License file that
019: * accompanied this code. If applicable, add the following below the
020: * License Header, with the fields enclosed by brackets [] replaced by
021: * your own identifying information:
022: * "Portions Copyrighted [year] [name of copyright owner]"
023: *
024: * Contributor(s):
025: *
026: * The Original Software is NetBeans. The Initial Developer of the Original
027: * Software is Sun Microsystems, Inc. Portions Copyright 1997-2006 Sun
028: * Microsystems, Inc. All Rights Reserved.
029: *
030: * If you wish your version of this file to be governed by only the CDDL
031: * or only the GPL Version 2, indicate your decision by adding
032: * "[Contributor] elects to include this software in this distribution
033: * under the [CDDL or GPL Version 2] license." If you do not indicate a
034: * single choice of license, a recipient has the option to distribute
035: * your version of this file under either the CDDL, the GPL Version 2 or
036: * to extend the choice of license to its licensees as provided above.
037: * However, if you add GPL Version 2 code and therefore, elected the GPL
038: * Version 2 license, then the option applies only if the new code is
039: * made subject to such option by the copyright holder.
040: */
041: package org.openide.util;
042:
043: import java.io.PrintWriter;
044: import java.io.StringWriter;
045: import java.util.*;
046:
047: /** Exception that signals that a topological sort failed due to
048: * unsortable nature of the graph and that provides support for
049: * reporting and recovering from that state.
050: *
051: * @author Jaroslav Tulach
052: * @since 3.30
053: * @see Utilities#topologicalSort
054: */
055: public final class TopologicalSortException extends Exception {
056: /** all vertexes */
057: private Collection vertexes;
058:
059: /** map with edges */
060: private Map edges;
061:
062: /** result if called twice */
063: private Set[] result;
064:
065: /** counter to number the vertexes */
066: private int counter;
067:
068: /** vertexes sorted by increasing value of y */
069: private Stack<Vertex> dualGraph = new Stack<Vertex>();
070:
071: TopologicalSortException(Collection vertexes, Map edges) {
072: this .vertexes = vertexes;
073: this .edges = edges;
074: }
075:
076: /** Because the full sort was not possible, this methods
077: * returns the best possible substitute for it that is available.
078: *
079: * @return list of partially sorted objects, the list can be freely modified
080: */
081: public final List partialSort() {
082: Set[] all = topologicalSets();
083:
084: ArrayList<Object> res = new ArrayList<Object>(vertexes.size());
085:
086: for (int i = 0; i < all.length; i++) {
087: for (Object e : all[i]) {
088: res.add(e);
089: }
090: }
091:
092: return res;
093: }
094:
095: /** The topological sort could not be finished as there
096: * are some objects that are mutually refering to each other.
097: * This methods finds such objects and partition them into
098: * separate sets. All objects in one set (transitively) refer to
099: * each other and thus prevent the sort from succeding. As
100: * there can be more of such "unsortable sets" an array
101: * of them is returned.
102: *
103: * @return array of sets that contain some of the original objects, result
104: * shall not be modified
105: */
106: public final Set[] unsortableSets() {
107: Set[] all = topologicalSets();
108:
109: ArrayList<Set> unsort = new ArrayList<Set>();
110:
111: for (int i = 0; i < all.length; i++) {
112: if ((all[i].size() > 1) || !(all[i] instanceof HashSet)) {
113: unsort.add(all[i]);
114: }
115: }
116:
117: return unsort.toArray(new Set[0]);
118: }
119:
120: @Override
121: public String getMessage() {
122: StringWriter w = new StringWriter();
123: PrintWriter pw = new PrintWriter(w);
124: printDebug(pw);
125: pw.close();
126: return w.toString();
127: }
128:
129: @Override
130: public String toString() {
131: String s = getClass().getName();
132: return s;
133: }
134:
135: private void printDebug(java.io.PrintWriter w) {
136: w.print("TopologicalSortException - Collection: "); // NOI18N
137: w.print(vertexes);
138: w.print(" with edges "); // NOI18N
139: w.print(edges);
140: w.println(" cannot be sorted"); // NOI18N
141:
142: Set[] bad = unsortableSets();
143:
144: for (int i = 0; i < bad.length; i++) {
145: w.print(" Conflict #"); // NOI18N
146: w.print(i);
147: w.print(": "); // NOI18N
148: w.println(bad[i]);
149: }
150: }
151:
152: /** Adds description why the graph cannot be sorted.
153: * @param w writer to write to
154: */
155: public final void printStackTrace(java.io.PrintWriter w) {
156: printDebug(w);
157: super .printStackTrace(w);
158: }
159:
160: /** Adds description why the graph cannot be sorted.
161: * @param s stream to write to
162: */
163: public final void printStackTrace(java.io.PrintStream s) {
164: java.io.PrintWriter w = new java.io.PrintWriter(s);
165: this .printStackTrace(w);
166: w.flush();
167: }
168:
169: /** As the full topological sort cannot be finished due to cycles
170: * in the graph this methods performs a partition topological sort.
171: * <P>
172: * First of all it identifies unsortable parts of the graph and
173: * partitions the graph into sets of original objects. Each set contains
174: * objects that are mutually unsortable (there is a cycle between them).
175: * Then the topological sort is performed again on those sets, this
176: * sort succeeds because the graph of sets is DAG (all problematic edges
177: * were only between objects now grouped inside the sets) and the
178: * result forms the return value of this method.
179: *
180: * @return array of sorted sets that contain the original objects, each
181: * object from the original collection is exactly in one set, result
182: * shall not be modified
183: */
184: public final Set[] topologicalSets() {
185: if (result != null) {
186: return result;
187: }
188:
189: HashMap<Object, Vertex> vertexInfo = new HashMap<Object, Vertex>();
190:
191: // computes value X and Y for each vertex
192: counter = 0;
193:
194: Iterator it = vertexes.iterator();
195:
196: while (it.hasNext()) {
197: constructDualGraph(counter, it.next(), vertexInfo);
198: }
199:
200: // now connect vertexes that cannot be sorted into own
201: // sets
202: // map from the original objects to
203: Map<Object, Set> objectsToSets = new HashMap<Object, Set>();
204:
205: ArrayList<Set> sets = new ArrayList<Set>();
206:
207: while (!dualGraph.isEmpty()) {
208: Vertex v = dualGraph.pop();
209:
210: if (!v.visited) {
211: Set<Object> set = new HashSet<Object>();
212: visitDualGraph(v, set);
213:
214: if ((set.size() == 1) && v.edgesFrom.contains(v)) {
215: // mark if there is a self reference and the
216: // set is only one element big, it means that there
217: // is a self cycle
218: //
219: // do not use HashSet but Collections.singleton
220: // to recognize such cycles
221: set = Collections.singleton(v.object);
222: }
223:
224: sets.add(set);
225:
226: // fill the objectsToSets mapping
227: it = set.iterator();
228:
229: while (it.hasNext()) {
230: objectsToSets.put(it.next(), set);
231: }
232: }
233: }
234:
235: // now topologically sort the sets
236: // 1. prepare the map
237: HashMap<Set, Collection<Set>> edgesBetweenSets = new HashMap<Set, Collection<Set>>();
238: it = edges.entrySet().iterator();
239:
240: while (it.hasNext()) {
241: Map.Entry entry = (Map.Entry) it.next();
242: Collection leadsTo = (Collection) entry.getValue();
243:
244: if ((leadsTo == null) || leadsTo.isEmpty()) {
245: continue;
246: }
247:
248: Set from = objectsToSets.get(entry.getKey());
249:
250: Collection<Set> setsTo = edgesBetweenSets.get(from);
251:
252: if (setsTo == null) {
253: setsTo = new ArrayList<Set>();
254: edgesBetweenSets.put(from, setsTo);
255: }
256:
257: Iterator convert = leadsTo.iterator();
258:
259: while (convert.hasNext()) {
260: Set to = objectsToSets.get(convert.next());
261:
262: if (from != to) {
263: // avoid self cycles
264: setsTo.add(to);
265: }
266: }
267: }
268:
269: // 2. do the sort
270: try {
271: List<Set> listResult = Utilities.topologicalSort(sets,
272: edgesBetweenSets);
273: result = listResult.toArray(new Set[0]);
274: } catch (TopologicalSortException ex) {
275: throw new IllegalStateException("Cannot happen"); // NOI18N
276: }
277:
278: return result;
279: }
280:
281: /** Traverses the tree
282: * @param counter current value
283: * @param vertex current vertex
284: * @param vertexInfo the info
285: */
286: private Vertex constructDualGraph(int counter, Object vertex,
287: HashMap<Object, Vertex> vertexInfo) {
288: Vertex info = vertexInfo.get(vertex);
289:
290: if (info == null) {
291: info = new Vertex(vertex, counter++);
292: vertexInfo.put(vertex, info);
293: } else {
294: // already (being) processed
295: return info;
296: }
297:
298: // process children
299: Collection c = (Collection) edges.get(vertex);
300:
301: if (c != null) {
302: Iterator it = c.iterator();
303:
304: while (it.hasNext()) {
305: Vertex next = constructDualGraph(counter, it.next(),
306: vertexInfo);
307: next.edgesFrom.add(info);
308: }
309: }
310:
311: // leaving the vertex
312: info.y = counter++;
313:
314: dualGraph.push(info);
315:
316: return info;
317: }
318:
319: /** Visit dual graph. Decreasing value of Y gives the order.
320: * Number
321: *
322: * @param vertex vertex to start from
323: * @param visited list of all objects that we've been to
324: */
325: private void visitDualGraph(Vertex vertex,
326: Collection<Object> visited) {
327: if (vertex.visited) {
328: return;
329: }
330:
331: visited.add(vertex.object);
332: vertex.visited = true;
333:
334: Iterator it = vertex.edges();
335:
336: while (it.hasNext()) {
337: Vertex v = (Vertex) it.next();
338: visitDualGraph(v, visited);
339: }
340: }
341:
342: /** Represents info about a vertex in the graph. Vertexes are
343: * comparable by the value of Y, but only after the value is set,
344: * so the sort has to be done latelly.
345: */
346: private static final class Vertex implements Comparable<Vertex> {
347: /** the found object */
348: public Object object;
349:
350: /** list of vertexes that point to this one */
351: public List<Vertex> edgesFrom = new ArrayList<Vertex>();
352:
353: /** the counter state when we entered the vertex */
354: public final int x;
355:
356: /** the counter when we exited the vertex */
357: public int y;
358:
359: /** already sorted, true if the edges has been sorted */
360: public boolean sorted;
361:
362: /** true if visited in dual graph */
363: public boolean visited;
364:
365: public Vertex(Object obj, int x) {
366: this .x = x;
367: this .object = obj;
368: }
369:
370: /** Iterator over edges
371: * @return iterator of Vertex items
372: */
373: public Iterator edges() {
374: if (!sorted) {
375: Collections.sort(edgesFrom);
376: sorted = true;
377: }
378:
379: return edgesFrom.iterator();
380: }
381:
382: /** Comparing based on value of Y.
383: *
384: * @param o the Object to be compared.
385: * @return a negative integer, zero, or a positive integer as this object
386: * is less than, equal to, or greater than the specified object.
387: */
388: public int compareTo(Vertex o) {
389: return o.y - y;
390: }
391: }
392: }
|