001/*-------------------------------------------------------------------------+
002|                                                                          |
003| Copyright 2005-2011 the ConQAT Project                                   |
004|                                                                          |
005| Licensed under the Apache License, Version 2.0 (the "License");          |
006| you may not use this file except in compliance with the License.         |
007| You may obtain a copy of the License at                                  |
008|                                                                          |
009|    http://www.apache.org/licenses/LICENSE-2.0                            |
010|                                                                          |
011| Unless required by applicable law or agreed to in writing, software      |
012| distributed under the License is distributed on an "AS IS" BASIS,        |
013| WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
014| See the License for the specific language governing permissions and      |
015| limitations under the License.                                           |
016+-------------------------------------------------------------------------*/
017package eu.cqse.check.framework.shallowparser.util;
018
019import java.util.ArrayList;
020import java.util.LinkedHashSet;
021import java.util.List;
022import java.util.Stack;
023import java.util.function.Predicate;
024import java.util.stream.Collectors;
025
026import org.conqat.lib.commons.collections.CollectionUtils;
027
028import eu.cqse.check.framework.shallowparser.framework.EShallowEntityType;
029import eu.cqse.check.framework.shallowparser.framework.ShallowEntity;
030import eu.cqse.check.framework.shallowparser.framework.ShallowEntityTraversalUtils.ShallowEntityVisitorBase;
031
032/**
033 * Traverses a shallow entity tree and collects groups of entities of the same
034 * type that are directly connected together. An entity is directly connected to
035 * another entity if the other entity is either the parent or a child of the
036 * entity and has the same type.
037 */
038public class ConnectedEntityCollector extends ShallowEntityVisitorBase {
039
040        /** The type of entities that is to be collected. */
041        private final EShallowEntityType entityType;
042
043        /**
044         * An additional predicate to filter entities within one connection group.
045         */
046        private final Predicate<ShallowEntity> entitySelector;
047
048        /** A list of connected entity groups. */
049        private final List<LinkedHashSet<ShallowEntity>> connectionGroups = new ArrayList<>();
050
051        /**
052         * A stack that manages connection groups while executing the depth first
053         * search.
054         */
055        private final Stack<LinkedHashSet<ShallowEntity>> groupStack = new Stack<>();
056
057        /** Constructor. */
058        public ConnectedEntityCollector(EShallowEntityType entityType) {
059                this(entityType, entity -> true);
060        }
061
062        /** Constructor. */
063        public ConnectedEntityCollector(EShallowEntityType entityType, Predicate<ShallowEntity> entitySelector) {
064                this.entityType = entityType;
065                this.entitySelector = entitySelector;
066        }
067
068        /** {@inheritDoc} */
069        @Override
070        public boolean visit(ShallowEntity entity) {
071                if (entity.getType() == entityType && entitySelector.test(entity)) {
072                        groupStack.peek().add(entity);
073                } else {
074                        pushGroup();
075                }
076                return true;
077        }
078
079        /** {@inheritDoc} */
080        @Override
081        public void endVisit(ShallowEntity entity) {
082                if (entity.getType() != entityType || !entitySelector.test(entity)) {
083                        popGroup();
084                }
085        }
086
087        /** Pushes a new connection group on the stack. */
088        private void pushGroup() {
089                groupStack.push(new LinkedHashSet<>());
090        }
091
092        /**
093         * Pops a connection group from the stack. If is is not empty it will be added
094         * to the connected entity groups.
095         */
096        private void popGroup() {
097                LinkedHashSet<ShallowEntity> group = groupStack.pop();
098                if (!group.isEmpty()) {
099                        connectionGroups.add(group);
100                }
101        }
102
103        /**
104         * Returns a list of connected entity groups. Each group is sorted in the order
105         * the entities where traversed while doing a depth first search.
106         */
107        public List<List<ShallowEntity>> getConnectedGroups(List<ShallowEntity> entities) {
108                // push the root group
109                pushGroup();
110                ShallowEntity.traverse(entities, this);
111                // pop the root group
112                popGroup();
113                return CollectionUtils.map(connectionGroups, set -> set.stream().collect(Collectors.toList()));
114        }
115
116}