001 /*
002 * Licensed to the Apache Software Foundation (ASF) under one or more
003 * contributor license agreements. See the NOTICE file distributed with
004 * this work for additional information regarding copyright ownership.
005 * The ASF licenses this file to You under the Apache License, Version 2.0
006 * (the "License"); you may not use this file except in compliance with
007 * the License. You may obtain a copy of the License at
008 *
009 * http://www.apache.org/licenses/LICENSE-2.0
010 *
011 * Unless required by applicable law or agreed to in writing, software
012 * distributed under the License is distributed on an "AS IS" BASIS,
013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
014 * See the License for the specific language governing permissions and
015 * limitations under the License.
016 */
017 package org.apache.commons.collections;
018
019 import java.util.AbstractCollection;
020 import java.util.Comparator;
021 import java.util.Iterator;
022 import java.util.NoSuchElementException;
023
024 /**
025 * Binary heap implementation of <code>PriorityQueue</code>.
026 * <p>
027 * The <code>PriorityQueue</code> interface has now been replaced for most uses
028 * by the <code>Buffer</code> interface. This class and the interface are
029 * retained for backwards compatibility. The intended replacement is
030 * {@link org.apache.commons.collections.buffer.PriorityBuffer PriorityBuffer}.
031 * <p>
032 * The removal order of a binary heap is based on either the natural sort
033 * order of its elements or a specified {@link Comparator}. The
034 * {@link #pop()} method always returns the first element as determined
035 * by the sort order. (The <code>isMinHeap</code> flag in the constructors
036 * can be used to reverse the sort order, in which case {@link #pop()}
037 * will always remove the last element.) The removal order is
038 * <i>not</i> the same as the order of iteration; elements are
039 * returned by the iterator in no particular order.
040 * <p>
041 * The {@link #insert(Object)} and {@link #pop()} operations perform
042 * in logarithmic time. The {@link #peek()} operation performs in constant
043 * time. All other operations perform in linear time or worse.
044 * <p>
045 * Note that this implementation is not synchronized. Use SynchronizedPriorityQueue
046 * to provide synchronized access to a <code>BinaryHeap</code>:
047 *
048 * <pre>
049 * PriorityQueue heap = new SynchronizedPriorityQueue(new BinaryHeap());
050 * </pre>
051 *
052 * @deprecated Replaced by PriorityBuffer in buffer subpackage.
053 * Due to be removed in v4.0.
054 * @since Commons Collections 1.0
055 * @version $Revision: 646777 $ $Date: 2008-04-10 13:33:15 +0100 (Thu, 10 Apr 2008) $
056 *
057 * @author Peter Donald
058 * @author Ram Chidambaram
059 * @author Michael A. Smith
060 * @author Paul Jack
061 * @author Stephen Colebourne
062 */
063 public final class BinaryHeap extends AbstractCollection
064 implements PriorityQueue, Buffer {
065
066 /**
067 * The default capacity for a binary heap.
068 */
069 private final static int DEFAULT_CAPACITY = 13;
070 /**
071 * The number of elements currently in this heap.
072 */
073 int m_size; // package scoped for testing
074 /**
075 * The elements in this heap.
076 */
077 Object[] m_elements; // package scoped for testing
078 /**
079 * If true, the first element as determined by the sort order will
080 * be returned. If false, the last element as determined by the
081 * sort order will be returned.
082 */
083 boolean m_isMinHeap; // package scoped for testing
084 /**
085 * The comparator used to order the elements
086 */
087 Comparator m_comparator; // package scoped for testing
088
089 /**
090 * Constructs a new minimum binary heap.
091 */
092 public BinaryHeap() {
093 this(DEFAULT_CAPACITY, true);
094 }
095
096 /**
097 * Constructs a new <code>BinaryHeap</code> that will use the given
098 * comparator to order its elements.
099 *
100 * @param comparator the comparator used to order the elements, null
101 * means use natural order
102 */
103 public BinaryHeap(Comparator comparator) {
104 this();
105 m_comparator = comparator;
106 }
107
108 /**
109 * Constructs a new minimum binary heap with the specified initial capacity.
110 *
111 * @param capacity The initial capacity for the heap. This value must
112 * be greater than zero.
113 * @throws IllegalArgumentException
114 * if <code>capacity</code> is <= <code>0</code>
115 */
116 public BinaryHeap(int capacity) {
117 this(capacity, true);
118 }
119
120 /**
121 * Constructs a new <code>BinaryHeap</code>.
122 *
123 * @param capacity the initial capacity for the heap
124 * @param comparator the comparator used to order the elements, null
125 * means use natural order
126 * @throws IllegalArgumentException
127 * if <code>capacity</code> is <= <code>0</code>
128 */
129 public BinaryHeap(int capacity, Comparator comparator) {
130 this(capacity);
131 m_comparator = comparator;
132 }
133
134 /**
135 * Constructs a new minimum or maximum binary heap
136 *
137 * @param isMinHeap if <code>true</code> the heap is created as a
138 * minimum heap; otherwise, the heap is created as a maximum heap
139 */
140 public BinaryHeap(boolean isMinHeap) {
141 this(DEFAULT_CAPACITY, isMinHeap);
142 }
143
144 /**
145 * Constructs a new <code>BinaryHeap</code>.
146 *
147 * @param isMinHeap true to use the order imposed by the given
148 * comparator; false to reverse that order
149 * @param comparator the comparator used to order the elements, null
150 * means use natural order
151 */
152 public BinaryHeap(boolean isMinHeap, Comparator comparator) {
153 this(isMinHeap);
154 m_comparator = comparator;
155 }
156
157 /**
158 * Constructs a new minimum or maximum binary heap with the specified
159 * initial capacity.
160 *
161 * @param capacity the initial capacity for the heap. This value must
162 * be greater than zero.
163 * @param isMinHeap if <code>true</code> the heap is created as a
164 * minimum heap; otherwise, the heap is created as a maximum heap.
165 * @throws IllegalArgumentException
166 * if <code>capacity</code> is <code><= 0</code>
167 */
168 public BinaryHeap(int capacity, boolean isMinHeap) {
169 if (capacity <= 0) {
170 throw new IllegalArgumentException("invalid capacity");
171 }
172 m_isMinHeap = isMinHeap;
173
174 //+1 as 0 is noop
175 m_elements = new Object[capacity + 1];
176 }
177
178 /**
179 * Constructs a new <code>BinaryHeap</code>.
180 *
181 * @param capacity the initial capacity for the heap
182 * @param isMinHeap true to use the order imposed by the given
183 * comparator; false to reverse that order
184 * @param comparator the comparator used to order the elements, null
185 * means use natural order
186 * @throws IllegalArgumentException
187 * if <code>capacity</code> is <code><= 0</code>
188 */
189 public BinaryHeap(int capacity, boolean isMinHeap, Comparator comparator) {
190 this(capacity, isMinHeap);
191 m_comparator = comparator;
192 }
193
194 //-----------------------------------------------------------------------
195 /**
196 * Clears all elements from queue.
197 */
198 public void clear() {
199 m_elements = new Object[m_elements.length]; // for gc
200 m_size = 0;
201 }
202
203 /**
204 * Tests if queue is empty.
205 *
206 * @return <code>true</code> if queue is empty; <code>false</code>
207 * otherwise.
208 */
209 public boolean isEmpty() {
210 return m_size == 0;
211 }
212
213 /**
214 * Tests if queue is full.
215 *
216 * @return <code>true</code> if queue is full; <code>false</code>
217 * otherwise.
218 */
219 public boolean isFull() {
220 //+1 as element 0 is noop
221 return m_elements.length == m_size + 1;
222 }
223
224 /**
225 * Inserts an element into queue.
226 *
227 * @param element the element to be inserted
228 */
229 public void insert(Object element) {
230 if (isFull()) {
231 grow();
232 }
233 //percolate element to it's place in tree
234 if (m_isMinHeap) {
235 percolateUpMinHeap(element);
236 } else {
237 percolateUpMaxHeap(element);
238 }
239 }
240
241 /**
242 * Returns the element on top of heap but don't remove it.
243 *
244 * @return the element at top of heap
245 * @throws NoSuchElementException if <code>isEmpty() == true</code>
246 */
247 public Object peek() throws NoSuchElementException {
248 if (isEmpty()) {
249 throw new NoSuchElementException();
250 } else {
251 return m_elements[1];
252 }
253 }
254
255 /**
256 * Returns the element on top of heap and remove it.
257 *
258 * @return the element at top of heap
259 * @throws NoSuchElementException if <code>isEmpty() == true</code>
260 */
261 public Object pop() throws NoSuchElementException {
262 final Object result = peek();
263 m_elements[1] = m_elements[m_size--];
264
265 // set the unused element to 'null' so that the garbage collector
266 // can free the object if not used anywhere else.(remove reference)
267 m_elements[m_size + 1] = null;
268
269 if (m_size != 0) {
270 // percolate top element to it's place in tree
271 if (m_isMinHeap) {
272 percolateDownMinHeap(1);
273 } else {
274 percolateDownMaxHeap(1);
275 }
276 }
277
278 return result;
279 }
280
281 /**
282 * Percolates element down heap from the position given by the index.
283 * <p>
284 * Assumes it is a minimum heap.
285 *
286 * @param index the index for the element
287 */
288 protected void percolateDownMinHeap(final int index) {
289 final Object element = m_elements[index];
290 int hole = index;
291
292 while ((hole * 2) <= m_size) {
293 int child = hole * 2;
294
295 // if we have a right child and that child can not be percolated
296 // up then move onto other child
297 if (child != m_size && compare(m_elements[child + 1], m_elements[child]) < 0) {
298 child++;
299 }
300
301 // if we found resting place of bubble then terminate search
302 if (compare(m_elements[child], element) >= 0) {
303 break;
304 }
305
306 m_elements[hole] = m_elements[child];
307 hole = child;
308 }
309
310 m_elements[hole] = element;
311 }
312
313 /**
314 * Percolates element down heap from the position given by the index.
315 * <p>
316 * Assumes it is a maximum heap.
317 *
318 * @param index the index of the element
319 */
320 protected void percolateDownMaxHeap(final int index) {
321 final Object element = m_elements[index];
322 int hole = index;
323
324 while ((hole * 2) <= m_size) {
325 int child = hole * 2;
326
327 // if we have a right child and that child can not be percolated
328 // up then move onto other child
329 if (child != m_size && compare(m_elements[child + 1], m_elements[child]) > 0) {
330 child++;
331 }
332
333 // if we found resting place of bubble then terminate search
334 if (compare(m_elements[child], element) <= 0) {
335 break;
336 }
337
338 m_elements[hole] = m_elements[child];
339 hole = child;
340 }
341
342 m_elements[hole] = element;
343 }
344
345 /**
346 * Percolates element up heap from the position given by the index.
347 * <p>
348 * Assumes it is a minimum heap.
349 *
350 * @param index the index of the element to be percolated up
351 */
352 protected void percolateUpMinHeap(final int index) {
353 int hole = index;
354 Object element = m_elements[hole];
355 while (hole > 1 && compare(element, m_elements[hole / 2]) < 0) {
356 // save element that is being pushed down
357 // as the element "bubble" is percolated up
358 final int next = hole / 2;
359 m_elements[hole] = m_elements[next];
360 hole = next;
361 }
362 m_elements[hole] = element;
363 }
364
365 /**
366 * Percolates a new element up heap from the bottom.
367 * <p>
368 * Assumes it is a minimum heap.
369 *
370 * @param element the element
371 */
372 protected void percolateUpMinHeap(final Object element) {
373 m_elements[++m_size] = element;
374 percolateUpMinHeap(m_size);
375 }
376
377 /**
378 * Percolates element up heap from from the position given by the index.
379 * <p>
380 * Assume it is a maximum heap.
381 *
382 * @param index the index of the element to be percolated up
383 */
384 protected void percolateUpMaxHeap(final int index) {
385 int hole = index;
386 Object element = m_elements[hole];
387
388 while (hole > 1 && compare(element, m_elements[hole / 2]) > 0) {
389 // save element that is being pushed down
390 // as the element "bubble" is percolated up
391 final int next = hole / 2;
392 m_elements[hole] = m_elements[next];
393 hole = next;
394 }
395
396 m_elements[hole] = element;
397 }
398
399 /**
400 * Percolates a new element up heap from the bottom.
401 * <p>
402 * Assume it is a maximum heap.
403 *
404 * @param element the element
405 */
406 protected void percolateUpMaxHeap(final Object element) {
407 m_elements[++m_size] = element;
408 percolateUpMaxHeap(m_size);
409 }
410
411 /**
412 * Compares two objects using the comparator if specified, or the
413 * natural order otherwise.
414 *
415 * @param a the first object
416 * @param b the second object
417 * @return -ve if a less than b, 0 if they are equal, +ve if a greater than b
418 */
419 private int compare(Object a, Object b) {
420 if (m_comparator != null) {
421 return m_comparator.compare(a, b);
422 } else {
423 return ((Comparable) a).compareTo(b);
424 }
425 }
426
427 /**
428 * Increases the size of the heap to support additional elements
429 */
430 protected void grow() {
431 final Object[] elements = new Object[m_elements.length * 2];
432 System.arraycopy(m_elements, 0, elements, 0, m_elements.length);
433 m_elements = elements;
434 }
435
436 /**
437 * Returns a string representation of this heap. The returned string
438 * is similar to those produced by standard JDK collections.
439 *
440 * @return a string representation of this heap
441 */
442 public String toString() {
443 final StringBuffer sb = new StringBuffer();
444
445 sb.append("[ ");
446
447 for (int i = 1; i < m_size + 1; i++) {
448 if (i != 1) {
449 sb.append(", ");
450 }
451 sb.append(m_elements[i]);
452 }
453
454 sb.append(" ]");
455
456 return sb.toString();
457 }
458
459
460 /**
461 * Returns an iterator over this heap's elements.
462 *
463 * @return an iterator over this heap's elements
464 */
465 public Iterator iterator() {
466 return new Iterator() {
467
468 private int index = 1;
469 private int lastReturnedIndex = -1;
470
471 public boolean hasNext() {
472 return index <= m_size;
473 }
474
475 public Object next() {
476 if (!hasNext()) throw new NoSuchElementException();
477 lastReturnedIndex = index;
478 index++;
479 return m_elements[lastReturnedIndex];
480 }
481
482 public void remove() {
483 if (lastReturnedIndex == -1) {
484 throw new IllegalStateException();
485 }
486 m_elements[ lastReturnedIndex ] = m_elements[ m_size ];
487 m_elements[ m_size ] = null;
488 m_size--;
489 if( m_size != 0 && lastReturnedIndex <= m_size) {
490 int compareToParent = 0;
491 if (lastReturnedIndex > 1) {
492 compareToParent = compare(m_elements[lastReturnedIndex],
493 m_elements[lastReturnedIndex / 2]);
494 }
495 if (m_isMinHeap) {
496 if (lastReturnedIndex > 1 && compareToParent < 0) {
497 percolateUpMinHeap(lastReturnedIndex);
498 } else {
499 percolateDownMinHeap(lastReturnedIndex);
500 }
501 } else { // max heap
502 if (lastReturnedIndex > 1 && compareToParent > 0) {
503 percolateUpMaxHeap(lastReturnedIndex);
504 } else {
505 percolateDownMaxHeap(lastReturnedIndex);
506 }
507 }
508 }
509 index--;
510 lastReturnedIndex = -1;
511 }
512
513 };
514 }
515
516
517 /**
518 * Adds an object to this heap. Same as {@link #insert(Object)}.
519 *
520 * @param object the object to add
521 * @return true, always
522 */
523 public boolean add(Object object) {
524 insert(object);
525 return true;
526 }
527
528 /**
529 * Returns the priority element. Same as {@link #peek()}.
530 *
531 * @return the priority element
532 * @throws BufferUnderflowException if this heap is empty
533 */
534 public Object get() {
535 try {
536 return peek();
537 } catch (NoSuchElementException e) {
538 throw new BufferUnderflowException();
539 }
540 }
541
542 /**
543 * Removes the priority element. Same as {@link #pop()}.
544 *
545 * @return the removed priority element
546 * @throws BufferUnderflowException if this heap is empty
547 */
548 public Object remove() {
549 try {
550 return pop();
551 } catch (NoSuchElementException e) {
552 throw new BufferUnderflowException();
553 }
554 }
555
556 /**
557 * Returns the number of elements in this heap.
558 *
559 * @return the number of elements in this heap
560 */
561 public int size() {
562 return m_size;
563 }
564
565 }