2 // Java Spatial Index Library
3 // Copyright (C) 2002-2005 Infomatiq Limited.
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.
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.
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
19 package com.infomatiq.jsi.rtree;
21 import gnu.trove.TFloatArrayList;
22 import gnu.trove.TIntArrayList;
23 import gnu.trove.TIntProcedure;
27 * Sorted List, backed by a TArrayList.
29 * The elements in the list are always ordered by priority.
30 * Methods exists to remove elements with the highest and lowest priorities.
32 * If more than one element has the highest priority, they will
33 * all be removed by calling removeHighest. Ditto for the lowest priority.
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
40 * This class is not optimised for large values of preferredMaximumSize. Values greater than,
41 * say, 5, are not recommended.
44 * @author aled@sourceforge.net
47 public class SortedList {
48 private static final int DEFAULT_PREFERRED_MAXIMUM_SIZE = 10;
50 private int preferredMaximumSize = 1;
51 private TIntArrayList ids = null;
52 private TFloatArrayList priorities = null;
54 public void init(int preferredMaximumSize) {
55 this.preferredMaximumSize = preferredMaximumSize;
56 ids.clear(preferredMaximumSize);
57 priorities.clear(preferredMaximumSize);
66 ids = new TIntArrayList(DEFAULT_PREFERRED_MAXIMUM_SIZE);
67 priorities = new TFloatArrayList(DEFAULT_PREFERRED_MAXIMUM_SIZE);
70 public void add(int id, float priority) {
71 float lowestPriority = Float.NEGATIVE_INFINITY;
73 if (priorities.size() > 0) {
74 lowestPriority = priorities.get(priorities.size() - 1);
77 if ((priority == lowestPriority) ||
78 (priority < lowestPriority && ids.size() < preferredMaximumSize)) {
79 // simply add the new entry at the lowest priority end
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--;
90 if (lowestPriorityIndex >= preferredMaximumSize - 1) {
91 ids.remove(lowestPriorityIndex, ids.size() - lowestPriorityIndex);
92 priorities.remove(lowestPriorityIndex, priorities.size() - lowestPriorityIndex);
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)) {
103 ids.insert(insertPosition, id);
104 priorities.insert(insertPosition, priority);
109 * return the lowest priority currently stored, or float.NEGATIVE_INFINITY if no
112 public float getLowestPriority() {
113 float lowestPriority = Float.NEGATIVE_INFINITY;
114 if (priorities.size() >= preferredMaximumSize) {
115 lowestPriority = priorities.get(priorities.size() - 1);
117 return lowestPriority;
120 public void forEachId(TIntProcedure v) {
121 for (int i = 0; i < ids.size(); i++) {
122 if (!v.execute(ids.get(i))) {
128 public int[] toNativeArray() {
129 return ids.toNativeArray();