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

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