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.ArrayList;
020import java.util.Iterator;
021import java.util.List;
022import java.util.Objects;
023
024/**
025 * A {@link SmartGeneralPriorityQueue} implementation that is backed by a
026 * {@link SmartDynamicPriorityQueue}.
027 * 
028 * The default {@link SmartDynamicPriorityQueue} to be used is a
029 * {@link BinaryHeap}, but every other implementation of this interface
030 * may be used. The backing queue is specified in the constructor.
031 * 
032 * @author Malte Isberner <malte.isberner@gmail.com>
033 *
034 * @param <E> element class.
035 * @param <K> key class.
036 */
037public class BackedGeneralPriorityQueue<E, K extends Comparable<K>> extends AbstractSmartCollection<E>
038                implements SmartGeneralPriorityQueue<E,K> {
039        
040        private static final int DEFAULT_INITIAL_CAPACITY = 10;
041        
042        private static class Entry<E,K extends Comparable<K>> implements Comparable<Entry<E,K>> {
043                public E element;
044                public K key;
045                
046                public Entry(E element, K key) {
047                        this.element = element;
048                        this.key = key;
049                }
050
051                @Override
052                public int compareTo(Entry<E,K> o) {
053                        return key.compareTo(o.key);
054                }
055        }
056        
057        
058        private static class ElementIterator<E> implements Iterator<E> {
059                private final Iterator<? extends Entry<E,?>> entryIterator;
060                
061                public ElementIterator(Iterator<? extends Entry<E,?>> entryIterator) {
062                        this.entryIterator = entryIterator;
063                }
064
065                @Override
066                public boolean hasNext() {
067                        return entryIterator.hasNext();
068                }
069
070                @Override
071                public E next() {
072                        return entryIterator.next().element;
073                }
074
075                @Override
076                public void remove() {
077                        entryIterator.remove();
078                }
079                
080        }
081        
082        private final SmartDynamicPriorityQueue<Entry<E,K>> backingQueue;
083        private K defaultKey;
084        
085        public BackedGeneralPriorityQueue() {
086                this(DEFAULT_INITIAL_CAPACITY);
087        }
088        
089        public BackedGeneralPriorityQueue(int initialCapacity) {
090                this.backingQueue = BinaryHeap.create(initialCapacity);
091        }
092        
093        public BackedGeneralPriorityQueue(List<? extends E> init, List<K> keys) {
094                List<Entry<E,K>> entries = new ArrayList<>(init.size());
095                
096                Iterator<? extends E> elemIt = init.iterator();
097                Iterator<K> keyIt = keys.iterator();
098                
099                while(elemIt.hasNext()) {
100                        K key = (keyIt.hasNext()) ? keyIt.next() : null;
101                        entries.add(new Entry<E,K>(elemIt.next(), key));
102                }
103                
104                this.backingQueue = BinaryHeap.create(entries);
105        }
106        
107        @SuppressWarnings("unchecked")
108        public BackedGeneralPriorityQueue(Class<? extends SmartDynamicPriorityQueue<?>> backingClazz) {
109                SmartDynamicPriorityQueue<?> backing;
110                try {
111                        backing = backingClazz.newInstance();
112                } catch (InstantiationException e) {
113                        throw new IllegalArgumentException("Cannot instantiate backing "
114                                        + "priority queue of type " + backingClazz.getName()
115                                        + ": " + e.getMessage(), e);
116                } catch (IllegalAccessException e) {
117                        throw new IllegalArgumentException("Cannot instantiate backing "
118                                        + "priority queue of type " + backingClazz.getName()
119                                        + ": " + e.getMessage(), e);
120                }
121                this.backingQueue = (SmartDynamicPriorityQueue<Entry<E,K>>)backing;
122        }
123        
124        /**
125         * Constructor. Explicitly initializes this queue with a given backing
126         * queue. Note that the provided queue must be empty and must not be used
127         * in any other way after being passed to the constructor.
128         * @param backingQueue the backing queue.
129         */
130        @SuppressWarnings("unchecked")
131        public BackedGeneralPriorityQueue(SmartDynamicPriorityQueue<?> backingQueue) {
132                if(!backingQueue.isEmpty())
133                        throw new IllegalArgumentException("Backing priority queue must "
134                                        + "be empty upon initialization!");
135                this.backingQueue = (SmartDynamicPriorityQueue<Entry<E,K>>)backingQueue;
136        }
137
138        /*
139         * (non-Javadoc)
140         * @see de.ls5.smartcollections.AbstractSmartCollection#choose()
141         */
142        @Override
143        public E choose() {
144                Entry<E,K> entry = backingQueue.choose();
145                if(entry == null)
146                        return null;
147                return entry.element;
148        }
149
150        /*
151         * (non-Javadoc)
152         * @see de.ls5.smartcollections.AbstractSmartCollection#chooseRef()
153         */
154        @Override
155        public ElementReference chooseRef() {
156                return backingQueue.chooseRef();
157        }
158
159        /*
160         * (non-Javadoc)
161         * @see de.ls5.smartcollections.AbstractSmartCollection#find(java.lang.Object)
162         */
163        @Override
164        public ElementReference find(Object element) {
165                for(ElementReference ref : backingQueue.references()) {
166                        Entry<E,K> entry = backingQueue.get(ref);
167                        if(Objects.equals(entry.element, element))
168                                return ref;
169                }
170                return null;
171        }
172
173        /*
174         * (non-Javadoc)
175         * @see de.ls5.smartcollections.SmartCollection#get(de.ls5.smartcollections.ElementReference)
176         */
177        @Override
178        public E get(ElementReference ref) {
179                Entry<E,K> entry = backingQueue.get(ref);
180                return entry.element;
181        }
182
183        /*
184         * (non-Javadoc)
185         * @see de.ls5.smartcollections.SmartCollection#referenceIterator()
186         */
187        @Override
188        public Iterator<ElementReference> referenceIterator() {
189                return backingQueue.referenceIterator();
190        }
191
192        /*
193         * (non-Javadoc)
194         * @see de.ls5.smartcollections.SmartCollection#referencedAdd(java.lang.Object)
195         */
196        @Override
197        public ElementReference referencedAdd(E elem) {
198                return add(elem, defaultKey);
199        }
200        
201        /* (non-Javadoc)
202         * @see de.ls5.smartcollections.SmartGeneralPriorityQueue#add(E, K)
203         */
204        @Override
205        public ElementReference add(E elem, K key) {
206                Entry<E,K> entry = new Entry<>(elem, key);
207                return backingQueue.referencedAdd(entry);
208        }
209
210        /*
211         * (non-Javadoc)
212         * @see de.ls5.smartcollections.SmartCollection#remove(de.ls5.smartcollections.ElementReference)
213         */
214        @Override
215        public void remove(ElementReference ref) {
216                backingQueue.remove(ref);
217        }
218
219        /*
220         * (non-Javadoc)
221         * @see de.ls5.smartcollections.SmartCollection#replace(de.ls5.smartcollections.ElementReference, java.lang.Object)
222         */
223        @Override
224        public void replace(ElementReference ref, E newElement) {
225                Entry<E,K> entry = backingQueue.get(ref);
226                entry.element = newElement;
227        }
228
229        /*
230         * (non-Javadoc)
231         * @see java.util.AbstractCollection#clear()
232         */
233        @Override
234        public void clear() {
235                backingQueue.clear();
236        }
237
238        /*
239         * (non-Javadoc)
240         * @see java.util.AbstractCollection#isEmpty()
241         */
242        @Override
243        public boolean isEmpty() {
244                return backingQueue.isEmpty();
245        }
246
247        /*
248         * (non-Javadoc)
249         * @see de.ls5.smartcollections.AbstractSmartCollection#iterator()
250         */
251        @Override
252        public Iterator<E> iterator() {
253                return new ElementIterator<>(backingQueue.iterator());
254        }
255
256        /*
257         * (non-Javadoc)
258         * @see java.util.AbstractCollection#size()
259         */
260        @Override
261        public int size() {
262                return backingQueue.size();
263        }
264        
265        
266        /* (non-Javadoc)
267         * @see de.ls5.smartcollections.SmartGeneralPriorityQueue#setDefaultPriority(int)
268         */
269        @Override
270        public void setDefaultKey(K defaultKey) {
271                this.defaultKey = defaultKey;
272        }
273        
274        /* (non-Javadoc)
275         * @see de.ls5.smartcollections.SmartGeneralPriorityQueue#changePriority(de.ls5.smartcollections.ElementReference, int)
276         */
277        @Override
278        public void changeKey(ElementReference ref, K newKey) {
279                Entry<E,K> entry = backingQueue.get(ref);
280                entry.key = newKey;
281                backingQueue.keyChanged(ref);
282        }
283        
284        
285        /*
286         * (non-Javadoc)
287         * @see de.ls5.smartcollections.SmartPriorityQueue#extractMin()
288         */
289        @Override
290        public E extractMin() {
291                Entry<E,K> min = backingQueue.extractMin();
292                return min.element;
293        }
294
295        /*
296         * (non-Javadoc)
297         * @see de.ls5.smartcollections.SmartPriorityQueue#peekMin()
298         */
299        @Override
300        public E peekMin() {
301                Entry<E,K> min = backingQueue.peekMin();
302                return min.element;
303        }
304
305        /*
306         * (non-Javadoc)
307         * @see net.automatalib.commons.smartcollections.AbstractSmartCollection#deepClear()
308         */
309        @Override
310        public void deepClear() {
311                backingQueue.deepClear();
312        }
313
314        /*
315         * (non-Javadoc)
316         * @see net.automatalib.commons.smartcollections.AbstractSmartCollection#quickClear()
317         */
318        @Override
319        public void quickClear() {
320                backingQueue.quickClear();
321        }
322        
323        
324}