java/java-impl/src/com/intellij/cyclicDependencies/CyclicDependenciesUtil.java

   1 /*
   2  * Copyright 2000-2009 JetBrains s.r.o.
   3  *
   4  * Licensed under the Apache License, Version 2.0 (the "License");
   5  * you may not use this file except in compliance with the License.
   6  * You may obtain a copy of the License at
   7  *
   8  * http://www.apache.org/licenses/LICENSE-2.0
   9  *
  10  * Unless required by applicable law or agreed to in writing, software
  11  * distributed under the License is distributed on an "AS IS" BASIS,
  12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13  * See the License for the specific language governing permissions and
  14  * limitations under the License.
  15  */
  16 package com.intellij.cyclicDependencies;
  17
  18 import com.intellij.util.Chunk;
  19 import com.intellij.util.graph.DFSTBuilder;
  20 import com.intellij.util.graph.Graph;
  21 import gnu.trove.TIntArrayList;
  22 import gnu.trove.TIntProcedure;
  23
  24 import java.util.*;
  25
  26 /**
  27  * User: anna
  28  * Date: Feb 10, 2005
  29  */
  30 public class CyclicDependenciesUtil{
  31   public static <Node> List<Chunk<Node>> buildChunks(Graph<Node> graph) {
  32     final DFSTBuilder<Node> dfstBuilder = new DFSTBuilder<Node>(graph);
  33     final TIntArrayList sccs = dfstBuilder.getSCCs();
  34     final List<Chunk<Node>> chunks = new ArrayList<Chunk<Node>>();
  35     sccs.forEach(new TIntProcedure() {
  36       int myTNumber = 0;
  37       public boolean execute(int size) {
  38         Set<Node> packs = new LinkedHashSet<Node>();
  39         for (int j = 0; j < size; j++) {
  40           packs.add(dfstBuilder.getNodeByTNumber(myTNumber + j));
  41         }
  42         chunks.add(new Chunk<Node>(packs));
  43         myTNumber += size;
  44         return true;
  45       }
  46     });
  47
  48     return chunks;
  49   }
  50
  51
  52   public static class Path <Node> {
  53     private ArrayList<Node> myPath = new ArrayList<Node>();
  54
  55     public Path() {
  56     }
  57
  58     public Path(Path<Node> path) {
  59       myPath = new ArrayList<Node>(path.myPath);
  60     }
  61
  62     public Node getBeg() {
  63       return myPath.get(0);
  64     }
  65
  66     public Node getEnd() {
  67       return myPath.get(myPath.size() - 1);
  68     }
  69
  70     public boolean contains(Node node) {
  71       return myPath.contains(node);
  72     }
  73
  74     public List<Node> getNextNodes(Node node) {
  75       List<Node> result = new ArrayList<Node>();
  76       for (int i = 0; i < myPath.size() - 1; i++) {
  77         Node nodeN = myPath.get(i);
  78         if (nodeN == node) {
  79           result.add(myPath.get(i + 1));
  80         }
  81       }
  82       return result;
  83     }
  84
  85     public void add(Node node) {
  86       myPath.add(node);
  87     }
  88
  89     public ArrayList<Node> getPath() {
  90       return myPath;
  91     }
  92   }
  93
  94   public static class GraphTraverser<Node> {
  95     private final List<Path<Node>> myCurrentPaths = new ArrayList<Path<Node>>();
  96     private final Node myBegin;
  97     private final Chunk<Node> myChunk;
  98     private final int myMaxPathsCount;
  99     private final Graph<Node> myGraph;
 100
 101     public GraphTraverser(final Node begin, final Chunk<Node> chunk, final int maxPathsCount, final Graph<Node> graph) {
 102       myBegin = begin;
 103       myChunk = chunk;
 104       myMaxPathsCount = maxPathsCount;
 105       myGraph = graph;
 106     }
 107
 108     public Set<Path<Node>> traverse() {
 109       Set<Path<Node>> result = new HashSet<Path<Node>>();
 110       Path<Node> firstPath = new Path<Node>();
 111       firstPath.add(myBegin);
 112       myCurrentPaths.add(firstPath);
 113       while (!myCurrentPaths.isEmpty() && result.size() < myMaxPathsCount) {
 114         final Path<Node> path = myCurrentPaths.get(0);
 115         final Set<Node> nextNodes = getNextNodes(path.getEnd());
 116         nextStep(nextNodes, path, result);
 117       }
 118       return result;
 119     }
 120
 121     public Set<ArrayList<Node>> convert(Set<Path<Node>> paths) {
 122       Set<ArrayList<Node>> result = new HashSet<ArrayList<Node>>();
 123       for (Path<Node> path : paths) {
 124         result.add(path.getPath());
 125       }
 126       return result;
 127     }
 128
 129     private void nextStep(final Set<Node> nextNodes, final Path<Node> path, Set<Path<Node>> result) {
 130       myCurrentPaths.remove(path);
 131       for (Node node : nextNodes) {
 132         if (path.getEnd() == node) {
 133           continue;
 134         }
 135         if (path.getBeg() == node) {
 136           result.add(path);
 137           continue;
 138         }
 139         Path<Node> newPath = new Path<Node>(path);
 140         newPath.add(node);
 141         if (path.contains(node)) {
 142           final Set<Node> nodesAfterInnerCycle = getNextNodes(node);
 143           nodesAfterInnerCycle.removeAll(path.getNextNodes(node));
 144           nextStep(nodesAfterInnerCycle, newPath, result);
 145         }
 146         else {
 147           myCurrentPaths.add(newPath);
 148         }
 149       }
 150     }
 151
 152     private Set<Node> getNextNodes(Node node) {
 153       Set<Node> result = new HashSet<Node>();
 154       final Iterator<Node> in = myGraph.getIn(node);
 155       for (; in.hasNext();) {
 156         final Node inNode = in.next();
 157         if (myChunk.containsNode(inNode)) {
 158           result.add(inNode);
 159         }
 160       }
 161       return result;
 162     }
 163   }
 164 }