| /******************************************************************************* |
| * Copyright (c) 2013, 2017 Obeo and others. |
| * All rights reserved. This program and the accompanying materials |
| * are made available under the terms of the Eclipse Public License v1.0 |
| * which accompanies this distribution, and is available at |
| * http://www.eclipse.org/legal/epl-v10.html |
| * |
| * Contributors: |
| * Obeo - initial API and implementation |
| * Alexandra Buzila - bug 478620 |
| *******************************************************************************/ |
| package org.eclipse.emf.compare.internal.utils; |
| |
| import static com.google.common.base.Preconditions.checkNotNull; |
| import static com.google.common.collect.Iterators.concat; |
| import static java.util.Collections.emptyIterator; |
| |
| import com.google.common.base.Preconditions; |
| import com.google.common.base.Predicate; |
| import com.google.common.collect.ImmutableSet; |
| import com.google.common.collect.Iterables; |
| import com.google.common.collect.Iterators; |
| import com.google.common.collect.Sets; |
| |
| import java.util.Collection; |
| import java.util.Collections; |
| import java.util.ConcurrentModificationException; |
| import java.util.HashSet; |
| import java.util.Iterator; |
| import java.util.LinkedHashMap; |
| import java.util.LinkedHashSet; |
| import java.util.LinkedList; |
| import java.util.ListIterator; |
| import java.util.Map; |
| import java.util.NoSuchElementException; |
| import java.util.Set; |
| import java.util.concurrent.locks.ReentrantLock; |
| |
| import org.eclipse.emf.common.util.AbstractTreeIterator; |
| import org.eclipse.emf.compare.graph.IGraph; |
| import org.eclipse.emf.compare.graph.PruningIterator; |
| |
| /** |
| * This structure will be used to maintain a undirected graph of elements. |
| * <p> |
| * This boils down to maintaining a list of children and parents of each node, updating them in sync with each |
| * other. |
| * </p> |
| * <p> |
| * Take note that the elements of this graph are not necessarily all connected together. This can be used to |
| * represent a set of trees, a set of undirected graphs, a set of roots with no children... |
| * </p> |
| * <p> |
| * This class is not intended to be sub-classed. |
| * </p> |
| * |
| * @param <E> |
| * Kind of elements used as this graph's nodes. |
| * @author <a href="mailto:laurent.goubet@obeo.fr">Laurent Goubet</a> |
| */ |
| public class Graph<E> implements IGraph<E> { |
| /** Keeps track of this graph's individual nodes. */ |
| private final Map<E, Node<E>> nodes; |
| |
| /** |
| * keeps track of this graph's roots. This will reference all nodes with no parents themselves, whether |
| * they are part of the same subgraph or totally unrelated to each other. |
| */ |
| private final Set<Node<E>> roots; |
| |
| /** |
| * All operations affecting the graph will be synchronized so that changes to {@link #nodes} and |
| * {@link #roots} are consistent with each other. |
| */ |
| private final ReentrantLock lock; |
| |
| /** |
| * This will be incremented each time this graph is structurally modified by an operation, ensuring |
| * fail-fast iterations from our returned iterators. |
| */ |
| private transient volatile int modcount; |
| |
| /** Constructs an empty graph. */ |
| public Graph() { |
| this.nodes = new LinkedHashMap<E, Node<E>>(); |
| this.roots = new LinkedHashSet<Node<E>>(); |
| this.lock = new ReentrantLock(); |
| } |
| |
| /** |
| * Checks whether this graph already contains the given element. |
| * |
| * @param element |
| * Element we need to check. |
| * @return <code>true</code> if this graph already contains the given elment, <code>false</code> |
| * otherwise. |
| */ |
| public boolean contains(E element) { |
| lock.lock(); |
| try { |
| return nodes.containsKey(element); |
| } finally { |
| lock.unlock(); |
| } |
| } |
| |
| /** Clears this graph and goes back to a pristine state. */ |
| public void clear() { |
| lock.lock(); |
| try { |
| nodes.clear(); |
| roots.clear(); |
| modcount++; |
| } finally { |
| lock.unlock(); |
| } |
| } |
| |
| /** |
| * Adds a new element to this graph, if it does not exists yet. Elements will initially have no connection |
| * to other elements, and can thus be considered "roots" of the graph. |
| * |
| * @param element |
| * The element to add as a new root to this graph. |
| * @return <code>true</code> if this element did not previously exist in the graph. |
| */ |
| public boolean add(E element) { |
| lock.lock(); |
| try { |
| Node<E> node = nodes.get(element); |
| if (node == null) { |
| node = new Node<E>(element); |
| nodes.put(element, node); |
| roots.add(node); |
| modcount++; |
| return true; |
| } |
| return false; |
| } finally { |
| lock.unlock(); |
| } |
| } |
| |
| /** |
| * Removes the given element's node from this graph. This will effectively break all connections to that |
| * node. |
| * |
| * @param element |
| * The element which is to be removed from this graph. |
| */ |
| public void remove(E element) { |
| lock.lock(); |
| try { |
| final Node<E> node = nodes.remove(element); |
| if (node != null) { |
| node.breakConnections(); |
| roots.remove(node); |
| modcount++; |
| } |
| } finally { |
| lock.unlock(); |
| } |
| } |
| |
| /** |
| * Removes the given elements' nodes from this graph. This will effectively break all connections to these |
| * nodes. |
| * |
| * @param elements |
| * The elements which are to be removed from this graph. |
| */ |
| public void removeAll(Collection<E> elements) { |
| lock.lock(); |
| try { |
| for (E e : elements) { |
| remove(e); |
| } |
| } finally { |
| lock.unlock(); |
| } |
| } |
| |
| /** |
| * Connects the given set of elements to a given parent. Note that nodes will be created for all new |
| * elements if they do not exist yet. |
| * |
| * @param element |
| * The element that is to be connected with new children. |
| * @param newChildren |
| * The set of elements to connect to the given parent. |
| */ |
| public void addChildren(E element, Set<E> newChildren) { |
| lock.lock(); |
| try { |
| Node<E> node = nodes.get(element); |
| if (node == null) { |
| node = new Node<E>(element); |
| nodes.put(element, node); |
| roots.add(node); |
| modcount++; |
| } |
| |
| for (E newChild : newChildren) { |
| Node<E> childNode = nodes.get(newChild); |
| if (childNode == null) { |
| childNode = new Node<E>(newChild); |
| nodes.put(newChild, childNode); |
| } else { |
| roots.remove(childNode); |
| } |
| modcount++; |
| node.connectChild(childNode); |
| } |
| } finally { |
| lock.unlock(); |
| } |
| } |
| |
| /** |
| * Checks if the given element is a parent of the given potential child, directly or not. |
| * |
| * @param parent |
| * Element that could be a parent of <code>potentialChild</code>. |
| * @param potentialChild |
| * The potential child of <code>parent</code>. |
| * @return <code>true</code> if <code>parent</code> is an ancestor of <code>potentialChild</code>. |
| */ |
| public boolean hasChild(E parent, E potentialChild) { |
| lock.lock(); |
| try { |
| final Node<E> node = nodes.get(potentialChild); |
| if (node != null) { |
| return Iterables.any(node.getAllParents(), is(parent)); |
| } |
| return false; |
| } finally { |
| lock.unlock(); |
| } |
| } |
| |
| /** |
| * This predicate will be used to check if a Node's element is the given one. |
| * |
| * @param element |
| * the element we expect a node for. |
| * @return The constructed predicate. |
| */ |
| private Predicate<? super Node<E>> is(final E element) { |
| return new Predicate<Node<E>>() { |
| public boolean apply(Node<E> input) { |
| return input != null && input.getElement().equals(element); |
| } |
| }; |
| } |
| |
| /** |
| * Returns the <u>direct</u> parents of the given <code>element</code>. |
| * <p> |
| * <b>Note</b> that the returned set is a view over a sub-graph of this graph, and that changes to it will |
| * not be reflected within the graph itself. |
| * </p> |
| * |
| * @param element |
| * The element which parents we seek. |
| * @return The set of <u>direct</u> parents for the given <code>element</code>. |
| */ |
| public Set<E> getDirectParents(E element) { |
| final Set<E> parents = new LinkedHashSet<E>(); |
| lock.lock(); |
| try { |
| final Node<E> node = nodes.get(element); |
| if (node != null) { |
| for (Node<E> parent : node.getParents()) { |
| parents.add(parent.getElement()); |
| } |
| } |
| } finally { |
| lock.unlock(); |
| } |
| return parents; |
| } |
| |
| /** |
| * Returns the tree starting from the given root element if it is contained in the graph. |
| * <p> |
| * Contrarily to {@link #getSubgraphContaining(Object)}, this will only iterate over the children (and |
| * recursively) of the given node, without ever "going up" to parents of these children. |
| * </p> |
| * <p> |
| * <b>Note</b> that the returned set is a view over a sub-graph of this graph, and that changes to it will |
| * not be reflected within the graph itself. |
| * </p> |
| * |
| * @param root |
| * The element we are to consider as the root of a tree. |
| * @return The tree starting from the given root element if it is contained in this graph, and empty set |
| * otherwise. |
| */ |
| public Set<E> getTreeFrom(E root) { |
| return getTreeFrom(root, Collections.<E> emptySet()); |
| } |
| |
| /** |
| * Returns the tree starting from the given root element and ending at the given boundaries.. |
| * <p> |
| * Contrarily to {@link #getSubgraphContaining(Object, Set)}, this will only iterate over the children |
| * (and recursively) of the given node, without ever "going up" to parents of these children. |
| * </p> |
| * <p> |
| * <b>Note</b> that the returned set is a view over a sub-graph of this graph, and that changes to it will |
| * not be reflected within the graph itself. |
| * </p> |
| * |
| * @param root |
| * The element we are to consider as the root of a tree. |
| * @param endPoints |
| * Boundaries of the tree. |
| * @return The tree starting from the given root element if it is contained in this graph, and empty set |
| * otherwise. |
| */ |
| public Set<E> getTreeFrom(E root, Set<E> endPoints) { |
| lock.lock(); |
| try { |
| final Node<E> node = nodes.get(root); |
| if (node != null) { |
| Set<E> boundaries = endPoints; |
| if (boundaries == null) { |
| boundaries = Collections.emptySet(); |
| } |
| return new SubgraphBuilder<E>(node, boundaries).buildTree(); |
| } |
| } finally { |
| lock.unlock(); |
| } |
| return Collections.emptySet(); |
| } |
| |
| /** |
| * Returns the set of all elements of the subgraph containing the given element. |
| * <p> |
| * <b>Note</b> that the returned set is a view over a sub-graph of this graph, and that changes to it will |
| * not be reflected within the graph itself. |
| * </p> |
| * |
| * @param element |
| * Element we need the subgraph of. |
| * @return The set of all elements of the subgraph containing the given element, an empty set if that |
| * element is not present in this graph. |
| */ |
| public Set<E> getSubgraphContaining(E element) { |
| return getSubgraphContaining(element, Collections.<E> emptySet()); |
| } |
| |
| /** |
| * Returns the set of all elements of the subgraph containing the given element and ending at the given |
| * boundaries. |
| * <p> |
| * <b>Note</b> that the returned set is a view over a sub-graph of this graph, and that changes to it will |
| * not be reflected within the graph itself. |
| * </p> |
| * |
| * @param element |
| * Element we need the subgraph of. |
| * @param endPoints |
| * Boundaries of the needed subgraph. |
| * @return An iterable over all elements of the subgraph containing the given element, an empty set if |
| * that element is not present in this graph. |
| */ |
| public Set<E> getSubgraphContaining(E element, Set<E> endPoints) { |
| lock.lock(); |
| try { |
| final Node<E> node = nodes.get(element); |
| if (node != null) { |
| Set<E> boundaries = endPoints; |
| if (boundaries == null) { |
| boundaries = Collections.emptySet(); |
| } |
| return new SubgraphBuilder<E>(node, boundaries).buildSubgraph(); |
| } |
| return Collections.emptySet(); |
| } finally { |
| lock.unlock(); |
| } |
| } |
| |
| /** |
| * Returns a breadth-first iterator over this whole graph. This will begin iteration on this graph's roots |
| * (whether they are linked together (directly or indirectly) or not), then carry on over each depth |
| * level. This will never visit the same element twice, nor will it ever visit an element which parents |
| * haven't all been iterated over yet. |
| * <p> |
| * The returned iterator does not support removal, and will fail or return undefined results if this graph |
| * is modified after the iterator's creation. |
| * </p> |
| * |
| * @return A breadth-first iterator over this whole graph. |
| */ |
| public PruningIterator<E> breadthFirstIterator() { |
| return new BreadthFirstIterator(); |
| } |
| |
| /** |
| * Returns a depth first iterator created with the given element as root. If the graph contains cycles, |
| * the same node won't be returned twice. |
| * <p> |
| * The root will be returned first, then the left-most child of that root, then the left-most child of |
| * that child if any, or the closest sibling to the right of the current element. For example, with the |
| * following tree: |
| * |
| * <pre> |
| * A |
| * / \ |
| * B C |
| * / / \ |
| * D E F |
| * </pre> |
| * |
| * The iteration order will be : A, B, D, C, E, F. |
| * </p> |
| * <p> |
| * The returned iterator does not support removal, and will fail or return undefined results if this graph |
| * is modified after the iterator's creation. |
| * </p> |
| * |
| * @param root |
| * The root of the tree over which we need to iterate. |
| * @return An iterator over the tree starting from the given root. |
| */ |
| public Iterator<E> depthFirstIterator(E root) { |
| return new ChildrenIterator(root); |
| } |
| |
| /** |
| * Get the parent data of the given element. |
| * <p> |
| * The parent data, is the URI of the parent resource's object in case of a containment relationship |
| * between the given element and its parent. |
| * <p> |
| * |
| * @param element |
| * Element we need the parent data of. |
| * @return A parent data of type <code>E</code> if this element has a parent data, <code>null</code> |
| * otherwise. |
| */ |
| public E getParentData(E element) { |
| lock.lock(); |
| try { |
| Node<E> node = nodes.get(element); |
| if (node != null) { |
| return node.getParentData(); |
| } |
| } finally { |
| lock.unlock(); |
| } |
| return null; |
| } |
| |
| /** |
| * Set the parent data for the given element. |
| * <p> |
| * The parent data, is the URI of the parent resource's object in case of a containment relationship |
| * between the given element and its parent. |
| * </p> |
| * If the given element has several parents, then the addition of a new parent data results in delete the |
| * parent data. If the given element has no parents, then the addition of a new parent data results in |
| * delete the parent data. |
| * |
| * @param element |
| * Element for which we need to set the parent data. |
| * @param parentData |
| * The parent data to set. |
| */ |
| public void addParentData(E element, E parentData) { |
| lock.lock(); |
| try { |
| Node<E> node = nodes.get(element); |
| if (node != null) { |
| E tmp = this.getParentData(element); |
| if (tmp == null) { |
| node.setParentData(parentData); |
| } else { |
| node.setParentData(null); |
| } |
| } |
| } finally { |
| lock.unlock(); |
| } |
| } |
| |
| /** |
| * This will be used to represent individual elements in our graph. |
| * |
| * @param <K> |
| * Type of the Node's underlying data. |
| * @author <a href="mailto:laurent.goubet@obeo.fr">Laurent Goubet</a> |
| */ |
| private static class Node<K> { |
| /** Underlying data of this Node. */ |
| private final K element; |
| |
| /** The object that contains underlying data of this Node. */ |
| private K parentData; |
| |
| /** Nodes that are connected with this one as a parent. */ |
| private final Set<Node<K>> children; |
| |
| /** Nodes that are connected with this one as a child. */ |
| private final Set<Node<K>> parents; |
| |
| /** |
| * Construct a new Node for the given element. |
| * |
| * @param element |
| * The element for which we need a graph Node. This element must not be null. |
| */ |
| Node(K element) { |
| Preconditions.checkNotNull(element); |
| this.element = element; |
| this.parentData = null; |
| this.parents = new LinkedHashSet<Node<K>>(); |
| this.children = new LinkedHashSet<Node<K>>(); |
| } |
| |
| /** |
| * Returns all children nodes of this one. |
| * |
| * @return All children nodes of this one. |
| */ |
| public Set<Node<K>> getChildren() { |
| return Collections.unmodifiableSet(children); |
| } |
| |
| /** |
| * Returns all parent nodes of this one. |
| * |
| * @return All parent nodes of this one. |
| */ |
| public Set<Node<K>> getParents() { |
| return Collections.unmodifiableSet(parents); |
| } |
| |
| /** |
| * Returns all direct and indirect parents of this node. |
| * |
| * @return All direct and indirect parents of this node. |
| */ |
| public Iterable<Node<K>> getAllParents() { |
| return new ParentsIterable<K>(this); |
| } |
| |
| /** |
| * Registers the given element as a child of this one. |
| * |
| * @param child |
| * The Node that is to be connected as a child of this one. |
| */ |
| public void connectChild(Node<K> child) { |
| this.children.add(child); |
| child.parents.add(this); |
| } |
| |
| /** |
| * Breaks all connections of this node. |
| */ |
| public void breakConnections() { |
| for (Node<K> parent : this.parents) { |
| parent.children.remove(this); |
| } |
| for (Node<K> child : this.children) { |
| child.parents.remove(this); |
| } |
| this.parents.clear(); |
| this.children.clear(); |
| this.parentData = null; |
| } |
| |
| /** |
| * Returns the underlying data of this Node. |
| * |
| * @return The underlying data of this Node. |
| */ |
| public K getElement() { |
| return element; |
| } |
| |
| /** |
| * Returns the object that contains underlying data of this Node. |
| * |
| * @return The object that contains underlying data of this Node. |
| */ |
| public K getParentData() { |
| return parentData; |
| } |
| |
| /** |
| * Sets the object that contains underlying data of this Node. |
| * |
| * @param parentData |
| * the object that contains underlying data of this Node. |
| */ |
| public void setParentData(K parentData) { |
| this.parentData = parentData; |
| } |
| } |
| |
| /** |
| * This can be used to create a set over an entire subgraph given a starting point within said subgraph. |
| * |
| * @param <L> |
| * Kind of elements the created set is meant to contain. |
| * @author <a href="mailto:laurent.goubet@obeo.fr">Laurent Goubet</a> |
| */ |
| private static class SubgraphBuilder<L> { |
| /** Keeps track of the elements we've already iterated over. */ |
| protected final Set<L> set; |
| |
| /** Nodes that will be considered as boundaries for this subgraph. */ |
| protected final Set<L> endPoints; |
| |
| /** The Node that will be used as a starting point of the iteration. */ |
| private final Node<L> start; |
| |
| /** |
| * Constructs a new iterable given the starting point the target subgraph and the elements that will |
| * be considered as (excluded) boundaries of that subgraph. |
| * |
| * @param start |
| * Starting point of the iteration. |
| * @param endPoints |
| * Excluded boundaries of the target subgraph. Iteration will be pruned on these, along |
| * with their own subgraphs. |
| */ |
| SubgraphBuilder(Node<L> start, Set<L> endPoints) { |
| this.start = start; |
| this.set = new LinkedHashSet<L>(); |
| this.set.add(start.getElement()); |
| this.endPoints = checkNotNull(endPoints); |
| } |
| |
| /** |
| * Constructs a set over the entire subgraph containing the specified starting point. |
| * |
| * @return The set of all nodes composing the required subgraph. |
| */ |
| public Set<L> buildSubgraph() { |
| return ImmutableSet.copyOf(new NodeIterator(start)); |
| } |
| |
| /** |
| * Constructs a set over the subtree starting from the specified starting point. This will only |
| * (recursively) iterate over the children of the nodes. |
| * |
| * @return The tree containined the specified starting point. |
| */ |
| public Set<L> buildTree() { |
| final Iterator<L> iterator = new NodeIterator(start) { |
| @Override |
| protected Iterator<Node<L>> createConnectedNodesIterator(Node<L> node) { |
| return node.getChildren().iterator(); |
| } |
| }; |
| return ImmutableSet.copyOf(iterator); |
| } |
| |
| /** |
| * A node iterator will allow us to iterate over the data of a Node and the data of all directly |
| * connected Nodes; all the while avoiding data we've already iterated over. |
| * <p> |
| * This kind of iterator does not support {@link #remove() removal}. |
| * </p> |
| * <p> |
| * Note : this is not a static class as we're building the external SubgraphBuilder's set through this |
| * (and checking for already iterated over elements). |
| * </p> |
| * |
| * @author <a href="mailto:laurent.goubet@obeo.fr">Laurent Goubet</a> |
| */ |
| private class NodeIterator implements Iterator<L> { |
| /** Iterator over the all nodes directly connected with the underlying Node. */ |
| private final Iterator<Node<L>> nodesIterator; |
| |
| /** |
| * Keeps track of the next Node's iterator. This will allow recursion over the connected Nodes' |
| * own connections. |
| */ |
| private Iterator<L> nextNodeIterator; |
| |
| /** Element that should be returned by the next call to {@link #next()}. */ |
| private L next; |
| |
| /** |
| * Construct an iterator over the given Node's connected data. |
| * |
| * @param node |
| * The node for which we need an iterator. |
| */ |
| NodeIterator(Node<L> node) { |
| this.next = node.getElement(); |
| this.nodesIterator = createConnectedNodesIterator(node); |
| prepareNextIterator(); |
| } |
| |
| /** |
| * Creates the iterator over the nodes connected to the current. By default, this will iterate |
| * over all parents, then all children. |
| * |
| * @param node |
| * the starting node for this iteration. |
| * @return Iterator over the connected nodes we are to iterate over. |
| */ |
| protected Iterator<Node<L>> createConnectedNodesIterator(Node<L> node) { |
| return concat(node.getParents().iterator(), node.getChildren().iterator()); |
| } |
| |
| /** |
| * {@inheritDoc} |
| * |
| * @see java.util.Iterator#hasNext() |
| */ |
| public boolean hasNext() { |
| return next != null || nextNodeIterator.hasNext(); |
| } |
| |
| /** |
| * {@inheritDoc} |
| * |
| * @see java.util.Iterator#next() |
| */ |
| public L next() { |
| if (next == null) { |
| throw new NoSuchElementException(); |
| } |
| L result = next; |
| prepareNext(); |
| return result; |
| } |
| |
| /** |
| * {@inheritDoc} |
| * |
| * @see java.util.Iterator#remove() |
| */ |
| public void remove() { |
| throw new UnsupportedOperationException(); |
| } |
| |
| /** |
| * This will be called to prepare for a subsequent call to {@link #next()}. |
| */ |
| private void prepareNext() { |
| if (!nextNodeIterator.hasNext()) { |
| prepareNextIterator(); |
| } |
| if (nextNodeIterator.hasNext()) { |
| next = nextNodeIterator.next(); |
| } else { |
| next = null; |
| } |
| } |
| |
| /** |
| * This will be called whenever we've consumed all nodes connected to the current to "jump over" |
| * to the next one. |
| */ |
| private void prepareNextIterator() { |
| if (nodesIterator.hasNext()) { |
| Node<L> nextNode = nodesIterator.next(); |
| while (SubgraphBuilder.this.set.contains(nextNode.getElement()) |
| && !SubgraphBuilder.this.endPoints.contains(nextNode.getElement()) |
| && nodesIterator.hasNext()) { |
| nextNode = nodesIterator.next(); |
| } |
| if (!SubgraphBuilder.this.endPoints.contains(nextNode.getElement()) |
| && SubgraphBuilder.this.set.add(nextNode.getElement())) { |
| nextNodeIterator = new NodeIterator(nextNode); |
| } else { |
| nextNodeIterator = emptyIterator(); |
| } |
| } else { |
| nextNodeIterator = emptyIterator(); |
| } |
| } |
| } |
| } |
| |
| /** |
| * A custom Iterable that will iterate over the Node->parent Node tree of a given Node. |
| * |
| * @param <O> |
| * The generic type of the class |
| * @author <a href="mailto:laurent.goubet@obeo.fr">Laurent Goubet</a> |
| */ |
| private static class ParentsIterable<O> implements Iterable<Node<O>> { |
| /** The leaf of the Node->parent tree for which this iterable has been constructed. */ |
| private final Node<O> start; |
| |
| /** |
| * Constructs an iterable given the leaf of its tree. |
| * |
| * @param start |
| * Leaf node of the tree we'll iterate over. |
| */ |
| ParentsIterable(Node<O> start) { |
| this.start = start; |
| } |
| |
| /** |
| * {@inheritDoc} |
| * |
| * @see java.lang.Iterable#iterator() |
| */ |
| public Iterator<Node<O>> iterator() { |
| return new ParentsIterator<O>(start); |
| } |
| } |
| |
| /** |
| * A custom TreeIterator that will iterate over the Node->parent Node tree. |
| * |
| * @param <P> |
| * The generic type of the class |
| * @author <a href="mailto:laurent.goubet@obeo.fr">Laurent Goubet</a> |
| */ |
| private static class ParentsIterator<P> extends AbstractTreeIterator<Node<P>> { |
| /** Generated SUID. */ |
| private static final long serialVersionUID = -4476850344598138970L; |
| |
| /** |
| * Objects we've visited and don't want to visit again. |
| */ |
| private final Set<Object> set = Sets.newHashSet(); |
| |
| /** |
| * A predicate that keeps track of objects we've visited, returning true only the first time for each |
| * object. |
| */ |
| private final Predicate<Object> predicate = new Predicate<Object>() { |
| public boolean apply(Object input) { |
| return set.add(input); |
| } |
| }; |
| |
| /** |
| * Construct an iterator given the root (well, "leaf") of its tree. |
| * |
| * @param start |
| * Start node of the tree we'll iterate over. |
| */ |
| ParentsIterator(Node<P> start) { |
| super(start, false); |
| } |
| |
| /** |
| * {@inheritDoc} |
| * |
| * @see org.eclipse.emf.common.util.AbstractTreeIterator#getChildren(java.lang.Object) |
| */ |
| @SuppressWarnings("unchecked") |
| @Override |
| protected Iterator<? extends Node<P>> getChildren(Object obj) { |
| return Iterables.filter(((Node<P>)obj).getParents(), predicate).iterator(); |
| } |
| } |
| |
| /** |
| * A custom iterator implementing a tree iteration algorithm over the underlying graph, using a given node |
| * as root. |
| * <p> |
| * <b>Note</b> that this iterator doesn't allow clients to structurally change the graph after its |
| * creation. Any attempt at doing so will make the next call to {@link #next()} fail in |
| * ConcurrentModificationException. |
| * </p> |
| * <p> |
| * This iterator does not support removal of values from its underlying graph. |
| * </p> |
| * |
| * @author <a href="mailto:laurent.goubet@obeo.fr">Laurent Goubet</a> |
| */ |
| private class ChildrenIterator implements Iterator<E>, Predicate<Node<E>> { |
| /** |
| * The expected {@link Graph#modcount} for this iterator. Any attempt at calling {@link #next()} after |
| * the underlying graph has been modified will fail in {@link ConcurrentModificationException}. |
| */ |
| private final int expectedModCount; |
| |
| /** The current stack of iterators. */ |
| private final LinkedList<Iterator<Node<E>>> iteratorStack; |
| |
| /** |
| * The set of all nodes from the underlying graph we've already iterated over. This will prevent us |
| * from cycling over nodes if there are cycles in our graph, and will also prevent us from iterating |
| * twice over the same node (when a node has multiple parents). |
| */ |
| private final Set<Node<E>> consumedNodes; |
| |
| /** |
| * Creates an iterator over the tree starting from the given root element. |
| * |
| * @param root |
| * Root of the tree we are to iterate over. |
| */ |
| ChildrenIterator(E root) { |
| this.expectedModCount = Graph.this.modcount; |
| this.iteratorStack = new LinkedList<Iterator<Node<E>>>(); |
| iteratorStack.add(Iterators.singletonIterator(Graph.this.nodes.get(root))); |
| consumedNodes = new HashSet<Node<E>>(); |
| } |
| |
| /** {@inheritDoc} */ |
| public boolean hasNext() { |
| return !iteratorStack.isEmpty() && iteratorStack.getLast().hasNext(); |
| } |
| |
| /** {@inheritDoc} */ |
| public E next() { |
| if (Graph.this.modcount != expectedModCount) { |
| throw new ConcurrentModificationException(); |
| } |
| if (iteratorStack.isEmpty()) { |
| throw new NoSuchElementException(); |
| } |
| Node<E> resultNode = iteratorStack.getLast().next(); |
| if (consumedNodes.add(resultNode)) { |
| // no check for emptiness, would be redundant with the following loop |
| iteratorStack.add(Iterators.filter(resultNode.getChildren().iterator(), this)); |
| } |
| |
| // remove the iterators we've consumed entirely from the stack. |
| ListIterator<Iterator<Node<E>>> reverseStackIterator = iteratorStack |
| .listIterator(iteratorStack.size()); |
| while (reverseStackIterator.hasPrevious() && !reverseStackIterator.previous().hasNext()) { |
| reverseStackIterator.remove(); |
| } |
| |
| return resultNode.getElement(); |
| } |
| |
| /** |
| * Unsupported. |
| * |
| * @throws UnsupportedOperationException |
| */ |
| public void remove() { |
| throw new UnsupportedOperationException(); |
| } |
| |
| /** |
| * Predicate implementation, only nodes that are not consumed will be accepted. |
| * |
| * @param input |
| * The node to filter |
| * @return true If and only if the given node is not in comsumedNodes. |
| */ |
| public boolean apply(Node<E> input) { |
| return !consumedNodes.contains(input); |
| } |
| } |
| |
| /** |
| * A custom iterator implementing a breadth-first iteration algorithm over the underlying graph. This will |
| * start from the graph's {@link Graph#roots roots} and carry the iteration downward to each individual |
| * node, never iterating twice on the same node, and never iterating over a node which parents have yet to |
| * be iterated over. |
| * <p> |
| * <b>Note</b> that this iterator doesn't allow clients to structurally change the graph after its |
| * creation. Any attempt at doing so will make the next call to {@link #next()} fail in |
| * ConcurrentModificationException. |
| * </p> |
| * <p> |
| * This iterator does not support removal of values from its underlying graph. |
| * </p> |
| * |
| * @author <a href="mailto:laurent.goubet@obeo.fr">Laurent Goubet</a> |
| */ |
| private class BreadthFirstIterator implements PruningIterator<E> { |
| /** |
| * The current depth-level iterator (first, an iterator over all roots, then, an iterator over all of |
| * these roots' direct children, and so on). See also {@link #nextIterable}. |
| */ |
| private Iterator<Node<E>> currentIterator; |
| |
| /** |
| * The set of all children found for the current depth level. This will be used in conjunction with |
| * {@link #consumedNodes} in order to determine the iterator we'll use when {@link #currentIterator} |
| * is exhausted. |
| */ |
| private Set<Node<E>> nextIterable; |
| |
| /** |
| * The set of all nodes from the underlying graph we've already iterated over. This will prevent us |
| * from cycling over nodes if there are cycles in our graph, and will also prevent us from iterating |
| * twice over the same node (when a node has multiple parents). |
| */ |
| private Set<Node<E>> consumedNodes; |
| |
| /** |
| * The node we've last returned from a call to {@link #next()}. This will be <code>null</code>ed out |
| * by a call to {@link #prune()}. |
| */ |
| private Node<E> lastReturned; |
| |
| /** |
| * The node we'll next return from a call to {@link #next()}. <code>null</code> when we've reached the |
| * end of our iteration. |
| */ |
| private Node<E> next; |
| |
| /** |
| * The expected {@link Graph#modcount} for this iterator. Any attempt at calling {@link #next()} after |
| * the underlying graph has been modified will fail in {@link ConcurrentModificationException}. |
| */ |
| private final int expectedModCount; |
| |
| /** Default constructor. */ |
| BreadthFirstIterator() { |
| this.currentIterator = Graph.this.roots.iterator(); |
| this.nextIterable = new LinkedHashSet<Node<E>>(); |
| this.consumedNodes = new LinkedHashSet<Node<E>>(); |
| this.expectedModCount = Graph.this.modcount; |
| prepareNext(); |
| } |
| |
| /** {@inheritDoc} */ |
| public boolean hasNext() { |
| // next is updated after a node is returned or pruned |
| return next != null; |
| } |
| |
| /** {@inheritDoc} */ |
| public E next() { |
| if (Graph.this.modcount != expectedModCount) { |
| throw new ConcurrentModificationException(); |
| } |
| if (next == null) { |
| throw new NoSuchElementException(); |
| } |
| final E result = next.getElement(); |
| consumedNodes.add(next); |
| lastReturned = next; |
| prepareNext(); |
| return result; |
| } |
| |
| /** {@inheritDoc} */ |
| public void prune() { |
| // do not accept successive pruning calls, and don't fail when trying to prune before even |
| // starting the iteration. |
| if (lastReturned == null) { |
| return; |
| } |
| // the current has already been added to the "consumed" set. |
| // All direct and indirect children of this path must be pruned as well. |
| // TODO any effective way of achieving this without iterating? |
| Set<Node<E>> children = lastReturned.getChildren(); |
| lastReturned = null; |
| while (!children.isEmpty()) { |
| final Set<Node<E>> copy = children; |
| children = new LinkedHashSet<Node<E>>(); |
| for (Node<E> child : copy) { |
| if (consumedNodes.add(child)) { |
| children.addAll(child.getChildren()); |
| } |
| } |
| } |
| // update next according to newly pruned nodes, if necessary |
| if (consumedNodes.contains(next)) { |
| prepareNext(); |
| } |
| } |
| |
| /** |
| * Unsupported. |
| * |
| * @throws UnsupportedOperationException |
| */ |
| public void remove() { |
| throw new UnsupportedOperationException(); |
| } |
| |
| /** |
| * This method prepares the {@link #next()} node by checking first the current iterator if there are |
| * any unconsumed nodes left and if not switching to the next iterator. If neither the current nor the |
| * next iterator have any unconsumed nodes, next will be set to null. |
| */ |
| private void prepareNext() { |
| // check if current iterator still has unconsumed nodes |
| boolean isConsumed = true; |
| while (isConsumed) { |
| next = currentNext(); |
| // check if node has already been consumed (or pruned) |
| isConsumed = next != null && consumedNodes.contains(next); |
| } |
| |
| if (next == null) { |
| // could not find unconsumed nodes in current iterator, try next iterator |
| prepareNextIterator(); |
| |
| // next iterator is now currentIterator only containing unconsumed nodes, if there are any |
| next = currentNext(); |
| } |
| } |
| |
| /** |
| * Returns the next node from the current iterator, if such a node exists. The children of the next |
| * node will be remembered for the next iterator. |
| * |
| * @return current next node |
| */ |
| private Node<E> currentNext() { |
| Node<E> currentNext = null; |
| if (currentIterator.hasNext()) { |
| currentNext = currentIterator.next(); |
| // remember children for next iterator |
| nextIterable.addAll(currentNext.getChildren()); |
| } |
| return currentNext; |
| } |
| |
| /** |
| * Whenever we've consumed all of the current depth's nodes, this will create a new iterator for the |
| * next depth level out of {@link #nextIterable} and {@link #consumedNodes}. |
| */ |
| private void prepareNextIterator() { |
| final Set<Node<E>> difference = new LinkedHashSet<Node<E>>(); |
| for (Node<E> node : nextIterable) { |
| if (!consumedNodes.contains(node)) { |
| difference.add(node); |
| } |
| } |
| currentIterator = difference.iterator(); |
| nextIterable.clear(); |
| } |
| } |
| } |