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