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
12 * http://www.apache.org/licenses/LICENSE-2.0
13 * Unless required by applicable law or agreed to in writing, software
14 * distributed under the License is distributed on an "AS IS" BASIS,
15 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
16 * See the License for the specific language governing permissions and
17 * limitations under the License.
18 * ============LICENSE_END=========================================================
20 * ECOMP and OpenECOMP are trademarks
21 * and service marks of AT&T Intellectual Property.
23 package org.openecomp.modelloader.entity.model;
25 import jline.internal.Log;
27 import org.openecomp.modelloader.entity.Artifact;
29 import java.util.ArrayList;
30 import java.util.Collection;
31 import java.util.HashMap;
32 import java.util.HashSet;
33 import java.util.Iterator;
34 import java.util.List;
37 * Utility class to sort the given Models according to their dependencies.
38 * Example: Given a list of Models [A, B, C] where B depends on A, and A depends
39 * on C, the sorted result will be [C, A, B]
41 public class ModelSorter {
44 * Wraps a Model object to form dependencies other Models using Edges.
47 private final ModelArtifact model;
48 private final HashSet<Edge> inEdges;
49 private final HashSet<Edge> outEdges;
51 public Node(ModelArtifact model) {
53 inEdges = new HashSet<Edge>();
54 outEdges = new HashSet<Edge>();
57 public Node addEdge(Node node) {
58 Edge edge = new Edge(this, node);
60 node.inEdges.add(edge);
65 public String toString() {
66 if (model.getModelInvariantId() == null) {
67 return model.getNameVersionId();
70 return model.getModelInvariantId();
74 public boolean equals(Object other) {
75 ModelArtifact otherModel = ((Node) other).model;
76 String modelId1 = this.model.getModelInvariantId();
77 if (modelId1 == null) {
78 modelId1 = this.model.getNameVersionId();
81 String modelId2 = otherModel.getModelInvariantId();
82 if (modelId2 == null) {
83 modelId2 = otherModel.getNameVersionId();
86 return modelId1.equals(modelId2);
90 public int hashCode() {
91 if (this.model.getModelInvariantId() == null) {
92 return this.model.getNameVersionId().hashCode();
95 return this.model.getModelInvariantId().hashCode();
100 * Represents a dependency between two Nodes.
103 public final Node from;
104 public final Node to;
106 public Edge(Node from, Node to) {
112 public boolean equals(Object obj) {
113 Edge edge = (Edge) obj;
114 return edge.from == from && edge.to == to;
119 * Returns the list of models sorted by order of dependency.
121 * @param originalList
122 * the list that needs to be sorted
123 * @return a list of sorted models
125 public List<Artifact> sort(List<Artifact> originalList) {
127 if (originalList.size() <= 1) {
131 Collection<Node> nodes = createNodes(originalList);
132 Collection<Node> sortedNodes = sortNodes(nodes);
134 List<Artifact> sortedModelsList = new ArrayList<Artifact>(sortedNodes.size());
135 for (Node node : sortedNodes) {
136 sortedModelsList.add(node.model);
139 return sortedModelsList;
143 * Create nodes from the list of models and their dependencies.
146 * what the nodes creation is based upon
147 * @return Collection of Node objects
149 private Collection<Node> createNodes(Collection<Artifact> models) {
151 // load list of models into a map, so we can later replace referenceIds with
153 HashMap<String, ModelArtifact> versionIdToModelMap = new HashMap<String, ModelArtifact>();
154 for (Artifact art : models) {
155 ModelArtifact ma = (ModelArtifact) art;
156 versionIdToModelMap.put(ma.getModelModelVerCombinedKey(), ma);
159 HashMap<String, Node> nodes = new HashMap<String, Node>();
160 // create a node for each model and its referenced models
161 for (Artifact art : models) {
163 ModelArtifact model = (ModelArtifact) art;
165 // node might have been created by another model referencing it
166 Node node = nodes.get(model.getModelModelVerCombinedKey());
169 node = new Node(model);
170 nodes.put(model.getModelModelVerCombinedKey(), node);
173 for (String referencedModelId : model.getDependentModelIds()) {
174 // node might have been created by another model referencing it
175 Node referencedNode = nodes.get(referencedModelId);
177 if (null == referencedNode) {
179 ModelArtifact referencedModel = versionIdToModelMap.get(referencedModelId);
180 if (referencedModel == null) {
181 Log.debug("ignoring " + referencedModelId);
182 continue; // referenced model not supplied, no need to sort it
184 referencedNode = new Node(referencedModel);
185 nodes.put(referencedModelId, referencedNode);
187 referencedNode.addEdge(node);
191 return nodes.values();
195 * Sorts the given Nodes by order of dependency.
197 * @param originalList
198 * the collection of nodes to be sorted
199 * @return a sorted collection of the given nodes
201 private Collection<Node> sortNodes(Collection<Node> unsortedNodes) {
202 // L <- Empty list that will contain the sorted elements
203 ArrayList<Node> nodeList = new ArrayList<Node>();
205 // S <- Set of all nodes with no incoming edges
206 HashSet<Node> nodeSet = new HashSet<Node>();
207 for (Node unsortedNode : unsortedNodes) {
208 if (unsortedNode.inEdges.size() == 0) {
209 nodeSet.add(unsortedNode);
213 // while S is non-empty do
214 while (!nodeSet.isEmpty()) {
215 // remove a node n from S
216 Node node = nodeSet.iterator().next();
217 nodeSet.remove(node);
222 // for each node m with an edge e from n to m do
223 for (Iterator<Edge> it = node.outEdges.iterator(); it.hasNext();) {
224 // remove edge e from the graph
225 Edge edge = it.next();
227 it.remove();// Remove edge from n
228 to.inEdges.remove(edge);// Remove edge from m
230 // if m has no other incoming edges then insert m into S
231 if (to.inEdges.isEmpty()) {
236 // Check to see if all edges are removed
237 boolean cycle = false;
238 for (Node node : unsortedNodes) {
239 if (!node.inEdges.isEmpty()) {
245 throw new RuntimeException(
246 "Circular dependency present between models, topological sort not possible");