-// 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
+// Node.java
+// Java Spatial Index Library
+// Copyright (C) 2002-2005 Infomatiq Limited
+// Copyright (C) 2008-2010 aled@sourceforge.net
+//
+// 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;
+
+/**
+ * <p>Used by RTree. There are no public methods in this class.</p>
+ *
+ * @author aled.morris@infomatiq.co.uk
+ * @version 1.0b8
+ */
+public class Node {
+ int nodeId = 0;
+ float mbrMinX = Float.MAX_VALUE;
+ float mbrMinY = Float.MAX_VALUE;
+ float mbrMaxX = -Float.MAX_VALUE;
+ float mbrMaxY = -Float.MAX_VALUE;
+
+ float[] entriesMinX = null;
+ float[] entriesMinY = null;
+ float[] entriesMaxX = null;
+ float[] entriesMaxY = null;
+
+ int[] ids = null;
+ int level;
+ int entryCount;
+
+ Node(int nodeId, int level, int maxNodeEntries) {
+ this.nodeId = nodeId;
+ this.level = level;
+ entriesMinX = new float[maxNodeEntries];
+ entriesMinY = new float[maxNodeEntries];
+ entriesMaxX = new float[maxNodeEntries];
+ entriesMaxY = new float[maxNodeEntries];
+ ids = new int[maxNodeEntries];
+ }
+
+ void addEntry(float minX, float minY, float maxX, float maxY, int id) {
+ ids[entryCount] = id;
+ entriesMinX[entryCount] = minX;
+ entriesMinY[entryCount] = minY;
+ entriesMaxX[entryCount] = maxX;
+ entriesMaxY[entryCount] = maxY;
+
+ if (minX < mbrMinX) mbrMinX = minX;
+ if (minY < mbrMinY) mbrMinY = minY;
+ if (maxX > mbrMaxX) mbrMaxX = maxX;
+ if (maxY > mbrMaxY) mbrMaxY = maxY;
+
+ entryCount++;
+ }
+
+ // Return the index of the found entry, or -1 if not found
+ int findEntry(float minX, float minY, float maxX, float maxY, int id) {
+ for (int i = 0; i < entryCount; i++) {
+ if (id == ids[i] &&
+ entriesMinX[i] == minX && entriesMinY[i] == minY &&
+ entriesMaxX[i] == maxX && entriesMaxY[i] == maxY) {
+ 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 lastIndex = entryCount - 1;
+ float deletedMinX = entriesMinX[i];
+ float deletedMinY = entriesMinY[i];
+ float deletedMaxX = entriesMaxX[i];
+ float deletedMaxY = entriesMaxY[i];
+
+ if (i != lastIndex) {
+ entriesMinX[i] = entriesMinX[lastIndex];
+ entriesMinY[i] = entriesMinY[lastIndex];
+ entriesMaxX[i] = entriesMaxX[lastIndex];
+ entriesMaxY[i] = entriesMaxY[lastIndex];
+ ids[i] = ids[lastIndex];
+ }
+ entryCount--;
+
+ // adjust the MBR
+ recalculateMBRIfInfluencedBy(deletedMinX, deletedMinY, deletedMaxX, deletedMaxY);
+ }
+
+ // deletedMin/MaxX/Y is a rectangle that has just been deleted or made smaller.
+ // Thus, the MBR is only recalculated if the deleted rectangle influenced the old MBR
+ void recalculateMBRIfInfluencedBy(float deletedMinX, float deletedMinY, float deletedMaxX, float deletedMaxY) {
+ if (mbrMinX == deletedMinX || mbrMinY == deletedMinY || mbrMaxX == deletedMaxX || mbrMaxY == deletedMaxY) {
+ recalculateMBR();
+ }
+ }
+
+ void recalculateMBR() {
+ mbrMinX = entriesMinX[0];
+ mbrMinY = entriesMinY[0];
+ mbrMaxX = entriesMaxX[0];
+ mbrMaxY = entriesMaxY[0];
+
+ for (int i = 1; i < entryCount; i++) {
+ if (entriesMinX[i] < mbrMinX) mbrMinX = entriesMinX[i];
+ if (entriesMinY[i] < mbrMinY) mbrMinY = entriesMinY[i];
+ if (entriesMaxX[i] > mbrMaxX) mbrMaxX = entriesMaxX[i];
+ if (entriesMaxY[i] > mbrMaxY) mbrMaxY = entriesMaxY[i];
+ }
+ }
+
+ /**
+ * 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 (ids[index] == -1) {
+ while (ids[countdownIndex] == -1 && countdownIndex > index) {
+ countdownIndex--;
+ }
+ entriesMinX[index] = entriesMinX[countdownIndex];
+ entriesMinY[index] = entriesMinY[countdownIndex];
+ entriesMaxX[index] = entriesMaxX[countdownIndex];
+ entriesMaxY[index] = entriesMaxY[countdownIndex];
+ ids[index] = ids[countdownIndex];
+ ids[countdownIndex] = -1;
+ }
+ }
+ }
+
+ public int getEntryCount() {
+ return entryCount;
+ }
+
+ public int getId(int index) {
+ if (index < entryCount) {
+ return ids[index];
+ }
+ return -1;
+ }
+
+ boolean isLeaf() {
+ return (level == 1);
+ }
+
+ public int getLevel() {
+ return level;
+ }
+}
Code Review / simantics / platform.git / blobdiff