/*
 * Copyright (c) 2007 Israfil Consulting Services Corporation
 * Copyright (c) 2007 Christian Edward Gruber
 * All Rights Reserved
 * 
 * This software is licensed under the Berkeley Standard Distribution license,
 * (BSD license), as defined below:
 * 
 * Redistribution and use in source and binary forms, with or without 
 * modification, are permitted provided that the following conditions are met:
 *
 * 1. Redistributions of source code must retain the above copyright notice, this 
 *    list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright notice, 
 *    this list of conditions and the following disclaimer in the documentation 
 *    and/or other materials provided with the distribution.
 * 3. Neither the name of Israfil Consulting Services nor the names of its contributors 
 *    may be used to endorse or promote products derived from this software without 
 *    specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND 
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED 
 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 
 * IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, 
 * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, 
 * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, 
 * OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, 
 * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 
 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY 
 * OF SUCH DAMAGE.
 * 
 * $Id: ArraySet.java 76 2006-08-03 15:37:05Z cgruber $
 */
package net.israfil.foundation.collections;

import java.security.SecureRandom;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Random;

/**
 * An iterator that is constructed from a collection and returns the 
 * contents of the collection in random order.  Note that this is 
 * an iterator over a copy of the collection, not the collection 
 * itself, so remove() is not supported, and underlying changes
 * to the original collection will not be reflected in this iterator.
 * 
 * @author <a href="mailto:cgruber@israfil.net">Christian Edward Gruber </a>
 */
public class RandomOrderIterator<E> implements Iterator<E>  {

	private transient List<E> _collection;
	
	private transient Random _random = new SecureRandom();
	
	private transient List<Integer> _indexes;
	
	
	public RandomOrderIterator(Collection<E> collection) {
		_collection = new ArrayList<E>(collection);
		_indexes = new LinkedList<Integer>();
		for (int i = 0; i < _collection.size();i++) {
			_indexes.add(i); // populate index source.
		}
	}

	public RandomOrderIterator(Collection<E> collection, Random random) {
		this(collection);
		this._random = random;
	}

	public boolean hasNext() {
		return _indexes.size() > 0;
	}

	public E next() {
		Integer index = _indexes.remove(_random.nextInt(_indexes.size()));
		return _collection.get(index);
	}

	/**
	 * Because of the means required to track the current node,
	 * removing anything from the underlying collection is not supported.
	 */
	public void remove() {
		throw new UnsupportedOperationException();
	}
	
	
		
}