content: //   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 net.sf.jsi.rtree;
  
  import java.io.Serializable;
  
  import gnu.trove.list.array.TFloatArrayList;
  import gnu.trove.list.array.TIntArrayList;
  import gnu.trove.procedure.TIntProcedure;
  
  /**
   * <p>
   * 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.
   * </p>
   */
  public class SortedList implements Serializable {
    private static final long serialVersionUID = -1549539544212731131L;
  
    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.toArray();
    }
  }
  