Clover coverage report - Drools - 2.0-rc2
Coverage timestamp: Wed May 11 2005 07:12:26 BST
file stats: LOC: 650   Methods: 29
NCLOC: 323   Classes: 1
 
 Source file Conditionals Statements Methods TOTAL
PriorityQueue.java 52.1% 57.4% 55.2% 55.7%
coverage coverage
 1    package org.drools.util;
 2    /*
 3    * Copyright 2001-2004 The Apache Software Foundation
 4    *
 5    * Licensed under the Apache License, Version 2.0 (the "License"); you may not
 6    * use this file except in compliance with the License. You may obtain a copy of
 7    * the License at
 8    *
 9    * http://www.apache.org/licenses/LICENSE-2.0
 10    *
 11    * Unless required by applicable law or agreed to in writing, software
 12    * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
 13    * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
 14    * License for the specific language governing permissions and limitations under
 15    * the License.
 16    */
 17   
 18    import java.io.Serializable;
 19    import java.util.AbstractCollection;
 20    import java.util.Comparator;
 21    import java.util.Iterator;
 22    import java.util.NoSuchElementException;
 23   
 24    /**
 25    * Binary heap implementation of <code>Buffer</code> that provides for removal
 26    * based on <code>Comparator</code> ordering. <p/>The removal order of a
 27    * binary heap is based on either the natural sort order of its elements or a
 28    * specified {@linkComparator}. The {@link #remove()}method always returns the
 29    * first element as determined by the sort order. (The
 30    * <code>ascendingOrder</code> flag in the constructors can be used to reverse
 31    * the sort order, in which case {@link#remove()}will always remove the last
 32    * element.) The removal order is <i>not </i> the same as the order of
 33    * iteration; elements are returned by the iterator in no particular order. <p/>
 34    * The {@link #add(Object)}and {@link #remove()}operations perform in
 35    * logarithmic time. The {@link #get()}operation performs in constant time. All
 36    * other operations perform in linear time or worse. <p/>Note that this
 37    * implementation is not synchronized.
 38    *
 39    * @author Peter Donald
 40    * @author Ram Chidambaram
 41    * @author Michael A. Smith
 42    * @author Paul Jack
 43    * @author Stephen Colebourne
 44    * @author <a href="mailto:simon@redhillconsulting.com.au">Simon Harris </a>
 45    * @version $Revision: 1.2 $ $Date: 2004/11/19 02:15:18 $
 46    */
 47    public class PriorityQueue extends AbstractCollection
 48    implements
 49    Serializable
 50    {
 51   
 52    /**
 53    * The default capacity for the buffer.
 54    */
 55    private static final int DEFAULT_CAPACITY = 13;
 56   
 57    /**
 58    * The elements in this buffer.
 59    */
 60    protected Object[] elements;
 61   
 62    /**
 63    * The number of elements currently in this buffer.
 64    */
 65    protected int size;
 66   
 67    /**
 68    * If true, the first element as determined by the sort order will be
 69    * returned. If false, the last element as determined by the sort order will
 70    * be returned.
 71    */
 72    protected boolean ascendingOrder;
 73   
 74    /**
 75    * The comparator used to order the elements
 76    */
 77    protected Comparator comparator;
 78   
 79    // -----------------------------------------------------------------------
 80    /**
 81    * Constructs a new empty buffer that sorts in ascending order by the
 82    * natural order of the objects added.
 83    */
 84  0 public PriorityQueue()
 85    {
 86  0 this( DEFAULT_CAPACITY,
 87    true,
 88    null );
 89    }
 90   
 91    /**
 92    * Constructs a new empty buffer that sorts in ascending order using the
 93    * specified comparator.
 94    *
 95    * @param comparator
 96    * the comparator used to order the elements, null means use
 97    * natural order
 98    */
 99  124 public PriorityQueue(Comparator comparator)
 100    {
 101  124 this( DEFAULT_CAPACITY,
 102    true,
 103    comparator );
 104    }
 105   
 106    /**
 107    * Constructs a new empty buffer specifying the sort order and using the
 108    * natural order of the objects added.
 109    *
 110    * @param ascendingOrder
 111    * if <code>true</code> the heap is created as a minimum heap;
 112    * otherwise, the heap is created as a maximum heap
 113    */
 114  0 public PriorityQueue(boolean ascendingOrder)
 115    {
 116  0 this( DEFAULT_CAPACITY,
 117    ascendingOrder,
 118    null );
 119    }
 120   
 121    /**
 122    * Constructs a new empty buffer specifying the sort order and comparator.
 123    *
 124    * @param ascendingOrder
 125    * true to use the order imposed by the given comparator; false
 126    * to reverse that order
 127    * @param comparator
 128    * the comparator used to order the elements, null means use
 129    * natural order
 130    */
 131  0 public PriorityQueue(boolean ascendingOrder,
 132    Comparator comparator)
 133    {
 134  0 this( DEFAULT_CAPACITY,
 135    ascendingOrder,
 136    comparator );
 137    }
 138   
 139    /**
 140    * Constructs a new empty buffer that sorts in ascending order by the
 141    * natural order of the objects added, specifying an initial capacity.
 142    *
 143    * @param capacity
 144    * the initial capacity for the buffer, greater than zero
 145    * @throws IllegalArgumentException
 146    * if <code>capacity</code> is &lt;= <code>0</code>
 147    */
 148  0 public PriorityQueue(int capacity)
 149    {
 150  0 this( capacity,
 151    true,
 152    null );
 153    }
 154   
 155    /**
 156    * Constructs a new empty buffer that sorts in ascending order using the
 157    * specified comparator and initial capacity.
 158    *
 159    * @param capacity
 160    * the initial capacity for the buffer, greater than zero
 161    * @param comparator
 162    * the comparator used to order the elements, null means use
 163    * natural order
 164    * @throws IllegalArgumentException
 165    * if <code>capacity</code> is &lt;= <code>0</code>
 166    */
 167  0 public PriorityQueue(int capacity,
 168    Comparator comparator)
 169    {
 170  0 this( capacity,
 171    true,
 172    comparator );
 173    }
 174   
 175    /**
 176    * Constructs a new empty buffer that specifying initial capacity and sort
 177    * order, using the natural order of the objects added.
 178    *
 179    * @param capacity
 180    * the initial capacity for the buffer, greater than zero
 181    * @param ascendingOrder
 182    * if <code>true</code> the heap is created as a minimum heap;
 183    * otherwise, the heap is created as a maximum heap.
 184    * @throws IllegalArgumentException
 185    * if <code>capacity</code> is <code>&lt;= 0</code>
 186    */
 187  0 public PriorityQueue(int capacity,
 188    boolean ascendingOrder)
 189    {
 190  0 this( capacity,
 191    ascendingOrder,
 192    null );
 193    }
 194   
 195    /**
 196    * Constructs a new empty buffer that specifying initial capacity, sort
 197    * order and comparator.
 198    *
 199    * @param capacity
 200    * the initial capacity for the buffer, greater than zero
 201    * @param ascendingOrder
 202    * true to use the order imposed by the given comparator; false
 203    * to reverse that order
 204    * @param comparator
 205    * the comparator used to order the elements, null means use
 206    * natural order
 207    * @throws IllegalArgumentException
 208    * if <code>capacity</code> is <code>&lt;= 0</code>
 209    */
 210  124 public PriorityQueue(int capacity,
 211    boolean ascendingOrder,
 212    Comparator comparator)
 213    {
 214  124 super( );
 215  124 if ( capacity <= 0 )
 216    {
 217  0 throw new IllegalArgumentException( "invalid capacity" );
 218    }
 219  124 this.ascendingOrder = ascendingOrder;
 220   
 221    // +1 as 0 is noop
 222  124 this.elements = new Object[capacity + 1];
 223  124 this.comparator = comparator;
 224    }
 225   
 226    // -----------------------------------------------------------------------
 227    /**
 228    * Checks whether the heap is ascending or descending order.
 229    *
 230    * @return true if ascending order (a min heap)
 231    */
 232  0 public boolean isAscendingOrder()
 233    {
 234  0 return ascendingOrder;
 235    }
 236   
 237    /**
 238    * Gets the comparator being used for this buffer, null is natural order.
 239    *
 240    * @return the comparator in use, null is natural order
 241    */
 242  0 public Comparator comparator()
 243    {
 244  0 return comparator;
 245    }
 246   
 247    // -----------------------------------------------------------------------
 248    /**
 249    * Returns the number of elements in this buffer.
 250    *
 251    * @return the number of elements in this buffer
 252    */
 253  1311 public int size()
 254    {
 255  1311 return size;
 256    }
 257   
 258    /**
 259    * Clears all elements from the buffer.
 260    */
 261  0 public void clear()
 262    {
 263  0 elements = new Object[elements.length]; // for gc
 264  0 size = 0;
 265    }
 266   
 267    /**
 268    * Adds an element to the buffer. <p/>The element added will be sorted
 269    * according to the comparator in use.
 270    *
 271    * @param element
 272    * the element to be added
 273    * @return true always
 274    */
 275  6252 public boolean add(Object element)
 276    {
 277  6252 if ( isAtCapacity( ) )
 278    {
 279  11 grow( );
 280    }
 281    // percolate element to it's place in tree
 282  6252 if ( ascendingOrder )
 283    {
 284  6252 percolateUpMinHeap( element );
 285    }
 286    else
 287    {
 288  0 percolateUpMaxHeap( element );
 289    }
 290  6252 return true;
 291    }
 292   
 293    /**
 294    * Gets the next element to be removed without actually removing it (peek).
 295    *
 296    * @return the next element
 297    * @throws NoSuchElementException
 298    * if the buffer is empty
 299    */
 300  481 public Object get()
 301    {
 302  481 if ( isEmpty( ) )
 303    {
 304  0 throw new NoSuchElementException( );
 305    }
 306    else
 307    {
 308  481 return elements[1];
 309    }
 310    }
 311   
 312    /**
 313    * Gets and removes the next element (pop).
 314    *
 315    * @return the next element
 316    * @throws NoSuchElementException
 317    * if the buffer is empty
 318    */
 319  481 public Object remove()
 320    {
 321  481 final Object result = get( );
 322  481 elements[1] = elements[size--];
 323   
 324    // set the unused element to 'null' so that the garbage collector
 325    // can free the object if not used anywhere else.(remove reference)
 326  481 elements[size + 1] = null;
 327   
 328  481 if ( size != 0 )
 329    {
 330    // percolate top element to it's place in tree
 331  326 if ( ascendingOrder )
 332    {
 333  326 percolateDownMinHeap( 1 );
 334    }
 335    else
 336    {
 337  0 percolateDownMaxHeap( 1 );
 338    }
 339    }
 340   
 341  481 return result;
 342    }
 343   
 344    // -----------------------------------------------------------------------
 345    /**
 346    * Tests if the buffer is at capacity.
 347    *
 348    * @return <code>true</code> if buffer is full; <code>false</code>
 349    * otherwise.
 350    */
 351  6252 protected boolean isAtCapacity()
 352    {
 353    // +1 as element 0 is noop
 354  6252 return elements.length == size + 1;
 355    }
 356   
 357    /**
 358    * Percolates element down heap from the position given by the index. <p/>
 359    * Assumes it is a minimum heap.
 360    *
 361    * @param index
 362    * the index for the element
 363    */
 364  6038 protected void percolateDownMinHeap(final int index)
 365    {
 366  6038 final Object element = elements[index];
 367  6038 int hole = index;
 368   
 369  6038 while ( (hole * 2) <= size )
 370    {
 371  22373 int child = hole * 2;
 372   
 373    // if we have a right child and that child can not be percolated
 374    // up then move onto other child
 375  22373 if ( child != size && compare( elements[child + 1],
 376    elements[child] ) < 0 )
 377    {
 378  8067 child++;
 379    }
 380   
 381    // if we found resting place of bubble then terminate search
 382  22373 if ( compare( elements[child],
 383    element ) >= 0 )
 384    {
 385  3916 break;
 386    }
 387   
 388  18457 elements[hole] = elements[child];
 389  18457 hole = child;
 390    }
 391   
 392  6038 elements[hole] = element;
 393    }
 394   
 395    /**
 396    * Percolates element down heap from the position given by the index. <p/>
 397    * Assumes it is a maximum heap.
 398    *
 399    * @param index
 400    * the index of the element
 401    */
 402  0 protected void percolateDownMaxHeap(final int index)
 403    {
 404  0 final Object element = elements[index];
 405  0 int hole = index;
 406   
 407  0 while ( (hole * 2) <= size )
 408    {
 409  0 int child = hole * 2;
 410   
 411    // if we have a right child and that child can not be percolated
 412    // up then move onto other child
 413  0 if ( child != size && compare( elements[child + 1],
 414    elements[child] ) > 0 )
 415    {
 416  0 child++;
 417    }
 418   
 419    // if we found resting place of bubble then terminate search
 420  0 if ( compare( elements[child],
 421    element ) <= 0 )
 422    {
 423  0 break;
 424    }
 425   
 426  0 elements[hole] = elements[child];
 427  0 hole = child;
 428    }
 429   
 430  0 elements[hole] = element;
 431    }
 432   
 433    /**
 434    * Percolates element up heap from the position given by the index. <p/>
 435    * Assumes it is a minimum heap.
 436    *
 437    * @param index
 438    * the index of the element to be percolated up
 439    */
 440  6252 protected void percolateUpMinHeap(final int index)
 441    {
 442  6252 int hole = index;
 443  6252 Object element = elements[hole];
 444  6252 while ( hole > 1 && compare( element,
 445    elements[hole / 2] ) < 0 )
 446    {
 447    // save element that is being pushed down
 448    // as the element "bubble" is percolated up
 449  235 final int next = hole / 2;
 450  235 elements[hole] = elements[next];
 451  235 hole = next;
 452    }
 453  6252 elements[hole] = element;
 454    }
 455   
 456    /**
 457    * Percolates a new element up heap from the bottom. <p/>Assumes it is a
 458    * minimum heap.
 459    *
 460    * @param element
 461    * the element
 462    */
 463  6252 protected void percolateUpMinHeap(final Object element)
 464    {
 465  6252 elements[++size] = element;
 466  6252 percolateUpMinHeap( size );
 467    }
 468   
 469    /**
 470    * Percolates element up heap from from the position given by the index.
 471    * <p/>Assume it is a maximum heap.
 472    *
 473    * @param index
 474    * the index of the element to be percolated up
 475    */
 476  0 protected void percolateUpMaxHeap(final int index)
 477    {
 478  0 int hole = index;
 479  0 Object element = elements[hole];
 480   
 481  0 while ( hole > 1 && compare( element,
 482    elements[hole / 2] ) > 0 )
 483    {
 484    // save element that is being pushed down
 485    // as the element "bubble" is percolated up
 486  0 final int next = hole / 2;
 487  0 elements[hole] = elements[next];
 488  0 hole = next;
 489    }
 490   
 491  0 elements[hole] = element;
 492    }
 493   
 494    /**
 495    * Percolates a new element up heap from the bottom. <p/>Assume it is a
 496    * maximum heap.
 497    *
 498    * @param element
 499    * the element
 500    */
 501  0 protected void percolateUpMaxHeap(final Object element)
 502    {
 503  0 elements[++size] = element;
 504  0 percolateUpMaxHeap( size );
 505    }
 506   
 507    /**
 508    * Compares two objects using the comparator if specified, or the natural
 509    * order otherwise.
 510    *
 511    * @param a
 512    * the first object
 513    * @param b
 514    * the second object
 515    * @return -ve if a less than b, 0 if they are equal, +ve if a greater than
 516    * b
 517    */
 518  51040 protected int compare(Object a,
 519    Object b)
 520    {
 521  51040 if ( comparator != null )
 522    {
 523  51040 return comparator.compare( a,
 524    b );
 525    }
 526    else
 527    {
 528  0 return ((Comparable) a).compareTo( b );
 529    }
 530    }
 531   
 532    /**
 533    * Increases the size of the heap to support additional elements
 534    */
 535  11 protected void grow()
 536    {
 537  11 final Object[] array = new Object[elements.length * 2];
 538  11 System.arraycopy( elements,
 539    0,
 540    array,
 541    0,
 542    elements.length );
 543  11 elements = array;
 544    }
 545   
 546    // -----------------------------------------------------------------------
 547    /**
 548    * Returns an iterator over this heap's elements.
 549    *
 550    * @return an iterator over this heap's elements
 551    */
 552  6697 public Iterator iterator()
 553    {
 554  6697 return new Iterator( )
 555    {
 556   
 557    private int index = 1;
 558   
 559    private int lastReturnedIndex = -1;
 560   
 561  45566 public boolean hasNext()
 562    {
 563  45566 return index <= size;
 564    }
 565   
 566  22315 public Object next()
 567    {
 568  22315 if ( !hasNext( ) )
 569    {
 570  0 throw new NoSuchElementException( );
 571    }
 572  22315 lastReturnedIndex = index;
 573  22315 index++;
 574  22315 return elements[lastReturnedIndex];
 575    }
 576   
 577  5768 public void remove()
 578    {
 579  5768 if ( lastReturnedIndex == -1 )
 580    {
 581  0 throw new IllegalStateException( );
 582    }
 583  5768 elements[lastReturnedIndex] = elements[size];
 584  5768 elements[size] = null;
 585  5768 size--;
 586  5768 if ( size != 0 && lastReturnedIndex <= size )
 587    {
 588  5712 int compareToParent = 0;
 589  5712 if ( lastReturnedIndex > 1 )
 590    {
 591  205 compareToParent = compare( elements[lastReturnedIndex],
 592    elements[lastReturnedIndex / 2] );
 593    }
 594  5712 if ( ascendingOrder )
 595    {
 596  5712 if ( lastReturnedIndex > 1 && compareToParent < 0 )
 597    {
 598  0 percolateUpMinHeap( lastReturnedIndex );
 599    }
 600    else
 601    {
 602  5712 percolateDownMinHeap( lastReturnedIndex );
 603    }
 604    }
 605    else
 606    { // max heap
 607  0 if ( lastReturnedIndex > 1 && compareToParent > 0 )
 608    {
 609  0 percolateUpMaxHeap( lastReturnedIndex );
 610    }
 611    else
 612    {
 613  0 percolateDownMaxHeap( lastReturnedIndex );
 614    }
 615    }
 616    }
 617  5768 index--;
 618  5768 lastReturnedIndex = -1;
 619    }
 620   
 621    };
 622    }
 623   
 624    /**
 625    * Returns a string representation of this heap. The returned string is
 626    * similar to those produced by standard JDK collections.
 627    *
 628    * @return a string representation of this heap
 629    */
 630  0 public String toString()
 631    {
 632  0 final StringBuffer sb = new StringBuffer( );
 633   
 634  0 sb.append( "[ " );
 635   
 636  0 for ( int i = 1; i < size + 1; i++ )
 637    {
 638  0 if ( i != 1 )
 639    {
 640  0 sb.append( ", " );
 641    }
 642  0 sb.append( elements[i] );
 643    }
 644   
 645  0 sb.append( " ]" );
 646   
 647  0 return sb.toString( );
 648    }
 649   
 650    }