rtree.java

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

      //find the leaf that contains the element
      Node delNode;
      if(fileHdr.isWriteThr())
        delNode = findLeaf(new Node(fileHdr.getFile(),fileName,root,fileHdr),elmt);
      else
        delNode = findLeaf(chdNodes.getNode(fileHdr.getFile(),fileName,root,fileHdr),elmt);
      //if found...
      if(delNode != null){
        Element[] elmts = delNode.getAllElements();//all the elements
        int totElmts = delNode.getTotalElements();//total elements
        //index of the desired element
        int childIndex = Node.NOT_DEFINED;
        //find the index of the element that has to be deleted
        for(int i=0;i<totElmts;i++){
          if(elmts[i].getRect().encloses(elmt.getRect()) && (elmts[i].getPtr() == elmt.getPtr())){
            childIndex = i;
            break;
          }
        }
        //strange, but the element is not found....impossible!
        if(childIndex == Node.NOT_DEFINED)
          throw new ElementNotFoundException("RTree.delete: Element not in tree");
        delNode.deleteElement(childIndex, false);
        Stack stack = new Stack();
        condenseTree(delNode,stack);
        //find the root
        Node rootNode;
        if(fileHdr.isWriteThr())
          rootNode = new Node(fileHdr.getFile(),fileName,fileHdr.getRootIndex(),
                              fileHdr);
        else
          rootNode = chdNodes.getNode(fileHdr.getFile(),fileName,fileHdr.getRootIndex(),
                                      fileHdr);
        //if root has only one element then make the node pointed by the
        //element as the new root
        if((rootNode.getTotalElements() == 1) && (rootNode.getElementType() == Node.NONLEAF_NODE)){
          long childPtr= rootNode.getElement(0).getPtr();
          Node child;
          if(fileHdr.isWriteThr())
            child = new Node(fileHdr.getFile(),fileName, childPtr,fileHdr);
          else
            child = chdNodes.getNode(fileHdr.getFile(),fileName, childPtr,fileHdr);
          //set as the new root
          child.setParent(Node.NOT_DEFINED);
          //delete the original parent
          rootNode.deleteNode();
        }
      }
      else
        throw new ElementNotFoundException("RTree.delete: Element not in tree");
    }
    catch(Exception e){
      if(e instanceof ElementNotFoundException)
        throw (ElementNotFoundException)e;
      throw new  RTreeException("RTree.delete: "+e.getMessage());
    }
    finally{
      fileHdr.unlock();
    }
  }

  private void condenseTree(Node node,Stack stack)
    throws Exception
  {
    //is the parent node
    if(node.getParent() == Node.NOT_DEFINED){
      while(!stack.empty()){
        Node nd = (Node)stack.pop();
        Vector v = trvsRPost(nd,true);
        for(int i=0;i<v.size();i++)
          insert((LeafElement)v.elementAt(i));
      }
      return;
    }
    //get the parent
    Node parentN;
    if(fileHdr.isWriteThr())
      parentN = new Node(fileHdr.getFile(),fileName,node.getParent(),fileHdr);
    else
      parentN = chdNodes.getNode(fileHdr.getFile(),fileName,node.getParent(),fileHdr);
    //get the parent element of 'node'.
    //Integer intValue = new Integer(node.getNodeIndex());
    int parentElmtIdx = parentN.getElementIndex(node.getNodeIndex()/*intValue*/);
    //delete parent element if node has less than 'm' elements
    if(node.getTotalElements() < Node.MIN){
      parentN.deleteElement(parentElmtIdx, false);
      stack.push(node);
    }
    else{//if ok
      parentN.modifyElement(parentElmtIdx,node.getNodeMBR());
    }
    condenseTree(parentN,stack);
  }
    
  /**Basically it returns the node that <b>may</b> contain the required element.
   */
  private Node findLeaf(Node node,LeafElement elmt)
    throws  IllegalValueException,FileNotFoundException,IOException, NodeReadException, NodeWriteException
  {
    if((node == null) || (elmt == null))
      throw new  IllegalValueException("RTree.findLeaf: Node is null");
    Node nd = null;
    Element[] allElmt = node.getAllElements();
    int totElements = node.getTotalElements();
    //Integer elmtPtr = (Integer)elmt.getPtr();
    for(int i=0; i<totElements; i++){//for every element
      //select elements that overlap
      if(!allElmt[i].getRect().disjoint(elmt.getRect())){//intersect
        //Integer nxtIndex = (Integer)allElmt[i].getPtr();
        if(allElmt[i].getElementType() == Node.NONLEAF_NODE){//non leaf
          if(fileHdr.isWriteThr())
            nd = findLeaf(new Node(fileHdr.getFile(),fileName, allElmt[i].getPtr(),fileHdr),elmt);
          else
            nd = findLeaf(chdNodes.getNode(fileHdr.getFile(),fileName, allElmt[i].getPtr(),fileHdr),elmt);
          if(nd != null)
            return nd;
        }
        else{
          //if any of the leaf element matches then check for exact 
          //match with passed element, also check for the pointer
          //value so that elements are excactly match.
          if(allElmt[i].getRect().equals(elmt.getRect()) && (allElmt[i].getPtr() == elmt.getPtr()))
            return node;
        }
      }
    }
    return null;
  }
  //-----------------------------------------------------------------------
  /**
   * Find all index records whose MBR overlap a search MBR 'rect'. - <b>Guttman the Great</b>.
   * 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 synchronized Vector overlaps(Rect rect)
    throws  RTreeException,FileNotFoundException
  {
    fileHdr.lockRead();
    //System.out.println("RTree.overlaps : in for thread " + Thread.currentThread().toString());
    long root;
    if(rect ==  null)
      throw new  RTreeException("RTree.overlaps: Rect is null");
    root = fileHdr.getRootIndex();
    try{
      Node node = chdNodes.getReadNode(fileHdr.getFile(),fileName,root, fileHdr);
      Vector ret = getRPostOvrlap(node, rect);
      return ret;
      //return(getRPostOvrlap(chdNodes.getNode(fileHdr.getFile(),fileName,root, fileHdr), rect));
    }
    catch(Exception e){
      throw new RTreeException("RTree.overlaps: "+e.getMessage());
    }
    finally{
      //System.out.println("RTree.overlaps : out for thread " + Thread.currentThread().toString());
      fileHdr.unlock();
    }
  }
  /**
     Given any node it traverses a tree in a recursive post order manner
     fetching all overlaping elements in the leaves.
  */
  private Vector getRPostOvrlap(Node node, Rect rect)
    throws  IllegalValueException,FileNotFoundException,NodeReadException,IOException, NodeWriteException
  {
    if((node == null) || (rect == null))
      throw new  IllegalValueException("RTree.getRPostOvrlap: Node is null");
    Vector list = new Vector();
    //System.out.println("Nodes visited:"+node.getNodeIndex());
    Element[] elmts = node.getAllElements();
    int totElements = node.getTotalElements();
    for(int i=0; i<totElements; i++){//for every element; we can use sweepline algorithm here
      if(elmts[i].getRect().overlaps(rect)){ //select elements that overlap
        if(elmts[i].getElementType() == Node.NONLEAF_NODE){//non leaf
          //Integer ndIndex = (Integer)elmts[i].getPtr();
          list.addAll(getRPostOvrlap(chdNodes.getReadNode(fileHdr.getFile(),fileName,elmts[i].getPtr(),
                                                          fileHdr),rect));
        }else{//if leaf element
          list.addElement(elmts[i]);
        }
      }
    }
    return list;
  }
  public synchronized Vector overlapsSweep(Rect rect)
    throws  RTreeException,FileNotFoundException
  {
    fileHdr.lockRead();
    long root;
    if(rect ==  null)
      throw new  RTreeException("RTree.overlaps: Rect is null");
    root = fileHdr.getRootIndex();
    try{
      return getRPostOvrlapSweep(chdNodes.getReadNode(fileHdr.getFile(),fileName,root, fileHdr), rect);
    }
    catch(Exception e){
      e.printStackTrace();
      throw new  RTreeException("RTree.overlaps: "+e.getMessage());
    }
    finally{
      fileHdr.unlock();
    }
  }
  private Vector getRPostOvrlapSweep(Node node, Rect rect)
    throws  IllegalValueException,FileNotFoundException,NodeReadException,IOException, NodeWriteException
  {
    if((node == null) || (rect == null))
      throw new  IllegalValueException("RTree.getRPostOvrlap: Node is null");
    Vector list = new Vector();
    //System.out.println("Nodes visited:"+node.getNodeIndex());
    Element[] elmts = node.getAllElements();
    int totElements = node.getTotalElements();
    SweepLine spLine = new SweepLine(new IntersectPred());
    //System.out.println("RTree.getRPostOvrlapSweep : calling sweep");
    List pairs = spLine.intersects(rect, elmts);
    //System.out.println("RTree.getRPostOvrlapSweep : called..and now for every pair");

    for(int i=0; i<pairs.size(); i++){//for every element; we can use sweepline algorithm here
      Element intElmt = ((PairElmt)pairs.get(i)).getRtElmt();
      if(intElmt.getElementType() == Node.NONLEAF_NODE){//non leaf
        list.addAll(getRPostOvrlapSweep(chdNodes.getReadNode(fileHdr.getFile(),fileName,intElmt.getPtr(),
                                                             fileHdr),rect));
        //System.out.println("RTree.getRPostOvrlapSweep : total objects NONLEAF " + list.size());
      }
      else{//if leaf element
        list.addElement(intElmt);
        //System.out.println("RTree.getRPostOvrlapSweep : total objects LEAF " + list.size());
      }
    }
    //System.out.println("RTree.getRPostOvrlapSweep : checked pairs as well");
    return list;
  }
  //-----------------------------------------------------------------------
  /**
     Find all index records whose MBR intsersect a search MBR 'rect'.
     The diff. betn. this method and 'overlap' method is that this method returns
     all rectangle that is in any way in touch with the test rectangle 'rect'.
     In method 'overlap' only the rects that have common area with 'rect'
     are returned but unlike this method it does not return rects that have
     common side with '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 nonDisjoint(Rect rect)
    throws  RTreeException,FileNotFoundException
  {
    fileHdr.lockRead();
    long root;
    if(rect ==  null)
      throw new  RTreeException("RTree.nonDisjoint: Rect is null");
    root = fileHdr.getRootIndex();
    try{
      return(getRPostIntsect(chdNodes.getReadNode(fileHdr.getFile(),fileName,root,fileHdr), rect));
    }
    catch(Exception e){
      throw new  RTreeException("RTree.nonDisjoint: "+e.getMessage());
    }
    finally{
      fileHdr.unlock();
    }
  }
  /**
     Given any node it traverses a tree in a recursive post order manner
     fetching all intersecting elements in the leaves.
  */
  private Vector getRPostIntsect(Node node, Rect rect)
    throws  IllegalValueException,FileNotFoundException,NodeReadException,IOException, NodeWriteException
  {
    if((node == null) || (rect == null))
      throw new  IllegalValueException("RTree.getRPostIntsect: Node is null");
    Vector list = new Vector();
    //System.out.println("Nodes visited:"+node.getNodeIndex());
    Element[] elmts = node.getAllElements();
    int totElements = node.getTotalElements();
    for(int i=0; i<totElements; i++){//for every element
      if(!elmts[i].getRect().disjoint(rect)){//select elements that overlap
        if(elmts[i].getElementType() == Node.NONLEAF_NODE){//non leaf
          //Integer ndIndex = (Integer)elmts[i].getPtr();
          list.addAll(getRPostIntsect(chdNodes.getReadNode(fileHdr.getFile(),fileName,elmts[i].getPtr(),
                                                           fileHdr),rect));
        }
        else{//if leaf element
          list.addElement(elmts[i]);
        }
      }
    }
    return list;
  }

  //-----------------------------------------------------------------------
  /**Find all index records whose MBR are enclosed by 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 containedBy(Rect rect)
    throws  RTreeException,FileNotFoundException
  {
    fileHdr.lockRead();
    long root;
    if(rect ==  null)
      throw new  RTreeException("RTree.containedBy: Rect is null");