OpenIntToDoubleHashMap.java

  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.  *      http://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.  */

  18. package org.apache.commons.math4.legacy.linear;

  20. import org.apache.commons.math4.core.jdkmath.JdkMath;

  22. import java.io.IOException;
  23. import java.io.ObjectInputStream;
  24. import java.io.Serializable;
  25. import java.util.ConcurrentModificationException;
  26. import java.util.NoSuchElementException;

  28. /**
  29.  * Open addressed map from int to double.
  30.  * <p>This class provides a dedicated map from integers to doubles with a
  31.  * much smaller memory overhead than standard <code>java.util.Map</code>.</p>
  32.  * <p>This class is not synchronized. The specialized iterators returned by
  33.  * {@link #iterator()} are fail-fast: they throw a
  34.  * <code>ConcurrentModificationException</code> when they detect the map has been
  35.  * modified during iteration.</p>
  36.  * @since 2.0
  37.  */
  38. class OpenIntToDoubleHashMap implements Serializable { // Not in public API.

  40.     /** Status indicator for free table entries. */
  41.     protected static final byte FREE    = 0;

  43.     /** Status indicator for full table entries. */
  44.     protected static final byte FULL    = 1;

  46.     /** Status indicator for removed table entries. */
  47.     protected static final byte REMOVED = 2;

  49.     /** Serializable version identifier. */
  50.     private static final long serialVersionUID = -3646337053166149105L;

  52.     /** Load factor for the map. */
  53.     private static final float LOAD_FACTOR = 0.5f;

  55.     /** Default starting size.
  56.      * <p>This must be a power of two for bit mask to work properly. </p>
  57.      */
  58.     private static final int DEFAULT_EXPECTED_SIZE = 16;

  60.     /** Multiplier for size growth when map fills up.
  61.      * <p>This must be a power of two for bit mask to work properly. </p>
  62.      */
  63.     private static final int RESIZE_MULTIPLIER = 2;

  65.     /** Number of bits to perturb the index when probing for collision resolution. */
  66.     private static final int PERTURB_SHIFT = 5;

  68.     /** Keys table. */
  69.     private int[] keys;

  71.     /** Values table. */
  72.     private double[] values;

  74.     /** States table. */
  75.     private byte[] states;

  77.     /** Return value for missing entries. */
  78.     private final double missingEntries;

  80.     /** Current size of the map. */
  81.     private int size;

  83.     /** Bit mask for hash values. */
  84.     private int mask;

  86.     /** Modifications count. */
  87.     private transient int count;

  89.     /**
  90.      * Build an empty map with default size and using NaN for missing entries.
  91.      */
  92.     OpenIntToDoubleHashMap() {
  93.         this(DEFAULT_EXPECTED_SIZE, Double.NaN);
  94.     }

  96.     /**
  97.      * Build an empty map with default size.
  98.      * @param missingEntries value to return when a missing entry is fetched
  99.      */
  100.     OpenIntToDoubleHashMap(final double missingEntries) {
  101.         this(DEFAULT_EXPECTED_SIZE, missingEntries);
  102.     }

  104.     /**
  105.      * Build an empty map with specified size and using NaN for missing entries.
  106.      * @param expectedSize expected number of elements in the map
  107.      */
  108.     OpenIntToDoubleHashMap(final int expectedSize) {
  109.         this(expectedSize, Double.NaN);
  110.     }

  112.     /**
  113.      * Build an empty map with specified size.
  114.      * @param expectedSize expected number of elements in the map
  115.      * @param missingEntries value to return when a missing entry is fetched
  116.      */
  117.     OpenIntToDoubleHashMap(final int expectedSize,
  118.                            final double missingEntries) {
  119.         final int capacity = computeCapacity(expectedSize);
  120.         keys   = new int[capacity];
  121.         values = new double[capacity];
  122.         states = new byte[capacity];
  123.         this.missingEntries = missingEntries;
  124.         mask   = capacity - 1;
  125.     }

  127.     /**
  128.      * Copy constructor.
  129.      * @param source map to copy
  130.      */
  131.     OpenIntToDoubleHashMap(final OpenIntToDoubleHashMap source) {
  132.         final int length = source.keys.length;
  133.         keys = new int[length];
  134.         System.arraycopy(source.keys, 0, keys, 0, length);
  135.         values = new double[length];
  136.         System.arraycopy(source.values, 0, values, 0, length);
  137.         states = new byte[length];
  138.         System.arraycopy(source.states, 0, states, 0, length);
  139.         missingEntries = source.missingEntries;
  140.         size  = source.size;
  141.         mask  = source.mask;
  142.         count = source.count;
  143.     }

  145.     /**
  146.      * Compute the capacity needed for a given size.
  147.      * @param expectedSize expected size of the map
  148.      * @return capacity to use for the specified size
  149.      */
  150.     private static int computeCapacity(final int expectedSize) {
  151.         if (expectedSize == 0) {
  152.             return 1;
  153.         }
  154.         final int capacity   = (int) JdkMath.ceil(expectedSize / LOAD_FACTOR);
  155.         final int powerOfTwo = Integer.highestOneBit(capacity);
  156.         if (powerOfTwo == capacity) {
  157.             return capacity;
  158.         }
  159.         return nextPowerOfTwo(capacity);
  160.     }

  162.     /**
  163.      * Find the smallest power of two greater than the input value.
  164.      * @param i input value
  165.      * @return smallest power of two greater than the input value
  166.      */
  167.     private static int nextPowerOfTwo(final int i) {
  168.         return Integer.highestOneBit(i) << 1;
  169.     }

  171.     /**
  172.      * Get the stored value associated with the given key.
  173.      * @param key key associated with the data
  174.      * @return data associated with the key
  175.      */
  176.     public double get(final int key) {

  178.         final int hash  = hashOf(key);
  179.         int index = hash & mask;
  180.         if (containsKey(key, index)) {
  181.             return values[index];
  182.         }

  184.         if (states[index] == FREE) {
  185.             return missingEntries;
  186.         }

  188.         int j = index;
  189.         for (int perturb = perturb(hash); states[index] != FREE; perturb >>= PERTURB_SHIFT) {
  190.             j = probe(perturb, j);
  191.             index = j & mask;
  192.             if (containsKey(key, index)) {
  193.                 return values[index];
  194.             }
  195.         }

  197.         return missingEntries;
  198.     }

  200.     /**
  201.      * Check if a value is associated with a key.
  202.      * @param key key to check
  203.      * @return true if a value is associated with key
  204.      */
  205.     public boolean containsKey(final int key) {

  207.         final int hash  = hashOf(key);
  208.         int index = hash & mask;
  209.         if (containsKey(key, index)) {
  210.             return true;
  211.         }

  213.         if (states[index] == FREE) {
  214.             return false;
  215.         }

  217.         int j = index;
  218.         for (int perturb = perturb(hash); states[index] != FREE; perturb >>= PERTURB_SHIFT) {
  219.             j = probe(perturb, j);
  220.             index = j & mask;
  221.             if (containsKey(key, index)) {
  222.                 return true;
  223.             }
  224.         }

  226.         return false;
  227.     }

  229.     /**
  230.      * Get an iterator over map elements.
  231.      * <p>The specialized iterators returned are fail-fast: they throw a
  232.      * <code>ConcurrentModificationException</code> when they detect the map
  233.      * has been modified during iteration.</p>
  234.      * @return iterator over the map elements
  235.      */
  236.     public Iterator iterator() {
  237.         return new Iterator();
  238.     }

  240.     /**
  241.      * Perturb the hash for starting probing.
  242.      * @param hash initial hash
  243.      * @return perturbed hash
  244.      */
  245.     private static int perturb(final int hash) {
  246.         return hash & 0x7fffffff;
  247.     }

  249.     /**
  250.      * Find the index at which a key should be inserted.
  251.      * @param key key to lookup
  252.      * @return index at which key should be inserted
  253.      */
  254.     private int findInsertionIndex(final int key) {
  255.         return findInsertionIndex(keys, states, key, mask);
  256.     }

  258.     /**
  259.      * Find the index at which a key should be inserted.
  260.      * @param keys keys table
  261.      * @param states states table
  262.      * @param key key to lookup
  263.      * @param mask bit mask for hash values
  264.      * @return index at which key should be inserted
  265.      */
  266.     private static int findInsertionIndex(final int[] keys, final byte[] states,
  267.                                           final int key, final int mask) {
  268.         final int hash = hashOf(key);
  269.         int index = hash & mask;
  270.         if (states[index] == FREE) {
  271.             return index;
  272.         } else if (states[index] == FULL && keys[index] == key) {
  273.             return changeIndexSign(index);
  274.         }

  276.         int perturb = perturb(hash);
  277.         int j = index;
  278.         if (states[index] == FULL) {
  279.             while (true) {
  280.                 j = probe(perturb, j);
  281.                 index = j & mask;
  282.                 perturb >>= PERTURB_SHIFT;

  284.                 if (states[index] != FULL || keys[index] == key) {
  285.                     break;
  286.                 }
  287.             }
  288.         }

  290.         if (states[index] == FREE) {
  291.             return index;
  292.         } else if (states[index] == FULL) {
  293.             // due to the loop exit condition,
  294.             // if (states[index] == FULL) then keys[index] == key
  295.             return changeIndexSign(index);
  296.         }

  298.         final int firstRemoved = index;
  299.         while (true) {
  300.             j = probe(perturb, j);
  301.             index = j & mask;

  303.             if (states[index] == FREE) {
  304.                 return firstRemoved;
  305.             } else if (states[index] == FULL && keys[index] == key) {
  306.                 return changeIndexSign(index);
  307.             }

  309.             perturb >>= PERTURB_SHIFT;
  310.         }
  311.     }

  313.     /**
  314.      * Compute next probe for collision resolution.
  315.      * @param perturb perturbed hash
  316.      * @param j previous probe
  317.      * @return next probe
  318.      */
  319.     private static int probe(final int perturb, final int j) {
  320.         return (j << 2) + j + perturb + 1;
  321.     }

  323.     /**
  324.      * Change the index sign.
  325.      * @param index initial index
  326.      * @return changed index
  327.      */
  328.     private static int changeIndexSign(final int index) {
  329.         return -index - 1;
  330.     }

  332.     /**
  333.      * Get the number of elements stored in the map.
  334.      * @return number of elements stored in the map
  335.      */
  336.     public int size() {
  337.         return size;
  338.     }


  341.     /**
  342.      * Remove the value associated with a key.
  343.      * @param key key to which the value is associated
  344.      * @return removed value
  345.      */
  346.     public double remove(final int key) {

  348.         final int hash  = hashOf(key);
  349.         int index = hash & mask;
  350.         if (containsKey(key, index)) {
  351.             return doRemove(index);
  352.         }

  354.         if (states[index] == FREE) {
  355.             return missingEntries;
  356.         }

  358.         int j = index;
  359.         for (int perturb = perturb(hash); states[index] != FREE; perturb >>= PERTURB_SHIFT) {
  360.             j = probe(perturb, j);
  361.             index = j & mask;
  362.             if (containsKey(key, index)) {
  363.                 return doRemove(index);
  364.             }
  365.         }

  367.         return missingEntries;
  368.     }

  370.     /**
  371.      * Check if the tables contain an element associated with specified key
  372.      * at specified index.
  373.      * @param key key to check
  374.      * @param index index to check
  375.      * @return true if an element is associated with key at index
  376.      */
  377.     private boolean containsKey(final int key, final int index) {
  378.         return (key != 0 || states[index] == FULL) && keys[index] == key;
  379.     }

  381.     /**
  382.      * Remove an element at specified index.
  383.      * @param index index of the element to remove
  384.      * @return removed value
  385.      */
  386.     private double doRemove(int index) {
  387.         keys[index]   = 0;
  388.         states[index] = REMOVED;
  389.         final double previous = values[index];
  390.         values[index] = missingEntries;
  391.         --size;
  392.         ++count;
  393.         return previous;
  394.     }

  396.     /**
  397.      * Put a value associated with a key in the map.
  398.      * @param key key to which value is associated
  399.      * @param value value to put in the map
  400.      * @return previous value associated with the key
  401.      */
  402.     public double put(final int key, final double value) {
  403.         int index = findInsertionIndex(key);
  404.         double previous = missingEntries;
  405.         boolean newMapping = true;
  406.         if (index < 0) {
  407.             index = changeIndexSign(index);
  408.             previous = values[index];
  409.             newMapping = false;
  410.         }
  411.         keys[index]   = key;
  412.         states[index] = FULL;
  413.         values[index] = value;
  414.         if (newMapping) {
  415.             ++size;
  416.             if (shouldGrowTable()) {
  417.                 growTable();
  418.             }
  419.             ++count;
  420.         }
  421.         return previous;
  422.     }

  424.     /**
  425.      * Grow the tables.
  426.      */
  427.     private void growTable() {

  429.         final int oldLength      = states.length;
  430.         final int[] oldKeys      = keys;
  431.         final double[] oldValues = values;
  432.         final byte[] oldStates   = states;

  434.         final int newLength = RESIZE_MULTIPLIER * oldLength;
  435.         final int[] newKeys = new int[newLength];
  436.         final double[] newValues = new double[newLength];
  437.         final byte[] newStates = new byte[newLength];
  438.         final int newMask = newLength - 1;
  439.         for (int i = 0; i < oldLength; ++i) {
  440.             if (oldStates[i] == FULL) {
  441.                 final int key = oldKeys[i];
  442.                 final int index = findInsertionIndex(newKeys, newStates, key, newMask);
  443.                 newKeys[index]   = key;
  444.                 newValues[index] = oldValues[i];
  445.                 newStates[index] = FULL;
  446.             }
  447.         }

  449.         mask   = newMask;
  450.         keys   = newKeys;
  451.         values = newValues;
  452.         states = newStates;
  453.     }

  455.     /**
  456.      * Check if tables should grow due to increased size.
  457.      * @return true if  tables should grow
  458.      */
  459.     private boolean shouldGrowTable() {
  460.         return size > (mask + 1) * LOAD_FACTOR;
  461.     }

  463.     /**
  464.      * Compute the hash value of a key.
  465.      * @param key key to hash
  466.      * @return hash value of the key
  467.      */
  468.     private static int hashOf(final int key) {
  469.         final int h = key ^ ((key >>> 20) ^ (key >>> 12));
  470.         return h ^ (h >>> 7) ^ (h >>> 4);
  471.     }


  474.     /** Iterator class for the map. */
  475.     public final class Iterator {

  477.         /** Reference modification count. */
  478.         private final int referenceCount;

  480.         /** Index of current element. */
  481.         private int current;

  483.         /** Index of next element. */
  484.         private int next;

  486.         /**
  487.          * Simple constructor.
  488.          */
  489.         private Iterator() {

  491.             // preserve the modification count of the map to detect concurrent modifications later
  492.             referenceCount = count;

  494.             // initialize current index
  495.             next = -1;
  496.             try {
  497.                 advance();
  498.             } catch (NoSuchElementException nsee) { // NOPMD
  499.                 // ignored
  500.             }
  501.         }

  503.         /**
  504.          * Check if there is a next element in the map.
  505.          * @return true if there is a next element
  506.          */
  507.         public boolean hasNext() {
  508.             return next >= 0;
  509.         }

  511.         /**
  512.          * Get the key of current entry.
  513.          * @return key of current entry
  514.          * @exception ConcurrentModificationException if the map is modified during iteration
  515.          * @exception NoSuchElementException if there is no element left in the map
  516.          */
  517.         public int key()
  518.             throws ConcurrentModificationException, NoSuchElementException {
  519.             if (referenceCount != count) {
  520.                 throw new ConcurrentModificationException();
  521.             }
  522.             if (current < 0) {
  523.                 throw new NoSuchElementException();
  524.             }
  525.             return keys[current];
  526.         }

  528.         /**
  529.          * Get the value of current entry.
  530.          * @return value of current entry
  531.          * @exception ConcurrentModificationException if the map is modified during iteration
  532.          * @exception NoSuchElementException if there is no element left in the map
  533.          */
  534.         public double value()
  535.             throws ConcurrentModificationException, NoSuchElementException {
  536.             if (referenceCount != count) {
  537.                 throw new ConcurrentModificationException();
  538.             }
  539.             if (current < 0) {
  540.                 throw new NoSuchElementException();
  541.             }
  542.             return values[current];
  543.         }

  545.         /**
  546.          * Advance iterator one step further.
  547.          * @exception ConcurrentModificationException if the map is modified during iteration
  548.          * @exception NoSuchElementException if there is no element left in the map
  549.          */
  550.         public void advance()
  551.             throws ConcurrentModificationException, NoSuchElementException {

  553.             if (referenceCount != count) {
  554.                 throw new ConcurrentModificationException();
  555.             }

  557.             // advance on step
  558.             current = next;

  560.             // prepare next step
  561.             try {
  562.                 do {
  563.                     ++next;
  564.                 } while (states[next] != FULL);
  565.             } catch (ArrayIndexOutOfBoundsException e) {
  566.                 next = -2;
  567.                 if (current < 0) {
  568.                     throw new NoSuchElementException();
  569.                 }
  570.             }
  571.         }
  572.     }

  574.     /**
  575.      * Read a serialized object.
  576.      * @param stream input stream
  577.      * @throws IOException if object cannot be read
  578.      * @throws ClassNotFoundException if the class corresponding
  579.      * to the serialized object cannot be found
  580.      */
  581.     private void readObject(final ObjectInputStream stream)
  582.         throws IOException, ClassNotFoundException {
  583.         stream.defaultReadObject();
  584.         count = 0;
  585.     }

  587. }
Created with JaCoCo 0.8.10.202304240956Code Coverage Report for Apache Commons Math 4.0-SNAPSHOT