rtree.java

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

    finally{
      fileHdr.unlock();
    }
  }

  /**
     Traverses the tree recursively in post order.
  */
  private void trvsRPrePrint(Node node)
    throws  IllegalValueException,
    FileNotFoundException,NodeReadException,
    IOException,NodeWriteException
  {
    if((node == null))
      throw new  IllegalValueException("RTree.trvsRPrePrint: Node is null");
    Vector list = new Vector();
    Element[] elmts = node.getAllElements();
    int totElements = node.getTotalElements();
    System.out.println(node.toString());
    for(int i=0; i<totElements; i++){//for every element
      if(elmts[i].getElementType() == Node.NONLEAF_NODE){//non leaf
        //Integer ndIndex = (Integer)elmts[i].getPtr();
        trvsRPrePrint(chdNodes.getReadNode(fileHdr.getFile(),fileName,elmts[i].getPtr(),fileHdr));
      }
    }
    return;
  }
  //-----------------------------------------------------------------------
  /**
     <b>Read Me Well.</b><br>
     The Nearest Neighbour(NN) search from Roussopoulos and Cheung.
     <br>The returned leaf elements are sorted in ascending order of their 
     differences from the query point. <br><b>If the no. of leaf elements found 
     are less then <code>n</code>, then the rest of the values in the returend array
     are null.<br></b>Give the limit(distance) within which you want to search. 
     The limit is in the same unit as the coordinates of the MBRs. <p>There may
     be some objects in the tree which come within the region but are so big 
     that their size makes them extend much beyond the given region.
     Such objects would also be considered.
     If you do not want any limit then give <code>Long.MAX_VALUE</code> in <code>range</code>.
     You can also search for presence of any object at the given point by giving
     <code>range</code> as <code>0</code>.
     Also required are the no. of objects that need to be fetched(N-Nearest objects).
     <br><b>The value of <code>range</code> is actually square of the distance you want. 
     Therefor if you want to search in an area of 10cm, give the <code>range</code> as 100.</b>
     @param pt the query point.
     @param range the region within which you want to search. 
     @param n the number of objects required.
     @return the leaf elements found near the point.The length of the returned 
     array would be equal to <code>n</code>.
  */
  public ABL[] nearestSearch(Point pt,long range,int n)
    throws  RTreeException, IllegalValueException
  {
    fileHdr.lockRead();
    if((pt == null) || (range < 0) || (n <= 0))
      throw new  IllegalValueException("RTree.nearestSearch: Illegal arguments");
    try{
      long root = fileHdr.getRootIndex();
      ABL[] elmts = new ABL[n];
      Nearest nrstDist = new Nearest();
      nrstDist.value = range;
      return INNSearch(chdNodes.getReadNode(fileHdr.getFile(),fileName,root,fileHdr),pt, elmts,nrstDist);
    }
    catch( IllegalValueException e){
      throw new IllegalValueException(e.getMessage());
    }
    catch(Exception e){
      throw new RTreeException("RTree.nearestSearch: " +e.getMessage());
    }
    finally{
      fileHdr.unlock();
    }
  }
  /**
     Improved Nearest Neighbour Search - Cheung, theory Roussopoulos
  */
  private ABL[] INNSearch(Node node, Point pt,ABL[] nrstElements,Nearest nrstDist)
    throws  IllegalValueException,FileNotFoundException,IOException,NodeReadException, 
    RTreeException,NodeWriteException
  {
    if((node == null))
      throw new  IllegalValueException("RTree.INNSearch: Node is null");
    Element[] elmts = node.getAllElements();
    int totElements = node.getTotalElements();
        
    if(totElements == 0)//no elements
      return null;
    //System.out.println("In Node:"+node.getNodeIndex());
    //if leaf
    if(node.getElementType() == Node.LEAF_NODE){
      //at leaf level compute distance to actual objects
      for(int i=0; i<totElements; i++){
        long lfDist = Rect.minDist(pt,elmts[i].
                                   getRect());
        if(lfDist <= nrstDist.value){//assign the new nearest value
          //Integer index = (Integer)elmts[i].getPtr();
          ABL newElmt =  new ABL(new LeafElement(elmts[i].getRect(),elmts[i].getPtr()), lfDist);
          insertArray(nrstElements,newElmt,nrstDist);
        }
      }
      return nrstElements;
    }
    //if non-leaf
    else{
      //the Active Branch List
      ABL[] abl = new ABL[totElements];
      //calculate MINDIST and assign to the ABL array
      for(int i=0; i<abl.length; i++){
        //Integer ndIndex = (Integer)elmts[i].getPtr();
        abl[i] = new ABL(new NonLeafElement(elmts[i].getRect(),elmts[i].getPtr()),
                         Rect.minDist(pt,elmts[i].getRect()));
      }
      //sort the ABL
      abl[0].mergeSort(abl);
      //upward prun the branch
      for(int i=0; i<abl.length; i++){
        if(abl[i].minDist <= nrstDist.value){
          //Integer ndIndex = (Integer)abl[i].element.getPtr();
          nrstElements = INNSearch(chdNodes.getReadNode(fileHdr.getFile(),fileName,elmts[i].getPtr(),
                                                        fileHdr),pt,nrstElements,nrstDist);
        }
      }
      return nrstElements;
    }//else
  }//INNSearch
  /**
     A utility method for the search algorithm that inserts an element into the
     the correct position and adjusts the array accordingly.
     Assumes that the new 'element' is lesser than the last element of 'arr'.
  */
  protected void insertArray(ABL[] arr,ABL elmt,Nearest nrstDist)
    throws  RTreeException
  {
    try{
      ABL temp=null,temp1=null;
      //int nNearest = 0;
      int i=arr.length-1;
      //if the first or the only element to enter
      if((arr[0] == null) || (arr.length == 1))
        arr[0] = (ABL)elmt.clone();
      else{
        while((i < arr.length) && (i >= 0)){
          if(arr[--i] != null){
            if((arr[i].minDist <= elmt.minDist) || 
               ((i == 0)&&(elmt.minDist<arr[i].minDist))){//special case
              if((i==0)&&(elmt.minDist<arr[i].minDist))//special case
                i--;
              temp = elmt;//the element to insert
              //shift all elements one place right
              while(++i < (arr.length)){
                if(arr[i] != null){//if next is not null
                  temp1 = arr[i];//backup
                  arr[i] = (ABL)temp.clone();//replace
                  temp = temp1;//for the next loop
                }
                else{
                  arr[i] = (ABL)temp.clone();
                  break;
                }
              }
              break;
            }
          }
        }
      }
            
      //if last element is null(arr is not full) then that means that more 
      //elements can be accepted in the given region. Thus do not change 
      //the min. distance. Else the last element will be the min. - every 
      //element that comes after must have a value less than that.
      if(arr[arr.length-1] != null)
        nrstDist.value = arr[arr.length-1].minDist; 
    }
    catch(Exception e){
      throw new  RTreeException("RTree.insertArray: "+e.getMessage());
    }
  }
  //-------------------------------------------------------------------------
  /**Another version of the <code>nearestSearch</code> method(not overloaded). This 
     method finds all the objects within the given range.<b> To understand 
     this method please refer to the other <code>nearestSearch</code> method.</b>
     <br>When the no. of objects required is less then a few thousands, this 
     method would be many <b>times</b> slower than the above method. 
     If possible use the other method.
     @return vector of ABL objects within the given range.
  */
  public Vector nearestSearch(Point pt,long range)
    throws  RTreeException, IllegalValueException
  {
    fileHdr.lockRead();
    if((pt == null) || (range < 0))
      throw new  IllegalValueException("RTree.nearestSearch: "
                                       +"Point null or int less than one");
    try{
      long root = fileHdr.getRootIndex();
      Vector elmts = new Vector();
      elmts = INNSearch(chdNodes.getReadNode(fileHdr.getFile(),fileName,root,fileHdr),pt,elmts,range);
      return elmts;
    }
    catch( IllegalValueException e){
      throw new  IllegalValueException(e.getMessage());
    }
    catch(Exception e){
      throw new  RTreeException("RTree.nearestSearch: " + e.getMessage());
    }
    finally{
      fileHdr.unlock();
    }
  }
  private Vector INNSearch(Node node, Point pt, Vector  nrstElements,long nrstDist)
    throws  IllegalValueException, FileNotFoundException,IOException,NodeReadException, Exception
  {
    if((node == null))
      throw new  IllegalValueException("RTree.INNSearch: Node is null");
    Element[] elmts = node.getAllElements();
    int totElements = node.getTotalElements();
        
    if(totElements == 0)//no elements
      return null;
    //System.out.println("In Node:"+node.getNodeIndex());
    //if leaf
    if(node.getElementType() == Node.LEAF_NODE){
      //at leaf level compute distance to actual objects
      for(int i=0; i<totElements; i++){
        long lfDist = Rect.minDist(pt,elmts[i].
                                   getRect());
        if(lfDist <= nrstDist){//assign the new nearest value
          //Integer index = (Integer)elmts[i].getPtr();
          ABL newElmt =  new ABL(new LeafElement(elmts[i].getRect(),elmts[i].getPtr()),lfDist);
          //insert into vector
          int j=0;
          //the following line is doubtful 
          for(j = 0;
              (j < nrstElements.size()) && 
                (((ABL)(nrstElements.elementAt(j))).minDist<=newElmt.minDist);
              j++);
          nrstElements.insertElementAt(newElmt,j);
        }
      }
      return nrstElements;
    }
    //if non-leaf
    else{
      //the Active Branch List
      ABL[] abl = new ABL[totElements];
      //calculate MINDIST and assign to the ABL array
      for(int i=0; i<abl.length; i++){
        //Integer ndIndex = (Integer)elmts[i].getPtr();
        abl[i] = new ABL(new NonLeafElement(elmts[i].getRect(),elmts[i].getPtr()),
                         Rect.minDist(pt,elmts[i].getRect()));
      }
      //sort the ABL
      abl[0].mergeSort(abl);
      //upward prun the branch
      for(int i=0; i<abl.length; i++){
        if(abl[i].minDist <= nrstDist){
          //Integer ndIndex = (Integer)abl[i].element.getPtr();
          nrstElements = INNSearch(chdNodes.getReadNode(fileHdr.getFile(),fileName,elmts[i].getPtr(),
                                                        fileHdr), pt,nrstElements,nrstDist);
        }
      }
      return nrstElements;
    }//else
  }//NNSearch
  
  /**
     this class is a wrapper class for a <code>long</code> value. There is no way to overwrite
     the value contained in the <code>java.lang.Long</code> wrapper class.
  */
  protected class Nearest//a wrapper class for long
  {
    public long value;
  }
  //--------------------------------get height------------------------------
  /**Upto 5 lakh objectes we can have a maximum height of 3
     TODO : Calculate other levels as well. One may need to know whether the tree is packed or unpacked for
     this.
     `*/
  public synchronized int getHeight()
  {
    int totNodes = fileHdr.getTotalNodes();
    if(totNodes <= 1)
      return 1;
    else if(totNodes <= 170)
      return 2;
    else //if((totNodes > (84*84)) && (totNodes < (169*169+1)))
      return 3;
    //    else
    //return 4;
  }
}
/* TODO:
   Immediate Improvements
   1)Take the common code from each query methods and put them in a single method.
   2)Make a way of retuning a Integer objects other than LeafElement Objects.
*/