jpa/plugins/org.eclipse.jpt.utility/src/org/eclipse/jpt/utility/internal/iterators/GraphIterator.java - dali/webtools.dali - Git at Google

 /*******************************************************************************
  * 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
  *
  * @see org.eclipse.jpt.utility.internal.iterables.GraphIterable
  */
 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$
 			}
 			private static final long serialVersionUID = 1L;
 			private Object readResolve() {
 				// replace this object with the singleton
 				return INSTANCE;
 			}
 		}

 		/** 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$
 			}
 			private static final long serialVersionUID = 1L;
 			private Object readResolve() {
 				// replace this object with the singleton
 				return INSTANCE;
 			}
 		}

 	}

 }
	/*******************************************************************************
	* 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
	*
	* @see org.eclipse.jpt.utility.internal.iterables.GraphIterable
	*/
	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$
	}
	private static final long serialVersionUID = 1L;
	private Object readResolve() {
	// replace this object with the singleton
	return INSTANCE;
	}
	}

	/** 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$
	}
	private static final long serialVersionUID = 1L;
	private Object readResolve() {
	// replace this object with the singleton
	return INSTANCE;
	}
	}

	}

	}