node.java

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

//Node.java
//  
//This library is free software; you can redistribute it and/or
//modify it under the terms of the GNU Lesser General Public
//License as published by the Free Software Foundation; either
//version 2.1 of the License, or (at your option) any later version.
//  
//This library is distributed in the hope that it will be useful,
//but WITHOUT ANY WARRANTY; without even the implied warranty of
//MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
//Lesser General Public License for more details.
package rtree;
import java.io.ByteArrayInputStream;
import java.io.ByteArrayOutputStream;
import java.io.DataInputStream;
import java.io.DataOutputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.RandomAccessFile;
import java.util.Arrays;

/**
   This class will contain one node at a time in memory.
   This class along with FileHdr are the only two classes that handle the 
   rtree file. No other class handles the rtree file. Therefore be very careful
   when modifying this class, you may corrupt the file in the process.
   </p><b>CHANGELOG</b> See the projects/ChangeLog file
   
   @author Prachuryya Barua
   @version Node.NOT_DEFINED
*/

public class Node implements Cloneable //can be made abstract if leaf and non leaf required
{
  /**max no. of entries in a node*/
  public final static int MAX = 169;//84;//101; //50;//testing 3
  /**min. no. of entries in a node*/
  public final static int MIN= 84;//51; //25;//testing 2
  /**The size of the cache.<br>
     Minimum cache size is 50% of total no. of elements (1lakh records has 597 nodes).
     <br>Maximum cache size should be 70%, beyound that there may not be major improvements but the
     overheads will increase.
     <br>Eg: 1 lakh packed records - Total nodes in tree - 597: Height 3, 1 root,4 nonleaf, 129 leaf
     and should have a cache size of 250(sufficient for normal casses) to 400(good for queries). 
     <br>Multiply the cache size by 4kbytes and you get the cache size in MBytes.
     <br><b>These observations are for a packed tree only. An unpacked tree
     needs a 100% buffer size - thererore don't use unpacked tree.</b>
     <br>For unpacked tree
     <br>1 lakh records - Total nodes in tree - 991( Height 3: 1 root, 10 NonLeaf, 981 Leaf

     These observations shold hold good for query building as well. But it is no harm to give large caches
     for query building.
  */
  public final static int CACHE_SIZE = 250;
  /**bytes*/
  final static int NODE_HDR_SIZE = 20;//16;
  /**2 kBytes - will include the file header and the stack*/
  final static int FILE_HDR_SIZE = 4096;//2048;//1024;
  /** 2 kByte*/
  final static int NODE_SIZE = 4096;//2048;//1024;
  /**2048-16=2032 then 2048-20=2028 NOW 4096-20=4076*/
  final static int NODE_BODY_SIZE = 4076;//2028;//2032;//1008;
  /**can be increased by increasing file header size*/
  final static int FREE_LIST_LIMIT = 1020;//509;//5102k;//2541k;
  /**So that I don't forget*/
  final static int INTEGER_SIZE = 4;
  /**So that I don't forget*/
  final static int LONG_SIZE = 8;
  /**node elements type - LEAF*/
  public final static int LEAF_NODE = 1;
  /**node elements type - NON LEAF*/
  public final static int NONLEAF_NODE = 2;
  /**node elements type - NONE*/
  public final static int NOT_DEFINED = -999;
  public final static long NOT_DEFINED_LONG = -999;
  /**for thread which reads the tree*/
  final static int READ = 0;
  /**for threads which writes the reads*/
  final static int WRITE = 1;
  /**No threads reading or writing*/
  final static int NONE = 2;
    
  /**-------------local variables-----------------------*/
  protected RandomAccessFile file;
  protected String fileName;
  protected boolean dirty = false;/*This flags keeps track of the changes made*/
  /**will contain the index of the node in the file*/
  protected long nodeIndex;
  /**a flag to see whether a node is empty*/
  //protected boolean isNodeEmpty;
  protected boolean sorted;
  /**will contain all the elements.*/
  protected Element[] elements;
  /**the file header and the free nodes stack*/
  protected FileHdr fileHdr;
  /**The cached Node MBR... no loops over the node Elements*/
  protected Rect nodeMBR;//remove
  /**-------------------Node header and body-----------------------*/
  /**total no. of elements*/
  protected int totalElements;
  /**parent index - root's parent is not defined*/
  protected long parent;
  /**size of the element*/
  protected int elementSize;
  /**type of the elements in the node*/
  protected int elementType;
  /**---------------Element structure------------*/
  /**
   *minX
   *minY
   *maxX
   *maxY
   *pointer
   */
  
  /**This is only for subclasses*/
  protected Node(){}

