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}