yang/yang-parser-impl/src/main/java/org/opendaylight/yangtools/yang/parser/util/GroupingSort.java

   1 /*
   2  * Copyright (c) 2013 Cisco Systems, Inc. and others.  All rights reserved.
   3  *
   4  * This program and the accompanying materials are made available under the
   5  * terms of the Eclipse Public License v1.0 which accompanies this distribution,
   6  * and is available at http://www.eclipse.org/legal/epl-v10.html
   7  */
   8 package org.opendaylight.yangtools.yang.parser.util;
   9
  10 import java.util.*;
  11
  12 import org.opendaylight.yangtools.yang.model.api.SchemaPath;
  13 import org.opendaylight.yangtools.yang.parser.builder.api.*;
  14 import org.opendaylight.yangtools.yang.parser.builder.impl.ChoiceBuilder;
  15 import org.opendaylight.yangtools.yang.parser.builder.impl.ChoiceCaseBuilder;
  16 import org.opendaylight.yangtools.yang.parser.util.TopologicalSort.Node;
  17
  18 import com.google.common.collect.Maps;
  19 import com.google.common.collect.Sets;
  20
  21 public class GroupingSort {
  22
  23     /**
  24      * Sorts set <code>groupingDefinitions</code> according to the mutual
  25      * dependencies.<br />
  26      *
  27      * Elements of <code>groupingDefinitions</code> are firstly transformed to
  28      * {@link org.opendaylight.yangtools.yang.parser.util.TopologicalSort.Node
  29      * Node} interfaces and then are sorted by
  30      * {@link org.opendaylight.yangtools.yang.parser.util.TopologicalSort#sort(Set)
  31      * sort()} method of <code>TopologicalSort</code>.<br />
  32      * <br />
  33      *
  34      *
  35      * <i>Definition of dependency relation:<br />
  36      * The first <code>GroupingDefinition</code> object (in this context)
  37      * depends on second <code>GroupingDefinition</code> object if the first one
  38      * contains in its set of <code>UsesNode</code> (obtained through
  39      * {@link org.opendaylight.yangtools.yang.model.api.DataNodeContainer#getUses()
  40      * getUses} method) reference to the second one.</i>
  41      *
  42      * @param groupingDefinitions
  43      *            set of grouping definition which should be sorted according to
  44      *            mutual dependencies
  45      * @return list of grouping definitiond which are sorted by mutual
  46      *         dependencies
  47      * @throws IllegalArgumentException
  48      *             if <code>groupingDefinitions</code>
  49      *
  50      */
  51     public static List<GroupingBuilder> sort(final Collection<GroupingBuilder> groupingDefinitions) {
  52         if (groupingDefinitions == null) {
  53             throw new IllegalArgumentException("Set of Type Definitions " + "cannot be NULL!");
  54         }
  55
  56         final List<GroupingBuilder> resultGroupingDefinitions = new ArrayList<GroupingBuilder>();
  57         final Set<Node> unsorted = groupingDefinitionsToNodes(groupingDefinitions);
  58         final List<Node> sortedNodes = TopologicalSort.sort(unsorted);
  59         for (Node node : sortedNodes) {
  60             NodeWrappedType nodeWrappedType = (NodeWrappedType) node;
  61             resultGroupingDefinitions.add((GroupingBuilder) (nodeWrappedType.getWrappedType()));
  62         }
  63         return resultGroupingDefinitions;
  64
  65     }
  66
  67     /**
  68      * Wraps every grouping definition to node type and adds to every node
  69      * information about dependencies.
  70      *
  71      * The map with mapping from schema path (represents grouping definition) to
  72      * node is created. For every created node (next <i>nodeFrom</i>) is for its
  73      * wrapped grouping definition passed the set of its <i>uses nodes</i>
  74      * through. For every uses node is found its wrapping node (next as
  75      * <i>nodeTo</i>). This dependency relationship between nodeFrom and all
  76      * found nodesTo is modeled with creating of one edge from nodeFrom to
  77      * nodeTo.
  78      *
  79      *
  80      * @param groupingDefinitions
  81      *            set of goruping definition which will be wrapped to nodes
  82      *
  83      * @return set of nodes where every one contains wrapped grouping definition
  84      */
  85     private static Set<Node> groupingDefinitionsToNodes(final Collection<GroupingBuilder> groupingDefinitions) {
  86         final Map<SchemaPath, Node> nodeMap = Maps.newHashMap();
  87         final Set<Node> resultNodes = Sets.newHashSet();
  88
  89         for (final GroupingBuilder groupingDefinition : groupingDefinitions) {
  90             final Node node = new NodeWrappedType(groupingDefinition);
  91             nodeMap.put(groupingDefinition.getPath(), node);
  92             resultNodes.add(node);
  93         }
  94
  95         for (final Node node : resultNodes) {
  96             final NodeWrappedType nodeWrappedType = (NodeWrappedType) node;
  97             final GroupingBuilder groupingDefinition = (GroupingBuilder) nodeWrappedType.getWrappedType();
  98
  99             Set<UsesNodeBuilder> usesNodes = getAllUsesNodes(groupingDefinition);
 100             for (UsesNodeBuilder usesNode : usesNodes) {
 101                 SchemaPath schemaPath = usesNode.getGroupingBuilder().getPath();
 102                 Node nodeTo = nodeMap.get(schemaPath);
 103                 if (nodeTo == null) {
 104                     throw new IllegalArgumentException("target grouping not found for uses " + usesNode);
 105                 }
 106                 nodeWrappedType.addEdge(nodeTo);
 107             }
 108         }
 109
 110         return resultNodes;
 111     }
 112
 113     /**
 114      * Returns the set of the uses nodes which are get from uses in
 115      * <code>container</code>, from uses in groupings inside
 116      * <code>container</code> and from uses inside child nodes of the
 117      * <code>container</code>.
 118      *
 119      * @param container
 120      *            data node container which can contain some uses of grouping
 121      * @return set of uses nodes which were find in <code>container</code>.
 122      */
 123     public static Set<UsesNodeBuilder> getAllUsesNodes(DataNodeContainerBuilder container) {
 124         Set<UsesNodeBuilder> ret = new HashSet<>();
 125         Set<UsesNodeBuilder> usesNodes = container.getUsesNodeBuilders();
 126         ret.addAll(usesNodes);
 127
 128         for (UsesNodeBuilder usesNode : usesNodes) {
 129             for (AugmentationSchemaBuilder augment : usesNode.getAugmentations()) {
 130                 ret.addAll(getAllUsesNodes(augment));
 131             }
 132         }
 133         Set<GroupingBuilder> groupings = container.getGroupingBuilders();
 134         for (GroupingBuilder groupingDefinition : groupings) {
 135             ret.addAll(getAllUsesNodes(groupingDefinition));
 136         }
 137         Set<DataSchemaNodeBuilder> childNodes = container.getChildNodeBuilders();
 138         for (DataSchemaNodeBuilder childNode : childNodes) {
 139             if (childNode instanceof DataNodeContainerBuilder) {
 140                 ret.addAll(getAllUsesNodes((DataNodeContainerBuilder) childNode));
 141             } else if (childNode instanceof ChoiceBuilder) {
 142                 Set<ChoiceCaseBuilder> cases = ((ChoiceBuilder) childNode).getCases();
 143                 for (ChoiceCaseBuilder choiceCaseNode : cases) {
 144                     ret.addAll(getAllUsesNodes(choiceCaseNode));
 145                 }
 146             }
 147         }
 148         return ret;
 149     }
 150
 151 }