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