Coverage report

  %line %branch
org.apache.jcs.utils.struct.SortedPreferentialArray
77% 
91% 

 1  
 package org.apache.jcs.utils.struct;
 2  
 
 3  
 /*
 4  
  * Licensed to the Apache Software Foundation (ASF) under one
 5  
  * or more contributor license agreements.  See the NOTICE file
 6  
  * distributed with this work for additional information
 7  
  * regarding copyright ownership.  The ASF licenses this file
 8  
  * to you under the Apache License, Version 2.0 (the
 9  
  * "License"); you may not use this file except in compliance
 10  
  * with the License.  You may obtain a copy of the License at
 11  
  *
 12  
  *   http://www.apache.org/licenses/LICENSE-2.0
 13  
  *
 14  
  * Unless required by applicable law or agreed to in writing,
 15  
  * software distributed under the License is distributed on an
 16  
  * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
 17  
  * KIND, either express or implied.  See the License for the
 18  
  * specific language governing permissions and limitations
 19  
  * under the License.
 20  
  */
 21  
 
 22  
 import org.apache.commons.logging.Log;
 23  
 import org.apache.commons.logging.LogFactory;
 24  
 
 25  
 /**
 26  
  * This maintains a sorted array with a preferential replacement policy when full.
 27  
  * <p>
 28  
  * Insertion time is n, search is log(n)
 29  
  * <p>
 30  
  * Clients must manage thread safety on previous version. I synchronized the public methods to add
 31  
  * easy thread safety. I synchronized all public methods that make modifications.
 32  
  */
 33  1
 public class SortedPreferentialArray
 34  
 {
 35  
     /** The logger */
 36  161
     private static final Log log = LogFactory.getLog( SortedPreferentialArray.class );
 37  
 
 38  
     /** prefer large means that the smallest will be removed when full. */
 39  566
     private boolean preferLarge = true;
 40  
 
 41  
     /** maximum number allowed */
 42  566
     private int maxSize = 0;
 43  
 
 44  
     /** The currency number */
 45  566
     private int curSize = 0;
 46  
 
 47  
     /** The primary array */
 48  
     private Comparable[] array;
 49  
 
 50  
     /** the number that have been inserted. */
 51  566
     private int insertCnt = 0;
 52  
 
 53  
     /**
 54  
      * Consruct the array with the maximum size.
 55  
      * <p>
 56  
      * @param maxSize int
 57  
      */
 58  12
     public SortedPreferentialArray( int maxSize )
 59  554
     {
 60  566
         this.maxSize = maxSize;
 61  566
         array = new Comparable[maxSize];
 62  566
     }
 63  
 
 64  
     /**
 65  
      * If the array is full this will remove the smallest if preferLarge==true and if obj is bigger,
 66  
      * or the largest if preferLarge=false and obj is smaller than the largest.
 67  
      * <p>
 68  
      * @param obj Object
 69  
      */
 70  
     public synchronized void add( Comparable obj )
 71  
     {
 72  228241
         if ( obj == null )
 73  
         {
 74  8
             return;
 75  
         }
 76  
 
 77  228174
         if ( curSize < maxSize )
 78  
         {
 79  214795
             insert( obj );
 80  214805
             return;
 81  
         }
 82  13335
         if ( preferLarge )
 83  
         {
 84  
             // insert if obj is larger than the smallest
 85  13335
             Comparable sma = getSmallest();
 86  13335
             if ( obj.compareTo( sma ) > 0 )
 87  
             {
 88  13328
                 insert( obj );
 89  13328
                 return;
 90  
             }
 91  
             // obj is less than or equal to the smallest.
 92  7
             if ( log.isDebugEnabled() )
 93  
             {
 94  0
                 log.debug( "New object is smaller than or equal to the smallest" );
 95  
             }
 96  7
             return;
 97  
         }
 98  
         // Not preferLarge
 99  0
         Comparable lar = getLargest();
 100  
         // insert if obj is smaller than the largest
 101  0
         int diff = obj.compareTo( lar );
 102  0
         if ( dclass="keyword">iff > 0 || dclass="keyword">iff == 0 )
 103  
         {
 104  0
             if ( log.isDebugEnabled() )
 105  
             {
 106  0
                 log.debug( "New object is larger than or equal to the largest" );
 107  
             }
 108  0
             return;
 109  
         }
 110  
         // obj is less than the largest.
 111  0
         insert( obj );
 112  0
         return;
 113  
     }
 114  
 
 115  
     /**
 116  
      * Returns the largest without removing it from the array.
 117  
      * <p>
 118  
      * @return Comparable
 119  
      */
 120  
     public synchronized Comparable getLargest()
 121  
     {
 122  312532
         return array[curSize - 1];
 123  
     }
 124  
 
 125  
     /**
 126  
      * Returns the smallest element without removing it from the array.
 127  
      * <p>
 128  
      * @return Comparable
 129  
      */
 130  
     public synchronized Comparable getSmallest()
 131  
     {
 132  373509
         return array[0];
 133  
     }
 134  
 
 135  
     /**
 136  
      * Insert looks for the nearest largest. It then determines which way to shuffle depending on
 137  
      * the preference.
 138  
      * <p>
 139  
      * @param obj Comparable
 140  
      */
 141  
     private void insert( Comparable obj )
 142  
     {
 143  
         try
 144  
         {
 145  228173
             int nLar = findNearestLargerEqualOrLastPosition( obj );
 146  228194
             if ( log.isDebugEnabled() )
 147  
             {
 148  0
                 log.debug( "nLar = " + nLar + " obj = " + obj );
 149  
             }
 150  
 
 151  228243
             if ( nLar == curSize )
 152  
             {
 153  
                 // this next check should be unnecessary
 154  
                 // findNearestLargerPosition should only return the curSize if
 155  
                 // there is
 156  
                 // room left. Check to be safe
 157  203457
                 if ( curSize < maxSize )
 158  
                 {
 159  203341
                     array[nLar] = obj;
 160  203423
                     curSize++;
 161  203312
                     if ( log.isDebugEnabled() )
 162  
                     {
 163  0
                         log.debug( this.dumpArray() );
 164  
                     }
 165  203407
                     if ( log.isDebugEnabled() )
 166  
                     {
 167  0
                         log.debug( "Inserted object at the end of the array" );
 168  
                     }
 169  203410
                     return;
 170  
                 } // end if not full
 171  
             }
 172  
 
 173  24786
             boolean isFull = false;
 174  24786
             if ( curSize == maxSize )
 175  
             {
 176  13328
                 isFull = true;
 177  
             }
 178  
 
 179  
             // The array is full, we must replace
 180  
             // remove smallest or largest to determine whether to
 181  
             // shuffle left or right to insert
 182  24786
             if ( preferLarge )
 183  
             {
 184  24786
                 if ( isFull )
 185  
                 {
 186  
                     // is full, prefer larger, remove smallest by shifting left
 187  13328
                     int pnt = nLar - 1; // set iteration stop point
 188  65909352
                     for ( int i = 0; i < pnt; i++ )
 189  
                     {
 190  65896024
                         array[i] = array[i + 1];
 191  
                     }
 192  
                     // use nLar-1 for insertion point
 193  13328
                     array[nLar - 1] = obj;
 194  13328
                     if ( log.isDebugEnabled() )
 195  
                     {
 196  0
                         log.debug( "Inserted object at " + ( nLar - 1 ) );
 197  
                     }
 198  13311
                 }
 199  
                 else
 200  
                 {
 201  
                     // not full, shift right from spot
 202  11458
                     int pnt = nLar; // set iteration stop point
 203  7548282
                     for ( int i = curSize; i > pnt; i-- )
 204  
                     {
 205  7536824
                         array[i] = array[i - 1];
 206  
                     }
 207  
                     // use nLar-1 for insertion point
 208  11458
                     array[nLar] = obj;
 209  11458
                     curSize++;
 210  11458
                     if ( log.isDebugEnabled() )
 211  
                     {
 212  0
                         log.debug( "Inserted object at " + ( nLar ) );
 213  
                     }
 214  
                 }
 215  11422
             }
 216  
             else
 217  
             {
 218  
                 // prefer smaller, remove largest by shifting right
 219  
                 // use nLar for insertion point
 220  0
                 int pnt = nLar + 1;
 221  0
                 if ( !isFull )
 222  
                 {
 223  0
                     pnt = nLar;
 224  
                 }
 225  0
                 for ( int i = curSize; i > pnt; i-- )
 226  
                 {
 227  0
                     array[i] = array[i - 1];
 228  
                 }
 229  0
                 array[nLar] = obj;
 230  0
                 if ( log.isDebugEnabled() )
 231  
                 {
 232  0
                     log.debug( "Inserted object at " + nLar );
 233  
                 }
 234  
             }
 235  
 
 236  24786
             if ( log.isDebugEnabled() )
 237  
             {
 238  0
                 log.debug( this.dumpArray() );
 239  
             }
 240  
         }
 241  0
         catch ( Exception e )
 242  
         {
 243  0
             log.error( "Insertion problem" + this.dumpArray(), e );
 244  24733
         }
 245  
 
 246  24786
         insertCnt++;
 247  24786
         if ( insertCnt % 100 == 0 )
 248  
         {
 249  227
             if ( log.isDebugEnabled() )
 250  
             {
 251  0
                 log.debug( this.dumpArray() );
 252  
             }
 253  
         }
 254  24786
     }
 255  
 
 256  
     /**
 257  
      * Determines whether the preference is for large or small.
 258  
      * <p>
 259  
      * @param pref boolean
 260  
      */
 261  
     public synchronized void setPreferLarge( boolean pref )
 262  
     {
 263  96
         preferLarge = pref;
 264  96
     }
 265  
 
 266  
     /**
 267  
      * Returns and removes the nearer larger or equal object from the aray.
 268  
      * <p>
 269  
      * @param obj Comparable
 270  
      * @return Comparable, null if arg is null or none was found.
 271  
      */
 272  
     public synchronized Comparable takeNearestLargerOrEqual( Comparable obj )
 273  
     {
 274  245266
         if ( obj == null )
 275  
         {
 276  8
             return null;
 277  
         }
 278  
 
 279  245245
         Comparable retVal = null;
 280  
         try
 281  
         {
 282  245239
             int pos = findNearestOccupiedLargerOrEqualPosition( obj );
 283  245273
             if ( pos == -1 )
 284  
             {
 285  129013
                 return null;
 286  
             }
 287  
 
 288  
             try
 289  
             {
 290  116221
                 retVal = array[pos];
 291  116221
                 remove( pos );
 292  
             }
 293  0
             catch ( Exception e )
 294  
             {
 295  0
                 log.error( "Problem removing from array. pos [" + pos + "] " + obj, e );
 296  116207
             }
 297  
 
 298  116221
             if ( log.isDebugEnabled() )
 299  
             {
 300  0
                 log.debug( "obj = " + obj + " || retVal = " + retVal );
 301  
             }
 302  
         }
 303  0
         catch ( Exception e )
 304  
         {
 305  0
             log.error( "Take problem" + this.dumpArray(), e );
 306  116207
         }
 307  116221
         return retVal;
 308  
     }
 309  
 
 310  
     /**
 311  
      * Returns the current size of the array.
 312  
      * <p>
 313  
      * @return int
 314  
      */
 315  
     public synchronized int size()
 316  
     {
 317  48663
         return this.curSize;
 318  
     }
 319  
 
 320  
     /**
 321  
      * This determines the position in the array that is occupied by an object that is larger or
 322  
      * equal to the argument. If none exists, -1 is returned.
 323  
      * <p>
 324  
      * @param obj Object
 325  
      * @return Object
 326  
      */
 327  
     private int findNearestOccupiedLargerOrEqualPosition( Comparable obj )
 328  
     {
 329  245218
         if ( curSize == 0 )
 330  
         {
 331  
             // nothing in the array
 332  67919
             return -1;
 333  
         }
 334  
 
 335  
         // this gives us an insert position.
 336  177346
         int pos = findNearestLargerEqualOrLastPosition( obj );
 337  
 
 338  
         // see if the previous will do to handle the empty insert spot position
 339  177346
         if ( pos == curSize )
 340  
         { // && curSize < maxSize ) {
 341  
             // pos will be > 0 if it equals curSize, we check for this above.
 342  109017
             if ( obj.compareTo( array[pos - 1] ) <= 0 )
 343  
             {
 344  61107
                 pos = pos - 1;
 345  61102
             }
 346  
             else
 347  
             {
 348  47910
                 pos = -1;
 349  
             }
 350  47908
         }
 351  
         else
 352  
         {
 353  
             // the find nearest, returns the last, since it is used by insertion.
 354  68329
             if ( obj.compareTo( array[pos] ) > 0 )
 355  
             {
 356  13215
                 return -1;
 357  
             }
 358  
         }
 359  
 
 360  164131
         return pos;
 361  
     }
 362  
 
 363  
     /**
 364  
      * This method determines the position where an insert should take place for a given object.
 365  
      * With some additional checking, this can also be used to find an object matching or greater
 366  
      * than the argument.
 367  
      * <p>
 368  
      * If the array is not full and the current object is larger than all the rest the first open
 369  
      * slot at the end will be returned.
 370  
      * <p>
 371  
      * NOTE: If the object is larger than the largest and it is full, it will return the last position.
 372  
      * <p>
 373  
      * If the array is empty, the first spot is returned.
 374  
      * <p>
 375  
      * If the object is smaller than all the rests, the first position is returned. The caller must
 376  
      * decide what to do given the preference.
 377  
      * <p>
 378  
      * Returns the position of the object nearest to or equal to the larger object.
 379  
      * <p>
 380  
      * If you want to find the takePosition, you have to calculate it.
 381  
      * findNearestOccupiedLargerOrEqualPosition will calculate this for you.
 382  
      * <p>
 383  
      * @param obj Comparable
 384  
      * @return int
 385  
      */
 386  
     private int findNearestLargerEqualOrLastPosition( Comparable obj )
 387  
     {
 388  
         // do nothing if a null was passed in
 389  405528
         if ( obj == null )
 390  
         {
 391  0
             return -1;
 392  
         }
 393  
 
 394  
         // return the first spot if the array is empty
 395  405549
         if ( curSize <= 0 )
 396  
         {
 397  45315
             return 0;
 398  
         }
 399  
 
 400  
         // mark the numer to be returned, the greaterPos as unset
 401  359950
         int greaterPos = -1;
 402  
         // prepare for a binary search
 403  359956
         int curPos = ( curSize - 1 ) / 2;
 404  360275
         int prevPos = -1;
 405  
 
 406  
         try
 407  
         {
 408  
             // set the loop exit flag to false
 409  360163
             boolean done = false;
 410  
 
 411  
             // check the ends
 412  
             // return insert position 0 if obj is smaller
 413  
             // than the smallest. the caller can determine what to
 414  
             // do with this, depending on the preference setting
 415  360123
             if ( obj.compareTo( getSmallest() ) <= 0 )
 416  
             {
 417  
                 // LESS THAN OR EQUAL TO SMALLEST
 418  47568
                 if ( log.isDebugEnabled() )
 419  
                 {
 420  0
                     log.debug( obj + " is smaller than or equal to " + getSmallest() );
 421  
                 }
 422  47568
                 greaterPos = 0;
 423  47568
                 done = true;
 424  
                 // return greaterPos;
 425  47562
             }
 426  
             else
 427  
             {
 428  
                 // GREATER THAN SMALLEST
 429  312706
                 if ( log.isDebugEnabled() )
 430  
                 {
 431  0
                     log.debug( obj + " is bigger than " + getSmallest() );
 432  
                 }
 433  
 
 434  
                 // return the largest position if obj is larger
 435  
                 // than the largest. the caller can determine what to
 436  
                 // do with this, depending on the preference setting
 437  312707
                 if ( obj.compareTo( getLargest() ) >= 0 )
 438  
                 {
 439  293608
                     if ( curSize == maxSize )
 440  
                     {
 441  
                         // there is no room left in the array, return the last
 442  
                         // spot
 443  26447
                         greaterPos = curSize - 1;
 444  26447
                         done = true;
 445  26441
                     }
 446  
                     else
 447  
                     {
 448  
                         // there is room left in the array
 449  266947
                         greaterPos = curSize;
 450  267159
                         done = true;
 451  
                     }
 452  266969
                 }
 453  
                 else
 454  
                 {
 455  
                     // the obj is less than or equal to the largest, so we know that the
 456  
                     // last item is larger or equal
 457  19100
                     greaterPos = curSize - 1;
 458  
                 }
 459  
             }
 460  
 
 461  
             // /////////////////////////////////////////////////////////////////////
 462  
             // begin binary search for insertion spot
 463  438510
             while ( !done )
 464  
             {
 465  97398
                 if ( log.isDebugEnabled() )
 466  
                 {
 467  0
                     log.debug( "\n curPos = " + curPos + "; greaterPos = " + greaterPos + "; prevpos = " + prevPos );
 468  
                 }
 469  
 
 470  
                 // get out of loop if we have come to the end or passed it
 471  97398
                 if ( curPos == prevPos || curPos >= curSize )
 472  
                 {
 473  11599
                     done = true;
 474  11599
                     break;
 475  
                 }
 476  
                 else
 477  
 
 478  
                 // EQUAL TO
 479  
                 // object at current position is equal to the obj, use this,
 480  
                 // TODO could avoid some shuffling if I found a lower pos.
 481  85799
                 if ( array[curPos].compareTo( obj ) == 0 )
 482  
                 {
 483  7501
                     if ( log.isDebugEnabled() )
 484  
                     {
 485  0
                         log.debug( array[curPos] + " is equal to " + obj );
 486  
                     }
 487  7501
                     greaterPos = curPos;
 488  7501
                     done = true;
 489  7501
                     break;
 490  
                 }
 491  
                 else
 492  
 
 493  
                 // GREATER THAN
 494  
                 // array object at current position is greater than the obj, go
 495  
                 // left
 496  78298
                 if ( array[curPos].compareTo( obj ) > 0 )
 497  
                 {
 498  26594
                     if ( log.isDebugEnabled() )
 499  
                     {
 500  0
                         log.debug( array[curPos] + " is greater than " + obj );
 501  
                     }
 502  
                     // set the smallest greater equal to the current position
 503  26594
                     greaterPos = curPos;
 504  
                     // set the current position to
 505  
                     // set the previous position to the current position
 506  
                     // We could have an integer overflow, but this array could
 507  
                     // never get that large.
 508  26594
                     int newPos = Math.min( curPos, ( curPos + prevPos ) / 2 );
 509  26594
                     prevPos = curPos;
 510  26594
                     curPos = newPos;
 511  26564
                 }
 512  
                 else
 513  
 
 514  
                 // LESS THAN
 515  
                 // the object at the current position is smaller, go right
 516  51704
                 if ( array[curPos].compareTo( obj ) < 0 )
 517  
                 {
 518  51704
                     if ( log.isDebugEnabled() )
 519  
                     {
 520  0
                         log.debug( array[curPos] + " is less than " + obj );
 521  
                     }
 522  51704
                     if ( ( greaterPos != -1 ) && greaterPos - curPos < 0 )
 523  
                     {
 524  0
                         done = true;
 525  0
                         break; // return greaterPos;
 526  
                     }
 527  
                     else
 528  
                     {
 529  51704
                         int newPos = 0;
 530  51704
                         if ( prevPos > curPos )
 531  
                         {
 532  26994
                             newPos = Math.min( ( curPos + prevPos ) / 2, curSize );
 533  26845
                         }
 534  24710
                         else if ( prevPos == -1 )
 535  
                         {
 536  5146
                             newPos = Math.min( ( curSize + curPos ) / 2, curSize );
 537  
                         }
 538  51704
                         prevPos = curPos;
 539  51704
                         curPos = newPos;
 540  
                     }
 541  51381
                 }
 542  
             } // end while
 543  
             // /////////////////////////////////////////////////////////////////////
 544  
 
 545  360275
             if ( log.isDebugEnabled() )
 546  
             {
 547  0
                 log.debug( "Greater Position is [" + greaterPos + "]" + " array[greaterPos] [" + array[greaterPos]
 548  
                     + "]" );
 549  
             }
 550  
         }
 551  0
         catch ( Exception e )
 552  
         {
 553  0
             log.error( "\n curPos = " + curPos + "; greaterPos = " + greaterPos + "; prevpos = " + prevPos + " "
 554  
                 + this.dumpArray(), e );
 555  360171
         }
 556  
 
 557  360274
         return greaterPos;
 558  
     }
 559  
 
 560  
     /**
 561  
      * Removes the item from the array at the specified position. The remaining items to the right
 562  
      * are shifted left.
 563  
      * <p>
 564  
      * @param position int
 565  
      * @throw IndexOutOfBoundsException if position is out of range.
 566  
      */
 567  
     private void remove( int position )
 568  
     {
 569  116221
         if ( position >= curSize || position < 0 )
 570  
         {
 571  0
             throw new IndexOutOfBoundsException( "position=" + position + " must be less than curSize=" + curSize );
 572  
         }
 573  116221
         curSize--;
 574  
 
 575  116221
         if ( position < curSize )
 576  
         {
 577  
             try
 578  
             {
 579  8084
                 System.arraycopy( array, position + 1, array, position, ( curSize - position ) );
 580  
             }
 581  0
             catch ( IndexOutOfBoundsException ibe )
 582  
             {
 583  
                 // throw this, log details for debugging. This shouldn't happen.
 584  0
                 log.warn( "Caught index out of bounds exception. "
 585  
                     + "called 'System.arraycopy( array, position + 1, array, position, (curSize - position) );'  "
 586  
                     + "array.lengh [" + array.length + "] position [" + position + "] curSize [" + curSize + "]" );
 587  0
                 throw ibe;
 588  8082
             }
 589  
         }
 590  116221
         return;
 591  
     }
 592  
 
 593  
     /**
 594  
      * Debugging method to return a human readable display of array data.
 595  
      * <p>
 596  
      * @return String representation of the contents.
 597  
      */
 598  
     protected synchronized String dumpArray()
 599  
     {
 600  576
         StringBuffer buf = new StringBuffer();
 601  576
         buf.append( "\n ---------------------------" );
 602  576
         buf.append( "\n curSize = " + curSize );
 603  576
         buf.append( "\n array.length = " + array.length );
 604  576
         buf.append( "\n ---------------------------" );
 605  576
         buf.append( "\n Dump:" );
 606  6312
         for ( int i = 0; i < curSize; i++ )
 607  
         {
 608  5736
             buf.append( "\n " + i + "=" + array[i] );
 609  
         }
 610  576
         return buf.toString();
 611  
     }
 612  
 }

This report is generated by jcoverage, Maven and Maven JCoverage Plugin.