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}