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