2 * ============LICENSE_START=======================================================
4 * ================================================================================
5 * Copyright © 2017 AT&T Intellectual Property.
6 * Copyright © 2017 Amdocs
8 * ================================================================================
9 * Licensed under the Apache License, Version 2.0 (the "License");
10 * you may not use this file except in compliance with the License.
11 * You may obtain a copy of the License at
13 * http://www.apache.org/licenses/LICENSE-2.0
15 * Unless required by applicable law or agreed to in writing, software
16 * distributed under the License is distributed on an "AS IS" BASIS,
17 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
18 * See the License for the specific language governing permissions and
19 * limitations under the License.
20 * ============LICENSE_END=========================================================
22 * ECOMP is a trademark and service mark of AT&T Intellectual Property.
24 package org.onap.aai.modelloader.entity.model;
26 import jline.internal.Log;
28 import java.util.ArrayList;
29 import java.util.Collection;
30 import java.util.HashMap;
31 import java.util.HashSet;
32 import java.util.Iterator;
33 import java.util.List;
35 import org.onap.aai.modelloader.entity.Artifact;
38 * Utility class to sort the given Models according to their dependencies.
39 * Example: Given a list of Models [A, B, C] where B depends on A, and A depends
40 * on C, the sorted result will be [C, A, B]
42 public class ModelSorter {
45 * Wraps a Model object to form dependencies other Models using Edges.
48 private final AbstractModelArtifact model;
49 private final HashSet<Edge> inEdges;
50 private final HashSet<Edge> outEdges;
52 public Node(AbstractModelArtifact model) {
54 inEdges = new HashSet<Edge>();
55 outEdges = new HashSet<Edge>();
58 public Node addEdge(Node node) {
59 Edge edge = new Edge(this, node);
61 node.inEdges.add(edge);
66 public String toString() {
67 return model.getUniqueIdentifier();
71 public boolean equals(Object other) {
72 AbstractModelArtifact otherModel = ((Node) other).model;
73 return this.model.getUniqueIdentifier().equals(otherModel.getUniqueIdentifier());
77 public int hashCode() {
78 return this.model.getUniqueIdentifier().hashCode();
83 * Represents a dependency between two Nodes.
86 public final Node from;
89 public Edge(Node from, Node to) {
95 public boolean equals(Object obj) {
96 Edge edge = (Edge) obj;
97 return edge.from == from && edge.to == to;
102 * Returns the list of models sorted by order of dependency.
104 * @param originalList
105 * the list that needs to be sorted
106 * @return a list of sorted models
108 public List<Artifact> sort(List<Artifact> originalList) {
110 if (originalList.size() <= 1) {
114 Collection<Node> nodes = createNodes(originalList);
115 Collection<Node> sortedNodes = sortNodes(nodes);
117 List<Artifact> sortedModelsList = new ArrayList<Artifact>(sortedNodes.size());
118 for (Node node : sortedNodes) {
119 sortedModelsList.add(node.model);
122 return sortedModelsList;
126 * Create nodes from the list of models and their dependencies.
129 * what the nodes creation is based upon
130 * @return Collection of Node objects
132 private Collection<Node> createNodes(Collection<Artifact> models) {
134 // load list of models into a map, so we can later replace referenceIds with
136 HashMap<String, AbstractModelArtifact> versionIdToModelMap = new HashMap<>();
137 for (Artifact art : models) {
138 AbstractModelArtifact ma = (AbstractModelArtifact) art;
139 versionIdToModelMap.put(ma.getUniqueIdentifier(), ma);
142 HashMap<String, Node> nodes = new HashMap<String, Node>();
143 // create a node for each model and its referenced models
144 for (Artifact art : models) {
146 AbstractModelArtifact model = (AbstractModelArtifact) art;
148 // node might have been created by another model referencing it
149 Node node = nodes.get(model.getUniqueIdentifier());
152 node = new Node(model);
153 nodes.put(model.getUniqueIdentifier(), node);
156 for (String referencedModelId : model.getDependentModelIds()) {
157 // node might have been created by another model referencing it
158 Node referencedNode = nodes.get(referencedModelId);
160 if (null == referencedNode) {
162 AbstractModelArtifact referencedModel = versionIdToModelMap.get(referencedModelId);
163 if (referencedModel == null) {
164 Log.debug("ignoring " + referencedModelId);
165 continue; // referenced model not supplied, no need to sort it
167 referencedNode = new Node(referencedModel);
168 nodes.put(referencedModelId, referencedNode);
170 referencedNode.addEdge(node);
174 return nodes.values();
178 * Sorts the given Nodes by order of dependency.
180 * @param originalList
181 * the collection of nodes to be sorted
182 * @return a sorted collection of the given nodes
184 private Collection<Node> sortNodes(Collection<Node> unsortedNodes) {
185 // L <- Empty list that will contain the sorted elements
186 ArrayList<Node> nodeList = new ArrayList<Node>();
188 // S <- Set of all nodes with no incoming edges
189 HashSet<Node> nodeSet = new HashSet<Node>();
190 for (Node unsortedNode : unsortedNodes) {
191 if (unsortedNode.inEdges.size() == 0) {
192 nodeSet.add(unsortedNode);
196 // while S is non-empty do
197 while (!nodeSet.isEmpty()) {
198 // remove a node n from S
199 Node node = nodeSet.iterator().next();
200 nodeSet.remove(node);
205 // for each node m with an edge e from n to m do
206 for (Iterator<Edge> it = node.outEdges.iterator(); it.hasNext();) {
207 // remove edge e from the graph
208 Edge edge = it.next();
210 it.remove();// Remove edge from n
211 to.inEdges.remove(edge);// Remove edge from m
213 // if m has no other incoming edges then insert m into S
214 if (to.inEdges.isEmpty()) {
219 // Check to see if all edges are removed
220 boolean cycle = false;
221 for (Node node : unsortedNodes) {
222 if (!node.inEdges.isEmpty()) {
228 throw new RuntimeException(
229 "Circular dependency present between models, topological sort not possible");