001/* 002 * SonarQube 003 * Copyright (C) 2009-2016 SonarSource SA 004 * mailto:contact 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(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}