Migrated source code from Simantics SVN

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

diff --git a/bundles/org.simantics.scenegraph/src/com/infomatiq/jsi/rtree/SortedList.java b/bundles/org.simantics.scenegraph/src/com/infomatiq/jsi/rtree/SortedList.java
new file mode 100644 (file)
index 0000000..3087699
--- /dev/null
+++ b/bundles/org.simantics.scenegraph/src/com/infomatiq/jsi/rtree/SortedList.java
@@ -0,0 +1,131 @@
+//   SortedList.java\r
+//   Java Spatial Index Library\r
+//   Copyright (C) 2002-2005 Infomatiq Limited.\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
+import gnu.trove.TFloatArrayList;\r
+import gnu.trove.TIntArrayList;\r
+import gnu.trove.TIntProcedure;\r
+\r
+/**\r
+ * <p>\r
+ * Sorted List, backed by a TArrayList.\r
+ * \r
+ * The elements in the list are always ordered by priority.\r
+ * Methods exists to remove elements with the highest and lowest priorities.\r
+ * \r
+ * If more than one element has the highest priority, they will\r
+ * all be removed by calling removeHighest. Ditto for the lowest priority.\r
+ * \r
+ * The list has a preferred maximum size. If possible, entries with the lowest priority\r
+ * will be removed to limit the maximum size. Note that entries with the lowest priority\r
+ * will not be removed if this would leave fewer than the preferred maximum number\r
+ * of entries.\r
+ * \r
+ * This class is not optimised for large values of preferredMaximumSize. Values greater than,\r
+ * say, 5, are not recommended.\r
+ * </p>\r
+ * \r
+ * @author aled@sourceforge.net\r
+ * @version 1.0b8\r
+ */\r
+public class SortedList {\r
+  private static final int DEFAULT_PREFERRED_MAXIMUM_SIZE = 10;\r
+  \r
+  private int preferredMaximumSize = 1;\r
+  private TIntArrayList ids = null;\r
+  private TFloatArrayList priorities = null;\r
+  \r
+  public void init(int preferredMaximumSize) {\r
+    this.preferredMaximumSize = preferredMaximumSize;\r
+    ids.clear(preferredMaximumSize);\r
+    priorities.clear(preferredMaximumSize); \r
+  }  \r
+ \r
+  public void reset() {\r
+    ids.reset();\r
+    priorities.reset();\r
+  }\r
+ \r
+  public SortedList() {\r
+    ids = new TIntArrayList(DEFAULT_PREFERRED_MAXIMUM_SIZE);\r
+    priorities = new TFloatArrayList(DEFAULT_PREFERRED_MAXIMUM_SIZE);\r
+  }\r
+  \r
+  public void add(int id, float priority) {\r
+    float lowestPriority = Float.NEGATIVE_INFINITY;\r
+    \r
+    if (priorities.size() > 0) {\r
+      lowestPriority = priorities.get(priorities.size() - 1);\r
+    }\r
+    \r
+    if ((priority == lowestPriority) ||\r
+        (priority < lowestPriority && ids.size() < preferredMaximumSize)) { \r
+      // simply add the new entry at the lowest priority end\r
+      ids.add(id);\r
+      priorities.add(priority);\r
+    } else if (priority > lowestPriority) {\r
+      if (ids.size() >= preferredMaximumSize) {\r
+        int lowestPriorityIndex = ids.size() - 1;\r
+        while ((lowestPriorityIndex - 1 >= 0) &&\r
+               (priorities.get(lowestPriorityIndex - 1) == lowestPriority)) {\r
+          lowestPriorityIndex--;\r
+        }\r
+        \r
+        if (lowestPriorityIndex >= preferredMaximumSize - 1) {\r
+          ids.remove(lowestPriorityIndex, ids.size() - lowestPriorityIndex); \r
+          priorities.remove(lowestPriorityIndex, priorities.size() - lowestPriorityIndex); \r
+        }\r
+      }\r
+    \r
+      // put the new entry in the correct position. Could do a binary search here if the \r
+      // preferredMaximumSize was large.\r
+      int insertPosition = ids.size();\r
+      while (insertPosition - 1 >= 0 && priority > priorities.get(insertPosition - 1)) {\r
+        insertPosition--;  \r
+      }\r
+      \r
+      ids.insert(insertPosition, id);\r
+      priorities.insert(insertPosition, priority);\r
+    }\r
+  }\r
+  \r
+  /**\r
+   * return the lowest priority currently stored, or float.NEGATIVE_INFINITY if no\r
+   * entries are stored\r
+   */\r
+  public float getLowestPriority() {\r
+    float lowestPriority = Float.NEGATIVE_INFINITY;\r
+    if (priorities.size() >= preferredMaximumSize) {\r
+      lowestPriority = priorities.get(priorities.size() - 1);\r
+    }\r
+    return lowestPriority;\r
+  }\r
+  \r
+  public void forEachId(TIntProcedure v) {\r
+    for (int i = 0; i < ids.size(); i++) {\r
+      if (!v.execute(ids.get(i))) {\r
+        break;\r
+      }\r
+    }\r
+  }\r
+  \r
+  public int[] toNativeArray() {\r
+    return ids.toNativeArray(); \r
+  }\r
+}\r