001: /*
002: * FindBugs - Find Bugs in Java programs
003: * Copyright (C) 2006, University of Maryland
004: *
005: * This library is free software; you can redistribute it and/or
006: * modify it under the terms of the GNU Lesser General Public
007: * License as published by the Free Software Foundation; either
008: * version 2.1 of the License, or (at your option) any later version.
009: *
010: * This library is distributed in the hope that it will be useful,
011: * but WITHOUT ANY WARRANTY; without even the implied warranty of
012: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
013: * Lesser General Public License for more details.
014: *
015: * You should have received a copy of the GNU Lesser General Public
016: * License along with this library; if not, write to the Free Software
017: * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
018: */
019:
020: package edu.umd.cs.findbugs.util;
021:
022: import java.util.ArrayList;
023: import java.util.Collection;
024: import java.util.Collections;
025: import java.util.HashSet;
026: import java.util.IdentityHashMap;
027: import java.util.Iterator;
028: import java.util.LinkedHashSet;
029: import java.util.LinkedList;
030: import java.util.List;
031: import java.util.Map;
032: import java.util.Set;
033:
034: import edu.umd.cs.findbugs.SystemProperties;
035: import edu.umd.cs.findbugs.log.Profiler;
036:
037: /**
038: * @author pugh
039: */
040: public class TopologicalSort {
041: final static boolean DEBUG = SystemProperties
042: .getBoolean("tsort.debug");
043:
044: public interface OutEdges<E> {
045: Collection<E> getOutEdges(E e);
046: }
047:
048: public static class OutEdgesCache<E> implements OutEdges<E> {
049:
050: final Map<E, Collection<E>> map = new IdentityHashMap<E, Collection<E>>();
051: final OutEdges<E> base;
052:
053: public OutEdgesCache(OutEdges<E> base) {
054: this .base = base;
055: }
056:
057: public Collection<E> getOutEdges(E e) {
058: Collection<E> result = map.get(e);
059: if (result == null) {
060: result = base.getOutEdges(e);
061: map.put(e, result);
062: }
063: return result;
064: }
065:
066: }
067:
068: public static <E> List<E> sortByCallGraph(Collection<E> elements,
069: OutEdges<E> outEdges) {
070: Profiler profile = Profiler.getInstance();
071: profile.start(TopologicalSort.class);
072: try {
073: SortAlgorithm<E> instance = new Worker2<E>(elements,
074: outEdges);
075: return instance.compute();
076: } finally {
077: profile.end(TopologicalSort.class);
078: }
079: }
080:
081: public static <E> void countBadEdges(List<E> elements,
082: OutEdges<E> outEdges) {
083: if (!DEBUG)
084: return;
085: HashSet<E> seen = new HashSet<E>();
086: HashSet<E> all = new HashSet<E>(elements);
087: int result = 0;
088: int total = 0;
089: for (E e : elements) {
090: for (E e2 : outEdges.getOutEdges(e))
091: if (e != e2 && all.contains(e2)
092: && !outEdges.getOutEdges(e2).contains(e)) {
093: total++;
094: if (!seen.contains(e2))
095: result++;
096: }
097: seen.add(e);
098: }
099: System.out.println(" bad edges are " + result + "/" + total);
100: }
101:
102: interface SortAlgorithm<E> {
103: List<E> compute();
104: }
105:
106: static class Worker<E> implements SortAlgorithm<E> {
107: Worker(Collection<E> consider, OutEdges<E> outEdges) {
108: this .consider = new LinkedHashSet<E>(consider);
109: this .outEdges = outEdges;
110: this .result = new ArrayList<E>(consider.size());
111:
112: }
113:
114: OutEdges<E> outEdges;
115:
116: List<E> result;
117:
118: HashSet<E> visited = new HashSet<E>();
119: Set<E> consider = new HashSet<E>();
120:
121: public List<E> compute() {
122: for (E e : consider)
123: visit(e);
124: return result;
125: }
126:
127: void visit(E e) {
128: if (!consider.contains(e))
129: return;
130: if (!visited.add(e))
131: return;
132: for (E e2 : outEdges.getOutEdges(e))
133: visit(e2);
134:
135: result.add(e);
136: }
137: }
138:
139: static class Worker2<E> implements SortAlgorithm<E> {
140: Worker2(Collection<E> consider, OutEdges<E> outEdges) {
141: if (outEdges == null)
142: throw new IllegalArgumentException(
143: "outEdges must not be null");
144: this .consider = new LinkedHashSet<E>(consider);
145: this .outEdges = outEdges;
146:
147: }
148:
149: OutEdges<E> outEdges;
150:
151: Set<E> consider = new HashSet<E>();
152: MultiMap<E, E> iEdges, oEdges;
153:
154: private void removeVertex(E e) {
155: Collection<E> outEdges = oEdges.get(e);
156:
157: Collection<E> inEdges = iEdges.get(e);
158: for (E e2 : outEdges) {
159: iEdges.remove(e2, e);
160: }
161: for (E e2 : inEdges) {
162: oEdges.remove(e2, e);
163: }
164: iEdges.removeAll(e);
165: oEdges.removeAll(e);
166: }
167:
168: public List<E> compute() {
169: ArrayList<E> doFirst = new ArrayList<E>(consider.size());
170: ArrayList<E> doLast = new ArrayList<E>(consider.size());
171:
172: HashSet<E> remaining = new HashSet<E>(consider);
173: iEdges = new MultiMap<E, E>(LinkedList.class);
174: oEdges = new MultiMap<E, E>(LinkedList.class);
175:
176: for (E e : consider)
177: for (E e2 : outEdges.getOutEdges(e))
178: if (e != e2 && consider.contains(e2)) {
179: iEdges.add(e2, e);
180: oEdges.add(e, e2);
181: }
182: for (E e : consider) {
183: HashSet<E> both = new HashSet<E>(iEdges.get(e));
184: both.retainAll(oEdges.get(e));
185: for (E e2 : both) {
186: iEdges.remove(e, e2);
187: oEdges.remove(e, e2);
188: }
189: }
190: while (!remaining.isEmpty()) {
191: boolean foundSomething = false;
192: E best = null;
193: int bestScore = Integer.MIN_VALUE;
194: for (Iterator<E> i = remaining.iterator(); i.hasNext();) {
195: E e = i.next();
196: if (oEdges.get(e).isEmpty()) {
197: doFirst.add(e);
198: removeVertex(e);
199: if (DEBUG)
200: System.out.println("do " + e + " first");
201: i.remove();
202: foundSomething = true;
203: } else if (iEdges.get(e).isEmpty()) {
204: doLast.add(e);
205: removeVertex(e);
206: if (DEBUG)
207: System.out.println("do " + e + " last");
208: i.remove();
209: foundSomething = true;
210: } else {
211: // Higher score: more likely to choose
212: int myScore = score(e);
213:
214: // myScore -= oEdges.get(e).size(); // more needs, more reluctant
215: // myScore += iEdges.get(e).size(); // needed more, more eager
216: if (bestScore < myScore) {
217: // my score is better than the best seen so far
218: bestScore = myScore;
219: best = e;
220: }
221: }
222: } // iterator
223: if (!foundSomething) {
224: if (DEBUG) {
225: if (best
226: .toString()
227: .equals(
228: "org/eclipse/jdt/internal/core/JavaModel")) {
229: System.out
230: .println("Full dump for org/eclipse/jdt/internal/core/JavaModel {");
231: for (E e : remaining) {
232: System.out.printf(" %4d %s\n",
233: score(e), e);
234: System.out.println(" needs: "
235: + oEdges.get(e));
236: System.out.println(" needed by: "
237: + iEdges.get(e));
238: }
239: System.out
240: .println("} Full dump for org/eclipse/jdt/internal/core/JavaModel");
241:
242: }
243: System.out.println("do " + best
244: + " first, reluctantly");
245: System.out.println(" needs: "
246: + oEdges.get(best));
247: System.out.println(" needed by: "
248: + iEdges.get(best));
249: }
250: doFirst.add(best);
251: removeVertex(best);
252: remaining.remove(best);
253: }
254: } // while
255: Collections.reverse(doLast);
256: doFirst.addAll(doLast);
257:
258: return doFirst;
259: }
260:
261: /**
262: * @param e
263: * @return
264: */
265: private int score(E e) {
266: int myScore = 0;
267: for (E e2 : oEdges.get(e))
268: if (iEdges.get(e2).size() == 1)
269: myScore -= 2;
270: else
271: myScore -= 1;
272: for (E e2 : iEdges.get(e))
273: if (oEdges.get(e2).size() == 1)
274: myScore += 2;
275: else
276: myScore += 1;
277: return myScore;
278: }
279:
280: }
281: }
|