001: /*
002: * GeoTools - OpenSource mapping toolkit
003: * http://geotools.org
004: * (C) 2005-2006, GeoTools Project Managment Committee (PMC)
005: *
006: * This library is free software; you can redistribute it and/or
007: * modify it under the terms of the GNU Lesser General Public
008: * License as published by the Free Software Foundation;
009: * version 2.1 of the License.
010: *
011: * This library is distributed in the hope that it will be useful,
012: * but WITHOUT ANY WARRANTY; without even the implied warranty of
013: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
014: * Lesser General Public License for more details.
015: */
016: package org.geotools.index.quadtree;
017:
018: import java.io.IOException;
019: import java.util.ArrayList;
020: import java.util.Collections;
021: import java.util.Iterator;
022: import java.util.List;
023: import java.util.NoSuchElementException;
024:
025: import org.geotools.data.shapefile.shp.IndexFile;
026: import org.geotools.index.Data;
027: import org.geotools.index.DataDefinition;
028: import org.geotools.index.TreeException;
029:
030: import com.vividsolutions.jts.geom.Envelope;
031:
032: /**
033: * Iterator that search the quad tree depth first. 32000 indices are cached at a time and each time a node is
034: * visited the indices are removed from the node so that the memory footprint is kept small. Note that if other
035: * iterators operate on the same tree then they can interfere with each other.
036: *
037: * @author Jesse
038: */
039: public class LazySearchIterator implements Iterator {
040:
041: static final DataDefinition DATA_DEFINITION = new DataDefinition(
042: "US-ASCII");
043:
044: private static final int MAX_INDICES = 32768;
045: static {
046: DATA_DEFINITION.addField(Integer.class);
047: DATA_DEFINITION.addField(Long.class);
048: }
049:
050: Data next = null;
051:
052: Node current;
053:
054: int idIndex = 0;
055:
056: private boolean closed;
057:
058: private Envelope bounds;
059:
060: Iterator data;
061:
062: private IndexFile indexfile;
063:
064: public LazySearchIterator(Node root, IndexFile indexfile,
065: Envelope bounds) {
066: super ();
067: this .current = root;
068: this .bounds = bounds;
069: this .closed = false;
070: this .next = null;
071: this .indexfile = indexfile;
072: }
073:
074: public boolean hasNext() {
075: if (closed)
076: throw new IllegalStateException("Iterator has been closed!");
077: if (next != null)
078: return true;
079: if (data != null && data.hasNext()) {
080: next = (Data) data.next();
081: } else {
082: fillCache();
083: if (data != null && data.hasNext())
084: next = (Data) data.next();
085: }
086: return next != null;
087: }
088:
089: private void fillCache() {
090: List indices = new ArrayList();
091: ArrayList dataList = new ArrayList();
092: try {
093: while (indices.size() < MAX_INDICES && current != null) {
094: if (idIndex < current.getNumShapeIds()
095: && !current.isVisited()
096: && current.getBounds().intersects(bounds)) {
097: indices
098: .add(new Integer(current
099: .getShapeId(idIndex)));
100: idIndex++;
101: } else {
102: current.setShapesId(new int[0]);
103: idIndex = 0;
104: boolean foundUnvisited = false;
105: for (int i = 0; i < current.getNumSubNodes(); i++) {
106: Node node = current.getSubNode(i);
107: if (!node.isVisited()
108: && node.getBounds().intersects(bounds)) {
109: foundUnvisited = true;
110: current = node;
111: break;
112: }
113: }
114: if (!foundUnvisited) {
115: current.setVisited(true);
116: current = current.getParent();
117: }
118: }
119: }
120: // sort so offset lookup is faster
121: Collections.sort(indices);
122: for (Iterator iter = indices.iterator(); iter.hasNext();) {
123: Integer recno = (Integer) iter.next();
124: Data data = new Data(DATA_DEFINITION);
125: data.addValue(new Integer(recno.intValue() + 1));
126: data.addValue(new Long(indexfile.getOffsetInBytes(recno
127: .intValue())));
128: dataList.add(data);
129: }
130: } catch (IOException e) {
131: throw new RuntimeException(e);
132: } catch (TreeException e) {
133: throw new RuntimeException(e);
134: } catch (StoreException e) {
135: throw new RuntimeException(e);
136: }
137: data = dataList.iterator();
138: }
139:
140: public Object next() {
141: if (!hasNext())
142: throw new NoSuchElementException(
143: "No more elements available");
144: Data temp = next;
145: next = null;
146: return temp;
147: }
148:
149: public void remove() {
150: throw new UnsupportedOperationException();
151: }
152:
153: public void close() throws StoreException {
154: this .closed = true;
155: }
156:
157: }
|