Migrated source code from Simantics SVN

[simantics/platform.git] / bundles / org.simantics.scenegraph / src / com / infomatiq / jsi / rtree / Node.java

diff --git a/bundles/org.simantics.scenegraph/src/com/infomatiq/jsi/rtree/Node.java b/bundles/org.simantics.scenegraph/src/com/infomatiq/jsi/rtree/Node.java
new file mode 100644 (file)
index 0000000..9c03bbb
--- /dev/null
+++ b/bundles/org.simantics.scenegraph/src/com/infomatiq/jsi/rtree/Node.java
@@ -0,0 +1,162 @@
+//   Node.java\r
+//   Java Spatial Index Library\r
+//   Copyright (C) 2002-2005 Infomatiq Limited\r
+//   Copyright (C) 2008-2010 aled@sourceforge.net\r
+//  \r
+//  This library is free software; you can redistribute it and/or\r
+//  modify it under the terms of the GNU Lesser General Public\r
+//  License as published by the Free Software Foundation; either\r
+//  version 2.1 of the License, or (at your option) any later version.\r
+//  \r
+//  This library is distributed in the hope that it will be useful,\r
+//  but WITHOUT ANY WARRANTY; without even the implied warranty of\r
+//  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU\r
+//  Lesser General Public License for more details.\r
+//  \r
+//  You should have received a copy of the GNU Lesser General Public\r
+//  License along with this library; if not, write to the Free Software\r
+//  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA\r
+\r
+package com.infomatiq.jsi.rtree;\r
+\r
+/**\r
+ * <p>Used by RTree. There are no public methods in this class.</p>\r
+ * \r
+ * @author aled.morris@infomatiq.co.uk\r
+ * @version 1.0b8\r
+ */\r
+public class Node {\r
+  int nodeId = 0;\r
+  float mbrMinX = Float.MAX_VALUE;\r
+  float mbrMinY = Float.MAX_VALUE;\r
+  float mbrMaxX = -Float.MAX_VALUE;\r
+  float mbrMaxY = -Float.MAX_VALUE;\r
+  \r
+  float[] entriesMinX = null;\r
+  float[] entriesMinY = null;\r
+  float[] entriesMaxX = null;\r
+  float[] entriesMaxY = null;\r
+  \r
+  int[] ids = null;\r
+  int level;\r
+  int entryCount;\r
+\r
+  Node(int nodeId, int level, int maxNodeEntries) {\r
+    this.nodeId = nodeId;\r
+    this.level = level;\r
+    entriesMinX = new float[maxNodeEntries];\r
+    entriesMinY = new float[maxNodeEntries];\r
+    entriesMaxX = new float[maxNodeEntries];\r
+    entriesMaxY = new float[maxNodeEntries];\r
+    ids = new int[maxNodeEntries];\r
+  }\r
+   \r
+  void addEntry(float minX, float minY, float maxX, float maxY, int id) {\r
+    ids[entryCount] = id;\r
+    entriesMinX[entryCount] = minX;\r
+    entriesMinY[entryCount] = minY;\r
+    entriesMaxX[entryCount] = maxX;\r
+    entriesMaxY[entryCount] = maxY;\r
+   \r
+    if (minX < mbrMinX) mbrMinX = minX;\r
+    if (minY < mbrMinY) mbrMinY = minY;\r
+    if (maxX > mbrMaxX) mbrMaxX = maxX;\r
+    if (maxY > mbrMaxY) mbrMaxY = maxY;\r
+    \r
+    entryCount++;\r
+  }\r
+  \r
+  // Return the index of the found entry, or -1 if not found\r
+  int findEntry(float minX, float minY, float maxX, float maxY, int id) {\r
+    for (int i = 0; i < entryCount; i++) {\r
+       if (id == ids[i] && \r
+          entriesMinX[i] == minX && entriesMinY[i] == minY &&\r
+          entriesMaxX[i] == maxX && entriesMaxY[i] == maxY) {\r
+         return i;     \r
+       }\r
+    }\r
+    return -1;\r
+  }\r
+  \r
+  // delete entry. This is done by setting it to null and copying the last entry into its space.\r
+  void deleteEntry(int i) {\r
+         int lastIndex = entryCount - 1;\r
+    float deletedMinX = entriesMinX[i];\r
+    float deletedMinY = entriesMinY[i];\r
+    float deletedMaxX = entriesMaxX[i];\r
+    float deletedMaxY = entriesMaxY[i];\r
+    \r
+    if (i != lastIndex) {\r
+      entriesMinX[i] = entriesMinX[lastIndex];\r
+      entriesMinY[i] = entriesMinY[lastIndex];\r
+      entriesMaxX[i] = entriesMaxX[lastIndex];\r
+      entriesMaxY[i] = entriesMaxY[lastIndex];\r
+       ids[i] = ids[lastIndex];\r
+         }\r
+    entryCount--;\r
+    \r
+    // adjust the MBR\r
+    recalculateMBRIfInfluencedBy(deletedMinX, deletedMinY, deletedMaxX, deletedMaxY);\r
+  } \r
+  \r
+  // deletedMin/MaxX/Y is a rectangle that has just been deleted or made smaller.\r
+  // Thus, the MBR is only recalculated if the deleted rectangle influenced the old MBR\r
+  void recalculateMBRIfInfluencedBy(float deletedMinX, float deletedMinY, float deletedMaxX, float deletedMaxY) {\r
+    if (mbrMinX == deletedMinX || mbrMinY == deletedMinY || mbrMaxX == deletedMaxX || mbrMaxY == deletedMaxY) { \r
+      recalculateMBR();   \r
+    }\r
+  }\r
+   \r
+  void recalculateMBR() {\r
+    mbrMinX = entriesMinX[0];\r
+    mbrMinY = entriesMinY[0];\r
+    mbrMaxX = entriesMaxX[0];\r
+    mbrMaxY = entriesMaxY[0];\r
+\r
+    for (int i = 1; i < entryCount; i++) {\r
+      if (entriesMinX[i] < mbrMinX) mbrMinX = entriesMinX[i];\r
+      if (entriesMinY[i] < mbrMinY) mbrMinY = entriesMinY[i];\r
+      if (entriesMaxX[i] > mbrMaxX) mbrMaxX = entriesMaxX[i];\r
+      if (entriesMaxY[i] > mbrMaxY) mbrMaxY = entriesMaxY[i];\r
+    }\r
+  }\r
+    \r
+  /**\r
+   * eliminate null entries, move all entries to the start of the source node\r
+   */\r
+  void reorganize(RTree rtree) {\r
+    int countdownIndex = rtree.maxNodeEntries - 1; \r
+    for (int index = 0; index < entryCount; index++) {\r
+      if (ids[index] == -1) {\r
+         while (ids[countdownIndex] == -1 && countdownIndex > index) {\r
+           countdownIndex--;\r
+         }\r
+         entriesMinX[index] = entriesMinX[countdownIndex];\r
+         entriesMinY[index] = entriesMinY[countdownIndex];\r
+         entriesMaxX[index] = entriesMaxX[countdownIndex];\r
+         entriesMaxY[index] = entriesMaxY[countdownIndex];\r
+         ids[index] = ids[countdownIndex];    \r
+         ids[countdownIndex] = -1;\r
+      }\r
+    }\r
+  }\r
+  \r
+  public int getEntryCount() {\r
+    return entryCount;\r
+  }\r
+ \r
+  public int getId(int index) {\r
+    if (index < entryCount) {\r
+      return ids[index];\r
+    }\r
+    return -1;\r
+  }\r
+  \r
+  boolean isLeaf() {\r
+    return (level == 1);\r
+  }\r
+  \r
+  public int getLevel() {\r
+    return level; \r
+  }\r
+}\r