View Javadoc

1   /*
2    * Licensed to the Apache Software Foundation (ASF) under one or more
3    * contributor license agreements.  See the NOTICE file distributed with
4    * this work for additional information regarding copyright ownership.
5    * The ASF licenses this file to You under the Apache License, Version 2.0
6    * (the "License"); you may not use this file except in compliance with
7    * the License.  You may obtain a copy of 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,
13   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14   * See the License for the specific language governing permissions and
15   * limitations under the License.
16   */
17  package org.apache.commons.math.util;
18  
19  import java.io.IOException;
20  import java.io.ObjectInputStream;
21  import java.io.Serializable;
22  import java.lang.reflect.Array;
23  import java.util.ConcurrentModificationException;
24  import java.util.NoSuchElementException;
25  
26  import org.apache.commons.math.Field;
27  import org.apache.commons.math.FieldElement;
28  import org.apache.commons.math.MathRuntimeException;
29  
30  /**
31   * Open addressed map from int to FieldElement.
32   * <p>This class provides a dedicated map from integers to FieldElements with a
33   * much smaller memory overhead than standard <code>java.util.Map</code>.</p>
34   * <p>This class is not synchronized. The specialized iterators returned by
35   * {@link #iterator()} are fail-fast: they throw a
36   * <code>ConcurrentModificationException</code> when they detect the map has been
37   * modified during iteration.</p>
38   * @param <T> the type of the field elements
39   * @version $Revision: 799857 $ $Date: 2009-08-01 09:07:12 -0400 (Sat, 01 Aug 2009) $
40   * @since 2.0
41   */
42  public class OpenIntToFieldHashMap<T extends FieldElement<T>> implements Serializable {
43      
44      /** Serializable version identifier. */
45      private static final long serialVersionUID = -9179080286849120720L;
46  
47      /** Load factor for the map. */
48      private static final float LOAD_FACTOR = 0.5f;
49  
50      /** Default starting size.
51       * <p>This must be a power of two for bit mask to work properly. </p>
52       */
53      private static final int DEFAULT_EXPECTED_SIZE = 16;
54  
55      /** Multiplier for size growth when map fills up.
56       * <p>This must be a power of two for bit mask to work properly. </p>
57       */
58      private static final int RESIZE_MULTIPLIER = 2;
59  
60      /** Number of bits to perturb the index when probing for collision resolution. */
61      private static final int PERTURB_SHIFT = 5;
62  
63      /** Status indicator for free table entries. */
64      protected static final byte FREE    = 0;
65  
66      /** Status indicator for full table entries. */
67      protected static final byte FULL    = 1;
68  
69      /** Status indicator for removed table entries. */
70      protected static final byte REMOVED = 2;
71  
72      /** Field to which the elements belong. */
73      private final Field<T> field;
74      
75      /** Keys table. */
76      private int[] keys;
77  
78      /** Values table. */
79      private T[] values;
80  
81      /** States table. */
82      private byte[] states;
83  
84      /** Return value for missing entries. */
85      private final T missingEntries;
86  
87      /** Current size of the map. */
88      private int size;
89  
90      /** Bit mask for hash values. */
91      private int mask;
92  
93      /** Modifications count. */
94      private transient int count;
95  
96      /**
97       * Build an empty map with default size and using zero for missing entries.
98       * @param field field to which the elements belong
99       */
100     public OpenIntToFieldHashMap(final Field<T>field) {
101         this(field, DEFAULT_EXPECTED_SIZE, field.getZero());
102     }
103 
104     /**
105      * Build an empty map with default size
106      * @param field field to which the elements belong
107      * @param missingEntries value to return when a missing entry is fetched
108      */
109     public OpenIntToFieldHashMap(final Field<T>field, final T missingEntries) {
110         this(field,DEFAULT_EXPECTED_SIZE, missingEntries);
111     }
112 
113     /**
114      * Build an empty map with specified size and using zero for missing entries.
115      * @param field field to which the elements belong
116      * @param expectedSize expected number of elements in the map
117      */
118     public OpenIntToFieldHashMap(final Field<T> field,final int expectedSize) {
119         this(field,expectedSize, field.getZero());
120     }
121 
122     /**
123      * Build an empty map with specified size.
124      * @param field field to which the elements belong
125      * @param expectedSize expected number of elements in the map
126      * @param missingEntries value to return when a missing entry is fetched
127      */
128     public OpenIntToFieldHashMap(final Field<T> field,final int expectedSize,
129                                   final T missingEntries) {
130         this.field = field;
131         final int capacity = computeCapacity(expectedSize);
132         keys   = new int[capacity];
133         values = buildArray(capacity);
134         states = new byte[capacity];
135         this.missingEntries = missingEntries;
136         mask   = capacity - 1;
137     }
138 
139     /**
140      * Copy constructor.
141      * @param source map to copy
142      */
143     public OpenIntToFieldHashMap(final OpenIntToFieldHashMap<T> source) {
144         field = source.field;
145         final int length = source.keys.length;
146         keys = new int[length];
147         System.arraycopy(source.keys, 0, keys, 0, length);
148         values = buildArray(length);
149         System.arraycopy(source.values, 0, values, 0, length);
150         states = new byte[length];
151         System.arraycopy(source.states, 0, states, 0, length);
152         missingEntries = source.missingEntries;
153         size  = source.size;
154         mask  = source.mask;
155         count = source.count;
156     }
157 
158     /**
159      * Compute the capacity needed for a given size.
160      * @param expectedSize expected size of the map
161      * @return capacity to use for the specified size
162      */
163     private static int computeCapacity(final int expectedSize) {
164         if (expectedSize == 0) {
165             return 1;
166         }
167         final int capacity   = (int) Math.ceil(expectedSize / LOAD_FACTOR);
168         final int powerOfTwo = Integer.highestOneBit(capacity);
169         if (powerOfTwo == capacity) {
170             return capacity;
171         }
172         return nextPowerOfTwo(capacity);
173     }
174 
175     /**
176      * Find the smallest power of two greater than the input value
177      * @param i input value
178      * @return smallest power of two greater than the input value
179      */
180     private static int nextPowerOfTwo(final int i) {
181         return Integer.highestOneBit(i) << 1;
182     }
183 
184     /**
185      * Get the stored value associated with the given key
186      * @param key key associated with the data
187      * @return data associated with the key
188      */
189     public T get(final int key) {
190 
191         final int hash  = hashOf(key);
192         int index = hash & mask;
193         if (containsKey(key, index)) {
194             return values[index];
195         }
196 
197         if (states[index] == FREE) {
198             return missingEntries;
199         }
200 
201         for (int perturb = perturb(hash), j = index; states[index] != FREE; perturb >>= PERTURB_SHIFT) {
202             j = probe(perturb, j);
203             index = j & mask;
204             if (containsKey(key, index)) {
205                 return values[index];
206             }
207         }
208 
209         return missingEntries;
210 
211     }
212 
213     /**
214      * Check if a value is associated with a key.
215      * @param key key to check
216      * @return true if a value is associated with key
217      */
218     public boolean containsKey(final int key) {
219 
220         final int hash  = hashOf(key);
221         int index = hash & mask;
222         if (containsKey(key, index)) {
223             return true;
224         }
225 
226         if (states[index] == FREE) {
227             return false;
228         }
229 
230         for (int perturb = perturb(hash), j = index; states[index] != FREE; perturb >>= PERTURB_SHIFT) {
231             j = probe(perturb, j);
232             index = j & mask;
233             if (containsKey(key, index)) {
234                 return true;
235             }
236         }
237 
238         return false;
239 
240     }
241 
242     /**
243      * Get an iterator over map elements.
244      * <p>The specialized iterators returned are fail-fast: they throw a
245      * <code>ConcurrentModificationException</code> when they detect the map
246      * has been modified during iteration.</p>
247      * @return iterator over the map elements
248      */
249     public Iterator iterator() {
250         return new Iterator();
251     }
252 
253     /**
254      * Perturb the hash for starting probing.
255      * @param hash initial hash
256      * @return perturbed hash
257      */
258     private static int perturb(final int hash) {
259         return hash & 0x7fffffff;
260     }
261 
262     /**
263      * Find the index at which a key should be inserted
264      * @param key key to lookup
265      * @return index at which key should be inserted
266      */
267     private int findInsertionIndex(final int key) {
268         return findInsertionIndex(keys, states, key, mask);
269     }
270 
271     /**
272      * Find the index at which a key should be inserted
273      * @param keys keys table
274      * @param states states table
275      * @param key key to lookup
276      * @param mask bit mask for hash values
277      * @return index at which key should be inserted
278      */
279     private static int findInsertionIndex(final int[] keys, final byte[] states,
280                                           final int key, final int mask) {
281         final int hash = hashOf(key);
282         int index = hash & mask;
283         if (states[index] == FREE) {
284             return index;
285         } else if (states[index] == FULL && keys[index] == key) {
286             return changeIndexSign(index);
287         }
288 
289         int perturb = perturb(hash);
290         int j = index;
291         if (states[index] == FULL) {
292             while (true) {
293                 j = probe(perturb, j);
294                 index = j & mask;
295                 perturb >>= PERTURB_SHIFT;
296                 
297                 if (states[index] != FULL || keys[index] == key) {
298                     break;
299                 }
300             }
301         }
302 
303         if (states[index] == FREE) {
304             return index;
305         } else if (states[index] == FULL) {
306             // due to the loop exit condition,
307             // if (states[index] == FULL) then keys[index] == key
308             return changeIndexSign(index);
309         }
310 
311         final int firstRemoved = index;
312         while (true) {
313             j = probe(perturb, j);
314             index = j & mask;
315 
316             if (states[index] == FREE) {
317                 return firstRemoved;
318             } else if (states[index] == FULL && keys[index] == key) {
319                 return changeIndexSign(index);
320             }
321 
322             perturb >>= PERTURB_SHIFT;
323 
324         }
325 
326     }
327 
328     /**
329      * Compute next probe for collision resolution
330      * @param perturb perturbed hash
331      * @param j previous probe
332      * @return next probe
333      */
334     private static int probe(final int perturb, final int j) {
335         return (j << 2) + j + perturb + 1;
336     }
337 
338     /**
339      * Change the index sign
340      * @param index initial index
341      * @return changed index
342      */
343     private static int changeIndexSign(final int index) {
344         return -index - 1;
345     }
346 
347     /**
348      * Get the number of elements stored in the map.
349      * @return number of elements stored in the map
350      */
351     public int size() {
352         return size;
353     }
354 
355     
356     /**
357      * Remove the value associated with a key.
358      * @param key key to which the value is associated
359      * @return removed value
360      */
361     public T remove(final int key) {
362 
363         final int hash  = hashOf(key);
364         int index = hash & mask;
365         if (containsKey(key, index)) {
366             return doRemove(index);
367         }
368 
369         if (states[index] == FREE) {
370             return missingEntries;
371         }
372 
373         for (int perturb = perturb(hash), j = index; states[index] != FREE; perturb >>= PERTURB_SHIFT) {
374             j = probe(perturb, j);
375             index = j & mask;
376             if (containsKey(key, index)) {
377                 return doRemove(index);
378             }
379         }
380 
381         return missingEntries;
382 
383     }
384 
385     /**
386      * Check if the tables contain an element associated with specified key
387      * at specified index.
388      * @param key key to check
389      * @param index index to check
390      * @return true if an element is associated with key at index
391      */
392     private boolean containsKey(final int key, final int index) {
393         return (key != 0 || states[index] == FULL) && keys[index] == key;
394     }
395 
396     /**
397      * Remove an element at specified index.
398      * @param index index of the element to remove
399      * @return removed value
400      */
401     private T doRemove(int index) {
402         keys[index]   = 0;
403         states[index] = REMOVED;
404         final T previous = values[index];
405         values[index] = missingEntries;
406         --size;
407         ++count;
408         return previous;
409     }
410 
411     /**
412      * Put a value associated with a key in the map.
413      * @param key key to which value is associated
414      * @param value value to put in the map
415      * @return previous value associated with the key
416      */
417     public T put(final int key, final T value) {
418         int index = findInsertionIndex(key);
419         T previous = missingEntries;
420         boolean newMapping = true;
421         if (index < 0) {
422             index = changeIndexSign(index);
423             previous = values[index];
424             newMapping = false;
425         }
426         keys[index]   = key;
427         states[index] = FULL;
428         values[index] = value;
429         if (newMapping) {
430             ++size;
431             if (shouldGrowTable()) {
432                 growTable();
433             }
434             ++count;
435         }
436         return previous;
437 
438     }
439 
440     /**
441      * Grow the tables.
442      */
443     private void growTable() {
444 
445         final int oldLength      = states.length;
446         final int[] oldKeys      = keys;
447         final T[] oldValues = values;
448         final byte[] oldStates   = states;
449 
450         final int newLength = RESIZE_MULTIPLIER * oldLength;
451         final int[] newKeys = new int[newLength];
452         final T[] newValues = buildArray(newLength);
453         final byte[] newStates = new byte[newLength];
454         final int newMask = newLength - 1;
455         for (int i = 0; i < oldLength; ++i) {
456             if (oldStates[i] == FULL) {
457                 final int key = oldKeys[i];
458                 final int index = findInsertionIndex(newKeys, newStates, key, newMask);
459                 newKeys[index]   = key;
460                 newValues[index] = oldValues[i];
461                 newStates[index] = FULL;
462             }
463         }
464 
465         mask   = newMask;
466         keys   = newKeys;
467         values = newValues;
468         states = newStates;
469 
470     }
471 
472     /**
473      * Check if tables should grow due to increased size.
474      * @return true if  tables should grow
475      */
476     private boolean shouldGrowTable() {
477         return size > (mask + 1) * LOAD_FACTOR;
478     }
479 
480     /**
481      * Compute the hash value of a key
482      * @param key key to hash
483      * @return hash value of the key
484      */
485     private static int hashOf(final int key) {
486         final int h = key ^ ((key >>> 20) ^ (key >>> 12));
487         return h ^ (h >>> 7) ^ (h >>> 4);
488     }
489 
490     
491     /** Iterator class for the map. */
492     public class Iterator {
493 
494         /** Reference modification count. */
495         private final int referenceCount;
496 
497         /** Index of current element. */
498         private int current;
499 
500         /** Index of next element. */
501         private int next;
502 
503         /**
504          * Simple constructor.
505          */
506         private Iterator() {
507 
508             // preserve the modification count of the map to detect concurrent modifications later
509             referenceCount = count;
510 
511             // initialize current index
512             next = -1;
513             try {
514                 advance();
515             } catch (NoSuchElementException nsee) {
516                 // ignored
517             }
518 
519         }
520 
521         /**
522          * Check if there is a next element in the map.
523          * @return true if there is a next element
524          */
525         public boolean hasNext() {
526             return next >= 0;
527         }
528 
529         /**
530          * Get the key of current entry.
531          * @return key of current entry
532          * @exception ConcurrentModificationException if the map is modified during iteration
533          * @exception NoSuchElementException if there is no element left in the map
534          */
535         public int key()
536             throws ConcurrentModificationException, NoSuchElementException {
537             if (referenceCount != count) {
538                 throw MathRuntimeException.createConcurrentModificationException("map has been modified while iterating");
539             }
540             if (current < 0) {
541                 throw MathRuntimeException.createNoSuchElementException("iterator exhausted");
542             }
543             return keys[current];
544         }
545 
546         /**
547          * Get the value of current entry.
548          * @return value of current entry
549          * @exception ConcurrentModificationException if the map is modified during iteration
550          * @exception NoSuchElementException if there is no element left in the map
551          */
552         public T value()
553             throws ConcurrentModificationException, NoSuchElementException {
554             if (referenceCount != count) {
555                 throw MathRuntimeException.createConcurrentModificationException("map has been modified while iterating");
556             }
557             if (current < 0) {
558                 throw MathRuntimeException.createNoSuchElementException("iterator exhausted");
559             }
560             return values[current];
561         }
562 
563         /**
564          * Advance iterator one step further.
565          * @exception ConcurrentModificationException if the map is modified during iteration
566          * @exception NoSuchElementException if there is no element left in the map
567          */
568         public void advance()
569             throws ConcurrentModificationException, NoSuchElementException {
570 
571             if (referenceCount != count) {
572                 throw MathRuntimeException.createConcurrentModificationException("map has been modified while iterating");
573             }
574 
575             // advance on step
576             current = next;
577 
578             // prepare next step
579             try {
580                 while (states[++next] != FULL) {
581                     // nothing to do
582                 }
583             } catch (ArrayIndexOutOfBoundsException e) {
584                 next = -2;
585                 if (current < 0) {
586                     throw MathRuntimeException.createNoSuchElementException("iterator exhausted");
587                 }
588             }
589 
590         }
591 
592     }
593 
594     /**
595      * Read a serialized object.
596      * @param stream input stream
597      * @throws IOException if object cannot be read
598      * @throws ClassNotFoundException if the class corresponding
599      * to the serialized object cannot be found
600      */
601     private void readObject(final ObjectInputStream stream)
602         throws IOException, ClassNotFoundException {
603         stream.defaultReadObject();
604         count = 0;
605     }
606 
607     /** Build an array of elements.
608      * @param length size of the array to build
609      * @return a new array
610      */
611     @SuppressWarnings("unchecked")
612     private T[] buildArray(final int length) {
613         return (T[]) Array.newInstance(field.getZero().getClass(), length);
614     }
615 
616 }