/*
* FindBugs - Find Bugs in Java programs
* Copyright (C) 2006, University of Maryland
*
* This library is free software; you can redistribute it and/or
* modify it under the terms of the GNU Lesser General Public
* License as published by the Free Software Foundation; either
* version 2.1 of the License, or (at your option) any later version.
*
* This library is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
* Lesser General Public License for more details.
*
* You should have received a copy of the GNU Lesser General Public
* License along with this library; if not, write to the Free Software
* Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
*/
package edu.umd.cs.findbugs.util;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.HashSet;
import java.util.IdentityHashMap;
import java.util.Iterator;
import java.util.LinkedHashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Set;
import edu.umd.cs.findbugs.SystemProperties;
import edu.umd.cs.findbugs.classfile.Global;
import edu.umd.cs.findbugs.log.Profiler;
/**
* @author pugh
*/
public class TopologicalSort {
final static boolean DEBUG = SystemProperties.getBoolean("tsort.debug");
public interface OutEdges<E> {
Collection<E> getOutEdges(E e);
}
public interface OutEdges2<E> extends OutEdges<E> {
int score(E e);
}
public static class OutEdgesCache<E> implements OutEdges<E> {
final Map<E, Collection<E>> map = new IdentityHashMap<E, Collection<E>>();
final OutEdges<E> base;
public OutEdgesCache(OutEdges<E> base) {
this.base = base;
}
@Override
public Collection<E> getOutEdges(E e) {
Collection<E> result = map.get(e);
if (result == null) {
result = base.getOutEdges(e);
map.put(e, result);
}
return result;
}
}
public static <E> List<E> sortByCallGraph(Collection<E> elements, OutEdges<E> outEdges) {
Profiler profile = Global.getAnalysisCache().getProfiler();
profile.start(TopologicalSort.class);
try {
SortAlgorithm<E> instance = new Worker2<E>(elements, outEdges);
return instance.compute();
} finally {
profile.end(TopologicalSort.class);
}
}
public static <E> void countBadEdges(List<E> elements, OutEdges<E> outEdges) {
if (!DEBUG) {
return;
}
HashSet<E> seen = new HashSet<E>();
HashSet<E> all = new HashSet<E>(elements);
int result = 0;
int total = 0;
for (E e : elements) {
for (E e2 : outEdges.getOutEdges(e)) {
if (e != e2 && all.contains(e2) && !outEdges.getOutEdges(e2).contains(e)) {
total++;
if (!seen.contains(e2)) {
result++;
}
}
}
seen.add(e);
}
System.out.println(" bad edges are " + result + "/" + total);
}
interface SortAlgorithm<E> {
List<E> compute();
}
static class Worker<E> implements SortAlgorithm<E> {
Worker(Collection<E> consider, OutEdges<E> outEdges) {
this.consider = new LinkedHashSet<E>(consider);
this.outEdges = outEdges;
this.result = new ArrayList<E>(consider.size());
}
OutEdges<E> outEdges;
List<E> result;
HashSet<E> visited = new HashSet<E>();
Set<E> consider = new HashSet<E>();
@Override
public List<E> compute() {
for (E e : consider) {
visit(e);
}
return result;
}
void visit(E e) {
if (!consider.contains(e)) {
return;
}
if (!visited.add(e)) {
return;
}
for (E e2 : outEdges.getOutEdges(e)) {
visit(e2);
}
result.add(e);
}
}
static class Worker2<E> implements SortAlgorithm<E> {
Worker2(Collection<E> consider, OutEdges<E> outEdges) {
if (outEdges == null) {
throw new IllegalArgumentException("outEdges must not be null");
}
this.consider = new LinkedHashSet<E>(consider);
this.outEdges = outEdges;
}
OutEdges<E> outEdges;
Set<E> consider = new HashSet<E>();
MultiMap<E, E> iEdges, oEdges;
private void removeVertex(E e) {
Collection<E> outEdges = oEdges.get(e);
Collection<E> inEdges = iEdges.get(e);
for (E e2 : outEdges) {
iEdges.remove(e2, e);
}
for (E e2 : inEdges) {
oEdges.remove(e2, e);
}
iEdges.removeAll(e);
oEdges.removeAll(e);
}
@Override
public List<E> compute() {
ArrayList<E> doFirst = new ArrayList<E>(consider.size());
ArrayList<E> doLast = new ArrayList<E>(consider.size());
HashSet<E> remaining = new HashSet<E>(consider);
iEdges = new MultiMap<E, E>(LinkedList.class);
oEdges = new MultiMap<E, E>(LinkedList.class);
for (E e : consider) {
for (E e2 : outEdges.getOutEdges(e)) {
if (e != e2 && consider.contains(e2)) {
iEdges.add(e2, e);
oEdges.add(e, e2);
}
}
}
for (E e : consider) {
HashSet<E> both = new HashSet<E>(iEdges.get(e));
both.retainAll(oEdges.get(e));
for (E e2 : both) {
iEdges.remove(e, e2);
oEdges.remove(e, e2);
}
}
while (!remaining.isEmpty()) {
boolean foundSomething = false;
E best = null;
int bestScore = Integer.MIN_VALUE;
for (Iterator<E> i = remaining.iterator(); i.hasNext();) {
E e = i.next();
if (oEdges.get(e).isEmpty()) {
doFirst.add(e);
removeVertex(e);
if (DEBUG) {
System.out.println("do " + e + " first");
}
i.remove();
foundSomething = true;
} else if (iEdges.get(e).isEmpty()) {
doLast.add(e);
removeVertex(e);
if (DEBUG) {
System.out.println("do " + e + " last");
}
i.remove();
foundSomething = true;
} else {
// Higher score: more likely to choose
int myScore = getScore(e);
// myScore -= oEdges.get(e).size(); // more needs, more
// reluctant
// myScore += iEdges.get(e).size(); // needed more, more
// eager
if (bestScore < myScore) {
// my score is better than the best seen so far
bestScore = myScore;
best = e;
}
}
} // iterator
if (!foundSomething) {
if (DEBUG) {
System.out.println("do " + best + " first, reluctantly");
System.out.println(" score: " + bestScore);
System.out.println(" needs: " + oEdges.get(best));
System.out.println(" needed by: " + iEdges.get(best));
}
doFirst.add(best);
removeVertex(best);
remaining.remove(best);
}
} // while
Collections.reverse(doLast);
doFirst.addAll(doLast);
return doFirst;
}
/**
* @param e
* @return
*/
private int getScore(E e) {
int myScore = score(e);
if (outEdges instanceof OutEdges2) {
int score2 = ((OutEdges2<E>) outEdges).score(e);
if (score2 > 1) {
score2 += 11;
}
myScore = 5 * myScore + score2;
}
return myScore;
}
/**
* @param e
* @return
*/
private int score(E e) {
int myScore = 0;
for (E e2 : oEdges.get(e)) {
if (iEdges.get(e2).size() == 1) {
myScore -= 2;
} else {
myScore -= 1;
}
}
for (E e2 : iEdges.get(e)) {
if (oEdges.get(e2).size() == 1) {
myScore += 2;
} else {
myScore += 1;
}
}
return myScore;
}
}
}