KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > org > apache > commons > collections > BinaryHeap


1 /*
2  * Copyright 2001-2004 The Apache Software Foundation
3  *
4  * Licensed under the Apache License, Version 2.0 (the "License");
5  * you may not use this file except in compliance with the License.
6  * You may obtain a copy of the License at
7  *
8  * http://www.apache.org/licenses/LICENSE-2.0
9  *
10  * Unless required by applicable law or agreed to in writing, software
11  * distributed under the License is distributed on an "AS IS" BASIS,
12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  * See the License for the specific language governing permissions and
14  * limitations under the License.
15  */

16 package org.apache.commons.collections;
17
18 import java.util.AbstractCollection JavaDoc;
19 import java.util.Comparator JavaDoc;
20 import java.util.Iterator JavaDoc;
21 import java.util.NoSuchElementException JavaDoc;
22
23 /**
24  * Binary heap implementation of <code>PriorityQueue</code>.
25  * <p>
26  * The <code>PriorityQueue</code> interface has now been replaced for most uses
27  * by the <code>Buffer</code> interface. This class and the interface are
28  * retained for backwards compatibility. The intended replacement is
29  * {@link org.apache.commons.collections.buffer.PriorityBuffer PriorityBuffer}.
30  * <p>
31  * The removal order of a binary heap is based on either the natural sort
32  * order of its elements or a specified {@link Comparator}. The
33  * {@link #pop()} method always returns the first element as determined
34  * by the sort order. (The <code>isMinHeap</code> flag in the constructors
35  * can be used to reverse the sort order, in which case {@link #pop()}
36  * will always remove the last element.) The removal order is
37  * <i>not</i> the same as the order of iteration; elements are
38  * returned by the iterator in no particular order.
39  * <p>
40  * The {@link #insert(Object)} and {@link #pop()} operations perform
41  * in logarithmic time. The {@link #peek()} operation performs in constant
42  * time. All other operations perform in linear time or worse.
43  * <p>
44  * Note that this implementation is not synchronized. Use SynchronizedPriorityQueue
45  * to provide synchronized access to a <code>BinaryHeap</code>:
46  *
47  * <pre>
48  * PriorityQueue heap = new SynchronizedPriorityQueue(new BinaryHeap());
49  * </pre>
50  *
51  * @deprecated Replaced by PriorityBuffer in buffer subpackage.
52  * Due to be removed in v4.0.
53  * @since Commons Collections 1.0
54  * @version $Revision: 1.24 $ $Date: 2004/02/18 01:15:42 $
55  *
56  * @author Peter Donald
57  * @author Ram Chidambaram
58  * @author Michael A. Smith
59  * @author Paul Jack
60  * @author Stephen Colebourne
61  */

