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 */
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(final Object... objects) {
041    if (objects != null) {
042      for (Object object : objects) {
043        add(object);
044      }
045    }
046  }
047
048  public Node add(final Object object, final Object... dependencies) {
049    Node node = registeredObjects.get(object);
050    if (node == null) {
051      node = new Node(object);
052      nodes.add(node);
053      registeredObjects.put(object, node);
054    }
055
056    if (dependencies != null) {
057      for (Object dependency : dependencies) {
058        Node depNode = add(dependency);
059        node.addDependency(depNode);
060      }
061    }
062    return node;
063  }
064
065  public List sort() {
066    sortNodes();
067
068    List<Object> result = new ArrayList<>();
069    for (Node node : nodes) {
070      result.add(node.getObject());
071    }
072    return result;
073  }
074
075  private List<Node> sortNodes() {
076    verify();
077    Collections.sort(nodes);
078    return nodes;
079  }
080
081  private void verify() {
082    for (Node node : nodes) {
083      node.reset();
084    }
085
086    for (Node node : nodes) {
087      for (Node dep : node.getDependencies()) {
088        if (!nodes.contains(dep)) {
089          throw new SonarException("A dependent node (" + dep + ") of "
090              + " (" + node + ") was not included in the nodes list.");
091        }
092      }
093
094      node.resolveOrder();
095    }
096  }
097}