node.java

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

      }
      //lowest high side for Y
      if(elmts[i].getRect().getMaxY() <= lhsY){
        lhsY = elmts[i].getRect().getMaxY();
        lhsIdxY = i;
      }
    }
    //"Normalize the separations" - Guttman
    //divide the separations along each dimensions by the width of the MBR
    int[] retIdx = new int[2];
    int Xpair = (Math.abs(lhsX - hlsX))/mbr.getWidth(); 
    int Ypair = (Math.abs(lhsY - hlsY))/mbr.getHeight();
    if(Xpair > Ypair){
      //if both are the same rect then choose randomly
      if(hlsIdxX == lhsIdxX){
        if(hlsIdxX != 0) 
          hlsIdxX = 0;
        else
          hlsIdxX = 1;
      }
      retIdx[0] = hlsIdxX;
      retIdx[1] = lhsIdxX;   
    }
    else if(Xpair < Ypair){
      /*if both are the same rect then choose randomly - an accidental 
        discovery*/
      if(hlsIdxY == lhsIdxY){
        if(hlsIdxY != 0) 
          hlsIdxY = 0;
        else
          hlsIdxY = 1;
      }
      retIdx[0] = hlsIdxY;
      retIdx[1] = lhsIdxY;          
    }
    else{//if normalized values are equal
      //choose the pair with the least separation(not normalized sap.)
      if((Math.abs(lhsX - hlsX)) >= (Math.abs(lhsY - hlsY))){
        if(hlsIdxX == lhsIdxX){
          if(hlsIdxX != 0) 
            hlsIdxX = 0;
          else
            hlsIdxX = 1;
        }
        retIdx[0] = hlsIdxX;
        retIdx[1] = lhsIdxX;        
      }
      else{
        if(hlsIdxY == lhsIdxY){
          if(hlsIdxY != 0) 
            hlsIdxY = 0;
          else
            hlsIdxY = 1;
        }
        retIdx[0] = hlsIdxY;
        retIdx[1] = lhsIdxY;        
      }
    }
    return(retIdx);
  }
  /**
     The quadratic Pick Seed method from Guttman.
     Assuming that we have only 2 dimensions. This method is slightly slower than the linear method but
     it results in better splits, besides it is much easier to implement.
     @return the two picked indexes from the node
  */
  private int[] quadPickSeeds(Element[] elmts)
    throws  IllegalValueException
  {
    if(elmts.length <= 1)
      throw new  IllegalValueException("Node.quadPickSeed : PickSeed not possible as there are no elements");
    int retIdx[] = new int[2];
    int mostIneff = Integer.MIN_VALUE;//area of the most inefficient pair
    for(int i=0;i<elmts.length;i++){
      for(int j=i+1;j<elmts.length;j++){
        Rect seedRect = Rect.getResultingMBR(elmts[i].getRect(), elmts[j].getRect());
        int arr = seedRect.getArea() - elmts[i].getRect().getArea() - elmts[j].getRect().getArea();
        //if this is the most inefficient pair
        if(arr > mostIneff){
          retIdx[0] = i;
          retIdx[1] = j;
          mostIneff = arr;
        }
      }
    }
    return retIdx;
  }
  public long getParent()
  {
    return(parent);
  }
  /**
   * returns index of the element with the pointer passed in the parameter
   * @param Object Depends upon the Element type.
   * @return returns NOT_DEFINED if ptr is not found
   */
  public int getElementIndex(long ptr/*Object ptr*/)
  {
    if(totalElements < 1)
      return NOT_DEFINED;
    for(int i=0; i<totalElements; i++){
      if(elements[i].getPtr() == ptr)
        return i;
    }
    System.out.println("Node.getElementIndex: Element not found, returning NOT_DEFINED");
    //Even if object types do not match it will return NOT_DEFINED
    return NOT_DEFINED;//if nothing found
  }
  /**
     Used to overwrite the old Element with the new one.
     It modifies the element in the disk as well as in the local variables.
  */
  public void modifyElement(int index,Element elmt)
    throws  IllegalValueException,IOException, NodeWriteException
  {
    if((index > totalElements) || (index < 0) || (elmt == null))
      throw new  IllegalValueException("Node.modifyElmtMBR : index out of bound or MBR is null");
        
    if(elmt.getElementType() != elementType)
      throw new  IllegalValueException("Node.modifyElmtMBR : Element of wrong type");
    if(fileHdr.isWriteThr())
      RTree.chdNodes.remove(fileName,nodeIndex);
    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]
      
      bs.flush();
      ds.flush();
      //write to the file
      seekElement(index);
      file.write(bs.toByteArray());
      setDirty(false);
    }else     
      setDirty(true);
    //adjsut in the local variable
    elements[index].setRect(elmt.getRect());
    elements[index].setPtr(elmt.getPtr());
    //we do not recalculate the whole mbr if we do not need to
    if(elmt.getRect().contains(elements[index].getRect()))//if previous MBR was smaller...
      nodeMBR.expandToInclude(elmt.getRect());
    else//i guess we need to calculate
      refreshNodeMBR();//remove
  }
  /**
     Overloaded
  */
  public void modifyElement(int index,long pointer)
    throws  IllegalValueException,IOException, NodeWriteException
  {
    if((index > totalElements) || (index < 0)){
      try{
        throw new  IllegalValueException("Node.modifyElmtMBR : index out of bound for node "+nodeIndex);
      }catch(Exception e){
        e.printStackTrace();
      }
    }
    if(fileHdr.isWriteThr())
      RTree.chdNodes.remove(fileName,nodeIndex);
    if(fileHdr.isWriteThr()){
      byte[] data = new byte[LONG_SIZE];
      ByteArrayOutputStream bs = new ByteArrayOutputStream(LONG_SIZE);
      DataOutputStream ds =  new DataOutputStream(bs);
      ds.writeLong(pointer);//ds.writeInt(pointer);
      bs.flush();
      ds.flush();
      //write to the file
      seekElementPtr(index);
      file.write(bs.toByteArray());
      setDirty(false);
    }
    else
      setDirty(true);
    //adjsut in the local variable
    elements[index].setPtr(pointer);
  }
  /**
     Overloaded
  */
  public void modifyElement(int index,Rect rect)
    throws  IllegalValueException,IOException, NodeWriteException
  {
    if((index > totalElements) || (index < 0))
      throw new IllegalValueException("Node.modifyElmtMBR : index out of bound or MBR is null");
    if(fileHdr.isWriteThr())
      RTree.chdNodes.remove(fileName,nodeIndex);
    if(fileHdr.isWriteThr()){
      byte[] data = new byte[Rect.sizeInBytes()];
      ByteArrayOutputStream bs = new ByteArrayOutputStream(Rect.sizeInBytes());
      DataOutputStream ds =  new DataOutputStream(bs);
      ds.writeInt(rect.getMinX());
      ds.writeInt(rect.getMinY());
      ds.writeInt(rect.getMaxX());
      ds.writeInt(rect.getMaxY());
      bs.flush();
      ds.flush();
      //write to the file
      seekElement(index);
      file.write(bs.toByteArray());
      setDirty(false);
    }else
      setDirty(true);
    //adjsut in the local variable
    elements[index].setRect(rect);
    //remove
    //we do not recalculate the whole mbr if we do not need to
    if(rect.contains(elements[index].getRect()))
      nodeMBR.expandToInclude(rect);
    else//i guess we need to calculate
      refreshNodeMBR();//remove
  }
  /**
     This function runs a loop on the elements to calculate the total MBR.
     Therefore in case if you already have loop that runs through each of the entries,
     then it is better to calculate MBR in that loop without calling this method.
     @throws IllegalValueException When there are no elements in the node.
  */
  public Rect getNodeMBR()
    throws  IllegalValueException
  {
    //remove
    if(totalElements < 1)
      throw new  IllegalValueException("Node.getNodeMBR: Node empty");
    return nodeMBR;
    //In case of trouble remove the above line and commission the below written lines
    /*
      Rect ret = elements[0].getRect();
      for(int i=1; i<totalElements; i++)
      ret = Rect.getResultingMBR(ret, elements[i].getRect());
      return ret;
    */
  }
  /**
     Will refresh the <code>nodeMBR</code> for the <code>elements</code>
  */
  private void refreshNodeMBR()
  {
    nodeMBR = new Rect();
    for(int i=0; i<totalElements; i++)
      nodeMBR.expandToInclude(elements[i].getRect());
  }

  /**
     No error echecking at all.
  */
  public void setParent(long /*int*/ prnt)
    throws IOException, NodeWriteException
  {
    if(prnt == NOT_DEFINED)//if this is the new root then update the file hdr
      fileHdr.writeFileHeader(fileHdr.totalNodes,nodeIndex);
    if(fileHdr.isWriteThr())
      RTree.chdNodes.remove(fileName,nodeIndex);
    writeNodeHeader(nodeIndex,totalElements,prnt,elementSize,elementType);
  }
  /**
     Obvious, isn't it?
  */
  public String toString()
  {
    String ret = "\n\t***Node at Index: "+Long.toString(nodeIndex)+"***";
    ret += "\nLocal Variables-";
    //ret += "\n\tFile: " + fileName;
    ret += "\n\tnodeIndex: "+ Long.toString(nodeIndex);
    if (totalElements <= 0){
      //ret += "\n\tisNodeEmpty: true";
      ret += "\n\tnodeMBR: isNull";
    }
    //  else{
    //    ret += "\n\tisNodeEmpty: false";
    //    //ret += "\n\tnodeMBR: " + nodeMBR.toString();
    //  }
    ret += "\nFile Header-";
    ret += "\n\ttotalNodes: " + Integer.toString(fileHdr.totalNodes);
    ret += "\n\trootIndex: " + Long.toString(fileHdr.rootIndex);
    ret += "\nNode Header-";
    ret += "\n\ttotalElements: " + Integer.toString(totalElements);
    ret += "\n\tparent: " + Long.toString(parent);
    ret += "\n\telementSize:" + Integer.toString(elementSize);
    ret += "\n\telementType:" + Integer.toString(elementType);
    for(int i=0;i<totalElements;i++)
      ret += elements[i].toString();
    return ret;
  }
  public int getTotalElements()
  {
    return totalElements;
  }
  /**
     Although it returns all the elements but the total elements will not be equal to the length of
     the returned array.Therefore <br><b>Never Use <code>.length</code> field With the Returned Array
     </b>. Instead use <code>getTotalElements()</code>.
     @return An element Array.
  */
  public Element[] getAllElements()
  {
    return elements;
  }
  Element getElement(int index)
    throws  IllegalValueException
  {
    if((index < 0) || (index > totalElements-1))
      throw new  IllegalValueException("Node.getElement Index out of bound");
    return elements[index];
  }
  /**
     Adds the node to the free stack.
     Be very careful with this method because once called, this node may be
     given to any new node even when you have not destroyed its object.
     If the node is the only node then it updates the file header as well.
     </br><i><b>Once called, there is no turning back!</b></i>.
  */
  public void deleteNode()
    throws NodeWriteException
  {
    setDirty(false);//this is intentional
    RTree.chdNodes.remove(fileName,nodeIndex);//we do not check for writeThr here
    try{
      fileHdr.push(nodeIndex);
    }catch(StackOverflowException e){
    }catch(IOException ex){
      throw new NodeWriteException(ex.getMessage());
    }
  }
  /**
   * This method is added to sort the elements in this node to help sweepline algorithm.
   */
  void sweepSort()//check out for null elements
  {
    if(elements != null && elements.length > 1 && sorted == false){
      Arrays.sort(elements, 0, totalElements, new rtree.join.CompElmtX());
      sorted = true;
    }//if
  }//sweepSort
  /**
     This is a new methos that will help the phylosophy where one should write to tbe cache only when
     required.
     @return true if needed write and written or false (not dirty).
  */
  public boolean flush()
    throws NodeWriteException
  {
    try{
      if(dirty && !fileHdr.isWriteThr()){
        deleteElement(-1, true);
        setDirty(false);
        return true;
      }else
        return false;
    }catch(Exception e){
      e.printStackTrace();
      throw new NodeWriteException(e.getMessage());
    }
  }
  void setDirty(boolean val)
  {
    if(val)//dirty
      sorted = false;
    dirty = val;
  }
  public boolean isDirty()
  {
    return dirty;
  }
  
}