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     */
017    package org.apache.commons.math.util;
018    
019    import java.io.IOException;
020    import java.io.ObjectInputStream;
021    import java.io.Serializable;
022    import java.lang.reflect.Array;
023    import java.util.ConcurrentModificationException;
024    import java.util.NoSuchElementException;
025    
026    import org.apache.commons.math.Field;
027    import org.apache.commons.math.FieldElement;
028    import org.apache.commons.math.MathRuntimeException;
029    
030    /**
031     * Open addressed map from int to FieldElement.
032     * <p>This class provides a dedicated map from integers to FieldElements with a
033     * much smaller memory overhead than standard <code>java.util.Map</code>.</p>
034     * <p>This class is not synchronized. The specialized iterators returned by
035     * {@link #iterator()} are fail-fast: they throw a
036     * <code>ConcurrentModificationException</code> when they detect the map has been
037     * modified during iteration.</p>
038     * @param <T> the type of the field elements
039     * @version $Revision: 799857 $ $Date: 2009-08-01 09:07:12 -0400 (Sat, 01 Aug 2009) $
040     * @since 2.0
041     */
042    public class OpenIntToFieldHashMap<T extends FieldElement<T>> implements Serializable {
043        
044        /** Serializable version identifier. */
045        private static final long serialVersionUID = -9179080286849120720L;
046    
047        /** Load factor for the map. */
048        private static final float LOAD_FACTOR = 0.5f;
049    
050        /** Default starting size.
051         * <p>This must be a power of two for bit mask to work properly. </p>
052         */
053        private static final int DEFAULT_EXPECTED_SIZE = 16;
054    
055        /** Multiplier for size growth when map fills up.
056         * <p>This must be a power of two for bit mask to work properly. </p>
057         */
058        private static final int RESIZE_MULTIPLIER = 2;
059    
060        /** Number of bits to perturb the index when probing for collision resolution. */
061        private static final int PERTURB_SHIFT = 5;
062    
063        /** Status indicator for free table entries. */
064        protected static final byte FREE    = 0;
065    
066        /** Status indicator for full table entries. */
067        protected static final byte FULL    = 1;
068    
069        /** Status indicator for removed table entries. */
070        protected static final byte REMOVED = 2;
071    
072        /** Field to which the elements belong. */
073        private final Field<T> field;
074        
075        /** Keys table. */
076        private int[] keys;
077    
078        /** Values table. */
079        private T[] values;
080    
081        /** States table. */
082        private byte[] states;
083    
084        /** Return value for missing entries. */
085        private final T missingEntries;
086    
087        /** Current size of the map. */
088        private int size;
089    
090        /** Bit mask for hash values. */
091        private int mask;
092    
093        /** Modifications count. */
094        private transient int count;
095    
096        /**
097         * Build an empty map with default size and using zero for missing entries.
098         * @param field field to which the elements belong
099         */
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    }