  /**for a new node
     Remember if the file is new this constructor will overwrite the 
     <code>parent</code> parameter with 'NOT_DEFINED' as it will be the root node.
     If the <code>prnt</code> parameter is given as NOT_DEFINED then it is understood
     that a new root is required.The file will then have a new root.
  */
  protected Node(RandomAccessFile file,String fileName, long prnt,int elmtType, FileHdr flHdr)
    throws IOException, NodeWriteException
  {
    this.file = file;
    fileHdr = flHdr;
    //initialise local variables
    this.fileName = fileName;
    elements = new Element[MAX];
    nodeMBR = new Rect();//remove
    int size;//size of the element type
    /* Though there is not much difference between LeafElement and NonLeafElement but we still use
       the if condition as there may sometime in the future come a case where they differ.
       But again then again to incorporate such change we must make MAX dynamic with the type of the element
       we have.
    */
    if(elmtType == NONLEAF_NODE) 
      size = NonLeafElement.sizeInBytes();
    else
      size = LeafElement.sizeInBytes();
    try{
      /*a new file with an empty root node*/
      //if((file.length() <= (FILE_HDR_SIZE+2))){//no nodes written
      if(fileHdr.getRootIndex() == NOT_DEFINED){//no nodes written
        //writing the file header
        fileHdr.writeFileHeader(1,0);
        //local variables
        nodeIndex = 0;//this is root - though empty
        //isNodeEmpty = true;
        //write node header
        writeNodeHeader(fileHdr.rootIndex,0,NOT_DEFINED,size,elmtType);
      }
      /*for an existing file with a new node*/
      else{
        //see if any free node exists
        try{
          nodeIndex = fileHdr.pop();
        }
        catch(StackUnderflowException e){//else
          nodeIndex = fileHdr.totalNodes++;//new node index
        }
        //local variables
        //isNodeEmpty = true;
        if(prnt == NOT_DEFINED)/*new Node is the root node.*/
          fileHdr.writeFileHeader(fileHdr.totalNodes,nodeIndex);
        else/*new node is any other node*/
          fileHdr.writeFileHeader(fileHdr.totalNodes,fileHdr.rootIndex);
        //write the node
        writeNodeHeader(nodeIndex,0,prnt,size,elmtType);
      }
            
      return;
    } 
    catch(IOException e){
      throw new IOException("Node.Node(new) : " + e.getMessage());
    }
  }
  /**
     Reading existing nodes. But if this a new file then it will create the 
     file and make a new root node.
  */
  protected Node(RandomAccessFile file,String fileName,long ndIndex,FileHdr flHdr)
    throws FileNotFoundException,IOException,NodeReadException, NodeWriteException
  {
    //check whether file is new or old
    //see whether the user must be specified or not if it is a new file
    fileHdr = flHdr;
    this.file = file;
    this.fileName = fileName;
    elements = new Element[MAX];
    nodeMBR = new Rect();//remove
    //a new file with an empty root node
    //if(file.length() <= (FILE_HDR_SIZE+2)){//new file with no nodes
    if(fileHdr.getRootIndex() == NOT_DEFINED){//no nodes written
      try{
        //write file header
        fileHdr.writeFileHeader(1,0);
        //local variables
        nodeIndex = 0;//this is root - though empty
        //isNodeEmpty = true;
        //write node header
        writeNodeHeader(fileHdr.rootIndex, 0, NOT_DEFINED, LeafElement.sizeInBytes(), LEAF_NODE);
      }
      catch(IOException e){
        throw new IOException("Node.constructor : Can't write to fileHeader and/or node " + e.getMessage());
      }
    }
    //if an old file with an existing node
    else{
      //if out of bond index
      if((FILE_HDR_SIZE+(NODE_SIZE*ndIndex)) > file.length())
        throw new NodeReadException("Node.Node.: nodeIndex is out of bound");
      //update the local variable
      this.nodeIndex = ndIndex;
      //read all the values into local variables from the node
      refreshNode();
    }
  }
    
