KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > org > apache > avalon > cornerstone > blocks > scheduler > BinaryHeap


1 /*
2  * Copyright 1999-2004 The Apache Software Foundation
3  * Licensed under the Apache License, Version 2.0 (the "License");
4  * you may not use this file except in compliance with the License.
5  * You may obtain a copy of the License at
6  *
7  * http://www.apache.org/licenses/LICENSE-2.0
8  *
9  * Unless required by applicable law or agreed to in writing, software
10  * distributed under the License is distributed on an "AS IS" BASIS,
11  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or
12  * implied.
13  *
14  * See the License for the specific language governing permissions and
15  * limitations under the License.
16  */
17
18 package org.apache.avalon.cornerstone.blocks.scheduler;
19
20 import java.util.Comparator JavaDoc;
21 import java.util.NoSuchElementException JavaDoc;
22
23 /**
24  * BinaryHeap implementation of priority queue.
25  * The heap is either a minimum or maximum heap as determined
26  * by parameters passed to constructor.
27  *
28  * @author <a HREF="mailto:dev@avalon.apache.org">Avalon Development Team</a>
29  * @version CVS $Revision: 1.1 $ $Date: 2004/03/16 12:49:52 $
30  * @since 4.0
31  */
32 public final class BinaryHeap
33     implements PriorityQueue
34 {
35     private static final class MinComparator
36         implements Comparator JavaDoc
37     {
38         public final int compare( final Object JavaDoc lhs, final Object JavaDoc rhs )
39         {
40             return ( (Comparable JavaDoc)lhs ).compareTo( rhs );
41         }
42     }
43
44     private static final class MaxComparator
45         implements Comparator JavaDoc
46     {
47         public final int compare( final Object JavaDoc lhs, final Object JavaDoc rhs )
48         {
49             return ( (Comparable JavaDoc)rhs ).compareTo( lhs );
50         }
51     }
52
53     /**
54      * Comparator used to instantiate a min heap - assumes contents implement
55      * the Comparable interface.
56      */
57     public static final Comparator JavaDoc MIN_COMPARATOR = new MinComparator();
58
59     /**
60      * Comparator used to instantiate a max heap - assumes contents implement
61      * the Comparable interface.
62      */
63     public static final Comparator JavaDoc MAX_COMPARATOR = new MaxComparator();
64
65     private static final int DEFAULT_CAPACITY = 13;
66     private static final Comparator JavaDoc DEFAULT_COMPARATOR = MIN_COMPARATOR;
67     private int m_size;
68     private Object JavaDoc[] m_elements;
69     private Comparator JavaDoc m_comparator;
70
71     /**
72      * Instantiates a new min binary heap with the default initial capacity.
73      */
74     public BinaryHeap()
75     {
76         this( DEFAULT_CAPACITY, DEFAULT_COMPARATOR );
77     }
78
79     /**
80      * Instantiates a new min binary heap with the given initial capacity.
81      *
82      * @param capacity the size of the heap
83      */
84     public BinaryHeap( final int capacity )
85     {
86         this( capacity, DEFAULT_COMPARATOR );
87     }
88
89     /**
90      * Instantiates a new binary heap with the default initial capacity and
91      * ordered using the given Comparator.
92      *
93      * @param comparator to order the contents of the heap
94      */
95     public BinaryHeap( final Comparator JavaDoc comparator )
96     {
97         this( DEFAULT_CAPACITY, comparator );
98     }
99
100     /**
101      * Instantiates a new binary heap with the given initial capacity and
102      * ordered using the given Comparator.
103      *
104      * @param capacity the size of the heap
105      * @param comparator to order the contents of the heap
106      */
107     public BinaryHeap( final int capacity, final Comparator JavaDoc comparator )
108     {
109         //+1 as 0 is noop
110 m_elements = new Object JavaDoc[ capacity + 1 ];
111         m_comparator = comparator;
112     }
113
114     /**
115      * Create a binary heap of Comparables. Takes a parameter
116      * to specify whether it is a minimum or maximum heap.
117      *
118      * @param isMinHeap true to make it a minimum heap, false to make it a max heap
119      */
120     public BinaryHeap( final boolean isMinHeap )
121     {
122         this( DEFAULT_CAPACITY, isMinHeap );
123     }
124
125     /**
126      * Create a binary heap of Comparables. Takes a parameter
127      * to specify whether it is a minimum or maximum heap and another
128      * parameter to specify the size of the heap.
129      *
130      * @param capacity the size of the heap
131      * @param isMinHeap true to make it a minimum heap, false to make it a max heap
132      */
133     public BinaryHeap( final int capacity, final boolean isMinHeap )
134     {
135         this( capacity, isMinHeap ? MIN_COMPARATOR : MAX_COMPARATOR );
136     }
137
138     /**
139      * Clear all elements from queue.
140      */
141     public void clear()
142     {
143         m_size = 0;
144     }
145
146     /**
147      * Test if queue is empty.
148      *
149      * @return true if queue is empty else false.
150      */
151     public boolean isEmpty()
152     {
153         return ( 0 == m_size );
154     }
155
156     /**
157      * Test if queue is full.
158      *
159      * @return true if queue is full else false.
160      */
161     public boolean isFull()
162     {
163         //+1 as element 0 is noop
164 return ( m_elements.length == m_size + 1 );
165     }
166
167     /**
168      * Returns the number of elements currently on the heap.
169      *
170      * @return the size of the heap.
171      */
172     public int size()
173     {
174         return m_size;
175     }
176
177     /**
178      * Insert an element into queue.
179      *
180      * @param element the element to be inserted
181      */
182     public void insert( final Object JavaDoc element )
183     {
184         if( isFull() )
185         {
186             grow();
187         }
188
189         percolateUpHeap( element );
190     }
191
192     /**
193      * Return element on top of heap but don't remove it.
194      *
195      * @return the element at top of heap
196      * @throws NoSuchElementException if isEmpty() == true
197      */
198     public Object JavaDoc peek() throws NoSuchElementException JavaDoc
199     {
200         if( isEmpty() )
201         {
202             throw new NoSuchElementException JavaDoc();
203         }
204         else
205         {
206             return m_elements[ 1 ];
207         }
208     }
209
210     /**
211      * Return element on top of heap and remove it.
212      *
213      * @return the element at top of heap
214      * @throws NoSuchElementException if isEmpty() == true
215      */
216     public Object JavaDoc pop() throws NoSuchElementException JavaDoc
217     {
218         final Object JavaDoc result = peek();
219         m_elements[ 1 ] = m_elements[ m_size-- ];
220
221         //set the unused element to 'null' so that the garbage collector
222 //can free the object if not used anywhere else.(remove reference)
223 m_elements[ m_size + 1 ] = null;
224
225         if( m_size != 0 )
226         {
227             percolateDownHeap( 1 );
228         }
229
230         return result;
231     }
232
233     /**
234      * Percolate element down heap from top.
235      *
236      * @param index the index of element
237      */
238     private void percolateDownHeap( final int index )
239     {
240         final Object JavaDoc element = m_elements[ index ];
241
242         int hole = index;
243         int child = hole << 1;
244
245         while( child <= m_size )
246         {
247             //if we have a right child and that child can not be percolated
248 //up then move onto other child
249 if( child != m_size &&
250                 m_comparator.compare( m_elements[ child + 1 ], m_elements[ child ] ) < 0 )
251             {
252                 child++;
253             }
254
255             //if we found resting place of bubble then terminate search
256 if( m_comparator.compare( m_elements[ child ], element ) >= 0 )
257             {
258                 break;
259             }
260
261             m_elements[ hole ] = m_elements[ child ];
262             hole = child;
263             child = hole << 1;
264         }
265
266         m_elements[ hole ] = element;
267     }
268
269     /**
270      * Percolate element up heap from bottom.
271      *
272      * @param element the element
273      */
274     private void percolateUpHeap( final Object JavaDoc element )
275     {
276         int hole = ++m_size;
277         int next = hole >> 1;
278
279         m_elements[ hole ] = element;
280
281         while( hole > 1 &&
282             m_comparator.compare( element, m_elements[ next ] ) < 0 )
283         {
284             m_elements[ hole ] = m_elements[ next ];
285             hole = next;
286             next = hole >> 1;
287         }
288
289         m_elements[ hole ] = element;
290     }
291
292     /**
293      * Grows the heap by a factor of 2.
294      */
295     private void grow()
296     {
297         final Object JavaDoc[] elements =
298             new Object JavaDoc[ m_elements.length * 2 ];
299         System.arraycopy( m_elements, 0, elements, 0, m_elements.length );
300         m_elements = elements;
301     }
302
303     /**
304      * Create a string representing heap
305      * and all elements in heap.
306      *
307      * @return the string representing heap
308      */
309     public String JavaDoc toString()
310     {
311         final StringBuffer JavaDoc sb = new StringBuffer JavaDoc();
312
313         sb.append( "[ " );
314
315         for( int i = 1; i < m_size + 1; i++ )
316         {
317             if( i != 1 )
318             {
319                 sb.append( ", " );
320             }
321             sb.append( m_elements[ i ] );
322         }
323
324         sb.append( " ]" );
325
326         return sb.toString();
327     }
328 }
329
330
Popular Tags