001/*
002 * SonarQube
003 * Copyright (C) 2009-2017 SonarSource SA
004 * mailto:info AT sonarsource DOT com
005 *
006 * This program 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 * This program 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 */
020package org.sonar.api.utils.dag;
021
022import org.sonar.api.utils.SonarException;
023
024import java.util.ArrayList;
025import java.util.Collections;
026import java.util.HashMap;
027import java.util.List;
028import java.util.Map;
029
030/**
031 * <a href="http://en.wikipedia.org/wiki/Directed_acyclic_graph">http://en.wikipedia.org/wiki/Directed_acyclic_graph</a>
032 *
033 * @since 1.10
034 */
035public class DirectAcyclicGraph {
036
037  private Map<Object, Node> registeredObjects = new HashMap<>();
038  private List<Node> nodes = new ArrayList<>();
039
040  public DirectAcyclicGraph(Object... objects) {
041    for (Object object : objects) {
042      add(object);
043    }
044  }
045
046  public Node add(Object object, 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    for (Object dependency : dependencies) {
055      Node depNode = add(dependency);
056      node.addDependency(depNode);
057    }
058    return node;
059  }
060
061  public List sort() {
062    sortNodes();
063
064    List<Object> result = new ArrayList<>();
065    for (Node node : nodes) {
066      result.add(node.getObject());
067    }
068    return result;
069  }
070
071  private List<Node> sortNodes() {
072    verify();
073    Collections.sort(nodes);
074    return nodes;
075  }
076
077  private void verify() {
078    for (Node node : nodes) {
079      node.reset();
080    }
081
082    for (Node node : nodes) {
083      for (Node dep : node.getDependencies()) {
084        if (!nodes.contains(dep)) {
085          throw new SonarException("A dependent node (" + dep + ") of "
086              + " (" + node + ") was not included in the nodes list.");
087        }
088      }
089
090      node.resolveOrder();
091    }
092  }
093}