001/* Copyright (C) 2013 TU Dortmund
002 * This file is part of AutomataLib, http://www.automatalib.net/.
003 * 
004 * AutomataLib is free software; you can redistribute it and/or
005 * modify it under the terms of the GNU Lesser General Public
006 * License version 3.0 as published by the Free Software Foundation.
007 * 
008 * AutomataLib is distributed in the hope that it will be useful,
009 * but WITHOUT ANY WARRANTY; without even the implied warranty of
010 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
011 * Lesser General Public License for more details.
012 * 
013 * You should have received a copy of the GNU Lesser General Public
014 * License along with AutomataLib; if not, see
015 * http://www.gnu.de/documents/lgpl.en.html.
016 */
017package net.automatalib.commons.smartcollections;
018
019import java.util.Collection;
020import java.util.Comparator;
021import java.util.Iterator;
022import java.util.PriorityQueue;
023
024import net.automatalib.commons.util.array.ResizingObjectArray;
025import net.automatalib.commons.util.comparison.CmpUtil;
026
027/**
028 * A {@link PriorityQueue} implementation using a binary heap.
029 *  
030 * @author Malte Isberner <malte.isberner@gmail.com>
031 *
032 * @param <E> element class.
033 */
034public class BinaryHeap<E>
035                extends AbstractSmartCollection<E> implements SmartDynamicPriorityQueue<E>,
036                        CapacityManagement {
037        
038        private static final int DEFAULT_INITIAL_CAPACITY = 10;
039        
040        /**
041         * Class for entries in a priority queue. Entry objects are returned by the
042         * {@link SmartDynamicPriorityQueue#insert(Comparable)} method and are passed to the
043         * {@link SmartDynamicPriorityQueue#keyChanged(Reference)} method. The usage of entry objects
044         * eliminates the necessity of an extra element to index mapping. 
045         * 
046         * @author Malte Isberner
047         *
048         * @param <E> element class.
049         */
050        private static final class Reference<E>
051                        implements ElementReference {
052                protected int index;
053                protected E element;
054        
055                /**
056                 * Constructor.
057                 * 
058                 * @param index the index of the entry inside the queue.
059                 * @param element the element stored in this entry.
060                 */
061                protected Reference(int index, E element) {
062                        this.element = element;
063                        this.index = index;
064                }
065        }
066        
067        private class ReferenceIterator implements Iterator<ElementReference> {
068                
069                private int current;
070
071                /*
072                 * (non-Javadoc)
073                 * @see java.util.Iterator#hasNext()
074                 */
075                @Override
076                public boolean hasNext() {
077                        return (current < size);
078                }
079
080                /*
081                 * (non-Javadoc)
082                 * @see java.util.Iterator#next()
083                 */
084                @Override
085                public ElementReference next() {
086                        return (ElementReference)entries.array[current++];
087                }
088
089                /*
090                 * (non-Javadoc)
091                 * @see java.util.Iterator#remove()
092                 */
093                @Override
094                public void remove() {
095                        BinaryHeap.this.remove(--current);
096                }
097        }
098        
099        @SuppressWarnings("unchecked")
100        private static <E> Reference<E> asHeapRef(ElementReference ref) {
101                if(ref.getClass() != Reference.class)
102                        throw new InvalidReferenceException("Reference is of wrong class '"
103                                        + ref.getClass().getName()
104                                        + "', should be " + Reference.class.getName() + ".");
105                return (Reference<E>)ref;
106        }
107        
108        
109        /*
110         * Retrieves, for a given child index, its parent index.
111         */
112        private static int parent(int child) {
113                return child/2;
114        }
115        
116        /*
117         * Retrieves the index of the left child of a given parent index.
118         */
119        private static int leftChild(int parent) {
120                return 2*parent;
121        }
122        
123        /*
124         * Retrieves the index of the right child of a given parent index.
125         */
126        private static int rightChild(int parent) {
127                return 2*parent + 1;
128        }
129        
130        /*
131         * Checks if the specified index has a parent.
132         */
133        private static boolean hasParent(int idx) {
134                return idx > 0;
135        }
136        
137        
138        public static <E extends Comparable<E>> BinaryHeap<E> create() {
139                return new BinaryHeap<>(DEFAULT_INITIAL_CAPACITY, CmpUtil.<E>naturalOrderingComparator());
140        }
141        
142        public static <E extends Comparable<E>> BinaryHeap<E> create(int initialCapacity) {
143                return new BinaryHeap<>(initialCapacity, CmpUtil.<E>naturalOrderingComparator());
144        }
145        
146        public static <E extends Comparable<E>> BinaryHeap<E> create(Collection<? extends E> initValues) {
147                return new BinaryHeap<>(0, initValues, CmpUtil.<E>naturalOrderingComparator());
148        }
149        
150        public static <E extends Comparable<E>> BinaryHeap<E> create(int initialCapacity, Collection<? extends E> initValues) {
151                return new BinaryHeap<>(initialCapacity, initValues, CmpUtil.<E>naturalOrderingComparator());
152        }
153        
154        public static <E> BinaryHeap<E> createCmp(Comparator<? super E> comparator) {
155                return new BinaryHeap<>(DEFAULT_INITIAL_CAPACITY, comparator);
156        }
157        
158        public static <E> BinaryHeap<E> createCmp(Comparator<? super E> comparator, int initialCapacity) {
159                return new BinaryHeap<>(initialCapacity, comparator);
160        }
161        
162        public static <E> BinaryHeap<E> createCmp(Comparator<? super E> comparator, Collection<? extends E> initValues) {
163                return new BinaryHeap<>(0, initValues, comparator);
164        }
165        
166        public static <E> BinaryHeap<E> createCmp(Comparator<? super E> comparator, int initialCapacity, Collection<? extends E> initValues) {
167                return new BinaryHeap<>(initialCapacity, initValues, comparator);
168        }
169        
170        
171        
172        
173        // Entry storage.
174        private ResizingObjectArray entries;
175        // Number of entries in the queue.
176        private int size = 0;
177        
178        private final Comparator<? super E> comparator;
179        
180        /*
181         * Checks whether the entry at the specified index has at least one child.
182         */
183        private boolean hasChildren(int idx) {
184                return idx*2 < size;
185        }
186        
187        /*
188         * Checks whether the entry at the specified index has two children.
189         */
190        private boolean hasRightChild(int idx) {
191                return idx*2+1 < size;
192        }
193
194        /*
195         * Removes the element at the specified index from the heap. This is
196         * done by simulating a key decrease to -infinity and then performing
197         * extractMin.
198         */
199        private void remove(int index) {
200                forceToTop(index);
201                extractMin();
202        }
203
204        /*
205         * Compares the referenced elements.
206         */
207        private int compare(Reference<E> e1, Reference<E> e2) {
208                return comparator.compare(e1.element, e2.element);
209        }
210        
211        /*
212         * Move an element upwards inside the heap, until it has a parent with a key
213         * less or equal to its own.
214         */
215        @SuppressWarnings("unchecked")
216        private void upHeap(int idx) {
217                Reference<E> e = (Reference<E>)entries.array[idx];
218                
219                while(hasParent(idx)) {
220                        int pidx = parent(idx);
221                        Reference<E> p = (Reference<E>)entries.array[pidx];
222                        if(compare(e, p) < 0) {
223                                entries.array[pidx] = e;
224                                entries.array[idx] = p;
225                                p.index = idx;
226                                idx = parent(idx);
227                        }
228                        else
229                                break;          
230                }
231                e.index = idx;
232        }
233        
234        /*
235         * Move an element downwards inside the heap, until all of its children have
236         * a key greater or equal to its own.
237         */
238        @SuppressWarnings("unchecked")
239        private void downHeap(int idx) {
240                Reference<E> e = (Reference<E>)entries.array[idx];
241                
242                while(hasChildren(idx)) {
243                        int cidx = leftChild(idx);
244                        Reference<E> c = (Reference<E>)entries.array[cidx];
245                        
246                        if(hasRightChild(idx)) {
247                                int rcidx = rightChild(idx);
248                                Reference<E> rc = (Reference<E>)entries.array[rcidx];
249                                if(compare(rc, c) < 0) {
250                                        cidx = rcidx;
251                                        c = rc;
252                                }
253                        }
254                        
255                        if(compare(e, c) <= 0)
256                                break;
257                        
258                        entries.array[cidx] = e;
259                        entries.array[idx] = c;
260                        c.index = idx;
261                        idx = cidx;
262                }
263                
264                e.index = idx;
265        }
266        
267        @SuppressWarnings("unchecked")
268        private void forceToTop(int idx) {
269                Reference<E> e = (Reference<E>)entries.array[idx];
270                
271                while(hasParent(idx)) {
272                        int pidx = parent(idx);
273                        Reference<E> p = (Reference<E>)entries.array[pidx];
274                        entries.array[pidx] = e;
275                        entries.array[idx] = p;
276                        p.index = idx;
277                        idx = parent(idx);      
278                }
279                e.index = idx;
280        }
281        
282        
283        private void buildHeap(int numElements) {
284                size = numElements;
285                for(int i = numElements/2; i >= 0; i--)
286                        downHeap(i);
287        }
288        
289
290        
291        protected BinaryHeap(int initialCapacity, Comparator<? super E> comparator) {
292                this.entries = new ResizingObjectArray(initialCapacity);
293                this.comparator = comparator;
294        }
295        
296        protected BinaryHeap(int initCapacity, Collection<? extends E> initValues, Comparator<? super E> comparator) {
297                this(initCapacity < initValues.size() ? initValues.size() : initCapacity, comparator);
298                int i = 0;
299                for(E e : initValues)
300                        entries.array[i++] = new Reference<>(0, e);
301                buildHeap(initValues.size());
302        }
303        
304        /*
305         * (non-Javadoc)
306         * @see edu.udo.ls5.util.PriorityQueue#extractMin()
307         */
308        @Override
309        @SuppressWarnings("unchecked")
310        public E extractMin() {
311                E min = ((Reference<E>)entries.array[0]).element;
312                entries.array[0] = entries.array[--size];
313                entries.array[size] = null;
314                
315                if(size > 0)
316                        downHeap(0);
317                
318                return min;
319        }
320
321        /*
322         * (non-Javadoc)
323         * @see edu.udo.ls5.util.PriorityQueue#keyChanged(edu.udo.ls5.util.PriorityQueue.Entry)
324         */
325        public void keyChanged(int index) {
326                upHeap(index);
327                downHeap(index);
328        }
329
330        /*
331         * (non-Javadoc)
332         * @see edu.udo.ls5.util.PriorityQueue#peekMin()
333         */
334        @Override
335        @SuppressWarnings("unchecked")
336        public E peekMin() {
337                return ((Reference<E>)entries.array[0]).element;
338        }
339        
340        @Override
341        public Reference<E> referencedAdd(E elem) {
342                ensureCapacity(size+1);
343                
344                Reference<E> entry = new Reference<>(size, elem);
345                entries.array[size] = entry;
346                upHeap(size++);
347                
348                return entry;
349        }
350        
351        /*
352         * (non-Javadoc)
353         * @see java.util.AbstractCollection#size()
354         */
355        @Override
356        public int size() {
357                return size;
358        }
359
360        /*
361         * (non-Javadoc)
362         * @see de.ls5.smartcollections.SmartPriorityQueue#keyChanged(de.ls5.smartcollections.ElementReference)
363         */
364        @Override
365        public void keyChanged(ElementReference ref) {
366                keyChanged(asHeapRef(ref).index);
367        }
368
369        /*
370         * (non-Javadoc)
371         * @see de.ls5.smartcollections.SmartCollection#get(de.ls5.smartcollections.ElementReference)
372         */
373        @Override
374        public E get(ElementReference ref) {
375                return BinaryHeap.<E>asHeapRef(ref).element;
376        }
377
378        /*
379         * (non-Javadoc)
380         * @see de.ls5.smartcollections.SmartCollection#referenceIterator()
381         */
382        @Override
383        public Iterator<ElementReference> referenceIterator() {
384                return new ReferenceIterator();
385        }
386
387
388        /*
389         * (non-Javadoc)
390         * @see de.ls5.smartcollections.SmartCollection#remove(de.ls5.smartcollections.ElementReference)
391         */
392        @Override
393        public void remove(ElementReference ref) {
394                remove(asHeapRef(ref).index);
395        }
396
397        /*
398         * (non-Javadoc)
399         * @see de.ls5.smartcollections.SmartCollection#replace(de.ls5.smartcollections.ElementReference, java.lang.Object)
400         */
401        @Override
402        public void replace(ElementReference ref, E newElement) {
403                Reference<E> heapRef = asHeapRef(ref);
404                heapRef.element = newElement;
405                keyChanged(ref);
406        }
407        
408        
409        /*
410         * (non-Javadoc)
411         * @see de.ls5.smartcollections.CapacityManagement#ensureCapacity(int)
412         */
413        @Override
414        public boolean ensureCapacity(int minCapacity) {
415                return entries.ensureCapacity(minCapacity);
416        }
417        
418        /*
419         * (non-Javadoc)
420         * @see de.ls5.smartcollections.CapacityManagement#ensureAdditionalCapacity(int)
421         */
422        @Override
423        public boolean ensureAdditionalCapacity(int additionalCapacity) {
424                return ensureCapacity(size+additionalCapacity);
425        }
426
427        /*
428         * (non-Javadoc)
429         * @see de.ls5.smartcollections.CapacityManagement#hintNextCapacity(int)
430         */
431        @Override
432        public void hintNextCapacity(int nextCapacityHint) {
433                entries.hintNextCapacity(nextCapacityHint);
434        }
435
436
437        /*
438         * (non-Javadoc)
439         * @see de.ls5.smartcollections.SmartCollection#deepClear()
440         */
441        @Override
442        public void deepClear() {
443                entries.setAll(null);
444        }
445
446
447        /*
448         * (non-Javadoc)
449         * @see de.ls5.smartcollections.SmartCollection#quickClear()
450         */
451        @Override
452        public void quickClear() {
453                size = 0;
454        }
455        
456        
457}