X-Git-Url: https://gerrit.simantics.org/r/gitweb?a=blobdiff_plain;f=bundles%2Forg.simantics.scenegraph%2Fsrc%2Fcom%2Finfomatiq%2Fjsi%2Frtree%2FSortedList.java;fp=bundles%2Forg.simantics.scenegraph%2Fsrc%2Fcom%2Finfomatiq%2Fjsi%2Frtree%2FSortedList.java;h=30876995ec7da5e5ba14b01756bfb4271a382a99;hb=969bd23cab98a79ca9101af33334000879fb60c5;hp=0000000000000000000000000000000000000000;hpb=866dba5cd5a3929bbeae85991796acb212338a08;p=simantics%2Fplatform.git

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