1 16 package org.apache.commons.collections.buffer; 17 18 import java.util.AbstractCollection ; 19 import java.util.Comparator ; 20 import java.util.Iterator ; 21 import java.util.NoSuchElementException ; 22 23 import org.apache.commons.collections.Buffer; 24 import org.apache.commons.collections.BufferUnderflowException; 25 26 61 public class PriorityBuffer extends AbstractCollection implements Buffer { 62 63 66 private static final int DEFAULT_CAPACITY = 13; 67 68 71 protected Object [] elements; 72 75 protected int size; 76 81 protected boolean ascendingOrder; 82 85 protected Comparator comparator; 86 87 92 public PriorityBuffer() { 93 this(DEFAULT_CAPACITY, true, null); 94 } 95 96 103 public PriorityBuffer(Comparator comparator) { 104 this(DEFAULT_CAPACITY, true, comparator); 105 } 106 107 114 public PriorityBuffer(boolean ascendingOrder) { 115 this(DEFAULT_CAPACITY, ascendingOrder, null); 116 } 117 118 126 public PriorityBuffer(boolean ascendingOrder, Comparator comparator) { 127 this(DEFAULT_CAPACITY, ascendingOrder, comparator); 128 } 129 130 137 public PriorityBuffer(int capacity) { 138 this(capacity, true, null); 139 } 140 141 150 public PriorityBuffer(int capacity, Comparator comparator) { 151 this(capacity, true, comparator); 152 } 153 154 163 public PriorityBuffer(int capacity, boolean ascendingOrder) { 164 this(capacity, ascendingOrder, null); 165 } 166 167 178 public PriorityBuffer(int capacity, boolean ascendingOrder, Comparator comparator) { 179 super(); 180 if (capacity <= 0) { 181 throw new IllegalArgumentException ("invalid capacity"); 182 } 183 this.ascendingOrder = ascendingOrder; 184 185 this.elements = new Object [capacity + 1]; 187 this.comparator = comparator; 188 } 189 190 196 public boolean isAscendingOrder() { 197 return ascendingOrder; 198 } 199 200 205 public Comparator comparator() { 206 return comparator; 207 } 208 209 215 public int size() { 216 return size; 217 } 218 219 222 public void clear() { 223 elements = new Object [elements.length]; size = 0; 225 } 226 227 235 public boolean add(Object element) { 236 if (isAtCapacity()) { 237 grow(); 238 } 239 if (ascendingOrder) { 241 percolateUpMinHeap(element); 242 } else { 243 percolateUpMaxHeap(element); 244 } 245 return true; 246 } 247 248 254 public Object get() { 255 if (isEmpty()) { 256 throw new BufferUnderflowException(); 257 } else { 258 return elements[1]; 259 } 260 } 261 262 268 public Object remove() { 269 final Object result = get(); 270 elements[1] = elements[size--]; 271 272 elements[size + 1] = null; 275 276 if (size != 0) { 277 if (ascendingOrder) { 279 percolateDownMinHeap(1); 280 } else { 281 percolateDownMaxHeap(1); 282 } 283 } 284 285 return result; 286 } 287 288 294 protected boolean isAtCapacity() { 295 return elements.length == size + 1; 297 } 298 299 300 307 protected void percolateDownMinHeap(final int index) { 308 final Object element = elements[index]; 309 int hole = index; 310 311 while ((hole * 2) <= size) { 312 int child = hole * 2; 313 314 if (child != size && compare(elements[child + 1], elements[child]) < 0) { 317 child++; 318 } 319 320 if (compare(elements[child], element) >= 0) { 322 break; 323 } 324 325 elements[hole] = elements[child]; 326 hole = child; 327 } 328 329 elements[hole] = element; 330 } 331 332 339 protected void percolateDownMaxHeap(final int index) { 340 final Object element = elements[index]; 341 int hole = index; 342 343 while ((hole * 2) <= size) { 344 int child = hole * 2; 345 346 if (child != size && compare(elements[child + 1], elements[child]) > 0) { 349 child++; 350 } 351 352 if (compare(elements[child], element) <= 0) { 354 break; 355 } 356 357 elements[hole] = elements[child]; 358 hole = child; 359 } 360 361 elements[hole] = element; 362 } 363 364 371 protected void percolateUpMinHeap(final int index) { 372 int hole = index; 373 Object element = elements[hole]; 374 while (hole > 1 && compare(element, elements[hole / 2]) < 0) { 375 final int next = hole / 2; 378 elements[hole] = elements[next]; 379 hole = next; 380 } 381 elements[hole] = element; 382 } 383 384 391 protected void percolateUpMinHeap(final Object element) { 392 elements[++size] = element; 393 percolateUpMinHeap(size); 394 } 395 396 403 protected void percolateUpMaxHeap(final int index) { 404 int hole = index; 405 Object element = elements[hole]; 406 407 while (hole > 1 && compare(element, elements[hole / 2]) > 0) { 408 final int next = hole / 2; 411 elements[hole] = elements[next]; 412 hole = next; 413 } 414 415 elements[hole] = element; 416 } 417 418 425 protected void percolateUpMaxHeap(final Object element) { 426 elements[++size] = element; 427 percolateUpMaxHeap(size); 428 } 429 430 438 protected int compare(Object a, Object b) { 439 if (comparator != null) { 440 return comparator.compare(a, b); 441 } else { 442 return ((Comparable ) a).compareTo(b); 443 } 444 } 445 446 449 protected void grow() { 450 final Object [] array = new Object [elements.length * 2]; 451 System.arraycopy(elements, 0, array, 0, elements.length); 452 elements = array; 453 } 454 455 461 public Iterator iterator() { 462 return new Iterator () { 463 464 private int index = 1; 465 private int lastReturnedIndex = -1; 466 467 public boolean hasNext() { 468 return index <= size; 469 } 470 471 public Object next() { 472 if (!hasNext()) { 473 throw new NoSuchElementException (); 474 } 475 lastReturnedIndex = index; 476 index++; 477 return elements[lastReturnedIndex]; 478 } 479 480 public void remove() { 481 if (lastReturnedIndex == -1) { 482 throw new IllegalStateException (); 483 } 484 elements[ lastReturnedIndex ] = elements[ size ]; 485 elements[ size ] = null; 486 size--; 487 if( size != 0 && lastReturnedIndex <= size) { 488 int compareToParent = 0; 489 if (lastReturnedIndex > 1) { 490 compareToParent = compare(elements[lastReturnedIndex], 491 elements[lastReturnedIndex / 2]); 492 } 493 if (ascendingOrder) { 494 if (lastReturnedIndex > 1 && compareToParent < 0) { 495 percolateUpMinHeap(lastReturnedIndex); 496 } else { 497 percolateDownMinHeap(lastReturnedIndex); 498 } 499 } else { if (lastReturnedIndex > 1 && compareToParent > 0) { 501 percolateUpMaxHeap(lastReturnedIndex); 502 } else { 503 percolateDownMaxHeap(lastReturnedIndex); 504 } 505 } 506 } 507 index--; 508 lastReturnedIndex = -1; 509 } 510 511 }; 512 } 513 514 520 public String toString() { 521 final StringBuffer sb = new StringBuffer (); 522 523 sb.append("[ "); 524 525 for (int i = 1; i < size + 1; i++) { 526 if (i != 1) { 527 sb.append(", "); 528 } 529 sb.append(elements[i]); 530 } 531 532 sb.append(" ]"); 533 534 return sb.toString(); 535 } 536 537 } 538 | Popular Tags |