bundles/org.simantics.scenegraph/src/com/infomatiq/jsi/PriorityQueue.java

   1 //  PriorityQueue.java
   2 //  Java Spatial Index Library
   3 //  Copyright (C) 2008 aled@sourceforge.net
   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;
  20
  21 import gnu.trove.TIntArrayList;
  22 import gnu.trove.TFloatArrayList;
  23
  24 /**
  25  * <p>
  26  * Priority Queue that stores values as ints and priorities as floats. Uses a
  27  * Heap to sort the priorities; the values are sorted "in step" with the
  28  * priorities.
  29  * </p>
  30  * <p>
  31  * A Heap is simply an array that is kept semi sorted; in particular if the
  32  * elements of the array are arranged in a tree structure; ie
  33  * </p>
  34  *
  35  *                                   00
  36  *                                 /     \
  37  *                             01          02
  38  *                            /  \        /  \
  39  *                          03    04    05    06
  40  *                          /\    /\    /\    /\
  41  *                        07 08 09 10 11 12 13 14
  42  *
  43  * <p>
  44  * then each parent is kept sorted with respect to it's immediate children. E.g.
  45  * 00 < 01, 00 < 02, 02 < 05, 02 < 06
  46  * </p>
  47  * <p>
  48  * This means that the array appears to be sorted, as long as we only ever look
  49  * at element 0.
  50  * </p>
  51  * <p>
  52  * Inserting new elements is much faster than if the entire array was kept
  53  * sorted; a new element is appended to the array, and then recursively swapped
  54  * with each parent to maintain the "parent is sorted w.r.t it's children"
  55  * property.
  56  * </p>
  57  * <p>
  58  * To return the "next" value it is necessary to remove the root element. The
  59  * last element in the array is placed in the root of the tree, and is
  60  * recursively swapped with one of it's children until the "parent is sorted
  61  * w.r.t it's children" property is restored.
  62  * </p>
  63  * <p>
  64  * Random access is slow (eg for deleting a particular value), and is not
  65  * implemented here - if this functionality is required, then a heap probably
  66  * isn't the right data structure.
  67  * </p>
  68  * @author Aled Morris <aled@sourceforge.net>
  69  * @version 1.0b8
  70  */
  71 public class PriorityQueue {
  72   public static final boolean SORT_ORDER_ASCENDING = true;
  73   public static final boolean SORT_ORDER_DESCENDING = false;
  74
  75   private TIntArrayList values = null;
  76   private TFloatArrayList priorities = null;
  77   private boolean sortOrder = SORT_ORDER_ASCENDING;
  78
  79   private static boolean INTERNAL_CONSISTENCY_CHECKING = false;
  80
  81   public PriorityQueue(boolean sortOrder) {
  82     this(sortOrder, 10);
  83   }
  84
  85   public PriorityQueue(boolean sortOrder, int initialCapacity) {
  86     this.sortOrder = sortOrder;
  87     values = new TIntArrayList(initialCapacity);
  88     priorities = new TFloatArrayList(initialCapacity);
  89   }
  90
  91   /**
  92    * @param p1
  93    * @param p2
  94    * @return true if p1 has an earlier sort order than p2.
  95    */
  96   private boolean sortsEarlierThan(float p1, float p2) {
  97     if (sortOrder == SORT_ORDER_ASCENDING) {
  98       return p1 < p2;
  99     }
 100     return p2 < p1;
 101   }
 102
 103   // to insert a value, append it to the arrays, then
 104   // reheapify by promoting it to the correct place.
 105   public void insert(int value, float priority) {
 106     values.add(value);
 107     priorities.add(priority);
 108
 109     promote(values.size() - 1, value, priority);
 110   }
 111
 112   private void promote(int index, int value, float priority) {
 113     // Consider the index to be a "hole"; i.e. don't swap priorities/values
 114     // when moving up the tree, simply copy the parent into the hole and
 115     // then consider the parent to be the hole.
 116     // Finally, copy the value/priority into the hole.
 117     while (index > 0) {
 118       int parentIndex = (index - 1) / 2;
 119       float parentPriority = priorities.get(parentIndex);
 120
 121       if (sortsEarlierThan(parentPriority, priority)) {
 122         break;
 123       }
 124
 125       // copy the parent entry into the current index.
 126       values.set(index, values.get(parentIndex));
 127       priorities.set(index, parentPriority);
 128       index = parentIndex;
 129     }
 130
 131     values.set(index, value);
 132     priorities.set(index, priority);
 133
 134     if (INTERNAL_CONSISTENCY_CHECKING) {
 135       check();
 136     }
 137   }
 138
 139   public int size() {
 140     return values.size();
 141   }
 142
 143   public void clear() {
 144     values.clear();
 145     priorities.clear();
 146   }
 147
 148   public void reset() {
 149     values.reset();
 150     priorities.reset();
 151   }
 152
 153   public int getValue() {
 154     return values.get(0);
 155   }
 156
 157   public float getPriority() {
 158     return priorities.get(0);
 159   }
 160
 161   private void demote(int index, int value, float priority) {
 162     int childIndex = (index * 2) + 1; // left child
 163
 164     while (childIndex < values.size()) {
 165       float childPriority = priorities.get(childIndex);
 166
 167       if (childIndex + 1 < values.size()) {
 168         float rightPriority = priorities.get(childIndex + 1);
 169         if (sortsEarlierThan(rightPriority, childPriority)) {
 170           childPriority = rightPriority;
 171           childIndex++; // right child
 172         }
 173       }
 174
 175       if (sortsEarlierThan(childPriority, priority)) {
 176         priorities.set(index, childPriority);
 177         values.set(index, values.get(childIndex));
 178         index = childIndex;
 179         childIndex = (index * 2) + 1;
 180       } else {
 181         break;
 182       }
 183     }
 184
 185     values.set(index, value);
 186     priorities.set(index, priority);
 187   }
 188
 189   // get the value with the lowest priority
 190   // creates a "hole" at the root of the tree.
 191   // The algorithm swaps the hole with the appropriate child, until
 192   // the last entry will fit correctly into the hole (ie is lower
 193   // priority than its children)
 194   public int pop() {
 195     int ret = values.get(0);
 196
 197     // record the value/priority of the last entry
 198     int lastIndex = values.size() - 1;
 199     int tempValue = values.get(lastIndex);
 200     float tempPriority = priorities.get(lastIndex);
 201
 202     values.remove(lastIndex);
 203     priorities.remove(lastIndex);
 204
 205     if (lastIndex > 0) {
 206       demote(0, tempValue, tempPriority);
 207     }
 208
 209     if (INTERNAL_CONSISTENCY_CHECKING) {
 210       check();
 211     }
 212
 213     return ret;
 214   }
 215
 216   public void setSortOrder(boolean sortOrder) {
 217     if (this.sortOrder != sortOrder) {
 218       this.sortOrder = sortOrder;
 219       // reheapify the arrays
 220       for (int i = (values.size() / 2) - 1; i >= 0; i--) {
 221         demote(i, values.get(i), priorities.get(i));
 222       }
 223     }
 224     if (INTERNAL_CONSISTENCY_CHECKING) {
 225       check();
 226     }
 227   }
 228
 229   private void check() {
 230     // for each entry, check that the child entries have a lower or equal
 231     // priority
 232     int lastIndex = values.size() - 1;
 233
 234     for (int i = 0; i < values.size() / 2; i++) {
 235       float currentPriority = priorities.get(i);
 236
 237       int leftIndex = (i * 2) + 1;
 238       if (leftIndex <= lastIndex) {
 239         float leftPriority = priorities.get(leftIndex);
 240         if (sortsEarlierThan(leftPriority, currentPriority)) {
 241           System.err.println("Internal error in PriorityQueue");
 242         }
 243       }
 244
 245       int rightIndex = (i * 2) + 2;
 246       if (rightIndex <= lastIndex) {
 247         float rightPriority = priorities.get(rightIndex);
 248         if (sortsEarlierThan(rightPriority, currentPriority)) {
 249           System.err.println("Internal error in PriorityQueue");
 250         }
 251       }
 252     }
 253   }
 254 }