rtree.java

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

//RTree.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.FileNotFoundException;
import java.io.IOException;
import java.util.Hashtable;
import java.util.List;
import java.util.Stack;
import java.util.Vector;

import rtree.join.IntersectPred;
import rtree.join.PairElmt;
import rtree.join.SweepLine;
/******************************************************************************************************
 * <p><b>1:</b>Call <code>flush</code> after single or multiple inserts. In affect before the application
 * shuts down, the flush method flushes all the rtrees.
 * <p><b>2:</b>Do not run more than one instance of this application. The package                     
 * cannot handle more than one instance of the application as all the locking                         
 * is done in the code itself(Monitors) and not on the hard-disk file.                                
 * <p><b>3:</b>The file name (of the rtree) is case insensitive.                                      
 * <p><b>4:</b>The package is thread proof, i.e you can run as many threads as                        
 * you want, not worrying about concurrent updations. The package will handle the                     
 * situation of concurrent reads and writes. Again, it can take care of threads                       
 * of only one process(Application) and not for more than one process of the  program.
 * <p><b>5:</b>For immediate effects of tree writes, give the thread that needs                       
 * to write to the file a high priority. This will further speed up tree writes.                      
 * <p><b>6:</b>Give messages like "Updating, please wait..." to the user when                         
 * calling any of the methods that modifies the tree as the thread may have to                        
 * wait on a lock variable.                                                                           
 * <p><b>7:</b>The package maintains a queue of all threads that need to wait on some lock.           
 * The sequence of excecution of the threads is dependent on that queue. All the actions are fired in 
 * the order in which they were received. <br><b>In short the tree is perfectly concurrent.</b>       
 * <p><b>8:</b>For developers: Always obtain a lock from the <code>lockRead</code> or                
 * <code>lockWrite</code> method before going into a <code>public</code> method of the                
 * <code>RTree</code> class. Unlock by calling the <code>unlock</code> method.                        
 * See any existing method to understand the mechanism.                                               
 * <p><b>9:</b>To adjust the cache buffer size, see the <code>Node</code> class documentation.
 * @author Prachuryya Barua 
 ******************************************************************************************************/
public class RTree //the tree that would be made
{
  /**<b>Caution:</b> The file name (of the rtree) is case insensitive in spite
     of the fact that this package was developed on a Linux(RH7.0) platform.
  */
  protected String fileName;
  static Hashtable fileList;//the no. of files open
  // static for the other way
  protected FileHdr fileHdr;
  public static CachedNodes chdNodes;
  /**Inner class for the fileList vector - A List of files*/
  class Header
  {
    FileHdr flHdr;
    String fileName;
    Header(FileHdr flH,String name)
    {
      fileName = name;
      flHdr = flH;
    }
  }
  public RTree(String fileName) 
    throws  RTreeException
  {
    try{
      this.fileName = fileName;
      if(fileList == null)
        fileList = new Hashtable();
      synchronized(fileList){//this may give problem
        if(fileList.get(fileName) != null){
          fileHdr = ((Header)fileList.get(fileName)).flHdr;
          return;
        }
        //a new file
        fileList.put(fileName, new Header(new FileHdr(Node.FREE_LIST_LIMIT, fileName),fileName));
        fileHdr = ((Header)fileList.get(fileName)).flHdr;
        //the cache of nodes - one cache for all the tree files.
        if(chdNodes == null)
          chdNodes = new CachedNodes();
      }
    }
    catch(Exception e){
      throw new  RTreeException("RTree.RTree: " +e.getMessage());
    }
  }
  /**
     This method is used to ask the fileHdr to update itself. This method is package parivate used by 
     <code>Pack</code> class only.
  */
  void updateHdr()
    throws RTreeException, IOException, FileNotFoundException, NodeWriteException
  {
    Header tmp = (Header)fileList.get(fileName);
    if(tmp != null){
      //chdNodes.removeAll();//XXX check this out
      fileHdr.update(fileName);
    }
  }

  public Node getReadNode(long index) throws RTreeException
  {
    try{
      return chdNodes.getReadNode(fileHdr.getFile(), fileName, index, fileHdr);
    }catch(Exception e){
      throw new RTreeException ("RTree.getSortedNode : " + e.getMessage());
    }
  }

