- * 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. - *
- * - * @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(); - } -} +// 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; + +/** + *+ * 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. + *
+ * + * @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(); + } +}