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