src/main/java/org/onap/aai/modelloader/entity/model/ModelSorter.java

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