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 &lt;= <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 &lt;= <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>&lt;= 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>&lt;= 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    }