2 // Java Spatial Index Library
3 // Copyright (C) 2008 aled@sourceforge.net
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.
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.
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
19 package com.infomatiq.jsi;
21 import gnu.trove.TIntArrayList;
22 import gnu.trove.TFloatArrayList;
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
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
41 * 07 08 09 10 11 12 13 14
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
48 * This means that the array appears to be sorted, as long as we only ever look
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"
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.
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.
68 * @author Aled Morris <aled@sourceforge.net>
71 public class PriorityQueue {
72 public static final boolean SORT_ORDER_ASCENDING = true;
73 public static final boolean SORT_ORDER_DESCENDING = false;
75 private TIntArrayList values = null;
76 private TFloatArrayList priorities = null;
77 private boolean sortOrder = SORT_ORDER_ASCENDING;
79 private static boolean INTERNAL_CONSISTENCY_CHECKING = false;
81 public PriorityQueue(boolean sortOrder) {
85 public PriorityQueue(boolean sortOrder, int initialCapacity) {
86 this.sortOrder = sortOrder;
87 values = new TIntArrayList(initialCapacity);
88 priorities = new TFloatArrayList(initialCapacity);
94 * @return true if p1 has an earlier sort order than p2.
96 private boolean sortsEarlierThan(float p1, float p2) {
97 if (sortOrder == SORT_ORDER_ASCENDING) {
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) {
107 priorities.add(priority);
109 promote(values.size() - 1, value, priority);
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.
118 int parentIndex = (index - 1) / 2;
119 float parentPriority = priorities.get(parentIndex);
121 if (sortsEarlierThan(parentPriority, priority)) {
125 // copy the parent entry into the current index.
126 values.set(index, values.get(parentIndex));
127 priorities.set(index, parentPriority);
131 values.set(index, value);
132 priorities.set(index, priority);
134 if (INTERNAL_CONSISTENCY_CHECKING) {
140 return values.size();
143 public void clear() {
148 public void reset() {
153 public int getValue() {
154 return values.get(0);
157 public float getPriority() {
158 return priorities.get(0);
161 private void demote(int index, int value, float priority) {
162 int childIndex = (index * 2) + 1; // left child
164 while (childIndex < values.size()) {
165 float childPriority = priorities.get(childIndex);
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
175 if (sortsEarlierThan(childPriority, priority)) {
176 priorities.set(index, childPriority);
177 values.set(index, values.get(childIndex));
179 childIndex = (index * 2) + 1;
185 values.set(index, value);
186 priorities.set(index, priority);
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)
195 int ret = values.get(0);
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);
202 values.remove(lastIndex);
203 priorities.remove(lastIndex);
206 demote(0, tempValue, tempPriority);
209 if (INTERNAL_CONSISTENCY_CHECKING) {
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));
224 if (INTERNAL_CONSISTENCY_CHECKING) {
229 private void check() {
230 // for each entry, check that the child entries have a lower or equal
232 int lastIndex = values.size() - 1;
234 for (int i = 0; i < values.size() / 2; i++) {
235 float currentPriority = priorities.get(i);
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");
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");