src/main/java/org/openecomp/modelloader/entity/model/ModelSorter.java

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