001/*
002 * Licensed to the Apache Software Foundation (ASF) under one or more
003 * contributor license agreements.  See the NOTICE file distributed with
004 * this work for additional information regarding copyright ownership.
005 * The ASF licenses this file to You under the Apache License, Version 2.0
006 * (the "License"); you may not use this file except in compliance with
007 * the License.  You may obtain a copy of the License at
008 *
009 *      http://www.apache.org/licenses/LICENSE-2.0
010 *
011 * Unless required by applicable law or agreed to in writing, software
012 * distributed under the License is distributed on an "AS IS" BASIS,
013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
014 * See the License for the specific language governing permissions and
015 * limitations under the License.
016 */
017package org.apache.commons.math4.util;
018
019import java.io.IOException;
020import java.io.ObjectInputStream;
021import java.io.Serializable;
022import java.lang.reflect.Array;
023import java.util.ConcurrentModificationException;
024import java.util.NoSuchElementException;
025
026import org.apache.commons.math4.Field;
027import org.apache.commons.math4.FieldElement;
028
029/**
030 * Open addressed map from int to FieldElement.
031 * <p>This class provides a dedicated map from integers to FieldElements with a
032 * much smaller memory overhead than standard <code>java.util.Map</code>.</p>
033 * <p>This class is not synchronized. The specialized iterators returned by
034 * {@link #iterator()} are fail-fast: they throw a
035 * <code>ConcurrentModificationException</code> when they detect the map has been
036 * modified during iteration.</p>
037 * @param <T> the type of the field elements
038 * @since 2.0
039 */
040public class OpenIntToFieldHashMap<T extends FieldElement<T>> implements Serializable {
041
042    /** Status indicator for free table entries. */
043    protected static final byte FREE    = 0;
044
045    /** Status indicator for full table entries. */
046    protected static final byte FULL    = 1;
047
048    /** Status indicator for removed table entries. */
049    protected static final byte REMOVED = 2;
050
051    /** Serializable version identifier. */
052    private static final long serialVersionUID = -9179080286849120720L;
053
054    /** Load factor for the map. */
055    private static final float LOAD_FACTOR = 0.5f;
056
057    /** Default starting size.
058     * <p>This must be a power of two for bit mask to work properly. </p>
059     */
060    private static final int DEFAULT_EXPECTED_SIZE = 16;
061
062    /** Multiplier for size growth when map fills up.
063     * <p>This must be a power of two for bit mask to work properly. </p>
064     */
065    private static final int RESIZE_MULTIPLIER = 2;
066
067    /** Number of bits to perturb the index when probing for collision resolution. */
068    private static final int PERTURB_SHIFT = 5;
069
070    /** Field to which the elements belong. */
071    private final Field<T> field;
072
073    /** Keys table. */
074    private int[] keys;
075
076    /** Values table. */
077    private T[] values;
078
079    /** States table. */
080    private byte[] states;
081
082    /** Return value for missing entries. */
083    private final T missingEntries;
084
085    /** Current size of the map. */
086    private int size;
087
088    /** Bit mask for hash values. */
089    private int mask;
090
091    /** Modifications count. */
092    private transient int count;
093
094    /**
095     * Build an empty map with default size and using zero for missing entries.
096     * @param field field to which the elements belong
097     */
098    public OpenIntToFieldHashMap(final Field<T>field) {
099        this(field, DEFAULT_EXPECTED_SIZE, field.getZero());
100    }
101
102    /**
103     * Build an empty map with default size
104     * @param field field to which the elements belong
105     * @param missingEntries value to return when a missing entry is fetched
106     */
107    public OpenIntToFieldHashMap(final Field<T>field, final T missingEntries) {
108        this(field,DEFAULT_EXPECTED_SIZE, missingEntries);
109    }
110
111    /**
112     * Build an empty map with specified size and using zero for missing entries.
113     * @param field field to which the elements belong
114     * @param expectedSize expected number of elements in the map
115     */
116    public OpenIntToFieldHashMap(final Field<T> field,final int expectedSize) {
117        this(field,expectedSize, field.getZero());
118    }
119
120    /**
121     * Build an empty map with specified size.
122     * @param field field to which the elements belong
123     * @param expectedSize expected number of elements in the map
124     * @param missingEntries value to return when a missing entry is fetched
125     */
126    public OpenIntToFieldHashMap(final Field<T> field,final int expectedSize,
127                                  final T missingEntries) {
128        this.field = field;
129        final int capacity = computeCapacity(expectedSize);
130        keys   = new int[capacity];
131        values = buildArray(capacity);
132        states = new byte[capacity];
133        this.missingEntries = missingEntries;
134        mask   = capacity - 1;
135    }
136
137    /**
138     * Copy constructor.
139     * @param source map to copy
140     */
141    public OpenIntToFieldHashMap(final OpenIntToFieldHashMap<T> source) {
142        field = source.field;
143        final int length = source.keys.length;
144        keys = new int[length];
145        System.arraycopy(source.keys, 0, keys, 0, length);
146        values = buildArray(length);
147        System.arraycopy(source.values, 0, values, 0, length);
148        states = new byte[length];
149        System.arraycopy(source.states, 0, states, 0, length);
150        missingEntries = source.missingEntries;
151        size  = source.size;
152        mask  = source.mask;
153        count = source.count;
154    }
155
156    /**
157     * Compute the capacity needed for a given size.
158     * @param expectedSize expected size of the map
159     * @return capacity to use for the specified size
160     */
161    private static int computeCapacity(final int expectedSize) {
162        if (expectedSize == 0) {
163            return 1;
164        }
165        final int capacity   = (int) FastMath.ceil(expectedSize / LOAD_FACTOR);
166        final int powerOfTwo = Integer.highestOneBit(capacity);
167        if (powerOfTwo == capacity) {
168            return capacity;
169        }
170        return nextPowerOfTwo(capacity);
171    }
172
173    /**
174     * Find the smallest power of two greater than the input value
175     * @param i input value
176     * @return smallest power of two greater than the input value
177     */
178    private static int nextPowerOfTwo(final int i) {
179        return Integer.highestOneBit(i) << 1;
180    }
181
182    /**
183     * Get the stored value associated with the given key
184     * @param key key associated with the data
185     * @return data associated with the key
186     */
187    public T get(final int key) {
188
189        final int hash  = hashOf(key);
190        int index = hash & mask;
191        if (containsKey(key, index)) {
192            return values[index];
193        }
194
195        if (states[index] == FREE) {
196            return missingEntries;
197        }
198
199        int j = index;
200        for (int perturb = perturb(hash); states[index] != FREE; perturb >>= PERTURB_SHIFT) {
201            j = probe(perturb, j);
202            index = j & mask;
203            if (containsKey(key, index)) {
204                return values[index];
205            }
206        }
207
208        return missingEntries;
209
210    }
211
212    /**
213     * Check if a value is associated with a key.
214     * @param key key to check
215     * @return true if a value is associated with key
216     */
217    public boolean containsKey(final int key) {
218
219        final int hash  = hashOf(key);
220        int index = hash & mask;
221        if (containsKey(key, index)) {
222            return true;
223        }
224
225        if (states[index] == FREE) {
226            return false;
227        }
228
229        int j = index;
230        for (int perturb = perturb(hash); 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        int j = index;
374        for (int perturb = perturb(hash); states[index] != FREE; perturb >>= PERTURB_SHIFT) {
375            j = probe(perturb, j);
376            index = j & mask;
377            if (containsKey(key, index)) {
378                return doRemove(index);
379            }
380        }
381
382        return missingEntries;
383
384    }
385
386    /**
387     * Check if the tables contain an element associated with specified key
388     * at specified index.
389     * @param key key to check
390     * @param index index to check
391     * @return true if an element is associated with key at index
392     */
393    private boolean containsKey(final int key, final int index) {
394        return (key != 0 || states[index] == FULL) && keys[index] == key;
395    }
396
397    /**
398     * Remove an element at specified index.
399     * @param index index of the element to remove
400     * @return removed value
401     */
402    private T doRemove(int index) {
403        keys[index]   = 0;
404        states[index] = REMOVED;
405        final T previous = values[index];
406        values[index] = missingEntries;
407        --size;
408        ++count;
409        return previous;
410    }
411
412    /**
413     * Put a value associated with a key in the map.
414     * @param key key to which value is associated
415     * @param value value to put in the map
416     * @return previous value associated with the key
417     */
418    public T put(final int key, final T value) {
419        int index = findInsertionIndex(key);
420        T previous = missingEntries;
421        boolean newMapping = true;
422        if (index < 0) {
423            index = changeIndexSign(index);
424            previous = values[index];
425            newMapping = false;
426        }
427        keys[index]   = key;
428        states[index] = FULL;
429        values[index] = value;
430        if (newMapping) {
431            ++size;
432            if (shouldGrowTable()) {
433                growTable();
434            }
435            ++count;
436        }
437        return previous;
438
439    }
440
441    /**
442     * Grow the tables.
443     */
444    private void growTable() {
445
446        final int oldLength      = states.length;
447        final int[] oldKeys      = keys;
448        final T[] oldValues = values;
449        final byte[] oldStates   = states;
450
451        final int newLength = RESIZE_MULTIPLIER * oldLength;
452        final int[] newKeys = new int[newLength];
453        final T[] newValues = buildArray(newLength);
454        final byte[] newStates = new byte[newLength];
455        final int newMask = newLength - 1;
456        for (int i = 0; i < oldLength; ++i) {
457            if (oldStates[i] == FULL) {
458                final int key = oldKeys[i];
459                final int index = findInsertionIndex(newKeys, newStates, key, newMask);
460                newKeys[index]   = key;
461                newValues[index] = oldValues[i];
462                newStates[index] = FULL;
463            }
464        }
465
466        mask   = newMask;
467        keys   = newKeys;
468        values = newValues;
469        states = newStates;
470
471    }
472
473    /**
474     * Check if tables should grow due to increased size.
475     * @return true if  tables should grow
476     */
477    private boolean shouldGrowTable() {
478        return size > (mask + 1) * LOAD_FACTOR;
479    }
480
481    /**
482     * Compute the hash value of a key
483     * @param key key to hash
484     * @return hash value of the key
485     */
486    private static int hashOf(final int key) {
487        final int h = key ^ ((key >>> 20) ^ (key >>> 12));
488        return h ^ (h >>> 7) ^ (h >>> 4);
489    }
490
491
492    /** Iterator class for the map. */
493    public class Iterator {
494
495        /** Reference modification count. */
496        private final int referenceCount;
497
498        /** Index of current element. */
499        private int current;
500
501        /** Index of next element. */
502        private int next;
503
504        /**
505         * Simple constructor.
506         */
507        private Iterator() {
508
509            // preserve the modification count of the map to detect concurrent modifications later
510            referenceCount = count;
511
512            // initialize current index
513            next = -1;
514            try {
515                advance();
516            } catch (NoSuchElementException nsee) { // NOPMD
517                // ignored
518            }
519
520        }
521
522        /**
523         * Check if there is a next element in the map.
524         * @return true if there is a next element
525         */
526        public boolean hasNext() {
527            return next >= 0;
528        }
529
530        /**
531         * Get the key of current entry.
532         * @return key of current entry
533         * @exception ConcurrentModificationException if the map is modified during iteration
534         * @exception NoSuchElementException if there is no element left in the map
535         */
536        public int key()
537            throws ConcurrentModificationException, NoSuchElementException {
538            if (referenceCount != count) {
539                throw new ConcurrentModificationException();
540            }
541            if (current < 0) {
542                throw new NoSuchElementException();
543            }
544            return keys[current];
545        }
546
547        /**
548         * Get the value of current entry.
549         * @return value of current entry
550         * @exception ConcurrentModificationException if the map is modified during iteration
551         * @exception NoSuchElementException if there is no element left in the map
552         */
553        public T value()
554            throws ConcurrentModificationException, NoSuchElementException {
555            if (referenceCount != count) {
556                throw new ConcurrentModificationException();
557            }
558            if (current < 0) {
559                throw new NoSuchElementException();
560            }
561            return values[current];
562        }
563
564        /**
565         * Advance iterator one step further.
566         * @exception ConcurrentModificationException if the map is modified during iteration
567         * @exception NoSuchElementException if there is no element left in the map
568         */
569        public void advance()
570            throws ConcurrentModificationException, NoSuchElementException {
571
572            if (referenceCount != count) {
573                throw new ConcurrentModificationException();
574            }
575
576            // advance on step
577            current = next;
578
579            // prepare next step
580            try {
581                while (states[++next] != FULL) { // NOPMD
582                    // nothing to do
583                }
584            } catch (ArrayIndexOutOfBoundsException e) {
585                next = -2;
586                if (current < 0) {
587                    throw new NoSuchElementException();
588                }
589            }
590
591        }
592
593    }
594
595    /**
596     * Read a serialized object.
597     * @param stream input stream
598     * @throws IOException if object cannot be read
599     * @throws ClassNotFoundException if the class corresponding
600     * to the serialized object cannot be found
601     */
602    private void readObject(final ObjectInputStream stream)
603        throws IOException, ClassNotFoundException {
604        stream.defaultReadObject();
605        count = 0;
606    }
607
608    /** Build an array of elements.
609     * @param length size of the array to build
610     * @return a new array
611     */
612    @SuppressWarnings("unchecked") // field is of type T
613    private T[] buildArray(final int length) {
614        return (T[]) Array.newInstance(field.getRuntimeClass(), length);
615    }
616
617}