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 <= <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 <= <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><= 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><= 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 }