rtreedemo.java

移动对象空间数据库中索引r树源码,能在eclipse下直接运行.

//RTreeDemo.java
//  
//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.
package rtree;

import java.io.RandomAccessFile;
import java.util.Random;
import java.util.Vector;
import java.io.ByteArrayInputStream;
import java.io.DataInputStream;
import rtree.join.*;
import rtree.seeded.*;
import java.util.List;
import java.util.HashSet;
import java.util.ArrayList;

/**
	One can look at this class to understand the usage of RTree.
*/
public class rTreeDemo
{
  public static void main(String argv[])
  {
    //rTreeDemo rt = new rTreeDemo();
    new TreeThread();
  }
  public List tryJoin()
  {
    TreeThread tr = new TreeThread();    
    return tr.tryJoin();
  }
  public void setName(String name)
  {
    TreeThread.fileName = name;
  }
}

class TreeThread implements Runnable
{
  static String fileName = "c:\\temp.tree";
  static long seed = 1015395880;//1015395880431;
  static int h = 15000000;//2148460;//15000000;
  static int w = 6000000;//2757573;//6000000;
  Thread tree;
  //String tname;
  TreeThread()
  {
    for(int i=0; i<1; i++){
      tree = new Thread(this,Integer.toString(i));
      //  try{Thread.currentThread().sleep(3000);}
      //  catch(Exception e){System.out.println("shdb");}
      tree.start();
    }
  }
  public void run()
  {
    try{
      RTree rt = new RTree(fileName);
      //rt.printTree();
      //  entry(fileName);
      entryRand(fileName);
      //  rt.flush();
      
      //  HashSet set = new HashSet(list);
      //  System.out.println("rTreeDemo.run : size of set " + set.size());
      
      //rt.printTree();
      //overlapRR(fileName);

      //Pack pck = new Pack();
      //System.out.println("rTreeDemo : rt has before " + rt.getAllElements().size());
      //pck.packTree(rt, fileName);
      //System.out.println("rTreeDemo : rt has after " + rt.getAllElements().size());
      //rt.printTree();
      //  pck.packTree(rt, fileName);
      
      //pck.packTree(new RTree(fileName+"2"), fileName+"2");
      //trySeed("/tmp/seed.dat", new RTree(fileName));
      //System.out.println("rTreeDemo : height " + rt.getHeight());
      
      RTreeRead rd = new RTreeRead(fileName);
      rd.readSeq();
       
      //tryJoin();
    }
    catch(Exception e){
      try{
        e.printStackTrace();
      }catch(Exception ex){
        ex.printStackTrace();
      }
    }
    //tryOverlap();
    //tryCvr();
  }
  /**
     Enter records within l - 15000000 and w - 6000000
  */
  public  void entryRand(String fileName)
    throws Exception
  {
    Vector vct = new Vector(0);
    int ix,iy,xx,xy;//mIn,maX
    RTree rt = new RTree(fileName);
    Random rnd = new Random(seed);
    long start = System.currentTimeMillis();
    Rect rect = new Rect();

    //point data
    for(int i=0;i<2000; i++){
      iy = rnd.nextInt(h);//height
      ix = rnd.nextInt(w);//width
      LeafElement lf = new LeafElement(new Rect(ix,iy,ix,iy),218);
      rt.insert(lf);
      //rect.expandToInclude(lf.getRect());
      //vct.add((LeafElement)lf.clone());
    }
    
    //rectangles
    for(int i=0;i<30000; i++){
      iy = rnd.nextInt(h-2);//height
      ix = rnd.nextInt(w-2);//width
      xy = rnd.nextInt(h - iy);
      xx = rnd.nextInt(w - ix);
      LeafElement lf = new LeafElement(new Rect(ix,iy,ix+xx,iy+xy),218);
      rt.insert(lf);
      //rect.expandToInclude(lf.getRect());
      //vct.add((LeafElement)lf.clone());
    }
    
    for(int i=0;i<20000; i++){
      iy = rnd.nextInt(h);//height
      ix = rnd.nextInt(w);//width
      LeafElement lf = new LeafElement(new Rect(ix,iy,ix,iy),218);
      rt.insert(lf);
      //rect.expandToInclude(lf.getRect());
      //vct.add((LeafElement)lf.clone());
    }
    //rectangles
    for(int i=0;i<30000; i++){
      iy = rnd.nextInt(h-2);//height
      ix = rnd.nextInt(w-2);//width
      xy = rnd.nextInt(h - iy);
      xx = rnd.nextInt(w - ix);
      LeafElement lf = new LeafElement(new Rect(ix,iy,ix+xx,iy+xy),218);
      rt.insert(lf);
      rect.expandToInclude(lf.getRect());
      //vct.add((LeafElement)lf.clone());
    }
    //for(int i=0; i<vct.size(); i++){
    //System.out.println(i);
    //delete(fileName, (LeafElement)vct.get(i));
    //}
    //  RTreeRead rd = new RTreeRead(fileName);
    //  rd.readSeq();
    
    System.out.println("Entry over in ms : " +(System.currentTimeMillis()-start)
                       + " for thread " + Thread.currentThread());
  }
  //public
  public void entry(String fileName)
  {
    try{
      //Point data
      /*
        RTree rtree = new RTree(fileName);
        LeafElement lf1 = 
        new LeafElement(new Rect(4,3,4,3),218);
        LeafElement lf2 = 
        new LeafElement(new Rect(6,5,6,5),218);
        LeafElement lf3 = 
        new LeafElement(new Rect(5,6,5,6),218);
        LeafElement lf4 =
        new LeafElement(new Rect(7,2,7,2),218);
        rtree.insert(lf1);
        rtree.insert(lf2);
        rtree.insert(lf3);
        rtree.insert(lf4);
      */
      //BOXES
      long start = System.currentTimeMillis();      
      RTree rtree = new RTree(fileName);
      LeafElement lf1 = new LeafElement(new Rect(3,2,4,3),3243);//keep for join
      rtree.insert(lf1);
      rtree.delete(lf1);
      /*
      //getall(fileName);
      RTree rtree1 = new RTree(fileName);
      LeafElement lf2 = new LeafElement(new Rect(5,4,6,5),5465);
      //rtree1.insert(lf2);
            
      RTree rtree2 = new RTree(fileName);
      LeafElement lf3 = new LeafElement(new Rect(9,6,10,7),96107);
      //rtree2.insert(lf3);
            
      RTree rtree3 = new RTree(fileName);
      LeafElement lf4 = new LeafElement(new Rect(6,1,7,3),6173);//keep for join
      rtree3.insert(lf4);

      RTree rtree4 = new RTree(fileName);
      LeafElement lf5 = new LeafElement(new Rect(6,2,8,3),6283);
      //rtree4.insert(lf5);

      RTree rtree5 = new RTree(fileName);
      LeafElement lf6 = new LeafElement(new Rect(4,4,5,6),4456);
      //rtree5.insert(lf6);
      
      RTree rtree6 = new RTree(fileName);
      LeafElement lf7 = new LeafElement(new Rect(5,3,7,4),5374);
      //rtree6.insert(lf7);
                    
      RTree rtree7 = new RTree(fileName);
      LeafElement lf8 = new LeafElement(new Rect(9,5,10,6),95106);//keep for join
      rtree2.insert(lf8);

      LeafElement lf9 = new LeafElement(new Rect(1,2,2,3),1223);//keep for join
      rtree2.insert(lf9);
      */
      System.out.println("Time in ms:" +(System.currentTimeMillis()-start));
      System.out.println("Entry over");
    }
    catch(Exception e){
      e.printStackTrace();
      System.exit(1);
    }
  }
  /*
    Random rect queries
  */
  public  void overlapRR(String name)
    throws Exception
  {
    RTree rt = new RTree(name);
    int ix,iy,xx,xy;
    Random rnd = new Random(System.currentTimeMillis());
    for(int i=0;i<1;i++){
      iy = rnd.nextInt(h-2);//height
      ix = rnd.nextInt(w-2);//width
      xy = rnd.nextInt(h - iy);
      xx = rnd.nextInt(w - ix);
      long start4 = System.currentTimeMillis();
      Vector elmts = null;
      //  elmts = rt.overlaps(new Rect(ix,iy,ix+xx,iy+xy));
      //  System.out.println("Time in ms:" + (System.currentTimeMillis()-start4));
      //  System.out.println("Search result-Total elements:"+elmts.size());
      System.out.println("Sweep");
      start4 = System.currentTimeMillis();
      elmts = rt.overlapsSweep(new Rect(ix,iy,ix+xx,iy+xy));
      System.out.println("Time in ms:" + (System.currentTimeMillis()-start4));
      System.out.println("Search result-Total elements:"+elmts.size()); 
    }
  }
  /*
    Random point queries
  */
  public  void overlapRP(String name)
    throws Exception
  {
    RTree rt = new RTree(name);
    int ix,iy;
    Random rnd = new Random(System.currentTimeMillis());
    for(int i=0;i<10;i++){
      iy = rnd.nextInt(h);//height
      ix = rnd.nextInt(w);//width
      long start4 = System.currentTimeMillis();
      Vector elmts = rt.overlaps(new Rect(ix,iy,ix,iy));
      System.out.println("Time in ms:" +
                         (System.currentTimeMillis()-start4));
      System.out.println("Search result-Total elements:"+elmts.size());
      /*
        start4 = System.currentTimeMillis();
        elmts = rt.overlaps(new Rect(ix,iy,ix,iy));
        System.out.println("Time in ms:" +
        (System.currentTimeMillis()-start4));
        System.out.println("Search result-Total elements:"+elmts.size());
      */
    }
  }
  public  void getall(String name)
  {
    try{
      //get All elements
      RTree rt = new RTree(name);
            
      long start1 = System.currentTimeMillis();
      Vector elmts1 = rt.getAllElements();
      System.out.println("Time in ms:" +
                         (System.currentTimeMillis()-start1));
      System.out.println("Record fetched by "+
                         Thread.currentThread().getName()+
                         ": " + elmts1.size()); 
      /*
        start1 = System.currentTimeMillis();
        LinkedList elmts2 = rt.testgetAllElements();
        System.out.println("Time in ms:" +
        (System.currentTimeMillis()-start1));
        System.out.println("Record fetched: " + elmts2.size());
      */
      //for(int i=0; i<elmts2.length; i++)
      //System.out.println(elmts2[i].toString());

    }
    catch(Exception e){
      e.printStackTrace();
      System.exit(1);
    }
  }

  public  void overlap(String name,Rect rect)
  {
    try{
      //Test overlap
      RTree rt = new RTree(name);
      long start4 = System.currentTimeMillis();
      Vector elmts = rt.nonDisjoint(rect);
      System.out.println("Time in ms:" +
                         (System.currentTimeMillis()-start4));
      System.out.println("overlap Search -Total elements:"+elmts.size());