node.java

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

        //  else
        //    isNodeEmpty = true;
      }
    }catch(Exception e){
      System.out.println("Node.deleteElement : Error while updating "
                         +"local variable...reading back from file..");
      try{
        refreshNode();
        System.out.println("...successful");
      }catch(IOException ex){
        setDirty(true);
        System.out.println("..node corrupted, rebuild tree  ...quitting");
        throw new NodeWriteException("Node.deleteElement : Can't delete element");
      }
    }
  }
  /**to add an element at the end
     As elements are allocated to this node, each allocated 
     element's children node's parent are reset. This is simply because the
     new node index(for <code>elmt</code>) would be different from the old
     ones(if any). 
     <br>Note:-This again is for non leaf node only.
  */
  public void insertElement(Element elmt) 
    throws NodeWriteException, NodeFullException
  {
    //check for space
    if((totalElements == MAX))
      throw new NodeFullException("Node.insertElement: Node full");
    //check if it is an empty node or not
    //if(!isNodeEmpty){//if not empty
    if(totalElements > 0){//if not empty
      if(elmt.getElementType() != elementType)
        throw new NodeWriteException("Node.insertElement: Wrong element type");
      if(((totalElements+1)*elementSize) > NODE_BODY_SIZE)//no space left
        throw new NodeWriteException("Node.insertElement: Node size is becoming more than allowed");
      if(fileHdr.isWriteThr())
        RTree.chdNodes.remove(fileName,nodeIndex);
      writeLastElement(elmt);
    }
    else{//else set the header values depending upon the new object header
      writeLastElement(elmt);
    }
    //update the children's parents
    if( elmt.getElementType() == Node.NONLEAF_NODE ){
      try{
        Node child = null;
        if(fileHdr.isWriteThr()){
          child = new Node(file, fileName, elmt.getPtr(), fileHdr);
          RTree.chdNodes.remove(fileName, child.getNodeIndex());
        }
        else{
          child = RTree.chdNodes.getNode(file, fileName, elmt.getPtr(), fileHdr);
        }
        child.setParent(nodeIndex);
      }
      catch(Exception e){
        throw new NodeWriteException("Node.insertElement: " + e.getMessage());
      }
    }
  }
  /**
     This func. writes the element to the last position.
     It also takes care of updating the node header.
     Also updates the local variables.
     Also takes care whether it is the first element in the node or not.
     If it is the first element then it sets the node header accordingly.
      
     Least error checking - use it with care.
     If the node is old and the new element type is of different type then it
     will change the node header to the new type - so be very very careful!
     In short don't call this method to insert an element different from the
     already present element type.
  */
  private void writeLastElement(Element elmt)
    throws NodeWriteException
  {
    //taking backup in case of rollback
    int oldElementSize = elementSize;
    int oldElementType = elementType;
    int oldTotalElements = totalElements;
    //boolean oldIsNodeEmpty = isNodeEmpty;
    if(fileHdr.isWriteThr())
      RTree.chdNodes.remove(fileName,nodeIndex);
    try{
      //setting local variables first
      if(elmt instanceof LeafElement){
        //size of the element
        elementSize = LeafElement.sizeInBytes();
        elementType = LEAF_NODE;
      }
      else{
        //size of the element
        elementSize = NonLeafElement.sizeInBytes();
        elementType = NONLEAF_NODE;
      }
      if(fileHdr.isWriteThr()){
        //byte[] data = new byte[elementSize];
        ByteArrayOutputStream bs = new ByteArrayOutputStream(elementSize);
        DataOutputStream ds =  new DataOutputStream(bs);
        ds.writeInt(elmt.getRect().getMinX());
        ds.writeInt(elmt.getRect().getMinY());
        ds.writeInt(elmt.getRect().getMaxX());
        ds.writeInt(elmt.getRect().getMaxY());
        ds.writeLong(elmt.getPtr());//see [2] - replace elements with elmt
        
        bs.flush();
        ds.flush();
        //write to the file
        seekLastElement();//uses var.
        file.write(bs.toByteArray());
        setDirty(false);
      }else
        setDirty(true);
      //write the node header
      writeNodeHeader(nodeIndex,totalElements+1,parent,elementSize,elementType);
      //local variables
      //isNodeEmpty = false;
      elements[totalElements-1] = elmt;
      nodeMBR.expandToInclude(elmt.getRect());//remove
    }
    catch(Exception e){
      //e.printStackTrace();
      //if anything goes wrong then set 'totalElements' will not
      //be set hence it remains '0'
      elementSize = oldElementSize;
      elementType = oldElementType;
      totalElements = oldTotalElements;
      //isNodeEmpty = oldIsNodeEmpty;
      throw new 
        NodeWriteException("Node.writeLastElement: Can't write element to file"); 
    }
  }

  /**to add more than one element at the end.
     As elements are allocated to this node, each allocated element's children node's parent are reset.
     This is simply because the new node index(for <code>elmts</code>) would be different from the old
     ones(if any). none of the element should be null.
     <br><b>Note:-</b> Giving <code>updateChldrn</code> <code>true</code> will not update the parent from
     cache, but would actually update the parent on disk.
     @param elmts The elements that are to be entered. None of them should be null.
     @param updateChldrn Whether to update the children. When we are moving from root to leaves,
     this should be false.
  */
  public void insertElement(Element[] elmts, boolean updateChldrn)
    throws NodeWriteException, NodeFullException
  {
    //check for space
    if(totalElements == MAX)
      throw new NodeFullException("Node.insertElement: Node full or not adequate space");
    //check if it is an empty node or not
    //if(!isNodeEmpty){//if not empty
    if(totalElements > 0){//if not empty
      if(elmts[0].getElementType() != elementType)
        throw new NodeWriteException("Node.insertElement: Wrong element type");
      if(((totalElements+elmts.length)*elementSize) > NODE_BODY_SIZE)//no space left
        throw new NodeWriteException("Node.insertElement: Node size is becoming more than allowed");
      if(fileHdr.isWriteThr())
        RTree.chdNodes.remove(fileName,nodeIndex);
      writeLastElements(elmts);
    }
    else{//else set the header values depending upon the new object header
      writeLastElements(elmts);
    }
    if(!updateChldrn)
      return;
    //update the children's parent from the disk and not the cache.
    if( elmts[0].getElementType() == Node.NONLEAF_NODE ){
      try{
        for(int i=0; i<elmts.length; i++){
          if(elmts[i].getPtr() == Node.NOT_DEFINED)
            continue;
          Node child = null;
          if(fileHdr.isWriteThr()){
            child = new Node(file, fileName, elmts[i].getPtr(), fileHdr);
            RTree.chdNodes.remove(fileName, child.getNodeIndex());
          }else
            child = RTree.chdNodes.getNode(file, fileName, elmts[i].getPtr(), fileHdr);
          //child = new Node(file, fileName, elmts[i].getPtr(), fileHdr);
          child.setParent(nodeIndex);
        }
      }catch(Exception e){
        e.printStackTrace();
        
        throw new NodeWriteException("Node.insertElement: " + e.getMessage());
      }
    }
  }
  /**
     This method helps in bulk loading.
     This func. writes the elements to the last position.
     It also takes care of updating the node header.
     Also updates the local variables.
     Also takes care whether these are the first elements in the node or not.
     If these <i>are</i> the first element then it sets the node header accordingly.

     Least error checking - use it with care.
     If the node is old and the new element type is of different type then it
     will change the node header to the new type - so be very very careful!
     In short don't call this method to insert an element different from the
     already present element type.
  */
  private void writeLastElements(Element[] elmts)
    throws NodeWriteException
  {
    //taking backup in case of rollback
    int oldElementSize = elementSize;
    int oldElementType = elementType;
    int oldTotalElements = totalElements;
    //boolean oldIsNodeEmpty = isNodeEmpty;
    if(fileHdr.isWriteThr())
      RTree.chdNodes.remove(fileName,nodeIndex);
    try{
      //setting local variables first
      if(elmts[0] instanceof LeafElement){
        //size of the element
        elementSize = LeafElement.sizeInBytes();
        elementType = LEAF_NODE;
      }
      else{
        //size of the element
        elementSize = NonLeafElement.sizeInBytes();
        elementType = NONLEAF_NODE;
      }
      ByteArrayOutputStream bs = null;
      DataOutputStream ds =  null;

      //write node header

      if(fileHdr.isWriteThr()){
        setDirty(false);
        bs = new ByteArrayOutputStream(Node.NODE_SIZE);
        ds =  new DataOutputStream(bs);
        writeNodeHeader(nodeIndex, totalElements+elmts.length, parent, elementSize, elementType, ds);
        //write the existing elements
        for(int i=0; i<oldTotalElements; i++){
          ds.writeInt(elements[i].getRect().getMinX());
          ds.writeInt(elements[i].getRect().getMinY());
          ds.writeInt(elements[i].getRect().getMaxX());
          ds.writeInt(elements[i].getRect().getMaxY());
          ds.writeLong(elements[i].getPtr());
        }
      }else{
        writeNodeHeader(nodeIndex, totalElements+elmts.length, parent, elementSize, elementType, ds);
        setDirty(true);
      }
      //write the new elements
      for(int i=0; i<elmts.length; i++){
        nodeMBR.expandToInclude(elmts[i].getRect());//remove
        elements[oldTotalElements+i] = elmts[i];
        if(fileHdr.isWriteThr()){
          ds.writeInt(elmts[i].getRect().getMinX());
          ds.writeInt(elmts[i].getRect().getMinY());
          ds.writeInt(elmts[i].getRect().getMaxX());
          ds.writeInt(elmts[i].getRect().getMaxY());
          ds.writeLong(elmts[i].getPtr());
        }
      }
      if(fileHdr.isWriteThr()){
        bs.flush();
        ds.flush();
        //write to the file
        seekNode(nodeIndex);
        file.write(bs.toByteArray());
      }
      //local variables
      //isNodeEmpty = false;
    }
    catch(Exception e){
      e.printStackTrace();
      //if anything goes wrong then set 'totalElements' will not
      //be set hence it remains '0'
      elementSize = oldElementSize;
      elementType = oldElementType;
      totalElements = oldTotalElements;
      //isNodeEmpty = oldIsNodeEmpty;
      try{
        writeNodeHeader(nodeIndex, totalElements+elmts.length, parent, elementSize, elementType);
      }catch(Exception ex){throw new NodeWriteException(ex.getMessage());}
      throw new NodeWriteException("Node.writeLastElement: Can't write element to file"); 
    }
  }

  /**this function simply places the file pointer, it does not check for any
     condition like placing the pointer beyond the end of file
  */
  private void seekCurrNode() throws IOException
  {
    file.seek(FILE_HDR_SIZE + (nodeIndex * NODE_SIZE));
  }
  /**seek the specified node*/
  private void seekNode(long nodeIdx) throws IOException
  {
    file.seek(FILE_HDR_SIZE + (nodeIdx * NODE_SIZE));
  }

  /**Seek the last element of the node. No checking*/
  private void seekLastElement() throws IOException
  {
    file.seek(FILE_HDR_SIZE + (nodeIndex * NODE_SIZE) 
              + (NODE_HDR_SIZE) +(elementSize * totalElements));
  }
  /**seek the specified element.No checking*/
  private void seekElement(int elmtIndex) throws IOException
  {
    file.seek(FILE_HDR_SIZE + (nodeIndex * NODE_SIZE) 
              + (NODE_HDR_SIZE) + (elementSize * elmtIndex));
  }
  /**seek the specified element's pointer.No checking*/
  private void seekElementPtr(int elmtIndex) throws IOException
  {
    file.seek(FILE_HDR_SIZE + (nodeIndex * NODE_SIZE) 
              + (NODE_HDR_SIZE) + (elementSize * elmtIndex)
              + Rect.sizeInBytes());
  }
  public int getElementType()
  {
    return elementType;
  }
  /**this func. writes the passed info to the current node's header.
     Also updates the local variables.
  */
  private void writeNodeHeader(long nodeIdx,int totElmt,long prnt,int elmtSz,int elmtTp)
    throws IOException, NodeWriteException
  {
    if(fileHdr.isWriteThr())
      RTree.chdNodes.remove(fileName,nodeIndex);
    if(fileHdr.isWriteThr()){
      ByteArrayOutputStream bs = new ByteArrayOutputStream(FILE_HDR_SIZE);
      DataOutputStream ds =  new DataOutputStream(bs);
      ds.writeInt(totElmt);//total elements
      ds.writeLong(prnt);//parent
      ds.writeInt(elmtSz);//element size 
      ds.writeInt(elmtTp);//element type 
      
      bs.flush();
      ds.flush();
      //write to the file
      seekNode(nodeIdx);
      file.write(bs.toByteArray());
      setDirty(false);
    }else
      setDirty(true);
    //update local variables
    totalElements = totElmt;
    parent = prnt;
    elementSize = elmtSz;
    elementType = elmtTp;
  }
  /**
     This method will write the node header into the <code>ds</code>. Will also update the local variables.
     It is assumed that the write pointer is correctly set in the o/p stream.
  */
  private void writeNodeHeader(long nodeIdx, int totElmt,long prnt,int elmtSz,int elmtTp, 
                               DataOutputStream ds)
    throws IOException, NodeWriteException
  {
    if(fileHdr.isWriteThr())
      RTree.chdNodes.remove(fileName,nodeIndex);
    if(fileHdr.isWriteThr()){
      ds.writeInt(totElmt);//total elements
      ds.writeLong(prnt);//parent
      ds.writeInt(elmtSz);//element size 
      ds.writeInt(elmtTp);//element type 
      ds.flush();
      setDirty(true);
    }else
      setDirty(true);
    //update local variables
    totalElements = totElmt;
    parent = prnt;