bundles/org.simantics.scenegraph/src/com/infomatiq/jsi/rtree/SortedList.java

   1 //   SortedList.java\r
   2 //   Java Spatial Index Library\r
   3 //   Copyright (C) 2002-2005 Infomatiq Limited.\r
   4 //\r
   5 //  This library is free software; you can redistribute it and/or\r
   6 //  modify it under the terms of the GNU Lesser General Public\r
   7 //  License as published by the Free Software Foundation; either\r
   8 //  version 2.1 of the License, or (at your option) any later version.\r
   9 //\r
  10 //  This library is distributed in the hope that it will be useful,\r
  11 //  but WITHOUT ANY WARRANTY; without even the implied warranty of\r
  12 //  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU\r
  13 //  Lesser General Public License for more details.\r
  14 //\r
  15 //  You should have received a copy of the GNU Lesser General Public\r
  16 //  License along with this library; if not, write to the Free Software\r
  17 //  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA\r
  18 \r
  19 package com.infomatiq.jsi.rtree;\r
  20 \r
  21 import gnu.trove.TFloatArrayList;\r
  22 import gnu.trove.TIntArrayList;\r
  23 import gnu.trove.TIntProcedure;\r
  24 \r
  25 /**\r
  26  * <p>\r
  27  * Sorted List, backed by a TArrayList.\r
  28  * \r
  29  * The elements in the list are always ordered by priority.\r
  30  * Methods exists to remove elements with the highest and lowest priorities.\r
  31  * \r
  32  * If more than one element has the highest priority, they will\r
  33  * all be removed by calling removeHighest. Ditto for the lowest priority.\r
  34  * \r
  35  * The list has a preferred maximum size. If possible, entries with the lowest priority\r
  36  * will be removed to limit the maximum size. Note that entries with the lowest priority\r
  37  * will not be removed if this would leave fewer than the preferred maximum number\r
  38  * of entries.\r
  39  * \r
  40  * This class is not optimised for large values of preferredMaximumSize. Values greater than,\r
  41  * say, 5, are not recommended.\r
  42  * </p>\r
  43  * \r
  44  * @author aled@sourceforge.net\r
  45  * @version 1.0b8\r
  46  */\r
  47 public class SortedList {\r
  48   private static final int DEFAULT_PREFERRED_MAXIMUM_SIZE = 10;\r
  49   \r
  50   private int preferredMaximumSize = 1;\r
  51   private TIntArrayList ids = null;\r
  52   private TFloatArrayList priorities = null;\r
  53   \r
  54   public void init(int preferredMaximumSize) {\r
  55     this.preferredMaximumSize = preferredMaximumSize;\r
  56     ids.clear(preferredMaximumSize);\r
  57     priorities.clear(preferredMaximumSize); \r
  58   }  \r
  59  \r
  60   public void reset() {\r
  61     ids.reset();\r
  62     priorities.reset();\r
  63   }\r
  64  \r
  65   public SortedList() {\r
  66     ids = new TIntArrayList(DEFAULT_PREFERRED_MAXIMUM_SIZE);\r
  67     priorities = new TFloatArrayList(DEFAULT_PREFERRED_MAXIMUM_SIZE);\r
  68   }\r
  69   \r
  70   public void add(int id, float priority) {\r
  71     float lowestPriority = Float.NEGATIVE_INFINITY;\r
  72     \r
  73     if (priorities.size() > 0) {\r
  74       lowestPriority = priorities.get(priorities.size() - 1);\r
  75     }\r
  76     \r
  77     if ((priority == lowestPriority) ||\r
  78         (priority < lowestPriority && ids.size() < preferredMaximumSize)) { \r
  79       // simply add the new entry at the lowest priority end\r
  80       ids.add(id);\r
  81       priorities.add(priority);\r
  82     } else if (priority > lowestPriority) {\r
  83       if (ids.size() >= preferredMaximumSize) {\r
  84         int lowestPriorityIndex = ids.size() - 1;\r
  85         while ((lowestPriorityIndex - 1 >= 0) &&\r
  86                (priorities.get(lowestPriorityIndex - 1) == lowestPriority)) {\r
  87           lowestPriorityIndex--;\r
  88         }\r
  89         \r
  90         if (lowestPriorityIndex >= preferredMaximumSize - 1) {\r
  91           ids.remove(lowestPriorityIndex, ids.size() - lowestPriorityIndex); \r
  92           priorities.remove(lowestPriorityIndex, priorities.size() - lowestPriorityIndex); \r
  93         }\r
  94       }\r
  95     \r
  96       // put the new entry in the correct position. Could do a binary search here if the \r
  97       // preferredMaximumSize was large.\r
  98       int insertPosition = ids.size();\r
  99       while (insertPosition - 1 >= 0 && priority > priorities.get(insertPosition - 1)) {\r
 100         insertPosition--;  \r
 101       }\r
 102       \r
 103       ids.insert(insertPosition, id);\r
 104       priorities.insert(insertPosition, priority);\r
 105     }\r
 106   }\r
 107   \r
 108   /**\r
 109    * return the lowest priority currently stored, or float.NEGATIVE_INFINITY if no\r
 110    * entries are stored\r
 111    */\r
 112   public float getLowestPriority() {\r
 113     float lowestPriority = Float.NEGATIVE_INFINITY;\r
 114     if (priorities.size() >= preferredMaximumSize) {\r
 115       lowestPriority = priorities.get(priorities.size() - 1);\r
 116     }\r
 117     return lowestPriority;\r
 118   }\r
 119   \r
 120   public void forEachId(TIntProcedure v) {\r
 121     for (int i = 0; i < ids.size(); i++) {\r
 122       if (!v.execute(ids.get(i))) {\r
 123         break;\r
 124       }\r
 125     }\r
 126   }\r
 127   \r
 128   public int[] toNativeArray() {\r
 129     return ids.toNativeArray(); \r
 130   }\r
 131 }\r