spatialindextest.java

R-Tree Java implementations 结构清晰

//   SpatialIndexTest.java
//   Java Spatial Index Library
//   Copyright (C) 2002 Infomatiq Limited
//   Copyright (C) 2008 Aled Morris <[e-mail]>
//  
//  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; either
//  version 2.1 of the License, or (at your option) any later version.
//  
//  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.
//  
//  You should have received a copy of the GNU Lesser General Public
//  License along with this library; if not, write to the Free Software
//  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307 USA

package com.infomatiq.jsi.test;

import java.io.File;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.FileOutputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.LineNumberReader;
import java.io.PrintWriter;
import java.text.DecimalFormat;
import java.text.SimpleDateFormat;
import java.util.Date;
import java.util.Iterator;
import java.util.List;
import java.util.Properties;
import java.util.Random;
import java.util.StringTokenizer;

import junit.framework.TestCase;

import org.apache.log4j.Logger;

import com.infomatiq.jsi.Point;
import com.infomatiq.jsi.Rectangle;
import com.infomatiq.jsi.SpatialIndex;

/**
 * SpatialIndexTest
 * 
 * @author  [e-mail]
 * @version 1.0b2p1
 */
public class SpatialIndexTest extends TestCase {
  
  private static final Logger log = 
    Logger.getLogger(SpatialIndexTest.class.getName());
    
  protected static final Logger intersectPerformanceLog = 
    Logger.getLogger("intersectPerformance");
  
  protected static final Logger containsPerformanceLog = 
    Logger.getLogger("containsPerformance");
  
  protected static final Logger nearestPerformanceLog = 
    Logger.getLogger("nearestPerformance");
    
  protected static final Logger addPerformanceLog = 
    Logger.getLogger("addPerformance");
  
  protected static final Logger deletePerformanceLog = 
    Logger.getLogger("deletePerformance");
    
  protected static final int PERFORMANCE_TEST = 0;
  protected static final int REFERENCE_COMPARISON_TEST = 1;
  protected static final int REFERENCE_GENERATE = 2;
  
  public SpatialIndexTest(String s) {
    super(s);
  }
  
  private void writeOutput(String outputLine, PrintWriter outputFile, LineNumberReader referenceFile) {
   try {
      outputFile.println(outputLine);
      outputFile.flush();
      if (referenceFile != null) { 
        String referenceLine = referenceFile.readLine();
        if (!outputLine.equals(referenceLine)) {
          log.error("Output does not match reference on line " + referenceFile.getLineNumber());
          log.error(" Reference result: " + referenceLine);
          log.error(" Test result:      " + outputLine);
          assertTrue("Output does not match reference on line " + referenceFile.getLineNumber(), false);
        }
      }
    }  catch (IOException e) {
       log.error("IOException while writing test results");
    }  
  }
  
  private Rectangle getRandomRectangle(Random r, float scale) {
    float x1 = (float) (r.nextGaussian() * scale);
    float y1 = (float) (r.nextGaussian() * scale);
    float x2 = x1 + (float) (r.nextGaussian() * 100);
    float y2 = y1 + (float) (r.nextGaussian() * 100);
    
    return new Rectangle(x1, y1, x2, y2);
  }
              
