001    /*
002     * Sonar, open source software quality management tool.
003     * Copyright (C) 2009 SonarSource SA
004     * mailto:contact AT sonarsource DOT com
005     *
006     * Sonar is free software; you can redistribute it and/or
007     * modify it under the terms of the GNU Lesser General Public
008     * License as published by the Free Software Foundation; either
009     * version 3 of the License, or (at your option) any later version.
010     *
011     * Sonar is distributed in the hope that it will be useful,
012     * but WITHOUT ANY WARRANTY; without even the implied warranty of
013     * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
014     * Lesser General Public License for more details.
015     *
016     * You should have received a copy of the GNU Lesser General Public
017     * License along with Sonar; if not, write to the Free Software
018     * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02
019     */
020    package org.sonar.squid.graph;
021    
022    import java.util.ArrayList;
023    import java.util.Arrays;
024    import java.util.Collection;
025    import java.util.List;
026    
027    public class CycleDetector {
028    
029      private final Collection<? extends Node> resourcesToAnalyze;
030      private final List<Node> alreadyAnalyzed;
031      private final List<Cycle>                cycles = new ArrayList<Cycle>(); ;
032    
033      public CycleDetector(Collection<? extends Node> resourcesToAnalyze) {
034        this.resourcesToAnalyze = resourcesToAnalyze;
035        this.alreadyAnalyzed = new ArrayList<Node>();
036        analyze();
037      }
038    
039      public CycleDetector(Node... resources) {
040        this(Arrays.asList(resources));
041      }
042    
043      private void analyze() {
044        for (Node resource : resourcesToAnalyze) {
045          if (! alreadyAnalyzed.contains(resource)) {
046            analyze(resource, new ArrayList<Node>());
047          }
048        }
049      }
050    
051      private void analyze(Node node, List<Node> path) {
052        path.add(node);
053        alreadyAnalyzed.add(node);
054        for (Node dependency : node.dependsUpon()) {
055          if (path.contains(dependency)) {
056            Cycle cycle = new Cycle(new ArrayList<Node>(path.subList(path.indexOf(dependency), path.indexOf(node) + 1)));
057            if (!cycles.contains(cycle)) {
058              cycles.add(cycle);
059            }
060          } else {
061            analyze(dependency, new ArrayList<Node>(path));
062          }
063        }
064      }
065    
066      public List<Cycle> getCycles() {
067        return cycles;
068      }
069    
070      public Cycle getCycles(int cycleNumber) {
071        return cycles.get(cycleNumber);
072      }
073    
074      public int getCyclesNumber() {
075        return cycles.size();
076      }
077    
078      @Override
079      public String toString() {
080        StringBuilder builder = new StringBuilder();
081        builder.append("There are " + getCyclesNumber() + " cycles.\n");
082        for (Cycle cycle : cycles) {
083          builder.append(cycle);
084        }
085        return builder.toString();
086      }
087    
088      public boolean contains(Cycle cycle) {
089        return cycles.contains(cycle);
090      }
091    }