You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@commons.apache.org by lu...@apache.org on 2008/12/14 15:56:51 UTC
svn commit: r726459 - in /commons/proper/math/trunk: ./
src/java/org/apache/commons/math/ src/java/org/apache/commons/math/util/
src/site/xdoc/ src/site/xdoc/userguide/
src/test/org/apache/commons/math/util/
Author: luc
Date: Sun Dec 14 06:56:50 2008
New Revision: 726459
URL: http://svn.apache.org/viewvc?rev=726459&view=rev
Log:
Added an int/double hash map (OpenIntToDoubleHashMap) with much smaller
memory overhead than standard java.util.Map (open addressing and no boxing)
Added:
commons/proper/math/trunk/src/java/org/apache/commons/math/util/OpenIntToDoubleHashMap.java (with props)
commons/proper/math/trunk/src/test/org/apache/commons/math/util/OpenIntToDoubleHashMapTest.java (with props)
Modified:
commons/proper/math/trunk/pom.xml
commons/proper/math/trunk/src/java/org/apache/commons/math/MathRuntimeException.java
commons/proper/math/trunk/src/java/org/apache/commons/math/MessagesResources_fr.java
commons/proper/math/trunk/src/site/xdoc/changes.xml
commons/proper/math/trunk/src/site/xdoc/userguide/utilities.xml
Modified: commons/proper/math/trunk/pom.xml
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/pom.xml?rev=726459&r1=726458&r2=726459&view=diff
==============================================================================
--- commons/proper/math/trunk/pom.xml (original)
+++ commons/proper/math/trunk/pom.xml Sun Dec 14 06:56:50 2008
@@ -124,6 +124,9 @@
<name>Matthias Hummel</name>
</contributor>
<contributor>
+ <name>Ismael Juma</name>
+ </contributor>
+ <contributor>
<name>Piotr Kochanski</name>
</contributor>
<contributor>
Modified: commons/proper/math/trunk/src/java/org/apache/commons/math/MathRuntimeException.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/java/org/apache/commons/math/MathRuntimeException.java?rev=726459&r1=726458&r2=726459&view=diff
==============================================================================
--- commons/proper/math/trunk/src/java/org/apache/commons/math/MathRuntimeException.java (original)
+++ commons/proper/math/trunk/src/java/org/apache/commons/math/MathRuntimeException.java Sun Dec 14 06:56:50 2008
@@ -22,8 +22,10 @@
import java.io.PrintWriter;
import java.text.MessageFormat;
import java.text.ParseException;
+import java.util.ConcurrentModificationException;
import java.util.Locale;
import java.util.MissingResourceException;
+import java.util.NoSuchElementException;
import java.util.ResourceBundle;
/**
@@ -35,7 +37,7 @@
public class MathRuntimeException extends RuntimeException {
/** Serializable version identifier. */
- private static final long serialVersionUID = 8560172512507661982L;
+ private static final long serialVersionUID = -143052521750625264L;
/** Cache for resources bundle. */
private static ResourceBundle cachedResources = null;
@@ -308,6 +310,48 @@
}
/**
+ * Constructs a new <code>ConcurrentModificationException</code> with specified formatted detail message.
+ * Message formatting is delegated to {@link java.text.MessageFormat}.
+ * @param pattern format specifier
+ * @param arguments format arguments
+ */
+ public static ConcurrentModificationException createConcurrentModificationException(final String pattern,
+ final Object[] arguments) {
+ return new ConcurrentModificationException(buildMessage(pattern, arguments, Locale.US)) {
+
+ /** Serializable version identifier. */
+ private static final long serialVersionUID = 6134247282754009421L;
+
+ /** {@inheritDoc} */
+ public String getLocalizedMessage() {
+ return buildMessage(pattern, arguments, Locale.getDefault());
+ }
+
+ };
+ }
+
+ /**
+ * Constructs a new <code>NoSuchElementException</code> with specified formatted detail message.
+ * Message formatting is delegated to {@link java.text.MessageFormat}.
+ * @param pattern format specifier
+ * @param arguments format arguments
+ */
+ public static NoSuchElementException createNoSuchElementException(final String pattern,
+ final Object[] arguments) {
+ return new NoSuchElementException(buildMessage(pattern, arguments, Locale.US)) {
+
+ /** Serializable version identifier. */
+ private static final long serialVersionUID = 7304273322489425799L;
+
+ /** {@inheritDoc} */
+ public String getLocalizedMessage() {
+ return buildMessage(pattern, arguments, Locale.getDefault());
+ }
+
+ };
+ }
+
+ /**
* Constructs a new <code>ParseException</code> with specified
* formatted detail message.
* Message formatting is delegated to {@link java.text.MessageFormat}.
Modified: commons/proper/math/trunk/src/java/org/apache/commons/math/MessagesResources_fr.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/java/org/apache/commons/math/MessagesResources_fr.java?rev=726459&r1=726458&r2=726459&view=diff
==============================================================================
--- commons/proper/math/trunk/src/java/org/apache/commons/math/MessagesResources_fr.java (original)
+++ commons/proper/math/trunk/src/java/org/apache/commons/math/MessagesResources_fr.java Sun Dec 14 06:56:50 2008
@@ -202,6 +202,12 @@
"une matrice doit comporter au moins une colonne" },
{ "some rows have length {0} while others have length {1}",
"certaines ligne ont une longueur de {0} alors que d''autres ont une longueur de {1}" },
+ { "{0}x{1} and {2}x{3} matrices are not addition compatible",
+ "les dimensions {0}x{1} et {2}x{3} sont incompatibles pour l'addition matricielle" },
+ { "{0}x{1} and {2}x{3} matrices are not subtraction compatible",
+ "les dimensions {0}x{1} et {2}x{3} sont incompatibles pour la soustraction matricielle" },
+ { "{0}x{1} and {2}x{3} matrices are not multiplication compatible",
+ "les dimensions {0}x{1} et {2}x{3} sont incompatibles pour la multiplication matricielle" },
// org.apache.commons.math.linear.BigMatrixImpl
// org.apache.commons.math.linear.RealMatrixImpl
@@ -219,12 +225,6 @@
"tableau des indices de lignes s\u00e9lectionn\u00e9es vide" },
{ "empty selected column index array",
"tableau des indices de colonnes s\u00e9lectionn\u00e9es vide" },
- { "{0}x{1} and {2}x{3} matrices are not multiplication compatible",
- "les dimensions {0}x{1} et {2}x{3} sont incompatibles pour la multiplication matricielle" },
- { "{0}x{1} and {2}x{3} matrices are not addition compatible",
- "les dimensions {0}x{1} et {2}x{3} sont incompatibles pour l'addition matricielle" },
- { "{0}x{1} and {2}x{3} matrices are not subtraction compatible",
- "les dimensions {0}x{1} et {2}x{3} sont incompatibles pour la soustraction matricielle" },
// org.apache.commons.math.random.EmpiricalDistributionImpl
// org.apache.commons.math.random.ValueServer
@@ -331,7 +331,13 @@
{ "invalid number of elements {0} (must be positive)",
"nombre d''\u00e9l\u00e9ments {0} invalide (doit \u00eatre positif)" },
{ "invalid exponent {0} (must be positive)",
- "exposant {0} invalide (doit \u00eatre positif)" }
+ "exposant {0} invalide (doit \u00eatre positif)" },
+
+ // org.apache.commons.math.util.OpenIntToDoubleHashMap
+ { "map has been modified while iterating",
+ "la table d''adressage a \u00e9t\u00e9 modifi\u00e9e pendant l''it\u00e9ration" },
+ { "iterator exhausted",
+ "it\u00e9ration achev\u00e9e" }
};
Added: commons/proper/math/trunk/src/java/org/apache/commons/math/util/OpenIntToDoubleHashMap.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/java/org/apache/commons/math/util/OpenIntToDoubleHashMap.java?rev=726459&view=auto
==============================================================================
--- commons/proper/math/trunk/src/java/org/apache/commons/math/util/OpenIntToDoubleHashMap.java (added)
+++ commons/proper/math/trunk/src/java/org/apache/commons/math/util/OpenIntToDoubleHashMap.java Sun Dec 14 06:56:50 2008
@@ -0,0 +1,555 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.commons.math.util;
+
+import java.io.Serializable;
+import java.util.ConcurrentModificationException;
+import java.util.NoSuchElementException;
+
+import org.apache.commons.math.MathRuntimeException;
+
+/**
+ * Open addressed map from int to double.
+ * <p>This class provides a dedicated map from integers to doubles with a
+ * much smaller memory overhead than standard <code>java.util.Map</code>.</p>
+ * <p>This class is not synchronized. The specialized iterators returned by
+ * {@link #iterator()} are fail-fast: they throw a
+ * <code>ConcurrentModificationException</code> when they detect the map has been
+ * modified during iteration.</p>
+ * @version $Revision$ $Date$
+ * @since 2.0
+ */
+public class OpenIntToDoubleHashMap implements Serializable {
+
+ /** Serializable version identifier */
+ private static final long serialVersionUID = -3646337053166149105L;
+
+ /** Load factor for the map. */
+ private static final float LOAD_FACTOR = 0.5f;
+
+ /** Default starting size.
+ * <p>This must be a power of two for bit mask to work properly. </p>
+ */
+ private static final int DEFAULT_EXPECTED_SIZE = 16;
+
+ /** Multiplier for size growth when map fills up.
+ * <p>This must be a power of two for bit mask to work properly. </p>
+ */
+ private static final int RESIZE_MULTIPLIER = 2;
+
+ /** Number of bits to perturb the index when probing for collision resolution. */
+ private static final int PERTURB_SHIFT = 5;
+
+ /** Status indicator for free table entries. */
+ protected static final byte FREE = 0;
+
+ /** Status indicator for full table entries. */
+ protected static final byte FULL = 1;
+
+ /** Status indicator for removed table entries. */
+ protected static final byte REMOVED = 2;
+
+ /** Keys table. */
+ private int[] keys;
+
+ /** Values table. */
+ private double[] values;
+
+ /** States table. */
+ private byte[] states;
+
+ /** Current size of the map. */
+ private int size;
+
+ /** Bit mask for hash values. */
+ private int mask;
+
+ /** Modifications count. */
+ private transient int count;
+
+ /**
+ * Build an empty map with default size.
+ */
+ public OpenIntToDoubleHashMap() {
+ this(DEFAULT_EXPECTED_SIZE);
+ }
+
+ /**
+ * Build an empty map with specified size.
+ * @param expectedSize expected number of elements in the map
+ */
+ public OpenIntToDoubleHashMap(final int expectedSize) {
+ final int capacity = computeCapacity(expectedSize);
+ keys = new int[capacity];
+ values = new double[capacity];
+ states = new byte[capacity];
+ mask = capacity - 1;
+ }
+
+ /**
+ * Copy constructor.
+ * @param source map to copy
+ */
+ public OpenIntToDoubleHashMap(final OpenIntToDoubleHashMap source) {
+ final int length = source.keys.length;
+ keys = new int[length];
+ System.arraycopy(source.keys, 0, keys, 0, length);
+ values = new double[length];
+ System.arraycopy(source.values, 0, values, 0, length);
+ states = new byte[length];
+ System.arraycopy(source.states, 0, states, 0, length);
+ size = source.size;
+ mask = source.mask;
+ count = source.count;
+ }
+
+ /**
+ * Compute the capacity needed for a given size.
+ * @param expectedSize expected size of the map
+ * @return capacity to use for the specified size
+ */
+ private static int computeCapacity(final int expectedSize) {
+ if (expectedSize == 0) {
+ return 1;
+ }
+ final int capacity = (int) Math.ceil(expectedSize / LOAD_FACTOR);
+ final int powerOfTwo = Integer.highestOneBit(capacity);
+ if (powerOfTwo == capacity) {
+ return capacity;
+ }
+ return nextPowerOfTwo(capacity);
+ }
+
+ /**
+ * Find the smallest power of two greater than the input value
+ * @param i input value
+ * @return smallest power of two greater than the input value
+ */
+ private static int nextPowerOfTwo(final int i) {
+ return Integer.highestOneBit(i) << 1;
+ }
+
+ /**
+ * Get the stored value associated with the given key
+ * @param key key associated with the data
+ * @return data associated with the key
+ */
+ public double get(final int key) {
+
+ final int hash = hashOf(key);
+ int index = hash & mask;
+ if (containsKey(key, index)) {
+ return values[index];
+ }
+
+ if (states[index] == FREE) {
+ return 0.0;
+ }
+
+ for (int perturb = perturb(hash), j = index; states[index] != FREE; perturb >>= PERTURB_SHIFT) {
+ j = probe(perturb, j);
+ index = j & mask;
+ if (containsKey(key, index)) {
+ return values[index];
+ }
+ }
+
+ return 0.0;
+
+ }
+
+ /**
+ * Check if a value is associated with a key.
+ * @param key key to check
+ * @return true if a value is associated with key
+ */
+ public boolean containsKey(final int key) {
+
+ final int hash = hashOf(key);
+ int index = hash & mask;
+ if (containsKey(key, index)) {
+ return true;
+ }
+
+ if (states[index] == FREE) {
+ return false;
+ }
+
+ for (int perturb = perturb(hash), j = index; states[index] != FREE; perturb >>= PERTURB_SHIFT) {
+ j = probe(perturb, j);
+ index = j & mask;
+ if (containsKey(key, index)) {
+ return true;
+ }
+ }
+
+ return false;
+
+ }
+
+ /**
+ * Get an iterator over map elements.
+ * <p>The specialized iterators returned are fail-fast: they throw a
+ * <code>ConcurrentModificationException</code> when they detect the map
+ * has been modified during iteration.</p>
+ * @return iterator over the map elements
+ */
+ public Iterator iterator() {
+ return new Iterator();
+ }
+
+ /**
+ * Perturb the hash for starting probing.
+ * @param hash initial hash
+ * @return perturbed hash
+ */
+ private static int perturb(final int hash) {
+ return hash & 0x7fffffff;
+ }
+
+ /**
+ * Find the index at which a key should be inserted
+ * @param key key to lookup
+ * @return index at which key should be inserted
+ */
+ private int findInsertionIndex(final int key) {
+ return findInsertionIndex(keys, states, key, mask);
+ }
+
+ /**
+ * Find the index at which a key should be inserted
+ * @param keys keys table
+ * @param states states table
+ * @param key key to lookup
+ * @param mask bit mask for hash values
+ * @return index at which key should be inserted
+ */
+ private static int findInsertionIndex(final int[] keys, final byte[] states,
+ final int key, final int mask) {
+ final int hash = hashOf(key);
+ int index = hash & mask;
+ if (states[index] == FREE) {
+ return index;
+ } else if (states[index] == FULL && keys[index] == key) {
+ return changeIndexSign(index);
+ }
+
+ int perturb = perturb(hash);
+ int j = index;
+ if (states[index] == FULL) {
+ while (true) {
+ j = probe(perturb, j);
+ index = j & mask;
+ perturb >>= PERTURB_SHIFT;
+
+ if (states[index] != FULL || keys[index] == key) {
+ break;
+ }
+ }
+ }
+
+ if (states[index] == FREE) {
+ return index;
+ } else if (states[index] == FULL) {
+ // due to the loop exit condition,
+ // if (states[index] == FULL) then keys[index] == key
+ return changeIndexSign(index);
+ }
+
+ final int firstRemoved = index;
+ while (true) {
+ j = probe(perturb, j);
+ index = j & mask;
+
+ if (states[index] == FREE) {
+ return firstRemoved;
+ } else if (states[index] == FULL && keys[index] == key) {
+ return changeIndexSign(index);
+ }
+
+ perturb >>= PERTURB_SHIFT;
+
+ }
+
+ }
+
+ /**
+ * Compute next probe for collision resolution
+ * @param perturb perturbed hash
+ * @param j previous probe
+ * @return next probe
+ */
+ private static int probe(final int perturb, final int j) {
+ return (j << 2) + j + perturb + 1;
+ }
+
+ /**
+ * Change the index sign
+ * @param index initial index
+ * @return changed index
+ */
+ private static int changeIndexSign(final int index) {
+ return -index - 1;
+ }
+
+ /**
+ * Get the number of elements stored in the map.
+ * @return number of elements stored in the map
+ */
+ public int size() {
+ return size;
+ }
+
+ /**
+ * Remove the value associated with a key.
+ * @param key key to which the value is associated
+ * @return removed value
+ */
+ public double remove(final int key) {
+
+ final int hash = hashOf(key);
+ int index = hash & mask;
+ if (containsKey(key, index)) {
+ return doRemove(index);
+ }
+
+ if (states[index] == FREE) {
+ return 0.0;
+ }
+
+ for (int perturb = perturb(hash), j = index; states[index] != FREE; perturb >>= PERTURB_SHIFT) {
+ j = probe(perturb, j);
+ index = j & mask;
+ if (containsKey(key, index)) {
+ return doRemove(index);
+ }
+ }
+
+ return 0.0;
+
+ }
+
+ /**
+ * Check if the tables contain an element associated with specified key
+ * at specified index.
+ * @param key key to check
+ * @param index index to check
+ * @return true if an element is associated with key at index
+ */
+ private boolean containsKey(final int key, final int index) {
+ return (key != 0 || states[index] == FULL) && keys[index] == key;
+ }
+
+ /**
+ * Remove an element at specified index.
+ * @param index index of the element to remove
+ * @return removed value
+ */
+ private double doRemove(int index) {
+ keys[index] = 0;
+ states[index] = REMOVED;
+ final double previous = values[index];
+ values[index] = 0;
+ --size;
+ ++count;
+ return previous;
+ }
+
+ /**
+ * Put a value associated with a key in the map.
+ * @param key key to which value is associated
+ * @param value value to put in the map
+ * @return previous value associated with the key
+ */
+ public double put(final int key, final double value) {
+ int index = findInsertionIndex(key);
+ double previous = 0.0;
+ boolean newMapping = true;
+ if (index < 0) {
+ index = changeIndexSign(index);
+ previous = values[index];
+ newMapping = false;
+ }
+ keys[index] = key;
+ states[index] = FULL;
+ values[index] = value;
+ if (newMapping) {
+ ++size;
+ if (shouldGrowTable()) {
+ growTable();
+ }
+ }
+
+ ++count;
+ return previous;
+
+ }
+
+ /**
+ * Grow the tables.
+ */
+ private void growTable() {
+
+ final int oldLength = states.length;
+ final int[] oldKeys = keys;
+ final double[] oldValues = values;
+ final byte[] oldStates = states;
+
+ final int newLength = RESIZE_MULTIPLIER * oldLength;
+ final int[] newKeys = new int[newLength];
+ final double[] newValues = new double[newLength];
+ final byte[] newStates = new byte[newLength];
+ final int newMask = newLength - 1;
+ for (int i = 0; i < oldLength; ++i) {
+ if (oldStates[i] == FULL) {
+ final int key = oldKeys[i];
+ final int index = findInsertionIndex(newKeys, newStates, key, newMask);
+ newKeys[index] = key;
+ newValues[index] = oldValues[i];
+ newStates[index] = FULL;
+ }
+ }
+
+ mask = newMask;
+ keys = newKeys;
+ values = newValues;
+ states = newStates;
+
+ }
+
+ /**
+ * Check if tables should grow due to increased size.
+ * @return true if tables should grow
+ */
+ private boolean shouldGrowTable() {
+ return size > (mask + 1) * LOAD_FACTOR;
+ }
+
+ /**
+ * Compute the hash value of a key
+ * @param key key to hash
+ * @return hash value of the key
+ */
+ private static int hashOf(final int key) {
+ final int h = key ^ ((key >>> 20) ^ (key >>> 12));
+ return h ^ (h >>> 7) ^ (h >>> 4);
+ }
+
+ /** Iterator class for the map. */
+ public class Iterator {
+
+ /** Reference modification count. */
+ final int referenceCount;
+
+ /** Index of next element. */
+ private int index;
+
+ /**
+ * Simple constructor.
+ */
+ private Iterator() {
+ referenceCount = count;
+ index = -1;
+ goToNext();
+ }
+
+ /**
+ * Check if there is a next element in the map.
+ * @return true if there is a next element
+ */
+ public boolean hasNext() {
+ return index >= 0;
+ }
+
+ /**
+ * Get the next entry.
+ * @return next entry
+ * @exception ConcurrentModificationException if the map is modified during iteration
+ * @exception NoSuchElementException if there is no element left in the map
+ */
+ public Entry next()
+ throws ConcurrentModificationException, NoSuchElementException {
+ if (referenceCount != count) {
+ throw MathRuntimeException.createConcurrentModificationException("map has been modified while iterating",
+ null);
+ }
+ if (index < 0) {
+ throw MathRuntimeException.createNoSuchElementException("iterator exhausted", null);
+ }
+ final Entry entry = new Entry(keys[index], values[index]);
+ goToNext();
+ return entry;
+ }
+
+ /**
+ * Find next index.
+ */
+ private void goToNext() {
+ try {
+ while (states[++index] != FULL) {
+ // nothing to do
+ }
+ } catch (ArrayIndexOutOfBoundsException e) {
+ index = -1;
+ }
+ }
+
+ }
+
+ /** Entry class for the map.
+ * <p>Entry elements are built on the fly only during iteration,
+ * copying values. So changes in the map are <strong>not</strong>
+ * reflected on already built entries.</p>
+ */
+ public static class Entry {
+
+ /** Key. */
+ private final int key;
+
+ /** Value. */
+ private final double value;
+
+ /**
+ * Simple constructor.
+ * @param key entry key
+ * @param value entry value
+ */
+ private Entry(final int key, final double value) {
+ this.key = key;
+ this.value = value;
+ }
+
+ /**
+ * Get the key.
+ * @return entry key
+ */
+ public int key() {
+ return key;
+ }
+
+ /**
+ * Get the value.
+ * @return entry value
+ */
+ public double value() {
+ return value;
+ }
+
+ }
+
+}
Propchange: commons/proper/math/trunk/src/java/org/apache/commons/math/util/OpenIntToDoubleHashMap.java
------------------------------------------------------------------------------
svn:eol-style = native
Propchange: commons/proper/math/trunk/src/java/org/apache/commons/math/util/OpenIntToDoubleHashMap.java
------------------------------------------------------------------------------
svn:keywords = Author Date Id Revision
Modified: commons/proper/math/trunk/src/site/xdoc/changes.xml
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/site/xdoc/changes.xml?rev=726459&r1=726458&r2=726459&view=diff
==============================================================================
--- commons/proper/math/trunk/src/site/xdoc/changes.xml (original)
+++ commons/proper/math/trunk/src/site/xdoc/changes.xml Sun Dec 14 06:56:50 2008
@@ -39,6 +39,10 @@
</properties>
<body>
<release version="2.0" date="TBD" description="TBD">
+ <action dev="luc" type="add" due-to="Ismael Juma">
+ Added an int/double hash map (OpenIntToDoubleHashMap) with much smaller
+ memory overhead than standard java.util.Map (open addressing and no boxing).
+ </action>
<action dev="luc" type="add" issue="MATH-152" due-to="Remi Arntzen">
Added support for multi-dimensional Fourier transform.
</action>
Modified: commons/proper/math/trunk/src/site/xdoc/userguide/utilities.xml
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/site/xdoc/userguide/utilities.xml?rev=726459&r1=726458&r2=726459&view=diff
==============================================================================
--- commons/proper/math/trunk/src/site/xdoc/userguide/utilities.xml (original)
+++ commons/proper/math/trunk/src/site/xdoc/userguide/utilities.xml Sun Dec 14 06:56:50 2008
@@ -72,7 +72,18 @@
</p>
</subsection>
-<subsection name="6.3 Continued Fractions" href="continued_fractions">
+<subsection name="6.3 int/double hash map" href="int_double_hash_map">
+ <p>
+ The <a href="../apidocs/org/apache/commons/math/util/OpenIntToDoubleHashMap.html">
+ org.apache.commons.math.util.OpenIntToDoubleHashMap</a> class provides a specialized
+ hash map implementation for int/double. This implementation has a much smaller memory
+ overhead than standard <code>java.util.HashMap</code> class. It uses open addressing
+ and primitive arrays, which greatly reduces the number of intermediate objects and
+ improve data locality.
+ </p>
+</subsection>
+
+<subsection name="6.4 Continued Fractions" href="continued_fractions">
<p>
The <a href="../apidocs/org/apache/commons/math/util/ContinuedFraction.html">
org.apache.commons.math.util.ContinuedFraction</a> class provides a generic
@@ -140,7 +151,7 @@
</p>
</subsection>
-<subsection name="6.4 binomial coefficients, factorials and other common math functions" href="math_utils">
+<subsection name="6.5 binomial coefficients, factorials and other common math functions" href="math_utils">
<p>
A collection of reusable math functions is provided in the
<a href="../apidocs/org/apache/commons/math/util/MathUtils.html">MathUtils</a>
Added: commons/proper/math/trunk/src/test/org/apache/commons/math/util/OpenIntToDoubleHashMapTest.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/test/org/apache/commons/math/util/OpenIntToDoubleHashMapTest.java?rev=726459&view=auto
==============================================================================
--- commons/proper/math/trunk/src/test/org/apache/commons/math/util/OpenIntToDoubleHashMapTest.java (added)
+++ commons/proper/math/trunk/src/test/org/apache/commons/math/util/OpenIntToDoubleHashMapTest.java Sun Dec 14 06:56:50 2008
@@ -0,0 +1,301 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.commons.math.util;
+
+import java.util.ConcurrentModificationException;
+import java.util.HashMap;
+import java.util.HashSet;
+import java.util.Map;
+import java.util.NoSuchElementException;
+import java.util.Random;
+import java.util.Set;
+
+import junit.framework.TestCase;
+
+/**
+ * Test cases for the {@link OpenIntToDoubleHashMap}.
+ */
+public class OpenIntToDoubleHashMapTest extends TestCase {
+
+ private Map<Integer, Double> javaMap = new HashMap<Integer, Double>();
+
+ @Override
+ protected void setUp() throws Exception {
+ javaMap.put(50, 100.0);
+ javaMap.put(75, 75.0);
+ javaMap.put(25, 500.0);
+ javaMap.put(Integer.MAX_VALUE, Double.MAX_VALUE);
+ javaMap.put(0, -1.0);
+ javaMap.put(1, 0.0);
+ javaMap.put(33, -0.1);
+ javaMap.put(23234234, -242343.0);
+ javaMap.put(23321, Double.MIN_VALUE);
+ javaMap.put(-4444, 332.0);
+ javaMap.put(-1, -2323.0);
+ javaMap.put(Integer.MIN_VALUE, 44.0);
+
+ /* Add a few more to cause the table to rehash */
+ javaMap.putAll(generate());
+
+ }
+
+ private Map<Integer, Double> generate() {
+ Map<Integer, Double> map = new HashMap<Integer, Double>();
+ Random r = new Random();
+ for (int i = 0; i < 2000; ++i)
+ map.put(r.nextInt(), r.nextDouble());
+ return map;
+ }
+
+ private OpenIntToDoubleHashMap createFromJavaMap() {
+ OpenIntToDoubleHashMap map = new OpenIntToDoubleHashMap();
+ for (Map.Entry<Integer, Double> mapEntry : javaMap.entrySet()) {
+ map.put(mapEntry.getKey(), mapEntry.getValue());
+ }
+ return map;
+ }
+
+ public void testPutAndGetWith0ExpectedSize() {
+ OpenIntToDoubleHashMap map = new OpenIntToDoubleHashMap(0);
+ assertPutAndGet(map);
+ }
+
+ public void testPutAndGetWithExpectedSize() {
+ OpenIntToDoubleHashMap map = new OpenIntToDoubleHashMap(500);
+ assertPutAndGet(map);
+ }
+
+ public void testPutAndGet() {
+ OpenIntToDoubleHashMap map = new OpenIntToDoubleHashMap();
+ assertPutAndGet(map);
+ }
+
+ private void assertPutAndGet(OpenIntToDoubleHashMap map) {
+ assertPutAndGet(map, 0, new HashSet<Integer>());
+ }
+
+ private void assertPutAndGet(OpenIntToDoubleHashMap map, int mapSize,
+ Set<Integer> keysInMap) {
+ assertEquals(mapSize, map.size());
+ for (Map.Entry<Integer, Double> mapEntry : javaMap.entrySet()) {
+ map.put(mapEntry.getKey(), mapEntry.getValue());
+ if (!keysInMap.contains(mapEntry.getKey()))
+ ++mapSize;
+ assertEquals(mapSize, map.size());
+ assertEquals(mapEntry.getValue(), map.get(mapEntry.getKey()));
+ }
+ }
+
+ public void testPutAbsentOnExisting() {
+ OpenIntToDoubleHashMap map = createFromJavaMap();
+ int size = javaMap.size();
+ for (Map.Entry<Integer, Double> mapEntry : generateAbsent().entrySet()) {
+ map.put(mapEntry.getKey(), mapEntry.getValue());
+ assertEquals(++size, map.size());
+ assertEquals(mapEntry.getValue(), map.get(mapEntry.getKey()));
+ }
+ }
+
+ public void testPutOnExisting() {
+ OpenIntToDoubleHashMap map = createFromJavaMap();
+ for (Map.Entry<Integer, Double> mapEntry : javaMap.entrySet()) {
+ map.put(mapEntry.getKey(), mapEntry.getValue());
+ assertEquals(javaMap.size(), map.size());
+ assertEquals(mapEntry.getValue(), map.get(mapEntry.getKey()));
+ }
+ }
+
+ public void testGetAbsent() {
+ Map<Integer, Double> generated = generateAbsent();
+ OpenIntToDoubleHashMap map = createFromJavaMap();
+
+ for (Map.Entry<Integer, Double> mapEntry : generated.entrySet())
+ assertEquals(0.0, map.get(mapEntry.getKey()));
+ }
+
+ public void testGetFromEmpty() {
+ OpenIntToDoubleHashMap map = new OpenIntToDoubleHashMap();
+ assertEquals(0.0, map.get(5));
+ assertEquals(0.0, map.get(0));
+ assertEquals(0.0, map.get(50));
+ }
+
+ public void testRemove() {
+ OpenIntToDoubleHashMap map = createFromJavaMap();
+ int mapSize = javaMap.size();
+ assertEquals(mapSize, map.size());
+ for (Map.Entry<Integer, Double> mapEntry : javaMap.entrySet()) {
+ map.remove(mapEntry.getKey());
+ assertEquals(--mapSize, map.size());
+ assertEquals(0.0, map.get(mapEntry.getKey()));
+ }
+
+ /* Ensure that put and get still work correctly after removals */
+ assertPutAndGet(map);
+ }
+
+ /* This time only remove some entries */
+ public void testRemove2() {
+ OpenIntToDoubleHashMap map = createFromJavaMap();
+ int mapSize = javaMap.size();
+ int count = 0;
+ Set<Integer> keysInMap = new HashSet<Integer>(javaMap.keySet());
+ for (Map.Entry<Integer, Double> mapEntry : javaMap.entrySet()) {
+ keysInMap.remove(mapEntry.getKey());
+ map.remove(mapEntry.getKey());
+ assertEquals(--mapSize, map.size());
+ assertEquals(0.0, map.get(mapEntry.getKey()));
+ if (count++ > 5)
+ break;
+ }
+
+ /* Ensure that put and get still work correctly after removals */
+ assertPutAndGet(map, mapSize, keysInMap);
+ }
+
+ public void testRemoveFromEmpty() {
+ OpenIntToDoubleHashMap map = new OpenIntToDoubleHashMap();
+ assertEquals(0.0, map.remove(50));
+ }
+
+ public void testRemoveAbsent() {
+ Map<Integer, Double> generated = generateAbsent();
+
+ OpenIntToDoubleHashMap map = createFromJavaMap();
+ int mapSize = map.size();
+
+ for (Map.Entry<Integer, Double> mapEntry : generated.entrySet()) {
+ map.remove(mapEntry.getKey());
+ assertEquals(mapSize, map.size());
+ assertEquals(0.0, map.get(mapEntry.getKey()));
+ }
+ }
+
+ /**
+ * Returns a map with at least 100 elements where each element is absent from javaMap.
+ */
+ private Map<Integer, Double> generateAbsent() {
+ Map<Integer, Double> generated = new HashMap<Integer, Double>();
+ do {
+ generated.putAll(generate());
+ for (Integer key : javaMap.keySet())
+ generated.remove(key);
+ } while (generated.size() < 100);
+ return generated;
+ }
+
+ public void testCopy() {
+ OpenIntToDoubleHashMap copy =
+ new OpenIntToDoubleHashMap(createFromJavaMap());
+ assertEquals(javaMap.size(), copy.size());
+
+ for (Map.Entry<Integer, Double> mapEntry : javaMap.entrySet())
+ assertEquals(mapEntry.getValue(), copy.get(mapEntry.getKey()));
+ }
+
+ public void testContainsKey() {
+ OpenIntToDoubleHashMap map = createFromJavaMap();
+ for (Map.Entry<Integer, Double> mapEntry : javaMap.entrySet()) {
+ assertTrue(map.containsKey(mapEntry.getKey()));
+ }
+ for (Map.Entry<Integer, Double> mapEntry : generateAbsent().entrySet()) {
+ assertFalse(map.containsKey(mapEntry.getKey()));
+ }
+ for (Map.Entry<Integer, Double> mapEntry : javaMap.entrySet()) {
+ int key = mapEntry.getKey();
+ assertTrue(map.containsKey(key));
+ map.remove(key);
+ assertFalse(map.containsKey(key));
+ }
+ }
+
+ public void testIterator() {
+ OpenIntToDoubleHashMap map = createFromJavaMap();
+ OpenIntToDoubleHashMap.Iterator iterator = map.iterator();
+ for (int i = 0; i < map.size(); ++i) {
+ assertTrue(iterator.hasNext());
+ OpenIntToDoubleHashMap.Entry entry = iterator.next();
+ int key = entry.key();
+ assertTrue(map.containsKey(key));
+ assertEquals(javaMap.get(key), map.get(key), 0);
+ assertTrue(javaMap.containsKey(key));
+ }
+ assertFalse(iterator.hasNext());
+ try {
+ iterator.next();
+ } catch (NoSuchElementException nsee) {
+ // expected
+ }
+ }
+
+ public void testConcurrentModification() {
+ OpenIntToDoubleHashMap map = createFromJavaMap();
+ OpenIntToDoubleHashMap.Iterator iterator = map.iterator();
+ map.put(3, 3);
+ try {
+ iterator.next();
+ } catch (ConcurrentModificationException cme) {
+ // expected
+ }
+ }
+
+ /**
+ * Regression test for a bug in findInsertionIndex where the hashing in the second probing
+ * loop was inconsistent with the first causing duplicate keys after the right sequence
+ * of puts and removes.
+ */
+ public void testPutKeysWithCollisions() {
+ OpenIntToDoubleHashMap map = new OpenIntToDoubleHashMap();
+ int key1 = -1996012590;
+ double value1 = 1.0;
+ map.put(key1, value1);
+ int key2 = 835099822;
+ map.put(key2, value1);
+ int key3 = 1008859686;
+ map.put(key3, value1);
+ assertEquals(value1, map.get(key3));
+ assertEquals(3, map.size());
+
+ map.remove(key2);
+ double value2 = 2.0;
+ map.put(key3, value2);
+ assertEquals(value2, map.get(key3));
+ assertEquals(2, map.size());
+ }
+
+ /**
+ * Similar to testPutKeysWithCollisions() but exercises the codepaths in a slightly
+ * different manner.
+ */
+ public void testPutKeysWithCollision2() {
+ OpenIntToDoubleHashMap map = new OpenIntToDoubleHashMap();
+ int key1 = 837989881;
+ double value1 = 1.0;
+ map.put(key1, value1);
+ int key2 = 476463321;
+ map.put(key2, value1);
+ assertEquals(2, map.size());
+ assertEquals(value1, map.get(key2));
+
+ map.remove(key1);
+ double value2 = 2.0;
+ map.put(key2, value2);
+ assertEquals(1, map.size());
+ assertEquals(value2, map.get(key2));
+ }
+
+}
Propchange: commons/proper/math/trunk/src/test/org/apache/commons/math/util/OpenIntToDoubleHashMapTest.java
------------------------------------------------------------------------------
svn:eol-style = native
Propchange: commons/proper/math/trunk/src/test/org/apache/commons/math/util/OpenIntToDoubleHashMapTest.java
------------------------------------------------------------------------------
svn:keywords = Author Date Id Revision