  public String getFileName()
  {
    return fileName;
  }
  /**
     Another package private method for getting the file header
  */
  public FileHdr getFileHdr()
  {
    return fileHdr;
  }
  public void flush()
    throws RTreeException
  {
    fileHdr.lockWrite();
    try{
      fileHdr.flush();
      chdNodes.flush();
    }catch(Exception e){
      throw new RTreeException(e.getMessage());
    }finally{
      fileHdr.unlock();
    }
  }
  /**
   * Adjust Tree from <b>Guttman the Great</b>.
   * @param Node[] The nodes that was has the new element and also the element
   * that resulted from the splt(if any).i.e N-node[0], NN-nodes[1]
   * Note:- This method is functionally very much coupled with Node.spliNode()
   * @param node The two new nodes caused by split.
   * @param slotIndex The index of the slot of this tree if any, else give NOT_DEFINED.
   * @return The new root (if it was created). If no new root was created then returns null.
   */
  protected Node adjustTree(Node[] nodes, long slotIndex)
    throws  RTreeException
  {
    try{
      //if(nodes[0].getParent() == Node.NOT_DEFINED){//original
      if(nodes[0].getParent() == slotIndex){
        if(nodes[1] != null){//if root is split
          Node newRoot;
          if(fileHdr.isWriteThr())
            newRoot = new Node(fileHdr.getFile(),fileName, slotIndex, Node.NONLEAF_NODE, 
                               ((Header)fileList.get(fileName)).flHdr);
          else
            newRoot = chdNodes.getNode(fileHdr.getFile(),fileName, slotIndex, Node.NONLEAF_NODE, 
                                       ((Header)fileList.get(fileName)).flHdr, nodes[0]);
          NonLeafElement branchA = new NonLeafElement(nodes[0].getNodeMBR(),nodes[0].getNodeIndex());
          NonLeafElement branchB = new NonLeafElement(nodes[1].getNodeMBR(),nodes[1].getNodeIndex());
          newRoot.insertElement(branchB);
          newRoot.insertElement(branchA);
          return newRoot;
        }
        return null;
      }else{
        //where the new element is inserted
        Node[] insertedNode = new Node[2];
        /*
          set the parent element's MBR equal to the nodeA's MBR.
        */
        //the parent of this node
        Node parentN;
        if(fileHdr.isWriteThr())
          parentN = new Node(fileHdr.getFile(),fileName,nodes[0].getParent(),fileHdr);
        else
          parentN = chdNodes.getNode(fileHdr.getFile(),fileName,nodes[0].getParent(),fileHdr);
        //get the parent element of nodes[0]
        //Integer intValue = new Integer(nodes[0].getNodeIndex());
        int parentElmtIndex = parentN.getElementIndex(nodes[0].getNodeIndex()/*intValue*/);
        //adjust the parent element's MBR 
        parentN.modifyElement(parentElmtIndex,nodes[0].getNodeMBR());
        insertedNode[0] = parentN;
        insertedNode[1] = null; 
        //if it is an split node add its entry in the parent
        if(nodes[1] != null){
          NonLeafElement elmtNN = new NonLeafElement(nodes[1].getNodeMBR(),nodes[1].getNodeIndex());
          try{//if another insert is possible
            parentN.insertElement(elmtNN);
            insertedNode[0] = parentN;
            insertedNode[1] = null; 
          }catch(NodeFullException e){
            insertedNode = parentN.splitNode(elmtNN, Node.NOT_DEFINED);
          }
        }
        return adjustTree(insertedNode, slotIndex);
      }
    }
    catch(Exception e){
      e.printStackTrace();
      throw new  RTreeException("RTree.adjustTree: "+e.getMessage());
    }
  }
  /**
     Pass a <code>LeafElement</code>object.
  */
  public void insert(Element elmt)//Leaf
    throws  RTreeInsertException
  {
    fileHdr.lockWrite();
    Node node = null;
    try{
      //the node into which to insert
      node = chooseLeaf(elmt);
      //System.out.println("Returned:"+node.getNodeIndex());
      Node[] newNodes = new Node[2];
      try{
        node.insertElement(elmt);//if another insert is possible
        newNodes[0] = node;
        newNodes[1] = null;
      }
      //if another insert is not possible
      catch(NodeFullException e){
        newNodes = node.splitNode(elmt, Node.NOT_DEFINED);
      }
      adjustTree(newNodes, Node.NOT_DEFINED);
    }
    catch(Exception e){
      //e.printStackTrace();
      throw new RTreeInsertException("RTree.insert: " + e.getMessage() + " for " +
                                     Thread.currentThread());
    }
    finally{
      fileHdr.unlock();
    }
  }
  /**
     See <b>Guttman the Great</b>.
  */
  private Node chooseLeaf(Element elmt)
    throws  IllegalValueException, RTreeException
  {
    try{            
      //get the root node
      long root = fileHdr.getRootIndex();
      Node node = null;
      if(fileHdr.isWriteThr())
        node = new Node(fileHdr.getFile(), fileName,root,fileHdr);
      else
        node = chdNodes.getNode(fileHdr.getFile(), fileName,root,fileHdr);
      switch (node.getElementType()){
      case Node.LEAF_NODE :
        break;
      case Node.NONLEAF_NODE :
        //repeat till you reach a leaf node
        while(true){
          //get the best fitting rect from the node
          Element nextElmt = node.getLeastEnlargement(elmt);
          if(nextElmt.getElementType() == Node.LEAF_NODE)
            break;
          if(fileHdr.isWriteThr())
            node = new Node(fileHdr.getFile(), fileName, nextElmt.getPtr(), fileHdr);
          else
            node = chdNodes.getNode(fileHdr.getFile(), fileName, nextElmt.getPtr(), fileHdr);
        }
        break;
      default :
        throw new IllegalValueException("RTree.chooseLeaf: Node corrupt, Illegal element type in "
                                        +"node");
      }
      return node;
    }
    catch( IllegalValueException e){
      throw new  IllegalValueException("RTree.chooseLeaf: "+e.getMessage());
    }
    catch(Exception e){
      e.printStackTrace();
      throw new  RTreeException("RTree.chooseLeaf: " + e.getMessage());
    }
  }
  /**
     given the leaf element, this method deletes the element from the tree
     compairing its Rect and pointer with the similar entries in the tree.
     @throws ElementNotException when the given element is not found.
  */ 
  public void delete(LeafElement elmt)
    throws  RTreeException,ElementNotFoundException
  {
    fileHdr.lockWrite();
    long root;
    if(elmt ==  null)
      throw new  RTreeException("RTree.delete: Rect is null");
    try{
      if(fileHdr.isWriteThr())
        chdNodes.removeAll();
      root = fileHdr.getRootIndex();//FileHdr.getRootIndex(fileName);