Clover coverage report - Drools - 2.0-rc2
Coverage timestamp: Wed May 11 2005 07:12:26 BST
file stats: LOC: 485   Methods: 24
NCLOC: 337   Classes: 2
 
 Source file Conditionals Statements Methods TOTAL
PrimitiveLongMap.java 89.1% 93.1% 87.5% 91.4%
coverage coverage
 1    package org.drools.util;
 2   
 3    import java.io.Serializable;
 4    import java.util.Arrays;
 5    import java.util.Collection;
 6   
 7    /*
 8    * $Id: PrimitiveLongMap.java,v 1.14 2005/01/09 01:27:33 mproctor Exp $
 9    *
 10    * Copyright 2004 (C) The Werken Company. All Rights Reserved.
 11    *
 12    * Redistribution and use of this software and associated documentation
 13    * ("Software"), with or without modification, are permitted provided that the
 14    * following conditions are met:
 15    *
 16    * 1. Redistributions of source code must retain copyright statements and
 17    * notices. Redistributions must also contain a copy of this document.
 18    *
 19    * 2. Redistributions in binary form must reproduce the above copyright notice,
 20    * this list of conditions and the following disclaimer in the documentation
 21    * and/or other materials provided with the distribution.
 22    *
 23    * 3. The name "drools" must not be used to endorse or promote products derived
 24    * from this Software without prior written permission of The Werken Company.
 25    * For written permission, please contact bob@werken.com.
 26    *
 27    * 4. Products derived from this Software may not be called "drools" nor may
 28    * "drools" appear in their names without prior written permission of The Werken
 29    * Company. "drools" is a trademark of The Werken Company.
 30    *
 31    * 5. Due credit should be given to The Werken Company. (http://werken.com/)
 32    *
 33    * THIS SOFTWARE IS PROVIDED BY THE WERKEN COMPANY AND CONTRIBUTORS ``AS IS''
 34    * AND ANY EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 35    * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 36    * ARE DISCLAIMED. IN NO EVENT SHALL THE WERKEN COMPANY OR ITS CONTRIBUTORS BE
 37    * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
 38    * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
 39    * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
 40    * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
 41    * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
 42    * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
 43    * POSSIBILITY OF SUCH DAMAGE.
 44    *
 45    */
 46   
 47    /**
 48    *
 49    * @author Mark Proctor
 50    */
 51    public class PrimitiveLongMap
 52    implements
 53    Serializable
 54    {
 55    private final static Object NULL = new Serializable( )
 56    {
 57    };
 58   
 59    private final int indexIntervals;
 60    private final int intervalShifts;
 61    private final int midIntervalPoint;
 62    private final int tableSize;
 63    private final int shifts;
 64    private final int doubleShifts;
 65    private final Page firstPage;
 66    private Page lastPage;
 67    private int lastPageId;
 68    private long maxKey;
 69    private Page[] pageIndex;
 70   
 71  1 public PrimitiveLongMap()
 72    {
 73  1 this( 32,
 74    8 );
 75    }
 76   
 77  0 public PrimitiveLongMap(int tableSize)
 78    {
 79  0 this( tableSize,
 80    8 );
 81    }
 82   
 83  78 public PrimitiveLongMap(int tableSize,
 84    int indexIntervals)
 85    {
 86    // determine number of shifts for intervals
 87  78 int i = 1;
 88  78 int size = 2;
 89  78 while ( size < indexIntervals )
 90    {
 91  149 size <<= 1;
 92  149 ++i;
 93    }
 94  78 this.indexIntervals = size;
 95  78 this.intervalShifts = i;
 96   
 97    // determine number of shifts for tableSize
 98  78 i = 1;
 99  78 size = 2;
 100  78 while ( size < tableSize )
 101    {
 102  298 size <<= 1;
 103  298 ++i;
 104    }
 105  78 this.tableSize = size;
 106  78 this.shifts = i;
 107  78 this.doubleShifts = this.shifts << 1;
 108   
 109    // determine mid point of an interval
 110  78 this.midIntervalPoint = ((this.tableSize << this.shifts) << this.intervalShifts) >> 1;
 111   
 112  78 this.lastPageId = 0;
 113   
 114    // instantiate the first page
 115    // previous sibling of first page is null
 116    // next sibling of last page is null
 117  78 this.firstPage = new Page( null,
 118    this.lastPageId,
 119    this.tableSize );
 120  78 this.maxKey = this.lastPageId + 1 << this.doubleShifts;
 121    // create an index of one
 122  78 pageIndex = new Page[]{this.firstPage};
 123   
 124    // our first page is also our last page
 125  78 this.lastPage = this.firstPage;
 126    }
 127   
 128  1713 public Object put(long key,
 129    Object value)
 130    {
 131  1713 if ( key < 0 )
 132    {
 133  1 throw new IllegalArgumentException( "-ve keys not supported: " + key );
 134    }
 135   
 136    // NULL is a placeholder to show the key exists
 137    // but contains a null value
 138  1712 if ( value == null )
 139    {
 140  0 value = NULL;
 141    }
 142   
 143  1712 Page page = findPage( key );
 144   
 145  1712 Object oldValue = page.put( key,
 146    value );
 147   
 148  1712 return oldValue;
 149    }
 150   
 151  380 public Object remove(long key)
 152    {
 153  380 if ( key > this.maxKey || key < 0 )
 154    {
 155  2 return null;
 156    }
 157   
 158  378 Page page = findPage( key );
 159   
 160  378 Object oldValue = page.put( key,
 161    null );
 162   
 163  378 if ( this.lastPageId != 0 && this.lastPage.isEmpty( ) )
 164    {
 165  3 shrinkPages( this.lastPageId );
 166    }
 167   
 168  378 return oldValue;
 169    }
 170   
 171  85204 public Object get(long key)
 172    {
 173  85204 if ( key > this.maxKey || key < 0 )
 174    {
 175  1 return null;
 176    }
 177   
 178  85203 Object value = findPage( key ).get( key );
 179   
 180    // NULL means the key exists, so return a real null
 181  85203 if ( value == NULL )
 182    {
 183  0 value = null;
 184    }
 185  85203 return value;
 186    }
 187   
 188  24 public Collection values()
 189    {
 190  24 CompositeCollection collection = new CompositeCollection( );
 191  24 Page page = this.firstPage;
 192  24 while ( page != null && page.getPageId( ) <= this.lastPageId )
 193    {
 194  24 collection.addComposited( Arrays.asList( page.getValues( ) ) );
 195  24 page = page.getNextSibling( );
 196    }
 197  24 return collection;
 198    }
 199   
 200  8 public boolean containsKey(long key)
 201    {
 202  2 if ( key < 0 ) return false;
 203   
 204  6 return get( key ) != null;
 205    }
 206   
 207    /**
 208    * Expand index to accomodate given pageId Create empty TopNodes
 209    */
 210  6 public Page expandPages(int toPageId)
 211    {
 212  6 for ( int x = this.lastPageId; x < toPageId; x++ )
 213    {
 214  13 this.lastPage = new Page( this.lastPage,
 215    ++this.lastPageId,
 216    this.tableSize );
 217    // index interval, so expand index
 218  13 if ( this.lastPage.getPageId( ) % this.indexIntervals == 0 )
 219    {
 220  2 int newSize = this.pageIndex.length + 1;
 221  2 resizeIndex( newSize );
 222  2 this.pageIndex[newSize - 1] = this.lastPage;
 223    }
 224    }
 225  6 this.maxKey = (this.lastPageId + 1 << this.doubleShifts) - 1;
 226  6 return this.lastPage;
 227    }
 228   
 229    /**
 230    * Shrink index to accomodate given pageId
 231    */
 232  3 public void shrinkPages(int toPageId)
 233    {
 234  3 for ( int x = this.lastPageId; x >= toPageId; x-- )
 235    {
 236    //last page is on index so shrink index
 237  3 if ( ( this.lastPageId ) % this.indexIntervals == 0 && this.lastPageId != 0 )
 238    {
 239  1 resizeIndex( this.pageIndex.length - 1 );
 240    }
 241   
 242  3 Page page = this.lastPage.getPreviousSibling( );
 243  3 page.setNextSibling( null );
 244  3 this.lastPage.clear( );
 245  3 this.lastPage = page;
 246  3 this.lastPageId = page.getPageId( );
 247   
 248    }
 249    }
 250   
 251  3 public void resizeIndex(int newSize)
 252    {
 253  3 Page[] newIndex = new Page[newSize];
 254  3 System.arraycopy( this.pageIndex,
 255    0,
 256    newIndex,
 257    0,
 258    newSize - 1 );
 259  3 this.pageIndex = newIndex;
 260    }
 261   
 262  87293 private Page findPage(long key)
 263    {
 264    // determine Page
 265  87293 int pageId = (int) key >> this.doubleShifts;
 266  87293 Page page;
 267   
 268    // if pageId is lastNodeId use lastNode reference
 269  87293 if ( pageId == this.lastPageId )
 270    {
 271  87286 page = this.lastPage;
 272    }
 273    // if pageId is zero use first page reference
 274  7 else if ( pageId == 0 )
 275    {
 276  0 page = this.firstPage;
 277    }
 278    // if pageId is greater than lastTopNodeId need to expand
 279  7 else if ( pageId > this.lastPageId )
 280    {
 281  6 page = expandPages( pageId );
 282    }
 283    else
 284    {
 285    // determine offset
 286  1 int offset = pageId >> this.intervalShifts;
 287    // are we before or after the halfway point of an index interval
 288  1 if ( (offset != (this.pageIndex.length - 1)) && ((key - (offset << this.intervalShifts << this.doubleShifts)) > this.midIntervalPoint) )
 289    {
 290    // after so go to next node index and go backwards
 291  1 page = this.pageIndex[offset + 1];
 292  1 while ( page.getPageId( ) != pageId )
 293    {
 294  1 page = page.getPreviousSibling( );
 295    }
 296    }
 297    else
 298    {
 299    // before so go to node index and go forwards
 300  0 page = pageIndex[offset];
 301  0 while ( page.getPageId( ) != pageId )
 302    {
 303  0 page = page.getNextSibling( );
 304    }
 305    }
 306    }
 307   
 308  87293 return page;
 309    }
 310   
 311    private static class Page
 312    implements
 313    Serializable
 314    {
 315    private final int pageSize;
 316    private final int pageId;
 317    private final int shifts;
 318    private final int tableSize;
 319    private Page nextSibling;
 320    private Page previousSibling;
 321    private Object[][] tables;
 322    private int filledSlots;
 323   
 324  91 Page(Page previousSibling,
 325    int pageId,
 326    int tableSize)
 327    {
 328    // determine number of shifts
 329  91 int i = 1;
 330  91 int size = 2;
 331  91 while ( size < tableSize )
 332    {
 333  342 size <<= 1;
 334  342 ++i;
 335    }
 336    // make sure table size is valid
 337  91 this.tableSize = size;
 338  91 this.shifts = i;
 339   
 340    // create bi-directional link
 341  91 this.previousSibling = previousSibling;
 342  91 if ( this.previousSibling != null )
 343    {
 344  13 this.previousSibling.setNextSibling( this );
 345    }
 346  91 this.pageId = pageId;
 347  91 this.pageSize = tableSize << this.shifts;
 348    }
 349   
 350  42 public int getPageId()
 351    {
 352  42 return this.pageId;
 353    }
 354   
 355  16 void setNextSibling(Page nextSibling)
 356    {
 357  16 this.nextSibling = nextSibling;
 358    }
 359   
 360  24 public Page getNextSibling()
 361    {
 362  24 return this.nextSibling;
 363    }
 364   
 365  0 void setPreviousSibling(Page previousSibling)
 366    {
 367  0 this.previousSibling = previousSibling;
 368    }
 369   
 370  4 public Page getPreviousSibling()
 371    {
 372  4 return this.previousSibling;
 373    }
 374   
 375  85203 public Object get(long key)
 376    {
 377  85203 if ( this.tables == null )
 378    {
 379  5 return null;
 380    }
 381    // normalise key
 382  85198 key -= this.pageSize * this.pageId;
 383   
 384    // determine page
 385  85198 int page = (int) key >> this.shifts;
 386   
 387    // determine offset
 388  85198 int offset = page << this.shifts;
 389   
 390    // tables[page][slot]
 391  85198 return this.tables[page][(int) key - offset];
 392    }
 393   
 394  2090 public Object put(long key,
 395    Object newValue)
 396    {
 397  2090 if ( this.tables == null )
 398    {
 399    // initiate tree;
 400  37 this.tables = new Object[this.tableSize][this.tableSize];
 401    }
 402   
 403    // normalise key
 404  2090 key -= this.pageSize * this.pageId;
 405   
 406    // determine page
 407  2090 int table = (int) key >> this.shifts;
 408   
 409    // determine offset
 410  2090 int offset = table << this.shifts;
 411   
 412    // determine slot
 413  2090 int slot = (int) key - offset;
 414   
 415    // get old value
 416  2090 Object oldValue = this.tables[table][slot];
 417  2090 this.tables[table][slot] = newValue;
 418   
 419    // update number of empty cells for TopNode
 420  2090 if ( oldValue == null && newValue != null )
 421    {
 422  1712 this.filledSlots++;
 423    }
 424  378 else if ( oldValue != null && newValue == null )
 425    {
 426  375 this.filledSlots--;
 427    }
 428   
 429    // if this page contains no values then null the array
 430    // to allow it to be garbage collected
 431  2090 if ( this.filledSlots == 0 )
 432    {
 433  10 this.tables = null;
 434    }
 435   
 436  2090 return oldValue;
 437    }
 438   
 439  0 Object[][] getTables()
 440    {
 441  0 return this.tables;
 442    }
 443   
 444  24 Object[] getValues()
 445    {
 446  24 Object[] values = new Object[this.filledSlots];
 447  24 if ( values.length == 0 )
 448    {
 449  3 return values;
 450    }
 451  21 int x = 0;
 452  21 Object value;
 453  21 for ( int i = 0; i < this.tableSize; i++ )
 454    {
 455  672 for ( int j = 0; j < this.tableSize; j++ )
 456    {
 457  21504 value = this.tables[i][j];
 458  21504 if ( value != null )
 459    {
 460    // swap NULL out placeholder
 461  821 if ( value == NULL )
 462    {
 463  0 value = null;
 464    }
 465  821 values[x] = value;
 466  821 x++;
 467    }
 468    }
 469    }
 470  21 return values;
 471    }
 472   
 473  4 public boolean isEmpty()
 474    {
 475  4 return this.filledSlots == 0;
 476    }
 477   
 478  3 void clear()
 479    {
 480  3 this.previousSibling = null;
 481  3 this.nextSibling = null;
 482  3 this.tables = null;
 483    }
 484    }
 485    }