  /**
     A stupid internal constructor for the clone method.
  */
  protected Node(RandomAccessFile file,String fileName,long nodeIndex, boolean sorted,
                 Element[] elmts, FileHdr fileHdr, int totalElements,long parent,int elmtSize,
                 int elmtType, boolean dirty, Rect nodeMBR)//remove
  {
    try{
      //Integer intVal;
      this.file = file;
      this.dirty = dirty;
      this.fileName = new String(fileName.toCharArray());
      this.nodeIndex = nodeIndex;
      //this.isNodeEmpty = isNodeEmpty;
      this.sorted = sorted;
      this.nodeMBR = new Rect(nodeMBR);//remove
      this.elements = new Element[elmts.length];
      for(int i=0; i<elmts.length; i++){
        if(elmts[i] != null){
          if(elmtType == LEAF_NODE)
            this.elements[i] = new LeafElement(new Rect(elmts[i].getRect()), elmts[i].getPtr());
          else
            this.elements[i] = new NonLeafElement(new Rect(elmts[i].getRect()), elmts[i].getPtr());
        }//if
      }//for
      this.fileHdr = fileHdr;
      this.totalElements = totalElements;
      this.parent = parent;
      this.elementSize = elmtSize;
      this.elementType = elmtType;
    }
    catch(Exception e){
      e.printStackTrace();
    }
  }
  public Object clone()
  {
    return new Node(file,fileName,nodeIndex, sorted, elements, fileHdr,totalElements,
                    parent, elementSize, elementType, dirty, nodeMBR);//remove
  }

  /**
     read an element from the hard disk. Not used any more
     @deprecated In-fact it has never been used except in early development days.
  */
  private Element readElement(long index) throws NodeReadException
  {
    if((index < 0)||(index > (MAX-1)) || (totalElements > index+1 ))
      throw new NodeReadException("Node.readElement: Index value not correct");
    try
      {
        int minX,minY,maxX,maxY;
        //create a buffer
        byte[] data = new byte[NODE_SIZE];
        seekCurrNode();
        file.read(data);
        DataInputStream ds = new DataInputStream(new ByteArrayInputStream(data));
        //skip the header - check for error value
        int skipValue = NODE_HDR_SIZE + (elementSize * (int)index);
        if(ds.skipBytes(skipValue) != skipValue)
          throw new NodeReadException("Can't read buffer: Header or index wrong");
        //read the points
        minX = ds.readInt();
        minY = ds.readInt();
        maxX = ds.readInt();
        maxY = ds.readInt();
        Rect Rectangle = new Rect(minX,minY,maxX,maxY);
        if(elementType == LEAF_NODE){
          long ptr = ds.readLong();
          return(new LeafElement(Rectangle, ptr));
        }
        //if non leaf type then...
        long nodePtr = ds.readLong();
        return(new NonLeafElement(Rectangle, nodePtr));
      }
    catch(Exception e){
      throw new NodeReadException("Node.readElement: " +e.getMessage());
    }
  }
  /**
     This method delets the element with the given index from the node.
     It rewrites the node.
     This method now also being used to write the whole node to the file.
     @param index The element to delete. Give -1 if the whole node is to be flushed.
     @param force Whether to force IO. As this method is also used to write the whole node, this was 
     required.
     @return thengaa!
     XXX : This is till not correct.
  */
  public void deleteElement(int index, boolean force)
    throws IllegalValueException, NodeWriteException
  {
    if((index > (totalElements-1)))
      throw new IllegalValueException("Node.deleteElement: index out of bound");
    if(fileHdr.isWriteThr())
      RTree.chdNodes.remove(fileName,nodeIndex);
    int j = -1;
    try{
      nodeMBR = new Rect();//remove
      ByteArrayOutputStream bs = null;
      DataOutputStream ds = null;
      if(fileHdr.isWriteThr() || force){
        bs = new ByteArrayOutputStream(NODE_SIZE);
        ds =  new DataOutputStream(bs);
        if(index < 0)
          ds.writeInt(totalElements);
        else
          ds.writeInt(totalElements - 1);
        ds.writeLong(parent);
        ds.writeInt(elementSize);
        ds.writeInt(elementType);
      }
      for(int i=0; i<totalElements; i++){
        if(i != index){
          nodeMBR.expandToInclude(elements[i].getRect());//update the local variable as well - remove
          if(fileHdr.isWriteThr() || force){//same condition of buffer policy again, we wanted the loop
            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());//see [2]
          }//if
        }else
          j = i;
      }//for
      if(fileHdr.isWriteThr() || force){
        bs.flush();
        ds.flush();
        seekCurrNode();
        file.write(bs.toByteArray());
        setDirty(false);
      }else{//if we do not write through
        setDirty(true);
        for(int i=0; i<totalElements; i++)
          if(i != index)
            nodeMBR.expandToInclude(elements[i].getRect());//update the local variable as well - remove
          else
            j = i;
      }//else
    }catch(Exception e){
      e.printStackTrace();
      throw new NodeWriteException("Node.deleteElement Can't delete element. Rtree may be corrupted.");
    }
    //update local variable
    try{
      if(j != -1){//do these things only if it an element was deleted
        totalElements--;
        if(totalElements>0)
          System.arraycopy(elements,j+1,elements,j,(totalElements-j));