![[Jenkins]](/ecp/static/e8bbdb94/images/svgs/logo.svg){kind=logo}
Package: PackageDependencyIterator
PackageDependencyIterator
| name | instruction | branch | complexity | line | method | ||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| PackageDependencyIterator(Collection, Collection) |
|
|
|
|
|
||||||||||||||||||||
| findNext() |
|
|
|
|
|
||||||||||||||||||||
| findRootCircle(Set) |
|
|
|
|
|
||||||||||||||||||||
| getCircleSet() |
|
|
|
|
|
||||||||||||||||||||
| hasNext() |
|
|
|
|
|
||||||||||||||||||||
| hasPathToOtherNode(PackageDependencyGraph.PackageTreeNode, PackageDependencyGraph.PackageTreeNode, Set) |
|
|
|
|
|
||||||||||||||||||||
| next() |
|
|
|
|
|
||||||||||||||||||||
| remove() |
|
|
|
|
|
||||||||||||||||||||
Coverage
1: /*******************************************************************************
2: * Copyright (c) 2011-2015 EclipseSource Muenchen GmbH and others.
3: *
4: * All rights reserved. This program and the accompanying materials
5: * are made available under the terms of the Eclipse Public License 2.0
6: * which accompanies this distribution, and is available at
7: * https://www.eclipse.org/legal/epl-2.0/
8: *
9: * SPDX-License-Identifier: EPL-2.0
10: *
11: * Contributors:
12: * jfaltermeier - initial API and implementation
13: ******************************************************************************/
14: package org.eclipse.emf.ecp.view.edapt;
15:
16: import java.util.Collection;
17: import java.util.Iterator;
18: import java.util.LinkedHashMap;
19: import java.util.LinkedHashSet;
20: import java.util.Map;
21: import java.util.Set;
22:
23: import org.eclipse.emf.ecp.view.edapt.PackageDependencyGraph.PackageTreeNode;
24:
25: /**
26: * Iterator for nsURIs based on the dependencies beginning from the roots.
27: *
28: * @author jfaltermeier
29: *
30: */
31: public class PackageDependencyIterator implements Iterator<Set<String>> {
32:
33: /**
34: * Next candidates contains the roots and the children of the last returned set of nodes. They act as an easy lookup
35: * for the next node to be returned by the iterator.
36: */
37: private final Set<PackageTreeNode> nextCandidates;
38:
39: private final Set<PackageTreeNode> visitedNodes;
40: private final Set<PackageTreeNode> unvisitedNodes;
41: private Set<PackageTreeNode> next;
42:
43: /**
44: * Constructs a new {@link PackageDependencyIterator}.
45: *
46: * @param roots the root nodes
47: * @param allNodes all nodes
48: */
49: public PackageDependencyIterator(Collection<PackageTreeNode> roots, Collection<PackageTreeNode> allNodes) {
50: visitedNodes = new LinkedHashSet<PackageTreeNode>();
51: unvisitedNodes = new LinkedHashSet<PackageTreeNode>(allNodes);
52: nextCandidates = new LinkedHashSet<PackageTreeNode>(roots);
53: next = findNext();
54: }
55:
56: @Override
57: public boolean hasNext() {
58:• return !next.isEmpty();
59: }
60:
61: @Override
62: public Set<String> next() {
63: visitedNodes.addAll(next);
64: unvisitedNodes.removeAll(next);
65: final Set<String> nsuri = new LinkedHashSet<String>();
66:• for (final PackageTreeNode nextNode : next) {
67: nsuri.add(nextNode.getNSURI());
68: }
69: next = findNext();
70: return nsuri;
71: }
72:
73: private Set<PackageTreeNode> findNext() {
74: /* we are looking for a node with no parents */
75: final Set<PackageTreeNode> result = new LinkedHashSet<PackageTreeNode>();
76:• for (final PackageTreeNode node : nextCandidates) {
77: boolean hasUnvisitedParent = false;
78:• for (final PackageTreeNode parent : node.getParents()) {
79:• if (!visitedNodes.contains(parent)) {
80: hasUnvisitedParent = true;
81: break;
82: }
83: }
84:• if (!hasUnvisitedParent) {
85:• for (final PackageTreeNode child : node.getChildren()) {
86:• if (!visitedNodes.contains(child)) {
87: nextCandidates.add(child);
88: }
89: }
90: result.add(node);
91: break;
92: }
93: }
94:• if (result.isEmpty() && !unvisitedNodes.isEmpty()) {
95: // circle detected
96: result.addAll(getCircleSet());
97: }
98:• for (final PackageTreeNode packageTreeNode : result) {
99: nextCandidates.remove(packageTreeNode);
100: }
101: return result;
102: }
103:
104: private Collection<? extends PackageTreeNode> getCircleSet() {
105: /* 1. circle detection: put all nodes which contain to the same circle in a set */
106: final Map<PackageTreeNode, Set<PackageTreeNode>> nodeToCircleMap = new LinkedHashMap<PackageTreeNode, Set<PackageTreeNode>>();
107: final Set<Set<PackageTreeNode>> allCircles = new LinkedHashSet<Set<PackageTreeNode>>();
108:• for (final PackageTreeNode nodeToAllocate : unvisitedNodes) {
109: // get existing circle set from map or create new set
110:• final Set<PackageTreeNode> circle = nodeToCircleMap.containsKey(nodeToAllocate)
111: ? nodeToCircleMap.get(nodeToAllocate)
112: : new LinkedHashSet<PackageTreeNode>();
113:
114: // if new set, fill map
115:• if (!nodeToCircleMap.containsKey(nodeToAllocate)) {
116: circle.add(nodeToAllocate);
117: nodeToCircleMap.put(nodeToAllocate, circle);
118: allCircles.add(circle);
119: }
120:
121: // nodes contain to same set if outgoing edge leads back to self
122: final Set<PackageTreeNode> outgoingEdges = nodeToAllocate.getChildren();
123:• for (final PackageTreeNode outgoingEdge : outgoingEdges) {
124: final boolean hasPathToOtherNode = hasPathToOtherNode(outgoingEdge, nodeToAllocate,
125: new LinkedHashSet<PackageTreeNode>());
126:• if (hasPathToOtherNode) {
127: circle.add(outgoingEdge);
128: nodeToCircleMap.put(outgoingEdge, circle);
129: }
130: }
131: }
132:
133: /* 2. find root circle */
134: return findRootCircle(allCircles);
135: }
136:
137: private Collection<? extends PackageTreeNode> findRootCircle(final Set<Set<PackageTreeNode>> allCircles) {
138:• for (final Set<PackageTreeNode> circle : allCircles) {
139: // root circle is the set where all unvisited parents are from the same set
140: boolean isRoot = true;
141:• for (final PackageTreeNode node : circle) {
142:• for (final PackageTreeNode mustBeInCircle : node.getParents()) {
143:• if (visitedNodes.contains(mustBeInCircle)) {
144: // the parent was already returned by the iterator, so we can skip it
145: continue;
146: }
147:• if (!circle.contains(mustBeInCircle)) {
148: isRoot = false;
149: break;
150: }
151: }
152:• if (!isRoot) {
153: break;
154: }
155: }
156:• if (isRoot) {
157: return circle;
158: }
159: }
160:
161: // this state is unexpected. if this is reached we could have returned a valid set of nsuri beforehand
162: // (either no circle at all, or the circle detection went wrong)
163: throw new IllegalStateException("No root circle found"); //$NON-NLS-1$
164: }
165:
166: private boolean hasPathToOtherNode(PackageTreeNode start, PackageTreeNode target,
167: Set<PackageTreeNode> visitedNodes) {
168: visitedNodes.add(start);
169: final Set<PackageTreeNode> outgoingNodes = start.getChildren();
170:• if (outgoingNodes.contains(target)) {
171: return true;
172: }
173: boolean result = false;
174:• for (final PackageTreeNode outgoingNode : outgoingNodes) {
175:• if (visitedNodes.contains(outgoingNode)) {
176: // we already visited/are visiting all children of this node -> skip
177: continue;
178: }
179: result |= hasPathToOtherNode(outgoingNode, target, visitedNodes);
180: }
181: return result;
182: }
183:
184: /**
185: * {@inheritDoc}
186: *
187: * @see java.util.Iterator#remove()
188: */
189: @Override
190: public void remove() {
191: throw new UnsupportedOperationException();
192: }
193:
194: }