/*
    * Copyright (c) 2003-2008 by Cosylab d. d.
    *
    * This file is part of Java-Common.
    *
    * Java-Common is free software: you can redistribute it and/or modify
    * it under the terms of the GNU General Public License as published by
    * the Free Software Foundation, either version 3 of the License, or
    * (at your option) any later version.
   *
   * Java-Common is distributed in the hope that it will be useful,
   * but WITHOUT ANY WARRANTY; without even the implied warranty of
   * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   * GNU General Public License for more details.
   *
   * You should have received a copy of the GNU General Public License
   * along with Java-Common.  If not, see <http://www.gnu.org/licenses/>.
   */
  
  package com.cosylab.util;
  
  import java.util.HashSet;
  import java.util.Iterator;
  
  /**
   * Utilities for working with iterators.
   * 
   * @author Klemen Zagar, Cosylab
   */
  public class Iterators {
  
  	/**
  	 * Determine whether two iterators iterate through the same set of elements.
  	 * If the same element appears more than once in the set, it is treated as
  	 * if it appeared exactly once.
  	 * 
  	 * <p>
  	 * <b>Note:</b> This implementation is not efficient for iterators over
  	 * large sets, as it first puts elements of both iterators in two sets, and
  	 * then compares the sets.
  	 * </p>
  	 * 
  	 * @param iterA
  	 *            First iterator.
  	 * @param iterB
  	 *            Second iterator.
  	 * @return <code>true</code> if elements are the same.
  	 */
  	public static boolean areEqual(Iterator<? extends Object> iterA,
  			Iterator<? extends Object> iterB) {
  		if (iterA == null || iterB == null) {
  			throw new IllegalArgumentException();
  		}
  
  		HashSet<Object> setA = new HashSet<Object>();
  		HashSet<Object> setB = new HashSet<Object>();
  
  		// First, we put elements of the iterators in a set.
  		while (iterA.hasNext()) {
  			setA.add(iterA.next());
  		}
  		while (iterB.hasNext()) {
  			setB.add(iterB.next());
  		}
  
  		// If the sets aren't of equal size, they can't possibly contain
  		// the same elements.
  		if (setA.size() != setB.size()) {
  			return false;
  		}
  
  		// Check that all elements of the first set are in the second set.
  		iterA = setA.iterator();
  		while (iterA.hasNext()) {
  			if (!setB.contains(iterA.next())) {
  				return false;
  			}
  		}
  
  		return true;
  	}
  
  	/**
  	 * Do two iterators iterate through the same elements in the same order?
  	 * 
  	 * @param iterA
  	 *            First iterator.
  	 * @param iterB
  	 *            Second iterator.
  	 * @return <code>true</code> if the iteration order is the same.
  	 */
  	public static boolean areEqualOrder(Iterator<? extends Object> iterA,
  			Iterator<? extends Object> iterB) {
  		if (iterA == null || iterB == null) {
  			throw new IllegalArgumentException();
  		}
  
  		while (iterA.hasNext()) {
  			if (!iterB.hasNext()) {
 				return false;
 			}
 
 			Object a = iterA.next();
 			Object b = iterB.next();
 
 			if (a == null) {
 				if (b != null) {
 					return false;
 				}
 			}
 
 			if (!a.equals(b)) {
 				return false;
 			}
 		}
 
 		if (iterB.hasNext()) {
 			return false;
 		}
 
 		return true;
 	}
 
 	/**
 	 * Intersection of two iterators.
 	 * 
 	 * <p>
 	 * <b>Note:</b> the implementation is such that the first iterator (<code>iterA</code>)
 	 * is first traversed in its entirety. Whenever possible, <code>iterA</code>
 	 * should be the <em>shorter</em> of the two iterators.
 	 * </p>
 	 * 
 	 * @param <T>
 	 *            Type across which the iterator iterates.
 	 * @param iterA
 	 *            First iterator.
 	 * @param iterB
 	 *            Second iterator.
 	 * @return Iterator through items traversed both by <code>iterA</code> and
 	 *         <code>iterB</code>.
 	 */
 	public static <T> Iterator<T> intersect(Iterator<T> iterA, Iterator<T> iterB) {
 		final HashSet<Object> setA = new HashSet<Object>();
 		final Iterator<T> iterBFinal = iterB;
 		while (iterA.hasNext()) {
 			setA.add(iterA.next());
 		}
 		return new Iterator<T>() {
 			private T current;
 
 			{
 				moveToNext();
 			}
 
 			private void moveToNext() {
 				T tmp = null;
 				current = null;
 				while (iterBFinal.hasNext()) {
 					tmp = iterBFinal.next();
 					if (setA.contains(tmp)) {
 						current = tmp;
 						return;
 					}
 				}
 			}
 
 			public boolean hasNext() {
 				return current != null;
 			}
 
 			public T next() {
 				T result = current;
 				current = null;
 				moveToNext();
 				return result;
 			}
 
 			public void remove() {
 				throw new UnsupportedOperationException();
 			}
 		};
 	}
 
 	/**
 	 * Create an iterator that iterates only through distinct values.
 	 * 
 	 * @param <T>
 	 *            Type across which the iterator is iterating.
 	 * @param iter
 	 *            The underlying iterator.
 	 * @return The iterator that iterates only through distinct values.
 	 */
 	public static <T> Iterator<T> distinct(final Iterator<T> iter) {
 		return new Iterator<T>() {
 			// Elements that were already returned.
 			private HashSet<T> elements = new HashSet<T>();
 			
 			// The value to return next.
 			private T next = null;
 			
 			// Instance initializer (constructor).
 			{
 				// Advance to the first element.
 				goToNext();
 			}
 
 			/*
 			 * (non-Javadoc)
 			 * @see java.util.Iterator#hasNext()
 			 */
 			public boolean hasNext() {
 				return next != null;
 			}
 
 			/*
 			 * (non-Javadoc)
 			 * @see java.util.Iterator#next()
 			 */
 			public T next() {
 				T result = next;
 				goToNext();
 				return result;
 			}
 
 			/*
 			 * (non-Javadoc)
 			 * @see java.util.Iterator#remove()
 			 */
 			public void remove() {
 				throw new UnsupportedOperationException();
 			}
 
 			/**
 			 * Advance to the next element.
 			 */
 			private void goToNext() {
 				while (iter.hasNext()) {
 					next = iter.next();
 					if (!elements.contains(next)) {
 						elements.add(next);
 						return;
 					}
 				}
 				next = null;
 			}
 		};
 	}
 }
 
 /* __oOo__ */