rtree.java

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

    root = fileHdr.getRootIndex();
    try{
      return(getRPostContBy(chdNodes.getReadNode(fileHdr.getFile(),fileName,root,fileHdr), rect));
    }
    catch(Exception e){
      throw new  RTreeException("RTree.containedBy: "+e.getMessage());
    }
    finally{
      fileHdr.unlock();
    }
  }
  /**
     Given any node it traverses a tree in a recursive post order manner
     fetching all the enclosed(inside 'rect') elements in the leaves.
  */
  private Vector getRPostContBy(Node node, Rect rect)
    throws  IllegalValueException,FileNotFoundException,NodeReadException,IOException, NodeWriteException
  {
    if((node == null) || (rect == null))
      throw new  IllegalValueException("RTree.getRPostContBy: Node is null");
    Vector list = new Vector();
    Element[] elmts = node.getAllElements();
    int totElements = node.getTotalElements();
    //System.out.println("Nodes visited:"+node.getNodeIndex());
    for(int i=0; i<totElements; i++){//for every element  //encloses
      if(rect.overlaps(elmts[i].getRect())){//select elements that overlap
        if(elmts[i].getElementType() == Node.NONLEAF_NODE){//non leaf
          //Integer ndIndex = (Integer)elmts[i].getPtr();
          list.addAll(getRPostContBy(chdNodes.getReadNode(fileHdr.getFile(),fileName,elmts[i].getPtr(),
                                                          fileHdr),rect));
        }
        else{//if leaf element
          if(elmts[i].getRect().containedBy(rect))
            list.addElement(elmts[i]);
        }
      }
    }
    return list;
  }
  //-----------------------------------------------------------------------
  /**Find all index records whose MBR are geometrically equal to MBR 'rect'
     An Vector is returned. The tree is traversed recusively in post order.
     @return If the file is empty or search rect. is out of scope then the 
     method returns a zero size vector.
  */
  public Vector equal(Rect rect)
    throws  RTreeException,
    FileNotFoundException
  {
    fileHdr.lockRead();
    long root;
    if(rect ==  null)
      throw new  RTreeException("RTree.equal: Rect is null");
    root = fileHdr.getRootIndex();
    try{
      return(getRPostEqual(chdNodes.getReadNode(fileHdr.getFile(),fileName,root,fileHdr), rect));
    }
    catch(Exception e){
      throw new  RTreeException("RTree.equal: "+e.getMessage());
    }
    finally{
      fileHdr.unlock();
    }
  }
  /**
     Given any node it traverses a tree in a recursive post order manner
     fetching all the enclosed(inside 'rect') elements in the leaves.
  */
  private Vector getRPostEqual(Node node, Rect rect)
    throws  IllegalValueException,FileNotFoundException,NodeReadException,IOException, NodeWriteException
  {
    if((node == null) || (rect == null))
      throw new  IllegalValueException("RTree.getRPostEqual: Node is null");
    Vector list = new Vector();
    Element[] elmts = node.getAllElements();
    int totElements = node.getTotalElements();
    //System.out.println("Nodes visited:"+node.getNodeIndex());
    for(int i=0; i<totElements; i++){//for every element  //encloses
      if(rect.overlaps(elmts[i].getRect())){//select elements that overlap
        if(elmts[i].getElementType() == Node.NONLEAF_NODE){//non leaf
          //Integer ndIndex = (Integer)elmts[i].getPtr();
          list.addAll(getRPostEqual(chdNodes.getReadNode(fileHdr.getFile(),fileName,elmts[i].getPtr(),
                                                         fileHdr),rect));
                    
        }
        else{//if leaf element
          if(elmts[i].getRect().equals(rect))
            list.addElement(elmts[i]);
        }
      }
    }
    return list;
  }
  //-----------------------------------------------------------------------
  /**Find all index records whose MBR meet on the sides of MBR 'rect'.
     An Vector is returned. The tree is traversed recusively in post order.
     @return If the file is empty or search rect. is out of scope then the 
     method returns a zero size vector.
  */
  public Vector meet(Rect rect)
    throws  RTreeException,FileNotFoundException
  {
    fileHdr.lockRead();
    long root;
    if(rect ==  null)
      throw new  RTreeException("RTree.meet: Rect is null");
    root = fileHdr.getRootIndex();
    try{
      return(getRPostMeet(chdNodes.getReadNode(fileHdr.getFile(),fileName,root,fileHdr),  rect));
    }
    catch(Exception e){
      throw new  RTreeException("RTree.meet: "+e.getMessage());
    }
    finally{
      fileHdr.unlock();
    }
  }
  /**
     Given any node it traverses a tree in a recursive post order manner
     fetching all the enclosed(inside 'rect') elements in the leaves.
  */
  private Vector getRPostMeet(Node node,Rect rect)
    throws  IllegalValueException, FileNotFoundException,NodeReadException,IOException, NodeWriteException
  {
    if((node == null) || (rect == null))
      throw new  IllegalValueException("RTree.meet: Node is null");
    Vector list = new Vector();
    Element[] elmts = node.getAllElements();
    int totElements = node.getTotalElements();
    //System.out.println("Nodes visited:"+node.getNodeIndex());
    for(int i=0; i<totElements; i++){//for every element  //encloses
      if(!rect.disjoint(elmts[i].getRect())){//select elements that overlap
        if(elmts[i].getElementType() == Node.NONLEAF_NODE){//non leaf
          //Integer ndIndex = (Integer)elmts[i].getPtr();
          list.addAll(getRPostMeet(chdNodes.getReadNode(fileHdr.getFile(),fileName, elmts[i].getPtr() ,
                                                        fileHdr),rect));
        }
        else{//if leaf element
          if(elmts[i].getRect().meet(rect))
            list.addElement(elmts[i]);
        }
      }
    }
    return list;
  }
  //----------------------------------------------------------------------
  /**Find all index records whose MBR enclose/contain the MBR 'rect'.
     An Vector is returned. The tree is traversed recusively in post order.
     @return If the file is empty or search rect. is out of scope then the 
     method returns a zero size vector.
  */
  public Vector contains(Rect rect)
    throws  RTreeException,FileNotFoundException
  {
    fileHdr.lockRead();
    long root;
    if(rect ==  null)
      throw new  RTreeException("RTree.contains: Rect is null");
    root = fileHdr.getRootIndex();
    try{
      return(getRPostContains(chdNodes.getReadNode(fileHdr.getFile(),fileName,root,fileHdr),rect));
    }
    catch(Exception e){
      throw new  RTreeException("RTree.contains: " +e.getMessage());
    }
    finally{
      fileHdr.unlock();
    }
  }
  /**
     Given any node it traverses a tree in a recursive post order manner
     fetching all the enclosed(inside 'rect') elements in the leaves.
  */
  private Vector getRPostContains(Node node, Rect rect)
    throws  IllegalValueException,FileNotFoundException,NodeReadException,IOException, NodeWriteException
  {
    if((node == null) || (rect == null))
      throw new  IllegalValueException("RTree.getRPostContains: Node is null");
    Vector list = new Vector();
    Element[] elmts = node.getAllElements();
    int totElements = node.getTotalElements();
    //System.out.println("Nodes visited:"+node.getNodeIndex());
    for(int i=0; i<totElements; i++){//for every element  //encloses
      if(rect.overlaps(elmts[i].getRect())){//select elements that overlap
        if(elmts[i].getElementType() == Node.NONLEAF_NODE){//non leaf
          //Integer ndIndex = (Integer)elmts[i].getPtr();
          list.addAll(getRPostContains(chdNodes.getReadNode(fileHdr.getFile(),fileName,elmts[i].getPtr(),
                                                            fileHdr),rect));
        }
        else{//if leaf element
          if(elmts[i].getRect().contains(rect))
            list.addElement(elmts[i]);
        }
      }
    }
    return list;
  }
  //-----------------------------------------------------------------------
  /**
     Returns all the elements traversing the tree recursively in <b>postorder</b>
  */
  public Vector getAllElements()
    throws  RTreeException, FileNotFoundException
  {
    //fileHdr.enter(Node.READ);
    fileHdr.lockRead();
    //System.out.println("RTree.getAllElements : in for thread " + Thread.currentThread().toString());
    long root;
    root = fileHdr.getRootIndex();
    try{
      return(trvsRPost(chdNodes.getReadNode(fileHdr.getFile(),fileName,root,fileHdr),false));
    }
    catch(Exception e){
      //e.printStackTrace();
      throw new RTreeException("RTree.getAllElements: " +e.getMessage());
    }
    finally{
      //fileHdr.leave();
      //System.out.println("RTree.getAllElements : out for thread " + Thread.currentThread().toString());
      fileHdr.unlock();
    }
  }
  /**
     Traverses the tree recursively in post order.
     The second parameter is for the delete method. As it goes through the nodes 
     returning the leafelements it also deletes the nodes.
     This feature is not required for any other methods hence set <code>del</code> as 
     <code>false</code> for all other cases.
  */
  private Vector trvsRPost(Node node,boolean del)
    throws  IllegalValueException,FileNotFoundException,NodeReadException,IOException, NodeWriteException
  {
    if((node == null))
      throw new  IllegalValueException("RTree.getRPostOvrlap: Node is null");
    Vector list = new Vector();
    Element[] elmts = node.getAllElements();
    int totElements = node.getTotalElements();
    //System.out.println("Nodes visited:"+node.getNodeIndex())
    for(int i=0; i<totElements; i++){//for every element
      //non leaf
      if(elmts[i].getElementType()==Node.NONLEAF_NODE){
        //Integer ndIndex = (Integer)elmts[i].getPtr();
        list.addAll(trvsRPost(chdNodes.getReadNode(fileHdr.getFile(),fileName,elmts[i].getPtr(), fileHdr),
                              del));
      }
      else{//if leaf element
        list.addElement(elmts[i]);
      }
    }
    if(del)
      node.deleteNode();
    return list;
  }
  //-------------------------------------------------------------------
  /**Prints the tree in recursively <b>preorder</b> manner.
   */
  public void printTree()
    throws  RTreeException,FileNotFoundException
  {
    fileHdr.lockRead();
    long root;
    root = fileHdr.getRootIndex();
    try{
      trvsRPrePrint(chdNodes.getReadNode(fileHdr.getFile(),fileName,root,fileHdr));
    }
    catch(Exception e){
      throw new  RTreeException("RTree.printTree: "+e.getMessage());
    }
    finally{
      fileHdr.unlock();
    }
  }
  /**
     This method will return MBR of the whole tree.
  */
  public Rect getTreeMBR()
  {
    fileHdr.lockRead();
    long root;
    try{
      root = fileHdr.getRootIndex();
      Node node = chdNodes.getReadNode(fileHdr.getFile(),fileName,root,fileHdr);
      return node.getNodeMBR();
    }
    catch(Exception e){
      return null;
    }
    finally{
      fileHdr.unlock();
    }
  }
  public void deleteAllElements()
    throws RTreeException
  {
    fileHdr.lockWrite();
    try{
      chdNodes.removeAll();
      fileHdr.resetHeader();
    }catch(Exception e){
      throw new RTreeException("RTree.deleteAllElements : " + e.getMessage());
    }