Coverage Report

Coverage Report - jaggregate.internal.HashingContainer

Classes in this File

Line Coverage

Branch Coverage

Complexity

HashingContainer

100%

84/84

100%

15/15

HashingContainer$Node

100%

6/6

N/A

 /*
  Copyright 2004-2008 Paul R. Holser, Jr.  All rights reserved.
  Licensed under the Academic Free License version 3.0
  */
 
 package jaggregate.internal;
 
 import jaggregate.Pair;
 import jaggregate.UnaryFunctor;
 import static jaggregate.internal.Casting.*;
 
 /**
  * A hash table, used internally for hashing containers such as
  * {@link jaggregate.Dictionary}.
  *
  * @param <K> the type of keys in the container
  * @param <V> the type of values in the container
  * @author <a href="mailto:pholser@alumni.rice.edu">Paul Holser</a>
  * @version $Id: HashingContainer.java,v 1.7 2008/05/12 23:49:08 pholser Exp $
  */
 public class HashingContainer<K, V> {
     private static final int DEFAULT_INITIAL_CAPACITY = 16;
     private static final double DEFAULT_LOAD_FACTOR = 0.75;
 
     private Object[] buckets;
     private int numberOfElements;
     private final EquivalenceTester equivalenceTester;
 
     /**
      * Creates a hashing container which uses the given strategy for detecting
      * equivalent keys, and has the default initial capacity.
      *
      * @param equivalenceTester the key equivalence strategy
      */
     public HashingContainer( EquivalenceTester equivalenceTester ) {
         this( DEFAULT_INITIAL_CAPACITY, equivalenceTester );
     }
 
     /**
      * Creates a hashing container which uses the given strategy for detecting
      * equivalent keys, and has the given initial capacity.
      *
      * @param capacity the initial capacity
      * @param equivalenceTester the key equivalence strategy
      */
     public HashingContainer( int capacity, EquivalenceTester equivalenceTester ) {
         this.equivalenceTester = equivalenceTester;
         buckets = new Object[ capacity ];
         numberOfElements = 0;
     }
 
     /**
      * Inserts the given value into this container at the given key.
      *
      * @param key the key to add
      * @param value the value to associate with {@code key}
      * @return the previous value associated with {@code key}, or {@code null} if there
      * was no previous association
      */
     public V put( K key, V value ) {
         int hashIndex = hash( key );
         Node<K, V> hashed = cast( buckets[ hashIndex ] );
 
         if ( hashed == null ) {
             buckets[ hashIndex ] = new Node<K, V>( key, value, null );
             ++numberOfElements;
             rehash();
             return null;
         }
 
         while ( hashed.nextNode != null && !areEqual( key, hashed.key() ) )
             hashed = hashed.nextNode;
 
         if ( areEqual( key, hashed.key() ) ) {
             V oldValue = hashed.value();
             hashed.pair.setValue( value );
             return oldValue;
         }
         else {
             hashed.nextNode = new Node<K, V>( key, value, null );
             ++numberOfElements;
             rehash();
             return null;
         }
     }
 
     /**
      * Gives the value in this container associated with the given key.
      *
      * @param key the key to look up
      * @return the value associated with {@code key}, or {@code null} if there is no
      * such association
      */
     public V get( K key ) {
         int hashIndex = hash( key );
         Node<K, V> hashed = cast( buckets[ hashIndex ] );
 
         while ( hashed != null && !areEqual( key, hashed.key() ) )
             hashed = hashed.nextNode;
 
         return hashed == null ? null : hashed.value();
     }
 
     /**
      * Removes the given key and its associated value from this container.
      *
      * @param key the key to remove
      * @return the value that was associated with {@code key}, or {@code null} if there
      * was no such association
      */
     public V remove( K key ) {
         int hashIndex = hash( key );
         Node<K, V> hashed = cast( buckets[ hashIndex ] );
         Node<K, V> current = hashed;
         Node<K, V> next;
 
         for ( ; current != null; hashed = current, current = next ) {
             next = current.nextNode;
 
             if ( areEqual( key, current.key() ) ) {
                 --numberOfElements;
 
                 if ( current == hashed )
                     buckets[ hashIndex ] = next;
                 else
                     hashed.nextNode = next;
 
                 return current.value();
             }
         }
 
         return null;
     }
 
     /**
      * Tells whether the given key is present in this container.
      *
      * @param key the key to look up
      * @return {@code true} if {@code key} is present in this container
      */
     public boolean hasKey( K key ) {
         int hashIndex = hash( key );
 
         for ( Node<K, V> hashed = cast( buckets[ hashIndex ] );
             hashed != null;
             hashed = hashed.nextNode ) {
 
             if ( areEqual( key, hashed.key() ) )
                 return true;
         }
 
         return false;
     }
 
     /**
      * Gives the number of keys in this container.
      *
      * @return the number of keys in this container
      */
     public int size() {
         return numberOfElements;
     }
 
     /**
      * Gives the internal capacity of this container.
      *
      * @return the internal capacity of this container
      */
     public int capacity() {
         return buckets.length;
     }
 
     /**
      * Performs the given operation for each key-value pair in this container.
      *
      * @param operation the operation to perform
      */
     public void forEachDo( UnaryFunctor<? super Pair<K, V>, ?> operation ) {
         for ( Object each : buckets )
             doForBucket( operation, each );
     }
 
     private void doForBucket( UnaryFunctor<? super Pair<K, V>, ?> operation,
         Object bucket ) {
 
         for ( Node<K, V> node = cast( bucket );
             node != null;
             node = node.nextNode ) {
 
             operation.evaluate( node.pair );
         }
     }
 
     /**
      * Tells whether this container would treat the two given objects as equivalent.
      *
      * @param first first object to compare
      * @param second second object to compare
      * @return {@code true} if this container would treat the two objects as
      * equivalent
      */
     public boolean areEqual( Object first, Object second ) {
         return equivalenceTester.areEqual( first, second );
     }
 
     /**
      * Causes the elements in this container to be rehashed.
      */
     public void rehash() {
         if ( size() >= (int) ( buckets.length * DEFAULT_LOAD_FACTOR ) ) {
             Object[] oldTable = buckets;
             buckets = new Object[ 2 * buckets.length ];
             numberOfElements = 0;
 
             for ( Object each : oldTable )
                 repopulateBucket( each );
         }
     }
 
     private void repopulateBucket( Object bucket ) {
         for ( Node<K, V> node = cast( bucket ); node != null; node = node.nextNode )
             put( node.key(), node.value() );
     }
 
     /**
      * <a href="http://www.concentric.net/~Ttwang/tech/inthash.htm">Thomas Wang's 32-bit
      * mix function</a>.
      */
     private int hash( K key ) {
         int[] perturbations = { 15, 10, 3, 6, 11, 16 };
 
         int hashValue = equivalenceTester.hashCode( key );
         int index = 0;
         hashValue += ~( hashValue << perturbations[ index ] );
         ++index;
         hashValue ^= hashValue >>> perturbations[ index ];
         ++index;
         hashValue += hashValue << perturbations[ index ];
         ++index;
         hashValue ^= hashValue >>> perturbations[ index ];
         ++index;
         hashValue += ~( hashValue << perturbations[ index ] );
         ++index;
         hashValue ^= hashValue >>> perturbations[ index ];
 
         return hashValue & ( buckets.length - 1 );
     }
 
     /**
      * @author <a href="mailto:pholser@alumni.rice.edu">Paul Holser</a>
      * @version $Id: HashingContainer.java,v 1.7 2008/05/12 23:49:08 pholser Exp $
      */
     public static class Node<K, V> {
         public final MutablePair<K, V> pair;
         public Node<K, V> nextNode;
 
         Node( K key, V value, Node<K, V> nextNode ) {
             this.nextNode = nextNode;
             pair = new MutablePair<K, V>( key, value );
         }
 
         K key() {
             return pair.key();
         }
 
         V value() {
             return pair.value();
         }
     }
 }

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		}