  /**
   * @return Time taken to execute method, in milliseconds.
   */
  protected long runScript(String indexType, Properties indexProperties, String testId, int testType) {
    if (log.isDebugEnabled()) {
      log.debug("runScript: " + indexType + ", testId=" + testId + 
               ", minEntries=" + indexProperties.getProperty("MinNodeEntries") + 
               ", maxEntries=" + indexProperties.getProperty("MaxNodeEntries") + 
               ", treeVariant=" + indexProperties.getProperty("TreeVariant"));
    }
    
    SpatialIndex si = SpatialIndexFactory.newInstance(indexType, indexProperties);
    
    ListDecorator ld = null;
    
    // Don't sort the results if we are testing the performance
    if (testType == PERFORMANCE_TEST) {
      ld = new ListDecorator(si); 
    } else {
      ld = new SortedListDecorator(si);
    } 
    
    Random random = new Random();
    DecimalFormat df = new DecimalFormat();
    df.setMinimumFractionDigits(4);
    df.setMaximumFractionDigits(4);
    df.setMinimumIntegerDigits(7);
    df.setMaximumIntegerDigits(7);
    df.setPositivePrefix(" ");
    df.setGroupingUsed(false);
 
    String strTestInputRoot = "tests" + File.separator + "test-" + testId;
    String strTestResultsRoot = "test-results" + File.separator + "test-" + testId;
    
    // open test input file for read-only
    LineNumberReader inputFile = null;
    String inputFilename = strTestInputRoot + "-in";
    try {
      inputFile = new LineNumberReader(new InputStreamReader(new FileInputStream(inputFilename)));
    } catch (FileNotFoundException e) {
      log.error("Unable to open test input file " + inputFilename);
      assertTrue("Unable to open test input file " + inputFilename, false);
      return -1;
    }
    
    // open reference results file for read-only. Filename is of form:
    // test-testId-reference
    LineNumberReader referenceFile = null;
    if (testType == REFERENCE_COMPARISON_TEST) {
      String referenceFilename = strTestResultsRoot + "-reference";
      try {
        referenceFile = new LineNumberReader(new InputStreamReader(new FileInputStream(referenceFilename)));
      } catch (FileNotFoundException e) {
        log.error("Unable to open reference test results file " + referenceFilename);
        assertTrue("Unable to open reference test results file " + referenceFilename, false);
        return -1;
      }
    }
   
    // open actual results file for writing. Filename is of form
    // test-testId-indexType-revision-datetime, unless generating reference results.
    PrintWriter outputFile = null;
    if (testType == REFERENCE_COMPARISON_TEST || testType == REFERENCE_GENERATE) {
      String outputFilename = null;
      if (testType == REFERENCE_COMPARISON_TEST) {
        outputFilename = strTestResultsRoot + "-" + si.getVersion() + 
          "-" + new SimpleDateFormat("yyMMddHHmmss").format(new Date());
      } else {
        outputFilename = strTestResultsRoot + "-reference";
      }
      try {     
        outputFile = new PrintWriter(new FileOutputStream(outputFilename));
      } catch (FileNotFoundException e) {
        log.error("Unable to open test output results file " + outputFilename);
        assertTrue("Unable to open test output results file " + outputFilename, false);
        return -1;
      }
    }
    
    long scriptStartTime = System.currentTimeMillis();
    
    try {
      // read lines from the test input file
      while (inputFile.ready()) {
        String inputLine = inputFile.readLine();
        
        if (inputLine.startsWith("#")) {
          continue; 
        }
        
        StringBuffer outputBuffer = null;
        
        if (testType == REFERENCE_COMPARISON_TEST || testType == REFERENCE_GENERATE) {
          outputBuffer = new StringBuffer(inputLine);
        }
            
        StringTokenizer st = new StringTokenizer(inputLine);
        while (st.hasMoreTokens()) {
         String operation = st.nextToken().toUpperCase();
          if (operation.equals("RANDOMIZE")) {
            random.setSeed(Long.parseLong(st.nextToken()));
            if (testType == REFERENCE_COMPARISON_TEST || testType == REFERENCE_GENERATE) {
              writeOutput(outputBuffer.toString() + " : OK", outputFile, referenceFile);
            }
          } else if (operation.equals("ADDRANDOM")) {
            int count = Integer.parseInt(st.nextToken());
            int startId = Integer.parseInt(st.nextToken());
            float scale = Float.parseFloat(st.nextToken());
            
            if (testType == REFERENCE_COMPARISON_TEST || testType == REFERENCE_GENERATE) {
              writeOutput(outputBuffer.toString(), outputFile, referenceFile);
            }
            
            long startTime = System.currentTimeMillis();
               
            for (int id = startId; id < startId + count; id++) {
              Rectangle r = getRandomRectangle(random, scale);
              si.add(r, id);
            
              if (testType == REFERENCE_COMPARISON_TEST || testType == REFERENCE_GENERATE) {
                String outputLine = "  " + id + " " + r.toString() + " : OK";
                writeOutput(outputLine, outputFile, referenceFile);
              }
            }
            long time = System.currentTimeMillis() - startTime;
            if (log.isDebugEnabled()) {
              log.debug("Added " + count + " entries in " + time +  "ms (" + time / (float) count + " ms per add)");
            }
            if (testType == PERFORMANCE_TEST) {
               addPerformanceLog.info(indexType + "," + 
                                            testId + "," + 
                                            indexProperties.getProperty("MinNodeEntries") + "," + 
                                            indexProperties.getProperty("MaxNodeEntries") + "," + 
                                            indexProperties.getProperty("TreeVariant") + "," +
                                            si.size() + "," + 
                                            count + "," + 
                                            (float) time / (float) count);
            }
          } else if (operation.equals("DELETERANDOM")) {
            int count = Integer.parseInt(st.nextToken());
            int startId = Integer.parseInt(st.nextToken());
            float scale = Float.parseFloat(st.nextToken());
            
            if (testType == REFERENCE_COMPARISON_TEST || testType == REFERENCE_GENERATE) {
              writeOutput(outputBuffer.toString(), outputFile, referenceFile);
            }
            
            long startTime = System.currentTimeMillis();
            
            int successfulDeleteCount = 0;   
            for (int id = startId; id < startId + count; id++) {
              Rectangle r = getRandomRectangle(random, scale);
              boolean deleted = si.delete(r, id);
             
              if (deleted) {
                successfulDeleteCount++;
              }
              
              if (testType == REFERENCE_COMPARISON_TEST || testType == REFERENCE_GENERATE) {
                String outputLine = "  " + id + " " + r.toString() + " : " + deleted;
                writeOutput(outputLine, outputFile, referenceFile);
              }
            }
            long time = System.currentTimeMillis() - startTime;
            if (log.isDebugEnabled()) {
              log.debug("Attempted to delete " + count + " entries (" + successfulDeleteCount + " successful) in " + time +  "ms (" + time / (float) count + " ms per delete)");
            }
            if (testType == PERFORMANCE_TEST) {