/*
 *    GeoTools - OpenSource mapping toolkit
 *    http://geotools.org
 *    (C) 2005-2006, GeoTools Project Managment Committee (PMC)
 *
 *    This library is free software; you can redistribute it and/or
 *    modify it under the terms of the GNU Lesser General Public
 *    License as published by the Free Software Foundation;
 *    version 2.1 of the License.
 *
 *    This library 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
 *    Lesser General Public License for more details.
 */
package org.geotools.index.quadtree;

import java.io.IOException;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Iterator;
import java.util.List;
import java.util.NoSuchElementException;

import org.geotools.data.shapefile.shp.IndexFile;
import org.geotools.index.Data;
import org.geotools.index.DataDefinition;
import org.geotools.index.TreeException;

import com.vividsolutions.jts.geom.Envelope;

/**
 * Iterator that search the quad tree depth first.  32000 indices are cached at a time and each time a node is
 * visited the indices are removed from the node so that the memory footprint is kept small.  Note that if other
 * iterators operate on the same tree then they can interfere with each other.
 * 
 * @author Jesse
 */
public class LazySearchIterator implements Iterator {

	static final DataDefinition DATA_DEFINITION = new DataDefinition("US-ASCII");

	private static final int MAX_INDICES = 32768;
	static {
		DATA_DEFINITION.addField(Integer.class);
		DATA_DEFINITION.addField(Long.class);
	}

	Data next = null;

	Node current;

	int idIndex = 0;

	private boolean closed;

	private Envelope bounds;

	Iterator data;


	private IndexFile indexfile;

	public LazySearchIterator(Node root, IndexFile indexfile, Envelope bounds) {
		super();
		this.current = root;
		this.bounds = bounds;
		this.closed = false;
		this.next = null;
		this.indexfile=indexfile;
	}



	public boolean hasNext() {
		if (closed)
			throw new IllegalStateException("Iterator has been closed!");
		if (next != null)
			return true;
		if (data != null && data.hasNext()) {
			next = (Data) data.next();
		} else {
			fillCache();
			if( data!=null && data.hasNext() )
				next = (Data) data.next();
		}
		return next != null;
	}

	private void fillCache() {
		List indices=new ArrayList();
		ArrayList dataList=new ArrayList();
		try {
			while (indices.size() < MAX_INDICES && current!=null) {
				if (idIndex < current.getNumShapeIds() && !current.isVisited() && current.getBounds().intersects(bounds)) {
					indices.add(new Integer( current.getShapeId(idIndex) ) );
					idIndex++;
				} else {
					current.setShapesId(new int[0]);
					idIndex = 0;
					boolean foundUnvisited=false;
					for (int i = 0; i < current.getNumSubNodes(); i++) {
						Node node = current.getSubNode(i);
						if (!node.isVisited()
								&& node.getBounds().intersects(bounds)){
						foundUnvisited=true;
						current = node;
						break;
						}
					}
					if( !foundUnvisited ){
						current.setVisited(true);
						current=current.getParent();
					}
				}
			}
			// sort so offset lookup is faster
			Collections.sort(indices);
			for (Iterator iter = indices.iterator(); iter.hasNext();) {
				Integer recno = (Integer) iter.next();
				Data data=new Data(DATA_DEFINITION);
				data.addValue(new Integer(recno.intValue()+1));
				data.addValue(new Long(indexfile.getOffsetInBytes(recno.intValue())));
				dataList.add(data);
			}
		} catch (IOException e) {
			throw new RuntimeException(e);
		} catch (TreeException e) {
			throw new RuntimeException(e);
		} catch (StoreException e) {
			throw new RuntimeException(e);
		}
		data=dataList.iterator();
	}

	public Object next() {
		if (!hasNext())
			throw new NoSuchElementException("No more elements available");
		Data temp = next;
		next=null;
		return temp;
	}

	public void remove() {
		throw new UnsupportedOperationException();
	}

	public void close() throws StoreException {
		this.closed = true;
	}

}
