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 import jline.internal.Log;
  33 import org.onap.aai.modelloader.entity.Artifact;
  34
  35 /**
  36  * Utility class to sort the given Models according to their dependencies.<br>
  37  * Example: Given a list of Models [A, B, C] <br>
  38  * where B depends on A, and A depends on C, the sorted result will be [C, A, B]
  39  */
  40 public class ModelSorter {
  41
  42     /**
  43      * Wraps a Model object to form dependencies other Models using Edges.
  44      */
  45     static class Node {
  46
  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<>();
  54             outEdges = new HashSet<>();
  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             if (other == null || this.getClass() != other.getClass()) {
  72                 return false;
  73             }
  74             AbstractModelArtifact otherModel = ((Node) other).model;
  75             return this.model.getUniqueIdentifier().equals(otherModel.getUniqueIdentifier());
  76         }
  77
  78         @Override
  79         public int hashCode() {
  80             return this.model.getUniqueIdentifier().hashCode();
  81         }
  82     }
  83
  84     /**
  85      * Represents a dependency between two Nodes.
  86      */
  87     static class Edge {
  88
  89         public final Node from;
  90         public final Node to;
  91
  92         public Edge(Node from, Node to) {
  93             this.from = from;
  94             this.to = to;
  95         }
  96
  97         @Override
  98         public boolean equals(Object obj) {
  99             if (obj == null || this.getClass() != obj.getClass()) {
 100                 return false;
 101             }
 102             Edge edge = (Edge) obj;
 103             return edge.from == from && edge.to == to;
 104         }
 105
 106         @Override
 107         public int hashCode() {
 108             return Objects.hash(this.from, this.to);
 109         }
 110     }
 111
 112     /**
 113      * Returns the list of models sorted by order of dependency.
 114      *
 115      * @param originalList the list that needs to be sorted
 116      * @return a list of sorted models
 117      * @throws BabelArtifactParsingException
 118      */
 119     public List<Artifact> sort(List<Artifact> originalList) throws BabelArtifactParsingException {
 120         if (originalList == null || originalList.size() <= 1) {
 121             return originalList;
 122         }
 123
 124         Collection<Node> sortedNodes = sortNodes(createNodes(originalList));
 125
 126         List<Artifact> sortedModelsList = new ArrayList<>(sortedNodes.size());
 127         for (Node node : sortedNodes) {
 128             sortedModelsList.add(node.model);
 129         }
 130
 131         return sortedModelsList;
 132     }
 133
 134     /**
 135      * Create nodes from the list of models and their dependencies.
 136      *
 137      * @param models what the nodes creation is based upon
 138      * @return Collection of Node objects
 139      */
 140     private Collection<Node> createNodes(Collection<Artifact> models) {
 141
 142         // load list of models into a map, so we can later replace referenceIds with real Models
 143         Map<String, AbstractModelArtifact> versionIdToModelMap = new HashMap<>();
 144         for (Artifact art : models) {
 145             AbstractModelArtifact ma = (AbstractModelArtifact) art;
 146             versionIdToModelMap.put(ma.getUniqueIdentifier(), ma);
 147         }
 148
 149         Map<String, Node> nodes = new HashMap<>();
 150         // create a node for each model and its referenced models
 151         for (Artifact art : models) {
 152
 153             AbstractModelArtifact model = (AbstractModelArtifact) art;
 154
 155             // node might have been created by another model referencing it
 156             Node node = nodes.get(model.getUniqueIdentifier());
 157
 158             if (null == node) {
 159                 node = new Node(model);
 160                 nodes.put(model.getUniqueIdentifier(), node);
 161             }
 162
 163             for (String referencedModelId : model.getDependentModelIds()) {
 164                 // node might have been created by another model referencing it
 165                 Node referencedNode = nodes.get(referencedModelId);
 166
 167                 if (null == referencedNode) {
 168                     // create node
 169                     AbstractModelArtifact referencedModel = versionIdToModelMap.get(referencedModelId);
 170                     if (referencedModel == null) {
 171                         Log.debug("ignoring " + referencedModelId);
 172                         continue; // referenced model not supplied, no need to sort it
 173                     }
 174                     referencedNode = new Node(referencedModel);
 175                     nodes.put(referencedModelId, referencedNode);
 176                 }
 177                 referencedNode.addEdge(node);
 178             }
 179         }
 180
 181         return nodes.values();
 182     }
 183
 184     /**
 185      * Sorts the given Nodes by order of dependency.
 186      *
 187      * @param unsortedNodes the collection of nodes to be sorted
 188      * @return a sorted collection of the given nodes
 189      * @throws BabelArtifactParsingException
 190      */
 191     private Collection<Node> sortNodes(Collection<Node> unsortedNodes) throws BabelArtifactParsingException {
 192         // L <- Empty list that will contain the sorted elements
 193         List<Node> nodeList = new ArrayList<>();
 194
 195         // S <- Set of all nodes with no incoming edges
 196         Set<Node> nodeSet = new HashSet<>();
 197         for (Node unsortedNode : unsortedNodes) {
 198             if (unsortedNode.inEdges.isEmpty()) {
 199                 nodeSet.add(unsortedNode);
 200             }
 201         }
 202
 203         // while S is non-empty do
 204         while (!nodeSet.isEmpty()) {
 205             // remove a node n from S
 206             Node node = nodeSet.iterator().next();
 207             nodeSet.remove(node);
 208
 209             // insert n into L
 210             nodeList.add(node);
 211
 212             // for each node m with an edge e from n to m do
 213             for (Iterator<Edge> it = node.outEdges.iterator(); it.hasNext();) {
 214                 // remove edge e from the graph
 215                 Edge edge = it.next();
 216                 Node to = edge.to;
 217                 it.remove();// Remove edge from n
 218                 to.inEdges.remove(edge);// Remove edge from m
 219
 220                 // if m has no other incoming edges then insert m into S
 221                 if (to.inEdges.isEmpty()) {
 222                     nodeSet.add(to);
 223                 }
 224             }
 225         }
 226         // Check to see if all edges are removed
 227         boolean cycle = false;
 228         for (Node node : unsortedNodes) {
 229             if (!node.inEdges.isEmpty()) {
 230                 cycle = true;
 231                 break;
 232             }
 233         }
 234         if (cycle) {
 235             throw new BabelArtifactParsingException(
 236                     "Circular dependency present between models, topological sort not possible");
 237         }
 238
 239         return nodeList;
 240     }
 241
 242 }