node.java

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

    elementSize = elmtSz;
    elementType = elmtTp;
  }
  /**
     will return the index of the node.
  */
  public long getNodeIndex()//for new nodes
  {
    return(nodeIndex);
  }
  private void refreshNode()//see wherever it is called from for writethr
    throws IOException
  {
    try{
      byte[] data = new byte[NODE_SIZE];
      seekCurrNode();
      //read the whole node
      file.read(data);
      //get the header details into the variables
      DataInputStream ds = new DataInputStream(new ByteArrayInputStream(data));
      totalElements = ds.readInt();
      parent = ds.readLong();//ds.readInt();
      elementSize = ds.readInt();
      elementType = ds.readInt();
      if(totalElements <= 0)//set local variable
        return;
      //  else
      //    isNodeEmpty = false;
      //get the elements if present
      if(totalElements < 1)
        return;
      nodeMBR = new Rect();//remove
      int minX,minY,maxX,maxY;
      for(int i=0; i< totalElements; i++){
        //read the points
        minX = ds.readInt();
        minY = ds.readInt();
        maxX = ds.readInt();
        maxY = ds.readInt();
        Rect rectangle = new Rect(minX,minY,maxX,maxY);
        nodeMBR.expandToInclude(rectangle);//remove
        if(elementType == LEAF_NODE){// modified see [1]
          long ptr = ds.readLong();
          elements[i] = new LeafElement(rectangle,ptr);
        }else if(elementType == NONLEAF_NODE){//if non leaf type then...
          long nodePtr = ds.readLong();
          elements[i] = new NonLeafElement(rectangle,nodePtr);
        }
      }
      ds.close();
    }
    catch(Exception e){
      throw new IOException("Node.refreshNode : Can't read from node header " + e.getMessage());
    }
        
  }
  Rect[] getAllRectangles()
    throws  IllegalValueException
  {
    if(totalElements == 0)
      throw new  IllegalValueException("Node.getAllRectangles: No elements in the node");
    Rect[] rects = new Rect[totalElements];
    for(int i=0; i<totalElements; i++){
      rects[i] = elements[i].getRect();
    }
    return rects;
  }
  /**
     Returns the element(of the current node) whose rectangle needs the least 
     enlargment to include <code>elmt</code>.
     The logic assumes that the elements are not sorted.
     See the documentation for least enlargement logic.
  */
  public Element getLeastEnlargement(Element elmt)
    throws NodeEmptyException, IllegalValueException, NodeWriteException
  {
    if(elmt == null)
      throw new  IllegalValueException("Node.getBestFitElement : Element is null");
    //if(isNodeEmpty){//if there are no elements in the node
    if(totalElements <= 0){//if there are no elements in the node
      throw new NodeEmptyException("Node.getBestFitElement : Node does not have any elements");
    }
    if(fileHdr.isWriteThr())
      RTree.chdNodes.remove(fileName,nodeIndex);
    Element retElmt;//initialize with first element         
    int area;
        
    //get area of first MBR and call it the least area
    int leastArea=(elements[0].getRect().getResultingMBR(elmt.getRect())).getArea();
    leastArea -= elements[0].getRect().getArea(); 
    if(elementType == Node.LEAF_NODE)
      //Integer intVal = (Integer)elements[0].getPtr();//the org. code
      retElmt = new LeafElement(elements[0].getRect(), elements[0].getPtr() );
    else
      retElmt = new NonLeafElement(elements[0].getRect(), elements[0].getPtr());
        
    //now check each of the elements
    for(int i=1; i < totalElements; ++i){
      //get area of the MBR of the two rects.
      area=(elements[i].getRect().getResultingMBR(elmt.getRect())).getArea();
      //remove the area of the encapsulating rect.
      area -= elements[i].getRect().getArea();
      //check if it is the smallest rect
      if(leastArea > area){
        leastArea = area;
        if(elementType == Node.LEAF_NODE)
          retElmt = new LeafElement(elements[i].getRect(), elements[i].getPtr());
        else
          retElmt = new NonLeafElement(elements[i].getRect(), elements[i].getPtr());
      }
      else if(leastArea == area){//Resovle ties by choosing the entry with the rectangle of smallest area."
        if(retElmt.getRect().getArea() >= elements[i].getRect().getArea()){
          leastArea = area;
          if(elementType == Node.LEAF_NODE)
            retElmt = new LeafElement(elements[i].getRect(), elements[i].getPtr());
          else
            retElmt = new NonLeafElement(elements[i].getRect(),elements[i].getPtr());
        }
      }
    }
    return(retElmt);
  }
  /**
     @return a boolean describing whether there is space for another element
  */
  boolean isInsertPossible()
  {
    if(totalElements >= MAX)
      return false;
    else
      return true;
  }

  /**
     See ./Logic.txt
     Linear split Algo.
     February 1003 - Now quad split algo.
     @return First node would be the original node.Second would be the new one.
     @param Element The new element to be inserted
     @param slotIndex The index of the slot of this tree if any, else give NOT_DEFINED.
  */
  public Node[] splitNode(Element elmtM1, long slotIndex)
    throws RTreeException, NodeWriteException
  {
    if((totalElements < MAX) || (elmtM1.getElementType() != elementType))
      throw new RTreeException("Node.splitNode: Node is not full or new element is of wrong type");
    if(fileHdr.isWriteThr())
      RTree.chdNodes.remove(fileName,nodeIndex);
    try{        
      int rem = totalElements+1;//no. of elements remaining + the new element
      Element[] elmtPlusOne = new Element[rem];
      for(int i=0;i<rem-1;i++)
        elmtPlusOne[i] = elements[i];
      elmtPlusOne[totalElements] = elmtM1; 
      //the elements which have been allocated: 1 - present, 0 - absent
      int[] elmtsGone = new int[rem];
      for(int i=0; i<elmtsGone.length; ++i)
        elmtsGone[i] = 1;//all elements present
      int elmtsInA = 0;//total elements in A
      int elmtsInB = 0;//total elements in B
      Rect mbrA;
      Rect mbrB;
      //int[] seeds = lnrPickSeeds(elmtPlusOne);//the two seed
      int[] seeds = quadPickSeeds(elmtPlusOne);//the two seed
      int elmtType = elmtPlusOne[0].getElementType();
      //never do any file read or write on the old node now as the new nodes
      //could very well be the old node from the free list.
      //Although they would be freed explicitly later.
      Node nodeA, nodeB;
      if(fileHdr.isWriteThr()){
        nodeA = new Node(file,fileName,parent,elmtType,fileHdr);
        nodeB = new Node(file,fileName,parent,elmtType,fileHdr);
      }else{
        nodeA = RTree.chdNodes.getNode(file,fileName,parent,elmtType,fileHdr);
        nodeB = RTree.chdNodes.getNode(file,fileName,parent,elmtType,fileHdr);
      }
      nodeA.insertElement(elmtPlusOne[seeds[0]]);
      nodeB.insertElement(elmtPlusOne[seeds[1]]);
      //update the MBRs
      mbrA = elmtPlusOne[seeds[0]].getRect();
      mbrB = elmtPlusOne[seeds[1]].getRect();
      //update the variables
      elmtsInA++;//Inc. 'A' count by 1
      elmtsGone[seeds[0]] = 0;//mark the element assigned
      elmtsInB++;//Inc. 'B' count by 1
      elmtsGone[seeds[1]] = 0;//mark the element assigned
      rem -= 2;//less the no. of elements still left
      //a loop till the elements last
      while(rem > 0){
        //if A needs all to equate m then give it all the elements - see Guttman
        if((Node.MIN - elmtsInA) == rem){
          for(int i=0; i < elmtsGone.length; i++){
            //check if the elmt. is already assigned
            if(elmtsGone[i] == 1){
              nodeA.insertElement(elmtPlusOne[i]);//read  variable
              elmtsGone[i] = 0;//element now is absent
              elmtsInA++;
              rem--;
              //find the new MBR fro A
              /*Commented because not required
                mbrA = Rect.getResultingMBR(mbrA,elmtPlusOne[i].getRect());
              */
              //the end of the loop and method
            }
          }
        }
        //if B needs all to equate m then give it all the elements-see Guttman
        else if((Node.MIN - elmtsInB) == rem){
          for(int i=0; i < elmtsGone.length; i++){
            //check if the elmt. is already assigned
            if(elmtsGone[i] == 1){
              nodeB.insertElement(elmtPlusOne[i]);//read  variable
              elmtsGone[i] = 0;//element now is absent
              elmtsInB++;
              rem--;
              //find the new MBR fro B
              /*Commented because not required
                mbrB = Rect.getResultingMBR(mbrB,elmtPlusOne[i].getRect());
              */
              //the end of the loop and method
            }
          }
        }
        //if both are ok
        else{
          int i=-1;
          //loop till an unassigned element is found
          try{
            while((++i<elmtsGone.length)&&(elmtsGone[i] == 0));
          }catch(Exception e){
            System.out.println("Node.splitNode: trouble in paradise");
            //System.exit(1);
          }
          /*Above statement can be troublesome, in that case use the 
            below logic
            for(int i=0; i < elmtsGone.length; i++)
            if(elmtsGone[i] == 0)
            break;
          */
          //find MBR for both the groups
          Rect newMBRA = elmtPlusOne[i].getRect().getResultingMBR(mbrA);
          Rect newMBRB = elmtPlusOne[i].getRect().getResultingMBR(mbrB);
          //remove the original area
          int newAreaA = newMBRA.getArea() - mbrA.getArea();
          int newAreaB = newMBRB.getArea() - mbrB.getArea();
          //find which group to enter - see - 'Guttman(QS3)
          //A needs least enlargement
          if (newAreaA < newAreaB){
            nodeA.insertElement(elmtPlusOne[i]);//read local variable
            elmtsGone[i] = 0;//element now is absent
            elmtsInA++;
            rem--;
            mbrA = newMBRA;
          }
          //B needs least enlargement
          else if(newAreaA > newAreaB){
            nodeB.insertElement(elmtPlusOne[i]);//read local variable
            elmtsGone[i] = 0;//element now is absent
            elmtsInB++;
            rem--;
            mbrB = newMBRB;
          }
          //if equal but A is smaller
          else if(mbrA.getArea() < mbrB.getArea()){
            nodeA.insertElement(elmtPlusOne[i]);//read local variable
            elmtsGone[i] = 0;//element now is absent
            elmtsInA++;
            rem--;
            mbrA = newMBRA;
          }
          //if equal but B is smaller
          else if(mbrA.getArea() > mbrB.getArea()){
            nodeB.insertElement(elmtPlusOne[i]);//read local variable
            elmtsGone[i] = 0;//element now is absent
            elmtsInB++;
            rem--;
            mbrB = newMBRB;
          }
          //also equal in area elmts. in A are less 
          else if(elmtsInA < elmtsInB){
            nodeA.insertElement(elmtPlusOne[i]);//read local variable
            elmtsGone[i] = 0;//element now is absent
            elmtsInA++;
            rem--;
            mbrA = newMBRA;
          }
          //also equal in area elemts. in B are less
          else if(elmtsInA > elmtsInB){
            nodeB.insertElement(elmtPlusOne[i]);//read local variable
            elmtsGone[i] = 0;//element now is absent
            elmtsInB++;
            rem--;
            mbrB = newMBRB;
          }
          //choose any one
          else{
            nodeA.insertElement(elmtPlusOne[i]);//read local variable
            elmtsGone[i] = 0;//element now is absent
            elmtsInA++;
            rem--;
            mbrA = newMBRA;
          }
        }
      }
      /*
        Adjust the parent element so that it points to the first nodeA.
      */
      if(parent != slotIndex){//NOT_DEFINED){
        Node parentN = null;
        if(fileHdr.isWriteThr())
          parentN = new Node(file,fileName,parent,fileHdr);
        else
          parentN = RTree.chdNodes.getNode(file,fileName,parent,fileHdr);
        if(fileHdr.isWriteThr())
          RTree.chdNodes.remove(fileName,parent);
        //get the parent element of nodes[0]
        int parentElmtIndex = parentN.getElementIndex(nodeIndex);
        parentN.modifyElement(parentElmtIndex, nodeA.getNodeIndex());
      }
      Node[] ret = new Node[2];
      ret[0] = nodeA;
      ret[1] = nodeB;
      deleteNode();
      return(ret);
    }catch(Exception e){
      e.printStackTrace();
      throw new RTreeException("Node.nodeSplit : " + e.getMessage());
    }
  }
  /**
   * The linear Pick Seed method from Guttman.
   * Assuming that we have only 2 dimensions.
   * <br>this method is no longer used (certainly not deprecated), instead <code>quadPickSeeds</code>
   * is being used
   * @return the two picked indexes from the node
   */
  private int[] lnrPickSeeds(Element[] elmts)
    throws  IllegalValueException
  {
    if(elmts.length <= 1)
      throw new  IllegalValueException("Node.lnrPickSeed : PickSeed not possible as there are no elements");
    //find the MBR of the set.
    Rect mbr = elmts[0].getRect();
    for(int i=1; i<elmts.length; ++i)
      mbr = elmts[i].getRect().getResultingMBR(mbr);
    //"Find Extreme Rectangles along all dimensions" - Guttman
    //find the highest low side and lowest high side.
    int hlsX = Integer.MIN_VALUE;//highest low side for X
    int hlsY = Integer.MIN_VALUE;//  ..
    int lhsX = Integer.MAX_VALUE;//  ..
    int lhsY = Integer.MAX_VALUE;//  ..
    int hlsIdxX = Integer.MAX_VALUE;//highest low side index for X
    int hlsIdxY = Integer.MAX_VALUE;//  ..
    int lhsIdxX = Integer.MAX_VALUE;//  ..
    int lhsIdxY = Integer.MAX_VALUE;//  ..

    for(int i=0; i<elmts.length; ++i){
      //highest low side for X
      if(elmts[i].getRect().getMinX() >= hlsX){
        hlsX = elmts[i].getRect().getMinX();
        hlsIdxX = i;
      }
      //highest low side for Y
      if(elmts[i].getRect().getMinY() >= hlsY){
        hlsY = elmts[i].getRect().getMinY();
        hlsIdxY = i;
      }
      //lowest high side for X
      if(elmts[i].getRect().getMaxX() <= lhsX){
        lhsX = elmts[i].getRect().getMaxX();
        lhsIdxX = i;