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

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