src/com/infomatiq/jsi/rtree/Node.java

   1 //   Node.java
   2 //   Java Spatial Index Library
   3 //   Copyright (C) 2002 Infomatiq Limited
   4 //
   5 //  This library is free software; you can redistribute it and/or
   6 //  modify it under the terms of the GNU Lesser General Public
   7 //  License as published by the Free Software Foundation; either
   8 //  version 2.1 of the License, or (at your option) any later version.
   9 //
  10 //  This library is distributed in the hope that it will be useful,
  11 //  but WITHOUT ANY WARRANTY; without even the implied warranty of
  12 //  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  13 //  Lesser General Public License for more details.
  14 //
  15 //  You should have received a copy of the GNU Lesser General Public
  16 //  License along with this library; if not, write to the Free Software
  17 //  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
  18
  19 package com.infomatiq.jsi.rtree;
  20
  21 import com.infomatiq.jsi.Rectangle;
  22
  23 /**
  24  * <p>Used by RTree. There are no public methods in this class.</p>
  25  *
  26  * @author aled.morris@infomatiq.co.uk
  27  * @version 1.0b2
  28  */
  29 public class Node {
  30   int nodeId = 0;
  31   Rectangle mbr = null;
  32   Rectangle[] entries = null;
  33   int[] ids = null;
  34   int level;
  35   int entryCount;
  36
  37   Node(int nodeId, int level, int maxNodeEntries) {
  38     this.nodeId = nodeId;
  39     this.level = level;
  40     entries = new Rectangle[maxNodeEntries];
  41     ids = new int[maxNodeEntries];
  42   }
  43
  44   void addEntry(Rectangle r, int id) {
  45     ids[entryCount] = id;
  46     entries[entryCount] = r.copy();
  47     entryCount++;
  48     if (mbr == null) {
  49       mbr = r.copy();
  50     } else {
  51       mbr.add(r);
  52     }
  53   }
  54
  55   void addEntryNoCopy(Rectangle r, int id) {
  56     ids[entryCount] = id;
  57     entries[entryCount] = r;
  58     entryCount++;
  59     if (mbr == null) {
  60       mbr = r.copy();
  61     } else {
  62       mbr.add(r);
  63     }
  64   }
  65
  66   // Return the index of the found entry, or -1 if not found
  67   int findEntry(Rectangle r, int id) {
  68     for (int i = 0; i < entryCount; i++) {
  69         if (id == ids[i] && r.equals(entries[i])) {
  70           return i;
  71         }
  72     }
  73     return -1;
  74   }
  75
  76   // delete entry. This is done by setting it to null and copying the last entry into its space.
  77   void deleteEntry(int i, int minNodeEntries) {
  78           int lastIndex = entryCount - 1;
  79           Rectangle deletedRectangle = entries[i];
  80     entries[i] = null;
  81           if (i != lastIndex) {
  82                 entries[i] = entries[lastIndex];
  83                 ids[i] = ids[lastIndex];
  84       entries[lastIndex] = null;
  85           }
  86     entryCount--;
  87
  88     // if there are at least minNodeEntries, adjust the MBR.
  89     // otherwise, don't bother, as the node will be
  90     // eliminated anyway.
  91     if (entryCount >= minNodeEntries) {
  92       recalculateMBR(deletedRectangle);
  93     }
  94   }
  95
  96   // oldRectangle is a rectangle that has just been deleted or made smaller.
  97   // Thus, the MBR is only recalculated if the OldRectangle influenced the old MBR
  98   void recalculateMBR(Rectangle deletedRectangle) {
  99     if (mbr.edgeOverlaps(deletedRectangle)) {
 100       mbr.set(entries[0].min, entries[0].max);
 101
 102       for (int i = 1; i < entryCount; i++) {
 103         mbr.add(entries[i]);
 104       }
 105     }
 106   }
 107
 108   public int getEntryCount() {
 109     return entryCount;
 110   }
 111
 112   public Rectangle getEntry(int index) {
 113     if (index < entryCount) {
 114       return entries[index];
 115     }
 116     return null;
 117   }
 118
 119   public int getId(int index) {
 120     if (index < entryCount) {
 121       return ids[index];
 122     }
 123     return -1;
 124   }
 125
 126   /**
 127    * eliminate null entries, move all entries to the start of the source node
 128    */
 129   void reorganize(RTree rtree) {
 130     int countdownIndex = rtree.maxNodeEntries - 1;
 131     for (int index = 0; index < entryCount; index++) {
 132       if (entries[index] == null) {
 133          while (entries[countdownIndex] == null && countdownIndex > index) {
 134            countdownIndex--;
 135          }
 136          entries[index] = entries[countdownIndex];
 137          ids[index] = ids[countdownIndex];
 138          entries[countdownIndex] = null;
 139       }
 140     }
 141   }
 142
 143   boolean isLeaf() {
 144     return (level == 1);
 145   }
 146
 147   public int getLevel() {
 148     return level;
 149   }
 150
 151   public Rectangle getMBR() {
 152     return mbr;
 153   }
 154 }