2 // Java Spatial Index Library
\r
3 // Copyright (C) 2002-2005 Infomatiq Limited.
\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
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
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
19 package com.infomatiq.jsi.rtree;
\r
21 import gnu.trove.TFloatArrayList;
\r
22 import gnu.trove.TIntArrayList;
\r
23 import gnu.trove.TIntProcedure;
\r
27 * Sorted List, backed by a TArrayList.
\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
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
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
40 * This class is not optimised for large values of preferredMaximumSize. Values greater than,
\r
41 * say, 5, are not recommended.
\r
44 * @author aled@sourceforge.net
\r
47 public class SortedList {
\r
48 private static final int DEFAULT_PREFERRED_MAXIMUM_SIZE = 10;
\r
50 private int preferredMaximumSize = 1;
\r
51 private TIntArrayList ids = null;
\r
52 private TFloatArrayList priorities = null;
\r
54 public void init(int preferredMaximumSize) {
\r
55 this.preferredMaximumSize = preferredMaximumSize;
\r
56 ids.clear(preferredMaximumSize);
\r
57 priorities.clear(preferredMaximumSize);
\r
60 public void reset() {
\r
65 public SortedList() {
\r
66 ids = new TIntArrayList(DEFAULT_PREFERRED_MAXIMUM_SIZE);
\r
67 priorities = new TFloatArrayList(DEFAULT_PREFERRED_MAXIMUM_SIZE);
\r
70 public void add(int id, float priority) {
\r
71 float lowestPriority = Float.NEGATIVE_INFINITY;
\r
73 if (priorities.size() > 0) {
\r
74 lowestPriority = priorities.get(priorities.size() - 1);
\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
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
90 if (lowestPriorityIndex >= preferredMaximumSize - 1) {
\r
91 ids.remove(lowestPriorityIndex, ids.size() - lowestPriorityIndex);
\r
92 priorities.remove(lowestPriorityIndex, priorities.size() - lowestPriorityIndex);
\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
103 ids.insert(insertPosition, id);
\r
104 priorities.insert(insertPosition, priority);
\r
109 * return the lowest priority currently stored, or float.NEGATIVE_INFINITY if no
\r
110 * entries are stored
\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
117 return lowestPriority;
\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
128 public int[] toNativeArray() {
\r
129 return ids.toNativeArray();
\r