1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
|
/**
* ============LICENSE_START=======================================================
* Model Loader
* ================================================================================
* Copyright © 2017 AT&T Intellectual Property.
* Copyright © 2017 Amdocs
* All rights reserved.
* ================================================================================
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
* You may obtain a copy of the License at
* http://www.apache.org/licenses/LICENSE-2.0
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
* ============LICENSE_END=========================================================
*
* ECOMP and OpenECOMP are trademarks
* and service marks of AT&T Intellectual Property.
*/
package org.openecomp.modelloader.entity.model;
import jline.internal.Log;
import org.openecomp.modelloader.entity.Artifact;
import java.util.ArrayList;
import java.util.Collection;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
/**
* Utility class to sort the given Models according to their dependencies.
* Example: Given a list of Models [A, B, C] where B depends on A, and A depends
* on C, the sorted result will be [C, A, B]
*/
public class ModelSorter {
/**
* Wraps a Model object to form dependencies other Models using Edges.
*/
static class Node {
private final ModelArtifact model;
private final HashSet<Edge> inEdges;
private final HashSet<Edge> outEdges;
public Node(ModelArtifact model) {
this.model = model;
inEdges = new HashSet<Edge>();
outEdges = new HashSet<Edge>();
}
public Node addEdge(Node node) {
Edge edge = new Edge(this, node);
outEdges.add(edge);
node.inEdges.add(edge);
return this;
}
@Override
public String toString() {
return model.getModelInvariantId();
}
@Override
public boolean equals(Object other) {
ModelArtifact otherModel = ((Node) other).model;
return this.model.getModelInvariantId().equals(otherModel.getModelInvariantId());
}
@Override
public int hashCode() {
return this.model.getModelInvariantId().hashCode();
}
}
/**
* Represents a dependency between two Nodes.
*/
static class Edge {
public final Node from;
public final Node to;
public Edge(Node from, Node to) {
this.from = from;
this.to = to;
}
@Override
public boolean equals(Object obj) {
Edge edge = (Edge) obj;
return edge.from == from && edge.to == to;
}
}
/**
* Returns the list of models sorted by order of dependency.
*
* @param originalList
* the list that needs to be sorted
* @return a list of sorted models
*/
public List<Artifact> sort(List<Artifact> originalList) {
if (originalList.size() <= 1) {
return originalList;
}
Collection<Node> nodes = createNodes(originalList);
Collection<Node> sortedNodes = sortNodes(nodes);
List<Artifact> sortedModelsList = new ArrayList<Artifact>(sortedNodes.size());
for (Node node : sortedNodes) {
sortedModelsList.add(node.model);
}
return sortedModelsList;
}
/**
* Create nodes from the list of models and their dependencies.
*
* @param models
* what the nodes creation is based upon
* @return Collection of Node objects
*/
private Collection<Node> createNodes(Collection<Artifact> models) {
// load list of models into a map, so we can later replace referenceIds with
// real Models
HashMap<String, ModelArtifact> versionIdToModelMap = new HashMap<String, ModelArtifact>();
for (Artifact art : models) {
ModelArtifact ma = (ModelArtifact) art;
versionIdToModelMap.put(ma.getModelModelVerCombinedKey(), ma);
}
HashMap<String, Node> nodes = new HashMap<String, Node>();
// create a node for each model and its referenced models
for (Artifact art : models) {
ModelArtifact model = (ModelArtifact) art;
// node might have been created by another model referencing it
Node node = nodes.get(model.getModelModelVerCombinedKey());
if (null == node) {
node = new Node(model);
nodes.put(model.getModelModelVerCombinedKey(), node);
}
for (String referencedModelId : model.getDependentModelIds()) {
// node might have been created by another model referencing it
Node referencedNode = nodes.get(referencedModelId);
if (null == referencedNode) {
// create node
ModelArtifact referencedModel = versionIdToModelMap.get(referencedModelId);
if (referencedModel == null) {
Log.debug("ignoring " + referencedModelId);
continue; // referenced model not supplied, no need to sort it
}
referencedNode = new Node(referencedModel);
nodes.put(referencedModelId, referencedNode);
}
referencedNode.addEdge(node);
}
}
return nodes.values();
}
/**
* Sorts the given Nodes by order of dependency.
*
* @param originalList
* the collection of nodes to be sorted
* @return a sorted collection of the given nodes
*/
private Collection<Node> sortNodes(Collection<Node> unsortedNodes) {
// L <- Empty list that will contain the sorted elements
ArrayList<Node> nodeList = new ArrayList<Node>();
// S <- Set of all nodes with no incoming edges
HashSet<Node> nodeSet = new HashSet<Node>();
for (Node unsortedNode : unsortedNodes) {
if (unsortedNode.inEdges.size() == 0) {
nodeSet.add(unsortedNode);
}
}
// while S is non-empty do
while (!nodeSet.isEmpty()) {
// remove a node n from S
Node node = nodeSet.iterator().next();
nodeSet.remove(node);
// insert n into L
nodeList.add(node);
// for each node m with an edge e from n to m do
for (Iterator<Edge> it = node.outEdges.iterator(); it.hasNext();) {
// remove edge e from the graph
Edge edge = it.next();
Node to = edge.to;
it.remove();// Remove edge from n
to.inEdges.remove(edge);// Remove edge from m
// if m has no other incoming edges then insert m into S
if (to.inEdges.isEmpty()) {
nodeSet.add(to);
}
}
}
// Check to see if all edges are removed
boolean cycle = false;
for (Node node : unsortedNodes) {
if (!node.inEdges.isEmpty()) {
cycle = true;
break;
}
}
if (cycle) {
throw new RuntimeException(
"Circular dependency present between models, topological sort not possible");
}
return nodeList;
}
}
|