001    /*
002     * SonarQube, open source software quality management tool.
003     * Copyright (C) 2008-2014 SonarSource
004     * mailto:contact AT sonarsource DOT com
005     *
006     * SonarQube 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     * SonarQube 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 License
017     * along with this program; if not, write to the Free Software Foundation,
018     * Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.
019     */
020    package org.sonar.api.utils.dag;
021    
022    import com.google.common.collect.Lists;
023    
024    import org.sonar.api.utils.SonarException;
025    
026    import java.util.*;
027    
028    /**
029     * <a href="http://en.wikipedia.org/wiki/Directed_acyclic_graph">http://en.wikipedia.org/wiki/Directed_acyclic_graph</a>
030     *
031     * @since 1.10
032     */
033    public class DirectAcyclicGraph {
034    
035      private Map<Object, Node> registeredObjects = new HashMap<Object, Node>();
036      private List<Node> nodes = new ArrayList<Node>();
037    
038      public DirectAcyclicGraph(final Object... objects) {
039        if (objects != null) {
040          for (Object object : objects) {
041            add(object);
042          }
043        }
044      }
045    
046      public Node add(final Object object, final Object... dependencies) {
047        Node node = registeredObjects.get(object);
048        if (node == null) {
049          node = new Node(object);
050          nodes.add(node);
051          registeredObjects.put(object, node);
052        }
053    
054        if (dependencies != null) {
055          for (Object dependency : dependencies) {
056            Node depNode = add(dependency);
057            node.addDependency(depNode);
058          }
059        }
060        return node;
061      }
062    
063      public List sort() {
064        sortNodes();
065    
066        List<Object> result = Lists.newArrayList();
067        for (Node node : nodes) {
068          result.add(node.getObject());
069        }
070        return result;
071      }
072    
073      private List<Node> sortNodes() {
074        verify();
075        Collections.sort(nodes);
076        return nodes;
077      }
078    
079      private void verify() {
080        for (Node node : nodes) {
081          node.reset();
082        }
083    
084        for (Node node : nodes) {
085          for (Node dep : node.getDependencies()) {
086            if (!nodes.contains(dep)) {
087              throw new SonarException("A dependent node (" + dep + ") of "
088                  + " (" + node + ") was not included in the nodes list.");
089            }
090          }
091    
092          node.resolveOrder();
093        }
094      }
095    }