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