appc-dg/appc-dg-shared/appc-dg-dependency-model/src/main/java/org/openecomp/appc/dg/flowbuilder/impl/ForwardFlowStrategy.java

   1 /*-
   2  * ============LICENSE_START=======================================================
   3  * ONAP : APPC
   4  * ================================================================================
   5  * Copyright (C) 2017 AT&T Intellectual Property. All rights reserved.
   6  * ================================================================================
   7  * Copyright (C) 2017 Amdocs
   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  *
  21  * ECOMP is a trademark and service mark of AT&T Intellectual Property.
  22  * ============LICENSE_END=========================================================
  23  */
  24
  25 package org.openecomp.appc.dg.flowbuilder.impl;
  26
  27 import java.util.*;
  28
  29 import org.openecomp.appc.dg.flowbuilder.exception.InvalidDependencyModel;
  30 import org.openecomp.appc.domainmodel.Vnfc;
  31
  32
  33 public class ForwardFlowStrategy extends AbstractFlowStrategy {
  34     @Override
  35     protected List<List<Vnfc>> orderDependencies() {
  36         ArrayList<List<Vnfc>> arrayList = new ArrayList<>();
  37
  38         Queue<Vnfc> queue1 = new LinkedList();
  39         Set<Vnfc> queue2 = new LinkedHashSet<>();
  40
  41         Set<Vnfc> uniqueElementSet = new HashSet<>();
  42         Set<Vnfc> duplicateElementSet = new HashSet<>();
  43
  44         // identifying independent nodes in queue1
  45         for(int rowIndex=0;rowIndex<graph.getSize();rowIndex++){
  46             Integer sum = 0;
  47             for(int colIndex=0;colIndex<graph.getSize();colIndex++){
  48                 sum+= graph.getDependencyMatrix()[rowIndex][colIndex];
  49             }
  50             if(sum==0){
  51                 Vnfc vnfc = graph.getVertexList().get(rowIndex);
  52                 queue1.add(vnfc);
  53             }
  54         }
  55         if(queue1.isEmpty()){
  56             throw new InvalidDependencyModel("There seems to be no Root/Independent node for Vnfc dependencies");
  57         }
  58         arrayList.add((List<Vnfc>)queue1);
  59         queue1 = new LinkedList<>(queue1);
  60
  61         boolean flag = true;
  62
  63         while(flag){
  64             // iterating over queue1 and for each node in it finding all dependent nodes and putting them on queue2
  65             while(!queue1.isEmpty()){
  66                 Vnfc listItem = queue1.remove();
  67                 Integer colIndex = graph.getIndex(listItem);
  68                 for(Integer index =0;index<graph.getSize();index++){
  69                     Integer value = graph.getDependencyMatrix()[index][colIndex];
  70                     if(value ==1){
  71                         Vnfc vnfc = graph.getVertexList().get(index);
  72                         queue2.add(vnfc);
  73                     }
  74                 }
  75             }
  76             for(Vnfc vnfc:queue2){
  77                 if(!uniqueElementSet.add(vnfc)){
  78                     duplicateElementSet.add(vnfc);
  79                 }
  80             }
  81             if(queue2.isEmpty()){
  82                 flag= false; // empty queue2 indicates that all leaf nodes have been identified, i.e. stop the iteration
  83             }
  84             else{
  85                 arrayList.add(new ArrayList<Vnfc>(queue2));
  86                 if(arrayList.size()>graph.getSize()){
  87                     // dependency list cannot be larger than total number of nodes
  88                     // if it happens indicates cycle in the dependency
  89                     throw new InvalidDependencyModel("Cycle detected in the VNFC dependencies");
  90                 }
  91                 queue1.addAll(queue2);
  92                 queue2 = new LinkedHashSet<>();
  93             }
  94         }
  95         // If any node depends on multiple nodes present in different execution sequence,
  96         // its execution should happen on the higher order, removing its presence on lower execution sequence
  97         if(!duplicateElementSet.isEmpty()){
  98             for(Vnfc vnfc:duplicateElementSet){
  99                 boolean firstOccurrence= true;
 100                 for(int i=arrayList.size()-1;i>=0;i--){
 101                     List<Vnfc> list = arrayList.get(i);
 102                     if(list.contains(vnfc)){
 103                         if(firstOccurrence){
 104                             firstOccurrence =false;
 105                             continue;
 106                         }
 107                         else{
 108                             list.remove(vnfc);
 109                         }
 110                     }
 111
 112                 }
 113             }
 114         }
 115         return  arrayList;
 116     }
 117 }