Java > Open Source Codes > org > apache > avalon > excalibur > collections > BinaryHeap


1 /*
2
3  ============================================================================
4                    The Apache Software License, Version 1.1
5  ============================================================================
6  
7  Copyright (C) 1999-2003 The Apache Software Foundation. All rights reserved.
8  
9  Redistribution and use in source and binary forms, with or without modifica-
10  tion, are permitted provided that the following conditions are met:
11  
12  1. Redistributions of source code must retain the above copyright notice,
13     this list of conditions and the following disclaimer.
14  
15  2. Redistributions in binary form must reproduce the above copyright notice,
16     this list of conditions and the following disclaimer in the documentation
17     and/or other materials provided with the distribution.
18  
19  3. The end-user documentation included with the redistribution, if any, must
20     include the following acknowledgment: "This product includes software
21     developed by the Apache Software Foundation (http://www.apache.org/)."
22     Alternately, this acknowledgment may appear in the software itself, if
23     and wherever such third-party acknowledgments normally appear.
24  
25  4. The names "Jakarta", "Avalon", "Excalibur" and "Apache Software Foundation"
26     must not be used to endorse or promote products derived from this software
27     without prior written permission. For written permission, please contact
28     apache@apache.org.
29  
30  5. Products derived from this software may not be called "Apache", nor may
31     "Apache" appear in their name, without prior written permission of the
32     Apache Software Foundation.
33  
34  THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED WARRANTIES,
35  INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND
36  FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
37  APACHE SOFTWARE FOUNDATION OR ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
38  INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLU-
39  DING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS
40  OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON
41  ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
42  (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
43  THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
44  
45  This software consists of voluntary contributions made by many individuals
46  on behalf of the Apache Software Foundation. For more information on the
47  Apache Software Foundation, please see <http://www.apache.org/>.
48  
49 */
50 package org.apache.avalon.excalibur.collections;
51
52 import java.util.Comparator ;
53 import java.util.NoSuchElementException ;
54
55 /**
56  * BinaryHeap implementation of priority queue.
57  * The heap is either a minimum or maximum heap as determined
58  * by parameters passed to constructor.
59  *
60  * @deprecated use org.apache.commons.collections.BinaryHeap instead;
61  *
62  * @author <a HREF="mailto:peter@apache.org">Peter Donald</a>
63  * @author <a HREF="mailto:ram.chidambaram@telus.com">Ram Chidambaram</a>
64  * @author <a HREF="mailto:stansburyc@earthlink.net">Chad Stansbury</a>
65  * @version CVS $Revision: 1.4 $ $Date: 2003/03/22 12:46:22 $
66  * @since 4.0
67  */
68 public final class BinaryHeap
69     implements PriorityQueue
70 {
71     private static final class MinComparator
72         implements Comparator
73     {
74         public final int compare( final Object lhs, final Object rhs )
75         {
76             return ( (Comparable )lhs ).compareTo( rhs );
77         }
78     }
79
80     private static final class MaxComparator
81         implements Comparator
82     {
83         public final int compare( final Object lhs, final Object rhs )
84         {
85             return ( (Comparable )rhs ).compareTo( lhs );
86         }
87     }
88
89     /**
90      * Comparator used to instantiate a min heap - assumes contents implement
91      * the Comparable interface.
92      */
93     public static final Comparator MIN_COMPARATOR = new MinComparator();
94
95     /**
96      * Comparator used to instantiate a max heap - assumes contents implement
97      * the Comparable interface.
98      */
99     public static final Comparator MAX_COMPARATOR = new MaxComparator();
100
101     private static final int DEFAULT_CAPACITY = 13;
102     private static final Comparator DEFAULT_COMPARATOR = MIN_COMPARATOR;
103     private int m_size;
104     private Object [] m_elements;
105     private Comparator m_comparator;
106
107     /**
108      * Instantiates a new min binary heap with the default initial capacity.
109      */
110     public BinaryHeap()
111     {
112         this( DEFAULT_CAPACITY, DEFAULT_COMPARATOR );
113     }
114
115     /**
116      * Instantiates a new min binary heap with the given initial capacity.
117      *
118      * @param capacity the size of the heap
119      */
120     public BinaryHeap( final int capacity )
121     {
122         this( capacity, DEFAULT_COMPARATOR );
123     }
124
125     /**
126      * Instantiates a new binary heap with the default initial capacity and
127      * ordered using the given Comparator.
128      *
129      * @param comparator to order the contents of the heap
130      */
131     public BinaryHeap( final Comparator comparator )
132     {
133         this( DEFAULT_CAPACITY, comparator );
134     }
135
136     /**
137      * Instantiates a new binary heap with the given initial capacity and
138      * ordered using the given Comparator.
139      *
140      * @param capacity the size of the heap
141      * @param comparator to order the contents of the heap
142      */
143     public BinaryHeap( final int capacity, final Comparator comparator )
144     {
145         //+1 as 0 is noop
146 m_elements = new Object [ capacity + 1 ];
147         m_comparator = comparator;
148     }
149
150     /**
151      * Create a binary heap of Comparables. Takes a parameter
152      * to specify whether it is a minimum or maximum heap.
153      *
154      * @param isMinHeap true to make it a minimum heap, false to make it a max heap
155      */
156     public BinaryHeap( final boolean isMinHeap )
157     {
158         this( DEFAULT_CAPACITY, isMinHeap );
159     }
160
161     /**
162      * Create a binary heap of Comparables. Takes a parameter
163      * to specify whether it is a minimum or maximum heap and another
164      * parameter to specify the size of the heap.
165      *
166      * @param capacity the size of the heap
167      * @param isMinHeap true to make it a minimum heap, false to make it a max heap
168      */
169     public BinaryHeap( final int capacity, final boolean isMinHeap )
170     {
171         this( capacity, isMinHeap ? MIN_COMPARATOR : MAX_COMPARATOR );
172     }
173
174     /**
175      * Clear all elements from queue.
176      */
177     public void clear()
178     {
179         m_size = 0;
180     }
181
182     /**
183      * Test if queue is empty.
184      *
185      * @return true if queue is empty else false.
186      */
187     public boolean isEmpty()
188     {
189         return ( 0 == m_size );
190     }
191
192     /**
193      * Test if queue is full.
194      *
195      * @return true if queue is full else false.
196      */
197     public boolean isFull()
198     {
199         //+1 as element 0 is noop
200 return ( m_elements.length == m_size + 1 );
201     }
202
203     /**
204      * Returns the number of elements currently on the heap.
205      *
206      * @return the size of the heap.
207      */
208     public int size()
209     {
210         return m_size;
211     }
212
213     /**
214      * Insert an element into queue.
215      *
216      * @param element the element to be inserted
217      */
218     public void insert( final Object element )
219     {
220         if( isFull() )
221         {
222             grow();
223         }
224
225         percolateUpHeap( element );
226     }
227
228     /**
229      * Return element on top of heap but don't remove it.
230      *
231      * @return the element at top of heap
232      * @throws NoSuchElementException if isEmpty() == true
233      */
234     public Object peek() throws NoSuchElementException
235     {
236         if( isEmpty() )
237         {
238             throw new NoSuchElementException ();
239         }
240         else
241         {
242             return m_elements[ 1 ];
243         }
244     }
245
246     /**
247      * Return element on top of heap and remove it.
248      *
249      * @return the element at top of heap
250      * @throws NoSuchElementException if isEmpty() == true
251      */
252     public Object pop() throws NoSuchElementException
253     {
254         final Object result = peek();
255         m_elements[ 1 ] = m_elements[ m_size-- ];
256
257         //set the unused element to 'null' so that the garbage collector
258 //can free the object if not used anywhere else.(remove reference)
259 m_elements[ m_size + 1 ] = null;
260
261         if( m_size != 0 )
262         {
263             percolateDownHeap( 1 );
264         }
265
266         return result;
267     }
268
269     /**
270      * Percolate element down heap from top.
271      *
272      * @param element the element
273      */
274     private void percolateDownHeap( final int index )
275     {
276         final Object element = m_elements[ index ];
277
278         int hole = index;
279         int child = hole << 1;
280
281         while( child <= m_size )
282         {
283             //if we have a right child and that child can not be percolated
284 //up then move onto other child
285 if( child != m_size &&
286                 m_comparator.compare( m_elements[ child + 1 ], m_elements[ child ] ) < 0 )
287             {
288                 child++;
289             }
290
291             //if we found resting place of bubble then terminate search
292 if( m_comparator.compare( m_elements[ child ], element ) >= 0 )
293             {
294                 break;
295             }
296
297             m_elements[ hole ] = m_elements[ child ];
298             hole = child;
299             child = hole << 1;
300         }
301
302         m_elements[ hole ] = element;
303     }
304
305     /**
306      * Percolate element up heap from bottom.
307      *
308      * @param element the element
309      */
310     private void percolateUpHeap( final Object element )
311     {
312         int hole = ++m_size;
313         int next = hole >> 1;
314
315         m_elements[ hole ] = element;
316
317         while( hole > 1 &&
318             m_comparator.compare( element, m_elements[ next ] ) < 0 )
319         {
320             m_elements[ hole ] = m_elements[ next ];
321             hole = next;
322             next = hole >> 1;
323         }
324
325         m_elements[ hole ] = element;
326     }
327
328     /**
329      * Grows the heap by a factor of 2.
330      */
331     private void grow()
332     {
333         final Object [] elements =
334             new Object [ m_elements.length * 2 ];
335         System.arraycopy( m_elements, 0, elements, 0, m_elements.length );
336         m_elements = elements;
337     }
338
339     /**
340      * Create a string representing heap
341      * and all elements in heap.
342      *
343      * @return the string representing heap
344      */
345     public String toString()
346     {
347         final StringBuffer sb = new StringBuffer ();
348
349         sb.append( "[ " );
350
351         for( int i = 1; i < m_size + 1; i++ )
352         {
353             if( i != 1 )
354             {
355                 sb.append( ", " );
356             }
357             sb.append( m_elements[ i ] );
358         }
359
360         sb.append( " ]" );
361
362         return sb.toString();
363     }
364 }
365
366

A to Z: JavaDoc & Examples

---

Daily Java News & Articles

---

Open Source Projects

---

Open Source Codes

---

Free Computer Books

---

Remove Frame

---

Popular Tags