Coverage Report - jaggregate.internal.HashingContainer
 
Classes in this File Line Coverage Branch Coverage Complexity
HashingContainer
100%
84/84
100%
15/15
0
HashingContainer$Node
100%
6/6
N/A
0
 
 1  
 /*
 2  
  Copyright 2004-2008 Paul R. Holser, Jr.  All rights reserved.
 3  
  Licensed under the Academic Free License version 3.0
 4  
  */
 5  
 
 6  
 package jaggregate.internal;
 7  
 
 8  
 import jaggregate.Pair;
 9  
 import jaggregate.UnaryFunctor;
 10  
 import static jaggregate.internal.Casting.*;
 11  
 
 12  
 /**
 13  
  * A hash table, used internally for hashing containers such as
 14  
  * {@link jaggregate.Dictionary}.
 15  
  *
 16  
  * @param <K> the type of keys in the container
 17  
  * @param <V> the type of values in the container
 18  
  * @author <a href="mailto:pholser@alumni.rice.edu">Paul Holser</a>
 19  
  * @version $Id: HashingContainer.java,v 1.7 2008/05/12 23:49:08 pholser Exp $
 20  
  */
 21  
 public class HashingContainer<K, V> {
 22  
     private static final int DEFAULT_INITIAL_CAPACITY = 16;
 23  
     private static final double DEFAULT_LOAD_FACTOR = 0.75;
 24  
 
 25  
     private Object[] buckets;
 26  
     private int numberOfElements;
 27  
     private final EquivalenceTester equivalenceTester;
 28  
 
 29  
     /**
 30  
      * Creates a hashing container which uses the given strategy for detecting
 31  
      * equivalent keys, and has the default initial capacity.
 32  
      *
 33  
      * @param equivalenceTester the key equivalence strategy
 34  
      */
 35  
     public HashingContainer( EquivalenceTester equivalenceTester ) {
 36  2329
         this( DEFAULT_INITIAL_CAPACITY, equivalenceTester );
 37  2329
     }
 38  
 
 39  
     /**
 40  
      * Creates a hashing container which uses the given strategy for detecting
 41  
      * equivalent keys, and has the given initial capacity.
 42  
      *
 43  
      * @param capacity the initial capacity
 44  
      * @param equivalenceTester the key equivalence strategy
 45  
      */
 46  2335
     public HashingContainer( int capacity, EquivalenceTester equivalenceTester ) {
 47  2335
         this.equivalenceTester = equivalenceTester;
 48  2335
         buckets = new Object[ capacity ];
 49  2335
         numberOfElements = 0;
 50  2335
     }
 51  
 
 52  
     /**
 53  
      * Inserts the given value into this container at the given key.
 54  
      *
 55  
      * @param key the key to add
 56  
      * @param value the value to associate with {@code key}
 57  
      * @return the previous value associated with {@code key}, or {@code null} if there
 58  
      * was no previous association
 59  
      */
 60  
     public V put( K key, V value ) {
 61  9149
         int hashIndex = hash( key );
 62  9149
         Node<K, V> hashed = cast( buckets[ hashIndex ] );
 63  
 
 64  9149
         if ( hashed == null ) {
 65  7453
             buckets[ hashIndex ] = new Node<K, V>( key, value, null );
 66  7453
             ++numberOfElements;
 67  7453
             rehash();
 68  7453
             return null;
 69  
         }
 70  
 
 71  1879
         while ( hashed.nextNode != null && !areEqual( key, hashed.key() ) )
 72  183
             hashed = hashed.nextNode;
 73  
 
 74  1696
         if ( areEqual( key, hashed.key() ) ) {
 75  616
             V oldValue = hashed.value();
 76  616
             hashed.pair.setValue( value );
 77  616
             return oldValue;
 78  
         }
 79  
         else {
 80  1080
             hashed.nextNode = new Node<K, V>( key, value, null );
 81  1080
             ++numberOfElements;
 82  1080
             rehash();
 83  1080
             return null;
 84  
         }
 85  
     }
 86  
 
 87  
     /**
 88  
      * Gives the value in this container associated with the given key.
 89  
      *
 90  
      * @param key the key to look up
 91  
      * @return the value associated with {@code key}, or {@code null} if there is no
 92  
      * such association
 93  
      */
 94  
     public V get( K key ) {
 95  6574
         int hashIndex = hash( key );
 96  6574
         Node<K, V> hashed = cast( buckets[ hashIndex ] );
 97  
 
 98  6864
         while ( hashed != null && !areEqual( key, hashed.key() ) )
 99  290
             hashed = hashed.nextNode;
 100  
 
 101  6574
         return hashed == null ? null : hashed.value();
 102  
     }
 103  
 
 104  
     /**
 105  
      * Removes the given key and its associated value from this container.
 106  
      *
 107  
      * @param key the key to remove
 108  
      * @return the value that was associated with {@code key}, or {@code null} if there
 109  
      * was no such association
 110  
      */
 111  
     public V remove( K key ) {
 112  1403
         int hashIndex = hash( key );
 113  1403
         Node<K, V> hashed = cast( buckets[ hashIndex ] );
 114  1403
         Node<K, V> current = hashed;
 115  
         Node<K, V> next;
 116  
 
 117  1699
         for ( ; current != null; hashed = current, current = next ) {
 118  1466
             next = current.nextNode;
 119  
 
 120  1466
             if ( areEqual( key, current.key() ) ) {
 121  1318
                 --numberOfElements;
 122  
 
 123  1318
                 if ( current == hashed )
 124  1183
                     buckets[ hashIndex ] = next;
 125  
                 else
 126  135
                     hashed.nextNode = next;
 127  
 
 128  1318
                 return current.value();
 129  
             }
 130  
         }
 131  
 
 132  85
         return null;
 133  
     }
 134  
 
 135  
     /**
 136  
      * Tells whether the given key is present in this container.
 137  
      *
 138  
      * @param key the key to look up
 139  
      * @return {@code true} if {@code key} is present in this container
 140  
      */
 141  
     public boolean hasKey( K key ) {
 142  2827
         int hashIndex = hash( key );
 143  
 
 144  2827
         for ( Node<K, V> hashed = cast( buckets[ hashIndex ] );
 145  3063
             hashed != null;
 146  236
             hashed = hashed.nextNode ) {
 147  
 
 148  2426
             if ( areEqual( key, hashed.key() ) )
 149  2190
                 return true;
 150  
         }
 151  
 
 152  637
         return false;
 153  
     }
 154  
 
 155  
     /**
 156  
      * Gives the number of keys in this container.
 157  
      *
 158  
      * @return the number of keys in this container
 159  
      */
 160  
     public int size() {
 161  12116
         return numberOfElements;
 162  
     }
 163  
 
 164  
     /**
 165  
      * Gives the internal capacity of this container.
 166  
      *
 167  
      * @return the internal capacity of this container
 168  
      */
 169  
     public int capacity() {
 170  6
         return buckets.length;
 171  
     }
 172  
 
 173  
     /**
 174  
      * Performs the given operation for each key-value pair in this container.
 175  
      *
 176  
      * @param operation the operation to perform
 177  
      */
 178  
     public void forEachDo( UnaryFunctor<? super Pair<K, V>, ?> operation ) {
 179  43588
         for ( Object each : buckets )
 180  41155
             doForBucket( operation, each );
 181  2433
     }
 182  
 
 183  
     private void doForBucket( UnaryFunctor<? super Pair<K, V>, ?> operation,
 184  
         Object bucket ) {
 185  
 
 186  41155
         for ( Node<K, V> node = cast( bucket );
 187  49043
             node != null;
 188  7888
             node = node.nextNode ) {
 189  
 
 190  8175
             operation.evaluate( node.pair );
 191  
         }
 192  40868
     }
 193  
 
 194  
     /**
 195  
      * Tells whether this container would treat the two given objects as equivalent.
 196  
      *
 197  
      * @param first first object to compare
 198  
      * @param second second object to compare
 199  
      * @return {@code true} if this container would treat the two objects as
 200  
      * equivalent
 201  
      */
 202  
     public boolean areEqual( Object first, Object second ) {
 203  12981
         return equivalenceTester.areEqual( first, second );
 204  
     }
 205  
 
 206  
     /**
 207  
      * Causes the elements in this container to be rehashed.
 208  
      */
 209  
     public void rehash() {
 210  8544
         if ( size() >= (int) ( buckets.length * DEFAULT_LOAD_FACTOR ) ) {
 211  24
             Object[] oldTable = buckets;
 212  24
             buckets = new Object[ 2 * buckets.length ];
 213  24
             numberOfElements = 0;
 214  
 
 215  1464
             for ( Object each : oldTable )
 216  1440
                 repopulateBucket( each );
 217  
         }
 218  8544
     }
 219  
 
 220  
     private void repopulateBucket( Object bucket ) {
 221  2520
         for ( Node<K, V> node = cast( bucket ); node != null; node = node.nextNode )
 222  1080
             put( node.key(), node.value() );
 223  1440
     }
 224  
 
 225  
     /**
 226  
      * <a href="http://www.concentric.net/~Ttwang/tech/inthash.htm">Thomas Wang's 32-bit
 227  
      * mix function</a>.
 228  
      */
 229  
     private int hash( K key ) {
 230  19953
         int[] perturbations = { 15, 10, 3, 6, 11, 16 };
 231  
 
 232  19953
         int hashValue = equivalenceTester.hashCode( key );
 233  19953
         int index = 0;
 234  19953
         hashValue += ~( hashValue << perturbations[ index ] );
 235  19953
         ++index;
 236  19953
         hashValue ^= hashValue >>> perturbations[ index ];
 237  19953
         ++index;
 238  19953
         hashValue += hashValue << perturbations[ index ];
 239  19953
         ++index;
 240  19953
         hashValue ^= hashValue >>> perturbations[ index ];
 241  19953
         ++index;
 242  19953
         hashValue += ~( hashValue << perturbations[ index ] );
 243  19953
         ++index;
 244  19953
         hashValue ^= hashValue >>> perturbations[ index ];
 245  
 
 246  19953
         return hashValue & ( buckets.length - 1 );
 247  
     }
 248  
 
 249  
     /**
 250  
      * @author <a href="mailto:pholser@alumni.rice.edu">Paul Holser</a>
 251  
      * @version $Id: HashingContainer.java,v 1.7 2008/05/12 23:49:08 pholser Exp $
 252  
      */
 253  
     public static class Node<K, V> {
 254  
         public final MutablePair<K, V> pair;
 255  
         public Node<K, V> nextNode;
 256  
 
 257  8533
         Node( K key, V value, Node<K, V> nextNode ) {
 258  8533
             this.nextNode = nextNode;
 259  8533
             pair = new MutablePair<K, V>( key, value );
 260  8533
         }
 261  
 
 262  
         K key() {
 263  11605
             return pair.key();
 264  
         }
 265  
 
 266  
         V value() {
 267  7455
             return pair.value();
 268  
         }
 269  
     }
 270  
 }