R树的java版本实现

这个代码比较适合算法类开发者学习，比较直观，实用。

//ABL.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;
//package rtree;
/**Active Branch List
   This class will consist of the Elements and their MINDIST from the point of query.
   When the array of this object is returned by the ‘nearestSearch‘ method
   kindly type cast ‘Elemen‘t to ‘LeafElement‘ when necessary.
   This library should be considered as an open source library. Formal GNU licensing I will include later.
*/
public class ABL implements Cloneable
{
  /**
     Please type cast it to LeafElement when used as a returned value of 
     the ‘nearestSearch‘ method.
  */
  public Element element;
  /**By Definition - The distance of a point P in Euclidean space （E（n））
     from a rectangle R in the same space denoted by MINDIST（PR）.

     In English - This is the minimum distance between the query point P
     and the MBR of the object.
     Note:- The distance（minDist） is the square of the actual distance.
     To get the actual distance call Math.sqrt（minDist） （cast minDist to
     Double）.
  */
  public long minDist;//MINDIST（Pthis）
  public ABL（Element elementlong minDist）
  {
    this.element = element;
    this.minDist = minDist;
  }
  //Uses Two-Way-Merge-Sort （Recursive）
  //Sorts an ABL array based on minDist. Make sure there are no null values.
  public void mergeSort（ABL[] arrABL）
  {
    twoWayMerge（arrABL0arrABL.length-1）;
  }
  private void twoWayMerge（ABL[] arrABLint startint finish）
  {
    try{
      int size = finish - start+1;
      if（size <= 2）{
        if（size < 2）
          return;
        ABL temp;
        if（arrABL[start].minDist > arrABL[finish].minDist）{
          temp = arrABL[start];
          arrABL[start] = arrABL[finish];
          arrABL[finish] = temp;
        }
        return;
      }
      Double middle = new Double（start+finish）;
      middle = new Double（Math.ceil（middle.doubleValue（）/2））;
      twoWayMerge（arrABLstartmiddle.intValue（））;
      twoWayMerge（arrABLmiddle.intValue（）finish）;
      simpleMerge（arrABLstartmiddle.intValue（）finish）;
    }
    catch（Exception e）{
      System.out.println（“rtree.ABL.twoWayMerge: most probably a null value in array“）;
    }
  }
    
  //simple merge
  private void simpleMerge（ABL[] arrABLint firstint secondint third）
    throws Exception
  {
    int i = first;
    int j = second;
    int l = 0;
    ABL[] temp = new ABL[third-first+1];
    while（（i < second） && （j <= third））{//loop till one lasts
      if（arrABL[i].minDist <= arrABL[j].minDist）
     

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----

     文件        299  2009-02-17 20:25  Rtree-eclipse\rtree\.classpath

     文件        381  2009-02-17 20:25  Rtree-eclipse\rtree\.project

     文件        634  2009-02-17 20:25  Rtree-eclipse\rtree\.settings\org.eclipse.jdt.core.prefs

     文件       2044  2009-02-17 20:25  Rtree-eclipse\rtree\bin\rtree\ABL.class

     文件        315  2009-02-17 20:25  Rtree-eclipse\rtree\bin\rtree\app.dat

     文件       4071  2009-02-17 20:25  Rtree-eclipse\rtree\bin\rtree\BufferHeader.class

     文件       5148  2009-02-17 20:25  Rtree-eclipse\rtree\bin\rtree\CachedNodes.class

     文件       3249  2009-02-17 20:25  Rtree-eclipse\rtree\bin\rtree\ChangeLog

     文件       1093  2009-02-17 20:25  Rtree-eclipse\rtree\bin\rtree\Element.class

     文件        372  2009-02-17 20:25  Rtree-eclipse\rtree\bin\rtree\ElementNotFoundException.class

     文件       8454  2009-02-17 20:25  Rtree-eclipse\rtree\bin\rtree\FileHdr.class

     文件        442  2009-02-17 20:25  Rtree-eclipse\rtree\bin\rtree\IllegalValueException.class

     文件       1173  2009-02-17 20:25  Rtree-eclipse\rtree\bin\rtree\join\CompElmtX.class

     文件        863  2009-02-17 20:25  Rtree-eclipse\rtree\bin\rtree\join\CompRectX.class

     文件       1590  2009-02-17 20:25  Rtree-eclipse\rtree\bin\rtree\join\ContainedByPred.class

     文件       1533  2009-02-17 20:25  Rtree-eclipse\rtree\bin\rtree\join\ContainsPred.class

     文件       1504  2009-02-17 20:25  Rtree-eclipse\rtree\bin\rtree\join\EqualsPred.class

     文件       1428  2009-02-17 20:25  Rtree-eclipse\rtree\bin\rtree\join\IntersectPred.class

     文件       5363  2009-02-17 20:25  Rtree-eclipse\rtree\bin\rtree\join\Join.class

     文件        426  2009-02-17 20:25  Rtree-eclipse\rtree\bin\rtree\join\JoinException.class

     文件       1022  2009-02-17 20:25  Rtree-eclipse\rtree\bin\rtree\join\MeetPred.class

     文件        812  2009-02-17 20:25  Rtree-eclipse\rtree\bin\rtree\join\Pair.class

     文件        998  2009-02-17 20:25  Rtree-eclipse\rtree\bin\rtree\join\PairElmt.class

     文件        592  2009-02-17 20:25  Rtree-eclipse\rtree\bin\rtree\join\Predicate.class

     文件       2454  2009-02-17 20:25  Rtree-eclipse\rtree\bin\rtree\join\SweepLine.class

     文件       2383  2009-02-17 20:25  Rtree-eclipse\rtree\bin\rtree\LeafElement.class

     文件       1405  2009-02-17 20:25  Rtree-eclipse\rtree\bin\rtree\Logic.txt

     文件      22943  2009-02-17 20:25  Rtree-eclipse\rtree\bin\rtree\Node.class

     文件        354  2009-02-17 20:25  Rtree-eclipse\rtree\bin\rtree\NodeEmptyException.class

     文件        351  2009-02-17 20:25  Rtree-eclipse\rtree\bin\rtree\NodeFullException.class

............此处省略84个文件信息