node.java

R-Tree Java implementations 结构清晰

//   Node.java
//   Java Spatial Index Library
//   Copyright (C) 2002 Infomatiq Limited
//  
//  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.
//  
//  You should have received a copy of the GNU Lesser General Public
//  License along with this library; if not, write to the Free Software
//  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA

package com.infomatiq.jsi.rtree;

import com.infomatiq.jsi.Rectangle;

/**
 * <p>Used by RTree. There are no public methods in this class.</p>
 * 
 * @author [e-mail]
 * @version 1.0b2p1
 */
public class Node {
  int nodeId = 0;
  Rectangle mbr = null;
  Rectangle[] entries = null;
  int[] ids = null;
  int level;
  int entryCount;

  Node(int nodeId, int level, int maxNodeEntries) {
    this.nodeId = nodeId;
    this.level = level;
    entries = new Rectangle[maxNodeEntries];
    ids = new int[maxNodeEntries];
  }
   
  void addEntry(Rectangle r, int id) {
    ids[entryCount] = id;
    entries[entryCount] = r.copy();
    entryCount++;
    if (mbr == null) {
      mbr = r.copy();
    } else {
      mbr.add(r);
    }
  }
  
  void addEntryNoCopy(Rectangle r, int id) {
    ids[entryCount] = id;
    entries[entryCount] = r;
    entryCount++;
    if (mbr == null) {
      mbr = r.copy();
    } else {
      mbr.add(r);
    }
  }
  
  // Return the index of the found entry, or -1 if not found
  int findEntry(Rectangle r, int id) {
    for (int i = 0; i < entryCount; i++) {
    	if (id == ids[i] && r.equals(entries[i])) {
    	  return i;	
    	}
    }
    return -1;
  }
  
  // delete entry. This is done by setting it to null and copying the last entry into its space.
  void deleteEntry(int i, int minNodeEntries) {
	  int lastIndex = entryCount - 1;
	  Rectangle deletedRectangle = entries[i];
    entries[i] = null;
	  if (i != lastIndex) {
	  	entries[i] = entries[lastIndex];
	  	ids[i] = ids[lastIndex];
      entries[lastIndex] = null;
	  }
    entryCount--;
    
    // if there are at least minNodeEntries, adjust the MBR.
    // otherwise, don't bother, as the node will be 
    // eliminated anyway.
    if (entryCount >= minNodeEntries) {
      recalculateMBR(deletedRectangle);
    }
  } 
  
  // oldRectangle is a rectangle that has just been deleted or made smaller.
  // Thus, the MBR is only recalculated if the OldRectangle influenced the old MBR
  void recalculateMBR(Rectangle deletedRectangle) {
    if (mbr.edgeOverlaps(deletedRectangle)) { 
      mbr.set(entries[0].min, entries[0].max);
      
      for (int i = 1; i < entryCount; i++) {
        mbr.add(entries[i]);
      }
    }
  }
   
  public int getEntryCount() {
    return entryCount;
  }
  
  public Rectangle getEntry(int index) {
    if (index < entryCount) {
      return entries[index];
    }
    return null;
  }
  
  public int getId(int index) {
    if (index < entryCount) {
      return ids[index];
    }
    return -1;
  }
  
  /**
   * eliminate null entries, move all entries to the start of the source node
   */
  void reorganize(RTree rtree) {
    int countdownIndex = rtree.maxNodeEntries - 1; 
    for (int index = 0; index < entryCount; index++) {
      if (entries[index] == null) {
         while (entries[countdownIndex] == null && countdownIndex > index) {
           countdownIndex--;
         }
         entries[index] = entries[countdownIndex];
         ids[index] = ids[countdownIndex];    
         entries[countdownIndex] = null;
      }
    }
  }
  
  boolean isLeaf() {
    return (level == 1);
  }
  
  public int getLevel() {
    return level; 
  }
  
  public Rectangle getMBR() {
    return mbr; 
  }
}