diff options
Diffstat (limited to 'jpa/plugins/org.eclipse.jpt.utility/src/org/eclipse/jpt/utility/internal/iterators/GraphIterator.java')
-rw-r--r-- | jpa/plugins/org.eclipse.jpt.utility/src/org/eclipse/jpt/utility/internal/iterators/GraphIterator.java | 271 |
1 files changed, 0 insertions, 271 deletions
diff --git a/jpa/plugins/org.eclipse.jpt.utility/src/org/eclipse/jpt/utility/internal/iterators/GraphIterator.java b/jpa/plugins/org.eclipse.jpt.utility/src/org/eclipse/jpt/utility/internal/iterators/GraphIterator.java deleted file mode 100644 index 3d9a8f6d0f..0000000000 --- a/jpa/plugins/org.eclipse.jpt.utility/src/org/eclipse/jpt/utility/internal/iterators/GraphIterator.java +++ /dev/null @@ -1,271 +0,0 @@ -/******************************************************************************* - * Copyright (c) 2005, 2009 Oracle. 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: - * Oracle - initial API and implementation - ******************************************************************************/ -package org.eclipse.jpt.utility.internal.iterators; - -import java.util.HashSet; -import java.util.Iterator; -import java.util.LinkedList; -import java.util.NoSuchElementException; - -import org.eclipse.jpt.utility.internal.StringTools; - -/** - * A <code>GraphIterator</code> is similar to a {@link TreeIterator} - * except that it cannot be assumed that all nodes assume a strict tree - * structure. For instance, in a tree, a node cannot be a descendent of - * itself, but a graph may have a cyclical structure. - * - * A <code>GraphIterator</code> simplifies the traversal of a - * graph of objects, where the objects' protocol(s) provides - * a method for getting the next collection of nodes in the graph, - * (or <em>neighbors</em>), but does not provide a method for - * getting <em>all</em> of the nodes in the graph. - * (e.g. a neighbor can return his neighbors, and those neighbors - * can return their neighbors, which might also include the original - * neighbor, but you only want to visit the original neighbor once.) - * <p> - * If a neighbor has already been visited (determined by using - * {@link #equals(Object)}), that neighbor is not visited again, - * nor are the neighbors of that object. - * <p> - * It is up to the user of this class to ensure a <em>complete</em> graph. - * <p> - * To use, supply:<ul> - * <li> either the initial node of the graph or an {@link Iterator} - * over an initial collection of graph nodes - * <li> a {@link MisterRogers] that tells who the neighbors are - * of each node - * (alternatively, subclass <code>GraphIterator</code> - * and override the {@link #neighbors(Object)} method) - * </ul> - * {@link #remove()} is not supported. This behavior, if - * desired, must be implemented by the user of this class. - * - * @param <E> the type of elements returned by the iterator - */ -public class GraphIterator<E> - implements Iterator<E> -{ - // use a LinkedList since we will be pulling off the front and adding to the end - private final LinkedList<Iterator<? extends E>> iterators = new LinkedList<Iterator<? extends E>>(); - private final HashSet<E> visitedNeighbors = new HashSet<E>(); - private final MisterRogers<E> misterRogers; - - private Iterator<? extends E> currentIterator; - - private E nextNeighbor; - private boolean done; - - - /** - * Construct an iterator that returns the nodes of a graph - * with the specified collection of roots - * and a disabled Mr. Rogers. - * Use this constructor if you want to override the - * {@link #neighbors(Object)} method instead of building - * a {@link MisterRogers}. - */ - public GraphIterator(E... roots) { - this(new ArrayIterator<E>(roots)); - } - - /** - * Construct an iterator that returns the nodes of a graph - * with the specified collection of roots - * and a disabled Mr. Rogers. - * Use this constructor if you want to override the - * {@link #neighbors(Object)} method instead of building - * a {@link MisterRogers}. - */ - public GraphIterator(Iterable<? extends E> roots) { - this(roots.iterator()); - } - - /** - * Construct an iterator that returns the nodes of a graph - * with the specified collection of roots - * and a disabled Mr. Rogers. - * Use this constructor if you want to override the - * {@link #neighbors(Object)} method instead of building - * a {@link MisterRogers}. - */ - public GraphIterator(Iterator<? extends E> roots) { - this(roots, MisterRogers.Disabled.<E>instance()); - } - - /** - * Construct an iterator that returns the nodes of a graph - * with the specified root - * and a disabled Mr. Rogers. - * Use this constructor if you want to override the - * <code>neighbors(Object)</code> method instead of building - * a <code>MisterRogers</code>. - */ - public GraphIterator(E root) { - this(root, MisterRogers.Disabled.<E>instance()); - } - - /** - * Construct an iterator that returns the nodes of a graph - * with the specified root and Mr. Rogers. - */ - public GraphIterator(E root, MisterRogers<E> misterRogers) { - this(new SingleElementIterator<E>(root), misterRogers); - } - - /** - * Construct an iterator that returns the nodes of a graph - * with the specified collection of roots and Mr. Rogers. - */ - public GraphIterator(E[] roots, MisterRogers<E> misterRogers) { - this(new ArrayIterator<E>(roots), misterRogers); - } - - /** - * Construct an iterator that returns the nodes of a graph - * with the specified roots and Mr. Rogers. - */ - public GraphIterator(Iterable<? extends E> roots, MisterRogers<E> misterRogers) { - this(roots.iterator(), misterRogers); - } - - /** - * Construct an iterator that returns the nodes of a graph - * with the specified roots and Mr. Rogers. - */ - public GraphIterator(Iterator<? extends E> roots, MisterRogers<E> misterRogers) { - super(); - this.currentIterator = roots; - this.misterRogers = misterRogers; - this.loadNextNeighbor(); - } - - /** - * Load next neighbor with the next entry from the current iterator. - * If the current iterator has none, load the next iterator. - * If there are no more, the {@link done} flag is set. - */ - private void loadNextNeighbor() { - if (this.currentIterator == EmptyIterator.instance()) { - this.done = true; - } - else if (this.currentIterator.hasNext()) { - E nextPossibleNeighbor = this.currentIterator.next(); - if (this.visitedNeighbors.contains(nextPossibleNeighbor)) { - this.loadNextNeighbor(); // recurse - } else { - this.nextNeighbor = nextPossibleNeighbor; - this.visitedNeighbors.add(nextPossibleNeighbor); - this.iterators.add(this.neighbors(nextPossibleNeighbor)); - } - } - else { - for (Iterator<? extends Iterator<? extends E>> stream = this.iterators.iterator(); ! this.currentIterator.hasNext() && stream.hasNext(); ) { - this.currentIterator = stream.next(); - stream.remove(); - } - if ( ! this.currentIterator.hasNext()) { - this.currentIterator = EmptyIterator.instance(); - } - this.loadNextNeighbor(); // recurse - } - } - - public boolean hasNext() { - return ! this.done; - } - - public E next() { - if (this.done) { - throw new NoSuchElementException(); - } - E next = this.nextNeighbor; - this.loadNextNeighbor(); - return next; - } - - public void remove() { - throw new UnsupportedOperationException(); - } - - /** - * Return the immediate neighbors of the specified object. - */ - protected Iterator<? extends E> neighbors(E next) { - return this.misterRogers.neighbors(next); - } - - @Override - public String toString() { - return StringTools.buildToStringFor(this, this.currentIterator); - } - - - //********** inner classes ********** - - /** - * Used by {@link GraphIterator} to retrieve - * the immediate neighbors of a node in the graph. - * "These are the people in your neighborhood..." - */ - public interface MisterRogers<T> { - - /** - * Return the immediate neighbors of the specified object. - */ - Iterator<? extends T> neighbors(T next); - - - final class Null<S> implements MisterRogers<S> { - @SuppressWarnings("unchecked") - public static final MisterRogers INSTANCE = new Null(); - @SuppressWarnings("unchecked") - public static <R> MisterRogers<R> instance() { - return INSTANCE; - } - // ensure single instance - private Null() { - super(); - } - // return no neighbors - public Iterator<S> neighbors(S next) { - return EmptyIterator.instance(); - } - @Override - public String toString() { - return "GraphIterator.MisterRogers.Null"; //$NON-NLS-1$ - } - } - - /** The Mr. Rogers used when the {@link GraphIterator#neighbors(Object)} method is overridden. */ - final class Disabled<S> implements MisterRogers<S> { - @SuppressWarnings("unchecked") - public static final MisterRogers INSTANCE = new Disabled(); - @SuppressWarnings("unchecked") - public static <R> MisterRogers<R> instance() { - return INSTANCE; - } - // ensure single instance - private Disabled() { - super(); - } - // throw an exception - public Iterator<S> neighbors(S next) { - throw new UnsupportedOperationException(); // GraphIterator.neighbors(Object) was not implemented - } - @Override - public String toString() { - return "GraphIterator.MisterRogers.Disabled"; //$NON-NLS-1$ - } - } - - } - -} |