62 public final class BinaryHeap extends AbstractCollection JavaDoc
63         implements PriorityQueue, Buffer {
64
65     /**
66      * The default capacity for a binary heap.
67      */

68     private final static int DEFAULT_CAPACITY = 13;
69     /**
70      * The number of elements currently in this heap.
71      */

72     int m_size; // package scoped for testing
73
/**
74      * The elements in this heap.
75      */

76     Object JavaDoc[] m_elements; // package scoped for testing
77
/**
78      * If true, the first element as determined by the sort order will
79      * be returned. If false, the last element as determined by the
80      * sort order will be returned.
81      */

82     boolean m_isMinHeap; // package scoped for testing
83
/**
84      * The comparator used to order the elements
85      */

86     Comparator JavaDoc m_comparator; // package scoped for testing
87

88     /**
89      * Constructs a new minimum binary heap.
90      */

91     public BinaryHeap() {
92         this(DEFAULT_CAPACITY, true);
93     }
94
95     /**
96      * Constructs a new <code>BinaryHeap</code> that will use the given
97      * comparator to order its elements.
98      *
99      * @param comparator the comparator used to order the elements, null
100      * means use natural order
101      */

102     public BinaryHeap(Comparator JavaDoc 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 &lt;= <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 &lt;= <code>0</code>
127      */

128     public BinaryHeap(int capacity, Comparator JavaDoc 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 JavaDoc 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>&lt;= 0</code>
166      */

167     public BinaryHeap(int capacity, boolean isMinHeap) {
168         if (capacity <= 0) {
169             throw new IllegalArgumentException JavaDoc("invalid capacity");
170         }
171         m_isMinHeap = isMinHeap;
172
173         //+1 as 0 is noop
174
m_elements = new Object JavaDoc[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>&lt;= 0</code>
187      */

188     public BinaryHeap(int capacity, boolean isMinHeap, Comparator JavaDoc comparator) {
189         this(capacity, isMinHeap);
190         m_comparator = comparator;
191     }
192
193     //-----------------------------------------------------------------------
194
/**
195      * Clears all elements from queue.
196      */

197     public void clear() {
198         m_elements = new Object JavaDoc[m_elements.length]; // for gc
199
m_size = 0;
200     }
201
202     /**
203      * Tests if queue is empty.
204      *
205      * @return <code>true</code> if queue is empty; <code>false</code>
206      * otherwise.
207      */

208     public boolean isEmpty() {
209         return m_size == 0;
210     }
211
212     /**
213      * Tests if queue is full.
214      *
215      * @return <code>true</code> if queue is full; <code>false</code>
216      * otherwise.
217      */

218     public boolean isFull() {
219         //+1 as element 0 is noop
220
return m_elements.length == m_size + 1;
221     }
222
223     /**
224      * Inserts an element into queue.
225      *
226      * @param element the element to be inserted
227      */

228     public void insert(Object JavaDoc element) {
229         if (isFull()) {
230             grow();
231         }
232         //percolate element to it's place in tree
233
if (m_isMinHeap) {
234             percolateUpMinHeap(element);
235         } else {
236             percolateUpMaxHeap(element);
237         }
238     }
239
240     /**
241      * Returns the element on top of heap but don't remove it.
242      *
243      * @return the element at top of heap
244      * @throws NoSuchElementException if <code>isEmpty() == true</code>
245      */

246     public Object JavaDoc peek() throws NoSuchElementException JavaDoc {
247         if (isEmpty()) {
248             throw new NoSuchElementException JavaDoc();
249         } else {
250             return m_elements[1];
251         }
252     }
253
254     /**
255      * Returns the element on top of heap and remove it.
256      *
257      * @return the element at top of heap
258      * @throws NoSuchElementException if <code>isEmpty() == true</code>
259      */

260     public Object JavaDoc pop() throws NoSuchElementException JavaDoc {
261         final Object JavaDoc result = peek();
262         m_elements[1] = m_elements[m_size--];
263
264         // set the unused element to 'null' so that the garbage collector
265
// can free the object if not used anywhere else.(remove reference)
266
m_elements[m_size + 1] = null;
267
268         if (m_size != 0) {
269             // percolate top element to it's place in tree
270
if (m_isMinHeap) {
271                 percolateDownMinHeap(1);
272             } else {
273                 percolateDownMaxHeap(1);
274             }
275         }
276
277         return result;
278     }
279
280     /**
281      * Percolates element down heap from the position given by the index.
282      * <p>
283      * Assumes it is a minimum heap.
284      *
285      * @param index the index for the element
286      */

287     protected void percolateDownMinHeap(final int index) {
288         final Object JavaDoc element = m_elements[index];
289         int hole = index;
290
291         while ((hole * 2) <= m_size) {
292             int child = hole * 2;
293
294             // if we have a right child and that child can not be percolated
295
// up then move onto other child
296
if (child != m_size && compare(m_elements[child + 1], m_elements[child]) < 0) {
297                 child++;
298             }
299
300             // if we found resting place of bubble then terminate search
301
if (compare(m_elements[child], element) >= 0) {
302                 break;
303             }
304
305             m_elements[hole] = m_elements[child];
306             hole = child;
307         }
308
309         m_elements[hole] = element;
310     }
311
312     /**
313      * Percolates element down heap from the position given by the index.
314      * <p>
315      * Assumes it is a maximum heap.
316      *
317      * @param index the index of the element
318      */

319     protected void percolateDownMaxHeap(final int index) {
320         final Object JavaDoc element = m_elements[index];
321         int hole = index;
322
323         while ((hole * 2) <= m_size) {
324             int child = hole * 2;
325
326             // if we have a right child and that child can not be percolated
327
// up then move onto other child
328
if (child != m_size && compare(m_elements[child + 1], m_elements[child]) > 0) {
329                 child++;
330             }
331
332             // if we found resting place of bubble then terminate search
333
if (compare(m_elements[child], element) <= 0) {
334                 break;
335             }
336
337             m_elements[hole] = m_elements[child];
338             hole = child;
339         }
340
341         m_elements[hole] = element;
342     }
343
344     /**
345      * Percolates element up heap from the position given by the index.
346      * <p>
347      * Assumes it is a minimum heap.
348      *
349      * @param index the index of the element to be percolated up
350      */

351     protected void percolateUpMinHeap(final int index) {
352         int hole = index;
353         Object JavaDoc element = m_elements[hole];
354         while (hole > 1 && compare(element, m_elements[hole / 2]) < 0) {
355             // save element that is being pushed down
356
// as the element "bubble" is percolated up
357
final int next = hole / 2;
358             m_elements[hole] = m_elements[next];
359             hole = next;
360         }
361         m_elements[hole] = element;
362     }
363
364     /**
365      * Percolates a new element up heap from the bottom.
366      * <p>
367      * Assumes it is a minimum heap.
368      *
369      * @param element the element
370      */

371     protected void percolateUpMinHeap(final Object JavaDoc element) {
372         m_elements[++m_size] = element;
373         percolateUpMinHeap(m_size);
374     }
375
376     /**
377      * Percolates element up heap from from the position given by the index.
378      * <p>
379      * Assume it is a maximum heap.
380      *
381      * @param index the index of the element to be percolated up
382      */

383     protected void percolateUpMaxHeap(final int index) {
384         int hole = index;
385         Object JavaDoc element = m_elements[hole];
386         
387         while (hole > 1 && compare(element, m_elements[hole / 2]) > 0) {
388             // save element that is being pushed down
389
// as the element "bubble" is percolated up
390
final int next = hole / 2;
391             m_elements[hole] = m_elements[next];
392             hole = next;
393         }
394
395         m_elements[hole] = element;
396     }
397     
398     /**
399      * Percolates a new element up heap from the bottom.
400      * <p>
401      * Assume it is a maximum heap.
402      *
403      * @param element the element
404      */

405     protected void percolateUpMaxHeap(final Object JavaDoc element) {
406         m_elements[++m_size] = element;
407         percolateUpMaxHeap(m_size);
408     }
409     
410     /**
411      * Compares two objects using the comparator if specified, or the
412      * natural order otherwise.
413      *
414      * @param a the first object
415      * @param b the second object
416      * @return -ve if a less than b, 0 if they are equal, +ve if a greater than b
417      */

418     private int compare(Object JavaDoc a, Object JavaDoc b) {
419         if (m_comparator != null) {
420             return m_comparator.compare(a, b);
421         } else {
422             return ((Comparable JavaDoc) a).compareTo(b);
423         }
424     }
425
426     /**
427      * Increases the size of the heap to support additional elements
428      */

429     protected void grow() {
430         final Object JavaDoc[] elements = new Object JavaDoc[m_elements.length * 2];
431         System.arraycopy(m_elements, 0, elements, 0, m_elements.length);
432         m_elements = elements;
433     }
434
435     /**
436      * Returns a string representation of this heap. The returned string
437      * is similar to those produced by standard JDK collections.
438      *
439      * @return a string representation of this heap
440      */

441     public String JavaDoc toString() {
442         final StringBuffer JavaDoc sb = new StringBuffer JavaDoc();
443
444         sb.append("[ ");
445
446         for (int i = 1; i < m_size + 1; i++) {
447             if (i != 1) {
448                 sb.append(", ");
449             }
450             sb.append(m_elements[i]);
451         }
452
453         sb.append(" ]");
454
455         return sb.toString();
456     }
457
458
459     /**
460      * Returns an iterator over this heap's elements.
461      *
462      * @return an iterator over this heap's elements
463      */

464     public Iterator JavaDoc iterator() {
465         return new Iterator JavaDoc() {
466
467             private int index = 1;
468             private int lastReturnedIndex = -1;
469
470             public boolean hasNext() {
471                 return index <= m_size;
472             }
473
474             public Object JavaDoc next() {
475                 if (!hasNext()) throw new NoSuchElementException JavaDoc();
476                 lastReturnedIndex = index;
477                 index++;
478                 return m_elements[lastReturnedIndex];
479             }
480
481             public void remove() {
482                 if (lastReturnedIndex == -1) {
483                     throw new IllegalStateException JavaDoc();
484                 }
485                 m_elements[ lastReturnedIndex ] = m_elements[ m_size ];
486                 m_elements[ m_size ] = null;
487                 m_size--;
488                 if( m_size != 0 && lastReturnedIndex <= m_size) {
489                     int compareToParent = 0;
490                     if (lastReturnedIndex > 1) {
491                         compareToParent = compare(m_elements[lastReturnedIndex],
492                             m_elements[lastReturnedIndex / 2]);
493                     }
494                     if (m_isMinHeap) {
495                         if (lastReturnedIndex > 1 && compareToParent < 0) {
496                             percolateUpMinHeap(lastReturnedIndex);
497                         } else {
498                             percolateDownMinHeap(lastReturnedIndex);
499                         }
500                     } else { // max heap
501
if (lastReturnedIndex > 1 && compareToParent > 0) {
502                             percolateUpMaxHeap(lastReturnedIndex);
503                         } else {
504                             percolateDownMaxHeap(lastReturnedIndex);
505                         }
506                     }
507                 }
508                 index--;
509                 lastReturnedIndex = -1;
510             }
511
512         };
513     }
514
515
516     /**
517      * Adds an object to this heap. Same as {@link #insert(Object)}.
518      *
519      * @param object the object to add
520      * @return true, always
521      */

522     public boolean add(Object JavaDoc object) {
523         insert(object);
524         return true;
525     }
526
527     /**
528      * Returns the priority element. Same as {@link #peek()}.
529      *
530      * @return the priority element
531      * @throws BufferUnderflowException if this heap is empty
532      */

533     public Object JavaDoc get() {
534         try {
535             return peek();
536         } catch (NoSuchElementException JavaDoc e) {
537             throw new BufferUnderflowException();
538         }
539     }
540
541     /**
542      * Removes the priority element. Same as {@link #pop()}.
543      *
544      * @return the removed priority element
545      * @throws BufferUnderflowException if this heap is empty
546      */

547     public Object JavaDoc remove() {
548         try {
549             return pop();
550         } catch (NoSuchElementException JavaDoc e) {
551             throw new BufferUnderflowException();
552         }
553     }
554
555     /**
556      * Returns the number of elements in this heap.
557      *
558      * @return the number of elements in this heap
559      */

560     public int size() {
561         return m_size;
562     }
563
564 }
565
Popular Tags