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.buffer; 018 019 import java.io.Serializable; 020 import java.util.AbstractCollection; 021 import java.util.Comparator; 022 import java.util.Iterator; 023 import java.util.NoSuchElementException; 024 025 import org.apache.commons.collections.Buffer; 026 import org.apache.commons.collections.BufferUnderflowException; 027 028 /** 029 * Binary heap implementation of <code>Buffer</code> that provides for 030 * removal based on <code>Comparator</code> ordering. 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 #remove()} method always returns the first element as determined 035 * by the sort order. (The <code>ascendingOrder</code> flag in the constructors 036 * can be used to reverse the sort order, in which case {@link #remove()} 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 #add(Object)} and {@link #remove()} operations perform 042 * in logarithmic time. The {@link #get()} 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 046 * {@link org.apache.commons.collections.BufferUtils#synchronizedBuffer(Buffer)} or 047 * {@link org.apache.commons.collections.buffer.SynchronizedBuffer#decorate(Buffer)} 048 * to provide synchronized access to a <code>PriorityBuffer</code>: 049 * <pre> 050 * Buffer heap = SynchronizedBuffer.decorate(new PriorityBuffer()); 051 * </pre> 052 * <p> 053 * This class is Serializable from Commons Collections 3.2. 054 * 055 * @since Commons Collections 3.0 (previously BinaryHeap v1.0) 056 * @version $Revision: 646777 $ $Date: 2008-04-10 13:33:15 +0100 (Thu, 10 Apr 2008) $ 057 * 058 * @author Peter Donald 059 * @author Ram Chidambaram 060 * @author Michael A. Smith 061 * @author Paul Jack 062 * @author Stephen Colebourne 063 * @author Steve Phelps 064 */ 065 public class PriorityBuffer extends AbstractCollection 066 implements Buffer, Serializable { 067 068 /** Serialization lock. */ 069 private static final long serialVersionUID = 6891186490470027896L; 070 071 /** 072 * The default capacity for the buffer. 073 */ 074 private static final int DEFAULT_CAPACITY = 13; 075 076 /** 077 * The elements in this buffer. 078 */ 079 protected Object[] elements; 080 /** 081 * The number of elements currently in this buffer. 082 */ 083 protected int size; 084 /** 085 * If true, the first element as determined by the sort order will 086 * be returned. If false, the last element as determined by the 087 * sort order will be returned. 088 */ 089 protected boolean ascendingOrder; 090 /** 091 * The comparator used to order the elements 092 */ 093 protected Comparator comparator; 094 095 //----------------------------------------------------------------------- 096 /** 097 * Constructs a new empty buffer that sorts in ascending order by the 098 * natural order of the objects added. 099 */ 100 public PriorityBuffer() { 101 this(DEFAULT_CAPACITY, true, null); 102 } 103 104 /** 105 * Constructs a new empty buffer that sorts in ascending order using the 106 * specified comparator. 107 * 108 * @param comparator the comparator used to order the elements, 109 * null means use natural order 110 */ 111 public PriorityBuffer(Comparator comparator) { 112 this(DEFAULT_CAPACITY, true, comparator); 113 } 114 115 /** 116 * Constructs a new empty buffer specifying the sort order and using the 117 * natural order of the objects added. 118 * 119 * @param ascendingOrder if <code>true</code> the heap is created as a 120 * minimum heap; otherwise, the heap is created as a maximum heap 121 */ 122 public PriorityBuffer(boolean ascendingOrder) { 123 this(DEFAULT_CAPACITY, ascendingOrder, null); 124 } 125 126 /** 127 * Constructs a new empty buffer specifying the sort order and comparator. 128 * 129 * @param ascendingOrder true to use the order imposed by the given 130 * comparator; false to reverse that order 131 * @param comparator the comparator used to order the elements, 132 * null means use natural order 133 */ 134 public PriorityBuffer(boolean ascendingOrder, Comparator comparator) { 135 this(DEFAULT_CAPACITY, ascendingOrder, comparator); 136 } 137 138 /** 139 * Constructs a new empty buffer that sorts in ascending order by the 140 * natural order of the objects added, specifying an initial capacity. 141 * 142 * @param capacity the initial capacity for the buffer, greater than zero 143 * @throws IllegalArgumentException if <code>capacity</code> is <= <code>0</code> 144 */ 145 public PriorityBuffer(int capacity) { 146 this(capacity, true, null); 147 } 148 149 /** 150 * Constructs a new empty buffer that sorts in ascending order using the 151 * specified comparator and initial capacity. 152 * 153 * @param capacity the initial capacity for the buffer, greater than zero 154 * @param comparator the comparator used to order the elements, 155 * null means use natural order 156 * @throws IllegalArgumentException if <code>capacity</code> is <= <code>0</code> 157 */ 158 public PriorityBuffer(int capacity, Comparator comparator) { 159 this(capacity, true, comparator); 160 } 161 162 /** 163 * Constructs a new empty buffer that specifying initial capacity and 164 * sort order, using the natural order of the objects added. 165 * 166 * @param capacity the initial capacity for the buffer, greater than zero 167 * @param ascendingOrder if <code>true</code> the heap is created as a 168 * minimum heap; otherwise, the heap is created as a maximum heap. 169 * @throws IllegalArgumentException if <code>capacity</code> is <code><= 0</code> 170 */ 171 public PriorityBuffer(int capacity, boolean ascendingOrder) { 172 this(capacity, ascendingOrder, null); 173 } 174 175 /** 176 * Constructs a new empty buffer that specifying initial capacity, 177 * sort order and comparator. 178 * 179 * @param capacity the initial capacity for the buffer, greater than zero 180 * @param ascendingOrder true to use the order imposed by the given 181 * comparator; false to reverse that order 182 * @param comparator the comparator used to order the elements, 183 * null means use natural order 184 * @throws IllegalArgumentException if <code>capacity</code> is <code><= 0</code> 185 */ 186 public PriorityBuffer(int capacity, boolean ascendingOrder, Comparator comparator) { 187 super(); 188 if (capacity <= 0) { 189 throw new IllegalArgumentException("invalid capacity"); 190 } 191 this.ascendingOrder = ascendingOrder; 192 193 //+1 as 0 is noop 194 this.elements = new Object[capacity + 1]; 195 this.comparator = comparator; 196 } 197 198 //----------------------------------------------------------------------- 199 /** 200 * Checks whether the heap is ascending or descending order. 201 * 202 * @return true if ascending order (a min heap) 203 */ 204 public boolean isAscendingOrder() { 205 return ascendingOrder; 206 } 207 208 /** 209 * Gets the comparator being used for this buffer, null is natural order. 210 * 211 * @return the comparator in use, null is natural order 212 */ 213 public Comparator comparator() { 214 return comparator; 215 } 216 217 //----------------------------------------------------------------------- 218 /** 219 * Returns the number of elements in this buffer. 220 * 221 * @return the number of elements in this buffer 222 */ 223 public int size() { 224 return size; 225 } 226 227 /** 228 * Clears all elements from the buffer. 229 */ 230 public void clear() { 231 elements = new Object[elements.length]; // for gc 232 size = 0; 233 } 234 235 /** 236 * Adds an element to the buffer. 237 * <p> 238 * The element added will be sorted according to the comparator in use. 239 * 240 * @param element the element to be added 241 * @return true always 242 */ 243 public boolean add(Object element) { 244 if (isAtCapacity()) { 245 grow(); 246 } 247 // percolate element to it's place in tree 248 if (ascendingOrder) { 249 percolateUpMinHeap(element); 250 } else { 251 percolateUpMaxHeap(element); 252 } 253 return true; 254 } 255 256 /** 257 * Gets the next element to be removed without actually removing it (peek). 258 * 259 * @return the next element 260 * @throws BufferUnderflowException if the buffer is empty 261 */ 262 public Object get() { 263 if (isEmpty()) { 264 throw new BufferUnderflowException(); 265 } else { 266 return elements[1]; 267 } 268 } 269 270 /** 271 * Gets and removes the next element (pop). 272 * 273 * @return the next element 274 * @throws BufferUnderflowException if the buffer is empty 275 */ 276 public Object remove() { 277 final Object result = get(); 278 elements[1] = elements[size--]; 279 280 // set the unused element to 'null' so that the garbage collector 281 // can free the object if not used anywhere else.(remove reference) 282 elements[size + 1] = null; 283 284 if (size != 0) { 285 // percolate top element to it's place in tree 286 if (ascendingOrder) { 287 percolateDownMinHeap(1); 288 } else { 289 percolateDownMaxHeap(1); 290 } 291 } 292 293 return result; 294 } 295 296 //----------------------------------------------------------------------- 297 /** 298 * Tests if the buffer is at capacity. 299 * 300 * @return <code>true</code> if buffer is full; <code>false</code> otherwise. 301 */ 302 protected boolean isAtCapacity() { 303 //+1 as element 0 is noop 304 return elements.length == size + 1; 305 } 306 307 308 /** 309 * Percolates element down heap from the position given by the index. 310 * <p> 311 * Assumes it is a minimum heap. 312 * 313 * @param index the index for the element 314 */ 315 protected void percolateDownMinHeap(final int index) { 316 final Object element = elements[index]; 317 int hole = index; 318 319 while ((hole * 2) <= size) { 320 int child = hole * 2; 321 322 // if we have a right child and that child can not be percolated 323 // up then move onto other child 324 if (child != size && compare(elements[child + 1], elements[child]) < 0) { 325 child++; 326 } 327 328 // if we found resting place of bubble then terminate search 329 if (compare(elements[child], element) >= 0) { 330 break; 331 } 332 333 elements[hole] = elements[child]; 334 hole = child; 335 } 336 337 elements[hole] = element; 338 } 339 340 /** 341 * Percolates element down heap from the position given by the index. 342 * <p> 343 * Assumes it is a maximum heap. 344 * 345 * @param index the index of the element 346 */ 347 protected void percolateDownMaxHeap(final int index) { 348 final Object element = elements[index]; 349 int hole = index; 350 351 while ((hole * 2) <= size) { 352 int child = hole * 2; 353 354 // if we have a right child and that child can not be percolated 355 // up then move onto other child 356 if (child != size && compare(elements[child + 1], elements[child]) > 0) { 357 child++; 358 } 359 360 // if we found resting place of bubble then terminate search 361 if (compare(elements[child], element) <= 0) { 362 break; 363 } 364 365 elements[hole] = elements[child]; 366 hole = child; 367 } 368 369 elements[hole] = element; 370 } 371 372 /** 373 * Percolates element up heap from the position given by the index. 374 * <p> 375 * Assumes it is a minimum heap. 376 * 377 * @param index the index of the element to be percolated up 378 */ 379 protected void percolateUpMinHeap(final int index) { 380 int hole = index; 381 Object element = elements[hole]; 382 while (hole > 1 && compare(element, elements[hole / 2]) < 0) { 383 // save element that is being pushed down 384 // as the element "bubble" is percolated up 385 final int next = hole / 2; 386 elements[hole] = elements[next]; 387 hole = next; 388 } 389 elements[hole] = element; 390 } 391 392 /** 393 * Percolates a new element up heap from the bottom. 394 * <p> 395 * Assumes it is a minimum heap. 396 * 397 * @param element the element 398 */ 399 protected void percolateUpMinHeap(final Object element) { 400 elements[++size] = element; 401 percolateUpMinHeap(size); 402 } 403 404 /** 405 * Percolates element up heap from from the position given by the index. 406 * <p> 407 * Assume it is a maximum heap. 408 * 409 * @param index the index of the element to be percolated up 410 */ 411 protected void percolateUpMaxHeap(final int index) { 412 int hole = index; 413 Object element = elements[hole]; 414 415 while (hole > 1 && compare(element, elements[hole / 2]) > 0) { 416 // save element that is being pushed down 417 // as the element "bubble" is percolated up 418 final int next = hole / 2; 419 elements[hole] = elements[next]; 420 hole = next; 421 } 422 423 elements[hole] = element; 424 } 425 426 /** 427 * Percolates a new element up heap from the bottom. 428 * <p> 429 * Assume it is a maximum heap. 430 * 431 * @param element the element 432 */ 433 protected void percolateUpMaxHeap(final Object element) { 434 elements[++size] = element; 435 percolateUpMaxHeap(size); 436 } 437 438 /** 439 * Compares two objects using the comparator if specified, or the 440 * natural order otherwise. 441 * 442 * @param a the first object 443 * @param b the second object 444 * @return -ve if a less than b, 0 if they are equal, +ve if a greater than b 445 */ 446 protected int compare(Object a, Object b) { 447 if (comparator != null) { 448 return comparator.compare(a, b); 449 } else { 450 return ((Comparable) a).compareTo(b); 451 } 452 } 453 454 /** 455 * Increases the size of the heap to support additional elements 456 */ 457 protected void grow() { 458 final Object[] array = new Object[elements.length * 2]; 459 System.arraycopy(elements, 0, array, 0, elements.length); 460 elements = array; 461 } 462 463 //----------------------------------------------------------------------- 464 /** 465 * Returns an iterator over this heap's elements. 466 * 467 * @return an iterator over this heap's elements 468 */ 469 public Iterator iterator() { 470 return new Iterator() { 471 472 private int index = 1; 473 private int lastReturnedIndex = -1; 474 475 public boolean hasNext() { 476 return index <= size; 477 } 478 479 public Object next() { 480 if (!hasNext()) { 481 throw new NoSuchElementException(); 482 } 483 lastReturnedIndex = index; 484 index++; 485 return elements[lastReturnedIndex]; 486 } 487 488 public void remove() { 489 if (lastReturnedIndex == -1) { 490 throw new IllegalStateException(); 491 } 492 elements[ lastReturnedIndex ] = elements[ size ]; 493 elements[ size ] = null; 494 size--; 495 if( size != 0 && lastReturnedIndex <= size) { 496 int compareToParent = 0; 497 if (lastReturnedIndex > 1) { 498 compareToParent = compare(elements[lastReturnedIndex], 499 elements[lastReturnedIndex / 2]); 500 } 501 if (ascendingOrder) { 502 if (lastReturnedIndex > 1 && compareToParent < 0) { 503 percolateUpMinHeap(lastReturnedIndex); 504 } else { 505 percolateDownMinHeap(lastReturnedIndex); 506 } 507 } else { // max heap 508 if (lastReturnedIndex > 1 && compareToParent > 0) { 509 percolateUpMaxHeap(lastReturnedIndex); 510 } else { 511 percolateDownMaxHeap(lastReturnedIndex); 512 } 513 } 514 } 515 index--; 516 lastReturnedIndex = -1; 517 } 518 519 }; 520 } 521 522 /** 523 * Returns a string representation of this heap. The returned string 524 * is similar to those produced by standard JDK collections. 525 * 526 * @return a string representation of this heap 527 */ 528 public String toString() { 529 final StringBuffer sb = new StringBuffer(); 530 531 sb.append("[ "); 532 533 for (int i = 1; i < size + 1; i++) { 534 if (i != 1) { 535 sb.append(", "); 536 } 537 sb.append(elements[i]); 538 } 539 540 sb.append(" ]"); 541 542 return sb.toString(); 543 } 544 545 }