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.math3.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.math3.Field;
027import org.apache.commons.math3.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 * @version $Id: OpenIntToFieldHashMap.java 1421448 2012-12-13 19:45:57Z tn $
039 * @since 2.0
040 */
041public class OpenIntToFieldHashMap<T extends FieldElement<T>> implements Serializable {
042
043    /** Status indicator for free table entries. */
044    protected static final byte FREE    = 0;
045
046    /** Status indicator for full table entries. */
047    protected static final byte FULL    = 1;
048
049    /** Status indicator for removed table entries. */
050    protected static final byte REMOVED = 2;
051
052    /** Serializable version identifier. */
053    private static final long serialVersionUID = -9179080286849120720L;
054
055    /** Load factor for the map. */
056    private static final float LOAD_FACTOR = 0.5f;
057
058    /** Default starting size.
059     * <p>This must be a power of two for bit mask to work properly. </p>
060     */
061    private static final int DEFAULT_EXPECTED_SIZE = 16;
062
063    /** Multiplier for size growth when map fills up.
064     * <p>This must be a power of two for bit mask to work properly. </p>
065     */
066    private static final int RESIZE_MULTIPLIER = 2;
067
068    /** Number of bits to perturb the index when probing for collision resolution. */
069    private static final int PERTURB_SHIFT = 5;
070
071    /** Field to which the elements belong. */
072    private final Field<T> field;
073
074    /** Keys table. */
075    private int[] keys;
076
077    /** Values table. */
078    private T[] values;
079
080    /** States table. */
081    private byte[] states;
082
083    /** Return value for missing entries. */
084    private final T missingEntries;
085
086    /** Current size of the map. */
087    private int size;
088
089    /** Bit mask for hash values. */
090    private int mask;
091
092    /** Modifications count. */
093    private transient int count;
094
095    /**
096     * Build an empty map with default size and using zero for missing entries.
097     * @param field field to which the elements belong
098     */
099    public OpenIntToFieldHashMap(final Field<T>field) {
100        this(field, DEFAULT_EXPECTED_SIZE, field.getZero());
101    }
102
103    /**
104     * Build an empty map with default size
105     * @param field field to which the elements belong
106     * @param missingEntries value to return when a missing entry is fetched
107     */
108    public OpenIntToFieldHashMap(final Field<T>field, final T missingEntries) {
109        this(field,DEFAULT_EXPECTED_SIZE, missingEntries);
110    }
111
112    /**
113     * Build an empty map with specified size and using zero for missing entries.
114     * @param field field to which the elements belong
115     * @param expectedSize expected number of elements in the map
116     */
117    public OpenIntToFieldHashMap(final Field<T> field,final int expectedSize) {
118        this(field,expectedSize, field.getZero());
119    }
120
121    /**
122     * Build an empty map with specified size.
123     * @param field field to which the elements belong
124     * @param expectedSize expected number of elements in the map
125     * @param missingEntries value to return when a missing entry is fetched
126     */
127    public OpenIntToFieldHashMap(final Field<T> field,final int expectedSize,
128                                  final T missingEntries) {
129        this.field = field;
130        final int capacity = computeCapacity(expectedSize);
131        keys   = new int[capacity];
132        values = buildArray(capacity);
133        states = new byte[capacity];
134        this.missingEntries = missingEntries;
135        mask   = capacity - 1;
136    }
137
138    /**
139     * Copy constructor.
140     * @param source map to copy
141     */
142    public OpenIntToFieldHashMap(final OpenIntToFieldHashMap<T> source) {
143        field = source.field;
144        final int length = source.keys.length;
145        keys = new int[length];
146        System.arraycopy(source.keys, 0, keys, 0, length);
147        values = buildArray(length);
148        System.arraycopy(source.values, 0, values, 0, length);
149        states = new byte[length];
150        System.arraycopy(source.states, 0, states, 0, length);
151        missingEntries = source.missingEntries;
152        size  = source.size;
153        mask  = source.mask;
154        count = source.count;
155    }
156
157    /**
158     * Compute the capacity needed for a given size.
159     * @param expectedSize expected size of the map
160     * @return capacity to use for the specified size
161     */
162    private static int computeCapacity(final int expectedSize) {
163        if (expectedSize == 0) {
164            return 1;
165        }
166        final int capacity   = (int) FastMath.ceil(expectedSize / LOAD_FACTOR);
167        final int powerOfTwo = Integer.highestOneBit(capacity);
168        if (powerOfTwo == capacity) {
169            return capacity;
170        }
171        return nextPowerOfTwo(capacity);
172    }
173
174    /**
175     * Find the smallest power of two greater than the input value
176     * @param i input value
177     * @return smallest power of two greater than the input value
178     */
179    private static int nextPowerOfTwo(final int i) {
180        return Integer.highestOneBit(i) << 1;
181    }
182
183    /**
184     * Get the stored value associated with the given key
185     * @param key key associated with the data
186     * @return data associated with the key
187     */
188    public T get(final int key) {
189
190        final int hash  = hashOf(key);
191        int index = hash & mask;
192        if (containsKey(key, index)) {
193            return values[index];
194        }
195
196        if (states[index] == FREE) {
197            return missingEntries;
198        }
199
200        int j = index;
201        for (int perturb = perturb(hash); 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        int j = index;
231        for (int perturb = perturb(hash); states[index] != FREE; perturb >>= PERTURB_SHIFT) {
232            j = probe(perturb, j);
233            index = j & mask;
234            if (containsKey(key, index)) {
235                return true;
236            }
237        }
238
239        return false;
240
241    }
242
243    /**
244     * Get an iterator over map elements.
245     * <p>The specialized iterators returned are fail-fast: they throw a
246     * <code>ConcurrentModificationException</code> when they detect the map
247     * has been modified during iteration.</p>
248     * @return iterator over the map elements
249     */
250    public Iterator iterator() {
251        return new Iterator();
252    }
253
254    /**
255     * Perturb the hash for starting probing.
256     * @param hash initial hash
257     * @return perturbed hash
258     */
259    private static int perturb(final int hash) {
260        return hash & 0x7fffffff;
261    }
262
263    /**
264     * Find the index at which a key should be inserted
265     * @param key key to lookup
266     * @return index at which key should be inserted
267     */
268    private int findInsertionIndex(final int key) {
269        return findInsertionIndex(keys, states, key, mask);
270    }
271
272    /**
273     * Find the index at which a key should be inserted
274     * @param keys keys table
275     * @param states states table
276     * @param key key to lookup
277     * @param mask bit mask for hash values
278     * @return index at which key should be inserted
279     */
280    private static int findInsertionIndex(final int[] keys, final byte[] states,
281                                          final int key, final int mask) {
282        final int hash = hashOf(key);
283        int index = hash & mask;
284        if (states[index] == FREE) {
285            return index;
286        } else if (states[index] == FULL && keys[index] == key) {
287            return changeIndexSign(index);
288        }
289
290        int perturb = perturb(hash);
291        int j = index;
292        if (states[index] == FULL) {
293            while (true) {
294                j = probe(perturb, j);
295                index = j & mask;
296                perturb >>= PERTURB_SHIFT;
297
298                if (states[index] != FULL || keys[index] == key) {
299                    break;
300                }
301            }
302        }
303
304        if (states[index] == FREE) {
305            return index;
306        } else if (states[index] == FULL) {
307            // due to the loop exit condition,
308            // if (states[index] == FULL) then keys[index] == key
309            return changeIndexSign(index);
310        }
311
312        final int firstRemoved = index;
313        while (true) {
314            j = probe(perturb, j);
315            index = j & mask;
316
317            if (states[index] == FREE) {
318                return firstRemoved;
319            } else if (states[index] == FULL && keys[index] == key) {
320                return changeIndexSign(index);
321            }
322
323            perturb >>= PERTURB_SHIFT;
324
325        }
326
327    }
328
329    /**
330     * Compute next probe for collision resolution
331     * @param perturb perturbed hash
332     * @param j previous probe
333     * @return next probe
334     */
335    private static int probe(final int perturb, final int j) {
336        return (j << 2) + j + perturb + 1;
337    }
338
339    /**
340     * Change the index sign
341     * @param index initial index
342     * @return changed index
343     */
344    private static int changeIndexSign(final int index) {
345        return -index - 1;
346    }
347
348    /**
349     * Get the number of elements stored in the map.
350     * @return number of elements stored in the map
351     */
352    public int size() {
353        return size;
354    }
355
356
357    /**
358     * Remove the value associated with a key.
359     * @param key key to which the value is associated
360     * @return removed value
361     */
362    public T remove(final int key) {
363
364        final int hash  = hashOf(key);
365        int index = hash & mask;
366        if (containsKey(key, index)) {
367            return doRemove(index);
368        }
369
370        if (states[index] == FREE) {
371            return missingEntries;
372        }
373
374        int j = index;
375        for (int perturb = perturb(hash); states[index] != FREE; perturb >>= PERTURB_SHIFT) {
376            j = probe(perturb, j);
377            index = j & mask;
378            if (containsKey(key, index)) {
379                return doRemove(index);
380            }
381        }
382
383        return missingEntries;
384
385    }
386
387    /**
388     * Check if the tables contain an element associated with specified key
389     * at specified index.
390     * @param key key to check
391     * @param index index to check
392     * @return true if an element is associated with key at index
393     */
394    private boolean containsKey(final int key, final int index) {
395        return (key != 0 || states[index] == FULL) && keys[index] == key;
396    }
397
398    /**
399     * Remove an element at specified index.
400     * @param index index of the element to remove
401     * @return removed value
402     */
403    private T doRemove(int index) {
404        keys[index]   = 0;
405        states[index] = REMOVED;
406        final T previous = values[index];
407        values[index] = missingEntries;
408        --size;
409        ++count;
410        return previous;
411    }
412
413    /**
414     * Put a value associated with a key in the map.
415     * @param key key to which value is associated
416     * @param value value to put in the map
417     * @return previous value associated with the key
418     */
419    public T put(final int key, final T value) {
420        int index = findInsertionIndex(key);
421        T previous = missingEntries;
422        boolean newMapping = true;
423        if (index < 0) {
424            index = changeIndexSign(index);
425            previous = values[index];
426            newMapping = false;
427        }
428        keys[index]   = key;
429        states[index] = FULL;
430        values[index] = value;
431        if (newMapping) {
432            ++size;
433            if (shouldGrowTable()) {
434                growTable();
435            }
436            ++count;
437        }
438        return previous;
439
440    }
441
442    /**
443     * Grow the tables.
444     */
445    private void growTable() {
446
447        final int oldLength      = states.length;
448        final int[] oldKeys      = keys;
449        final T[] oldValues = values;
450        final byte[] oldStates   = states;
451
452        final int newLength = RESIZE_MULTIPLIER * oldLength;
453        final int[] newKeys = new int[newLength];
454        final T[] newValues = buildArray(newLength);
455        final byte[] newStates = new byte[newLength];
456        final int newMask = newLength - 1;
457        for (int i = 0; i < oldLength; ++i) {
458            if (oldStates[i] == FULL) {
459                final int key = oldKeys[i];
460                final int index = findInsertionIndex(newKeys, newStates, key, newMask);
461                newKeys[index]   = key;
462                newValues[index] = oldValues[i];
463                newStates[index] = FULL;
464            }
465        }
466
467        mask   = newMask;
468        keys   = newKeys;
469        values = newValues;
470        states = newStates;
471
472    }
473
474    /**
475     * Check if tables should grow due to increased size.
476     * @return true if  tables should grow
477     */
478    private boolean shouldGrowTable() {
479        return size > (mask + 1) * LOAD_FACTOR;
480    }
481
482    /**
483     * Compute the hash value of a key
484     * @param key key to hash
485     * @return hash value of the key
486     */
487    private static int hashOf(final int key) {
488        final int h = key ^ ((key >>> 20) ^ (key >>> 12));
489        return h ^ (h >>> 7) ^ (h >>> 4);
490    }
491
492
493    /** Iterator class for the map. */
494    public class Iterator {
495
496        /** Reference modification count. */
497        private final int referenceCount;
498
499        /** Index of current element. */
500        private int current;
501
502        /** Index of next element. */
503        private int next;
504
505        /**
506         * Simple constructor.
507         */
508        private Iterator() {
509
510            // preserve the modification count of the map to detect concurrent modifications later
511            referenceCount = count;
512
513            // initialize current index
514            next = -1;
515            try {
516                advance();
517            } catch (NoSuchElementException nsee) { // NOPMD
518                // ignored
519            }
520
521        }
522
523        /**
524         * Check if there is a next element in the map.
525         * @return true if there is a next element
526         */
527        public boolean hasNext() {
528            return next >= 0;
529        }
530
531        /**
532         * Get the key of current entry.
533         * @return key of current entry
534         * @exception ConcurrentModificationException if the map is modified during iteration
535         * @exception NoSuchElementException if there is no element left in the map
536         */
537        public int key()
538            throws ConcurrentModificationException, NoSuchElementException {
539            if (referenceCount != count) {
540                throw new ConcurrentModificationException();
541            }
542            if (current < 0) {
543                throw new NoSuchElementException();
544            }
545            return keys[current];
546        }
547
548        /**
549         * Get the value of current entry.
550         * @return value of current entry
551         * @exception ConcurrentModificationException if the map is modified during iteration
552         * @exception NoSuchElementException if there is no element left in the map
553         */
554        public T value()
555            throws ConcurrentModificationException, NoSuchElementException {
556            if (referenceCount != count) {
557                throw new ConcurrentModificationException();
558            }
559            if (current < 0) {
560                throw new NoSuchElementException();
561            }
562            return values[current];
563        }
564
565        /**
566         * Advance iterator one step further.
567         * @exception ConcurrentModificationException if the map is modified during iteration
568         * @exception NoSuchElementException if there is no element left in the map
569         */
570        public void advance()
571            throws ConcurrentModificationException, NoSuchElementException {
572
573            if (referenceCount != count) {
574                throw new ConcurrentModificationException();
575            }
576
577            // advance on step
578            current = next;
579
580            // prepare next step
581            try {
582                while (states[++next] != FULL) { // NOPMD
583                    // nothing to do
584                }
585            } catch (ArrayIndexOutOfBoundsException e) {
586                next = -2;
587                if (current < 0) {
588                    throw new NoSuchElementException();
589                }
590            }
591
592        }
593
594    }
595
596    /**
597     * Read a serialized object.
598     * @param stream input stream
599     * @throws IOException if object cannot be read
600     * @throws ClassNotFoundException if the class corresponding
601     * to the serialized object cannot be found
602     */
603    private void readObject(final ObjectInputStream stream)
604        throws IOException, ClassNotFoundException {
605        stream.defaultReadObject();
606        count = 0;
607    }
608
609    /** Build an array of elements.
610     * @param length size of the array to build
611     * @return a new array
612     */
613    @SuppressWarnings("unchecked") // field is of type T
614    private T[] buildArray(final int length) {
615        return (T[]) Array.newInstance(field.getRuntimeClass(), length);
616    }
617
618}