001: /*
002: * GeoTools - OpenSource mapping toolkit
003: * http://geotools.org
004: * (C) 2003-2006, GeoTools Project Managment Committee (PMC)
005: * (C) 2002, Centre for Computational Geography
006: *
007: * This library is free software; you can redistribute it and/or
008: * modify it under the terms of the GNU Lesser General Public
009: * License as published by the Free Software Foundation;
010: * version 2.1 of the License.
011: *
012: * This library is distributed in the hope that it will be useful,
013: * but WITHOUT ANY WARRANTY; without even the implied warranty of
014: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
015: * Lesser General Public License for more details.
016: */
017: package org.geotools.data.shapefile.indexed;
018:
019: import com.vividsolutions.jts.geom.Envelope;
020: import org.geotools.data.shapefile.Lock;
021: import org.geotools.data.shapefile.shp.IndexFile;
022: import org.geotools.data.shapefile.shp.ShapefileHeader;
023: import org.geotools.data.shapefile.shp.ShapefileReader;
024: import org.geotools.data.shapefile.shp.ShapefileReader.Record;
025: import org.geotools.index.Data;
026: import org.geotools.index.DataDefinition;
027: import org.geotools.index.LockTimeoutException;
028: import org.geotools.index.TreeException;
029: import org.geotools.index.quadtree.QuadTree;
030: import org.geotools.index.quadtree.StoreException;
031: import org.geotools.index.quadtree.fs.FileSystemIndexStore;
032: import org.geotools.index.quadtree.fs.IndexHeader;
033: import org.geotools.index.rtree.PageStore;
034: import org.geotools.index.rtree.RTree;
035: import org.geotools.index.rtree.cachefs.FileSystemPageStore;
036: import java.io.File;
037: import java.io.FileInputStream;
038: import java.io.FileOutputStream;
039: import java.io.IOException;
040: import java.io.InputStream;
041: import java.io.OutputStream;
042: import java.net.MalformedURLException;
043: import java.nio.channels.FileChannel;
044: import java.util.Hashtable;
045: import java.util.logging.Logger;
046:
047: /**
048: * Utility class for Shapefile spatial indexing
049: *
050: * @author Tommaso Nolli
051: * @source $URL: http://svn.geotools.org/geotools/tags/2.4.1/modules/plugin/shapefile/src/main/java/org/geotools/data/shapefile/indexed/ShapeFileIndexer.java $
052: */
053: public class ShapeFileIndexer {
054: public static final String RTREE = "RTREE";
055: public static final String QUADTREE = "QUADTREE";
056: private static final Logger LOGGER = org.geotools.util.logging.Logging
057: .getLogger("org.geotools.data.shapefile");
058:
059: /**
060: * Minimum time a thread will wait for index build by another thread by
061: * default this is 2 seconds
062: */
063: private static final long MIN_WAIT_TIME = 2000;
064:
065: /**
066: * Maximum time a thread will wait for index build by another thread by
067: * default this is 5 minutes (is it too much?)
068: */
069: private static final long MAX_WAIT_TIME = 5 * 60 * 1000;
070: private static Hashtable IDX_CREATION = new Hashtable();
071: private String idxType;
072: private int max = 50;
073: private int min = 25;
074: private short split = PageStore.SPLIT_QUADRATIC;
075: private String fileName;
076: private String byteOrder;
077:
078: public static void main(String[] args) {
079: if ((args.length < 1) || (((args.length - 1) % 2) != 0)) {
080: usage();
081: }
082:
083: long start = System.currentTimeMillis();
084:
085: ShapeFileIndexer idx = new ShapeFileIndexer();
086:
087: for (int i = 0; i < args.length; i++) {
088: if (args[i].equals("-t")) {
089: idx.setIdxType(args[++i]);
090: } else if (args[i].equals("-M")) {
091: idx.setMax(Integer.parseInt(args[++i]));
092: } else if (args[i].equals("-m")) {
093: idx.setMin(Integer.parseInt(args[++i]));
094: } else if (args[i].equals("-s")) {
095: idx.setSplit(Short.parseShort(args[++i]));
096: } else if (args[i].equals("-b")) {
097: idx.setByteOrder(args[++i]);
098: } else {
099: if (!args[i].toLowerCase().endsWith(".shp")) {
100: System.out.println("File extension must be '.shp'");
101: System.exit(1);
102: }
103:
104: idx.setShapeFileName(args[i]);
105: }
106: }
107:
108: try {
109: System.out.print("Indexing ");
110:
111: int cnt = idx.index(true, new Lock());
112: System.out.println();
113: System.out.print(cnt + " features indexed ");
114: System.out.println("in "
115: + (System.currentTimeMillis() - start) + "ms.");
116: System.out.println();
117: } catch (Exception e) {
118: e.printStackTrace();
119: usage();
120: System.exit(1);
121: }
122: }
123:
124: private static void usage() {
125: System.out.println("Usage: ShapeFileIndexer "
126: + "-t <RTREE | QUADTREE> "
127: + "[-M <max entries per node>] "
128: + "[-m <min entries per node>] "
129: + "[-s <split algorithm>] "
130: + "[-b <byte order NL | NM>] " + "<shape file>");
131:
132: System.out.println();
133:
134: System.out.println("Options:");
135: System.out.println("\t-t Index type: RTREE or QUADTREE");
136: System.out.println();
137: System.out.println("Following options apllies only to RTREE:");
138: System.out.println("\t-M maximum number of entries per node");
139: System.out.println("\t-m minimum number of entries per node");
140: System.out.println("\t-s split algorithm to use");
141: System.out.println();
142: System.out
143: .println("Following options apllies only to QUADTREE:");
144: System.out.println("\t-b byte order to use: NL = LSB; "
145: + "NM = MSB (default)");
146:
147: System.exit(1);
148: }
149:
150: /**
151: * Index the shapefile denoted by setShapeFileName(String fileName) If
152: * when a thread starts, another thread is indexing the same file, this
153: * thread will wait that the first thread ends indexing; in this case
154: * <b>zero</b> is reurned as result of the indexing process.
155: *
156: * @param verbose enable/disable printing of dots every 500 indexed records
157: * @param lock DOCUMENT ME!
158: *
159: * @return The number of indexed records (or zero)
160: *
161: * @throws MalformedURLException
162: * @throws IOException
163: * @throws TreeException
164: * @throws StoreException DOCUMENT ME!
165: * @throws LockTimeoutException
166: */
167: public int index(boolean verbose, Lock lock)
168: throws MalformedURLException, IOException, TreeException,
169: StoreException, LockTimeoutException {
170: /* We don't want that 2 threads do a parallel
171: * indexing of the same shape file...
172: */
173: boolean alreadyRunning = true;
174: Object sync = null;
175:
176: if (this .fileName == null) {
177: throw new IOException("You have to set a shape file name!");
178: }
179:
180: File file = new File(this .fileName);
181:
182: if (!file.canWrite())
183: return 0;
184:
185: synchronized (IDX_CREATION) {
186: sync = IDX_CREATION.get(this .fileName);
187:
188: if (sync == null) {
189: sync = Thread.currentThread().getName();
190: IDX_CREATION.put(this .fileName, sync);
191: alreadyRunning = false;
192: }
193: }
194:
195: /*
196: * If another thread is running wait for index completition
197: */
198: if (alreadyRunning) {
199: try {
200: LOGGER
201: .fine("Waiting for index build completition by thread "
202: + sync);
203:
204: long start = System.currentTimeMillis();
205:
206: while ((IDX_CREATION.get(this .fileName) != null)
207: && ((System.currentTimeMillis() - start) < MAX_WAIT_TIME)) {
208: synchronized (sync) {
209: sync.wait(MIN_WAIT_TIME);
210: }
211: }
212:
213: if (IDX_CREATION.get(this .fileName) != null) {
214: throw new TreeException(
215: "Max wait time for index build "
216: + "reached!");
217: }
218:
219: return 0;
220: } catch (InterruptedException ie) {
221: throw new TreeException(
222: "Interrupted during wait for index " + "build");
223: }
224: }
225:
226: int cnt = 0;
227:
228: try {
229: if (!RTREE.equals(this .idxType)
230: && !QUADTREE.equals(this .idxType)) {
231: throw new TreeException("Index type must be " + RTREE
232: + " or " + QUADTREE);
233: }
234:
235: FileInputStream is = new FileInputStream(file);
236: FileChannel channel = is.getChannel();
237: ShapefileReader reader = null;
238: String ext = this .fileName.substring(this .fileName
239: .lastIndexOf('.'));
240: String rtreeName = this .fileName.substring(0, this .fileName
241: .lastIndexOf('.'));
242:
243: // Temporary file for building...
244: File treeFile = new File(rtreeName + ".bld");
245:
246: try {
247: reader = new ShapefileReader(channel, true, false, lock);
248:
249: if (!ext.equalsIgnoreCase(".shp")) {
250: throw new TreeException(
251: "The file to index must have "
252: + "'.shp' extension");
253: }
254:
255: // Build index name
256: if (this .idxType.equals(RTREE)) {
257: rtreeName += (ext.equals(".shp") ? ".grx" : ".GRX");
258: } else if (this .idxType.equals(QUADTREE)) {
259: rtreeName += (ext.equals(".shp") ? ".qix" : ".QIX");
260: }
261:
262: // Delete temporary file if exists
263: if (treeFile.exists()) {
264: if (!treeFile.delete()) {
265: throw new TreeException("Unable to delete "
266: + treeFile
267: + " cannot create a new index!");
268: }
269: }
270:
271: if (this .idxType.equals(RTREE)) {
272: cnt = this .buildRTree(reader, treeFile, verbose);
273: } else if (this .idxType.equals(QUADTREE)) {
274: cnt = this .buildQuadTree(reader, treeFile, verbose);
275: }
276: } finally {
277: if (reader != null)
278: reader.close();
279: if (is != null)
280: is.close();
281: }
282:
283: // Final index file
284: File finalFile = new File(rtreeName);
285: boolean copied = false;
286:
287: // Delete file if exists
288: if (finalFile.exists()) {
289: if (!finalFile.delete()) {
290: try {
291: copyFile(treeFile, finalFile);
292: copied = true;
293: } catch (IOException ie) {
294: throw new TreeException("Unable to delete "
295: + treeFile
296: + " cannot commit the new index!");
297:
298: }
299: }
300: }
301:
302: if (!copied && !treeFile.renameTo(finalFile)) {
303: throw new TreeException("Unable to rename " + treeFile
304: + " to " + finalFile
305: + " cannot commit the new index!");
306: }
307: } finally {
308: if (!alreadyRunning) {
309: synchronized (sync) {
310: IDX_CREATION.remove(this .fileName);
311: sync.notifyAll();
312: }
313: }
314: }
315:
316: return cnt;
317: }
318:
319: /**
320: * Copy data from source file to destination file.
321: *
322: * @param source source file
323: * @param dest destination file
324: */
325: private static void copyFile(File source, File dest)
326: throws IOException {
327: if (!dest.exists()) {
328: dest.createNewFile();
329: }
330: InputStream in = null;
331: OutputStream out = null;
332: try {
333: in = new FileInputStream(source);
334: out = new FileOutputStream(dest);
335:
336: // Transfer bytes from in to out
337: byte[] buf = new byte[1024];
338: int len;
339: while ((len = in.read(buf)) > 0) {
340: out.write(buf, 0, len);
341: }
342: } finally {
343: if (in != null) {
344: in.close();
345: }
346: if (out != null) {
347: out.close();
348: }
349: }
350: }
351:
352: /**
353: * DOCUMENT ME!
354: *
355: * @param reader
356: * @param rtreeFile
357: * @param verbose
358: *
359: *
360: * @throws TreeException
361: * @throws LockTimeoutException
362: * @throws IOException
363: */
364: private int buildRTree(ShapefileReader reader, File rtreeFile,
365: boolean verbose) throws TreeException,
366: LockTimeoutException, IOException {
367: DataDefinition keyDef = new DataDefinition("US-ASCII");
368: keyDef.addField(Integer.class);
369: keyDef.addField(Long.class);
370:
371: FileSystemPageStore fps = new FileSystemPageStore(rtreeFile,
372: keyDef, this .max, this .min, this .split);
373: RTree rtree = new RTree(fps);
374:
375: Record record = null;
376: Data data = null;
377:
378: int cnt = 0;
379:
380: while (reader.hasNext()) {
381: record = reader.nextRecord();
382: data = new Data(keyDef);
383: data.addValue(new Integer(++cnt));
384: data.addValue(new Long(record.offset()));
385:
386: rtree.insert(new Envelope(record.minX, record.maxX,
387: record.minY, record.maxY), data);
388:
389: if (verbose && ((cnt % 500) == 0)) {
390: System.out.print('.');
391: }
392: }
393:
394: rtree.close();
395:
396: return cnt;
397: }
398:
399: private int buildQuadTree(ShapefileReader reader, File file,
400: boolean verbose) throws IOException, StoreException {
401: byte order = 0;
402:
403: if ((this .byteOrder == null)
404: || this .byteOrder.equalsIgnoreCase("NM")) {
405: order = IndexHeader.NEW_MSB_ORDER;
406: } else if (this .byteOrder.equalsIgnoreCase("NL")) {
407: order = IndexHeader.NEW_LSB_ORDER;
408: } else {
409: throw new StoreException("Asked byte order '"
410: + this .byteOrder + "' must be 'NL' or 'NM'!");
411: }
412:
413: String ext = this .fileName.substring(this .fileName
414: .lastIndexOf('.'));
415:
416: String idxFileName = this .fileName.substring(0, this .fileName
417: .length() - 4)
418: + (ext.equals(".shp") ? ".shx" : ".SHX");
419:
420: FileInputStream fisIdx = new FileInputStream(idxFileName);
421: FileChannel channelIdx = fisIdx.getChannel();
422: IndexFile shpIndex = new IndexFile(channelIdx);
423: QuadTree tree = null;
424: int cnt = 0;
425: try {
426: int numRecs = shpIndex.getRecordCount();
427: ShapefileHeader header = reader.getHeader();
428: Envelope bounds = new Envelope(header.minX(),
429: header.maxX(), header.minY(), header.maxY());
430:
431: tree = new QuadTree(numRecs, max, bounds, shpIndex);
432:
433: Record rec = null;
434:
435: while (reader.hasNext()) {
436: rec = reader.nextRecord();
437: tree.insert(cnt++, new Envelope(rec.minX, rec.maxX,
438: rec.minY, rec.maxY));
439:
440: if (verbose && ((cnt % 1000) == 0)) {
441: System.out.print('.');
442: }
443: if (cnt % 100000 == 0)
444: System.out.print('\n');
445: }
446: if (verbose)
447: System.out.println("done");
448: } finally {
449: channelIdx.close();
450: fisIdx.close();
451: shpIndex.close();
452: }
453: FileSystemIndexStore store = new FileSystemIndexStore(file,
454: order);
455: store.store(tree);
456:
457: return cnt;
458: }
459:
460: /**
461: * DOCUMENT ME!
462: *
463: * For quad tree this is the max depth. I don't know what it is for RTree
464: *
465: * @param i
466: */
467: public void setMax(int i) {
468: max = i;
469: }
470:
471: /**
472: * DOCUMENT ME!
473: *
474: * @param i
475: */
476: public void setMin(int i) {
477: min = i;
478: }
479:
480: /**
481: * DOCUMENT ME!
482: *
483: * @param s
484: */
485: public void setSplit(short s) {
486: split = s;
487: }
488:
489: /**
490: * DOCUMENT ME!
491: *
492: * @param string
493: */
494: public void setShapeFileName(String string) {
495: fileName = string;
496: }
497:
498: /**
499: * DOCUMENT ME!
500: *
501: * @param idxType The idxType to set.
502: */
503: public void setIdxType(String idxType) {
504: this .idxType = idxType;
505: }
506:
507: /**
508: * DOCUMENT ME!
509: *
510: * @param byteOrder The byteOrder to set.
511: */
512: public void setByteOrder(String byteOrder) {
513: this.byteOrder = byteOrder;
514: }
515: }
|