You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@commons.apache.org by er...@apache.org on 2010/06/28 14:09:02 UTC
svn commit: r958552 - in /commons/proper/math/trunk/src:
main/java/org/apache/commons/math/util/MultidimensionalCounter.java
site/xdoc/changes.xml site/xdoc/userguide/utilities.xml
test/java/org/apache/commons/math/util/MultidimensionalCounterTest.java
Author: erans
Date: Mon Jun 28 12:09:02 2010
New Revision: 958552
URL: http://svn.apache.org/viewvc?rev=958552&view=rev
Log:
MATH-379
Added:
commons/proper/math/trunk/src/main/java/org/apache/commons/math/util/MultidimensionalCounter.java (with props)
commons/proper/math/trunk/src/test/java/org/apache/commons/math/util/MultidimensionalCounterTest.java (with props)
Modified:
commons/proper/math/trunk/src/site/xdoc/changes.xml
commons/proper/math/trunk/src/site/xdoc/userguide/utilities.xml
Added: commons/proper/math/trunk/src/main/java/org/apache/commons/math/util/MultidimensionalCounter.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/main/java/org/apache/commons/math/util/MultidimensionalCounter.java?rev=958552&view=auto
==============================================================================
--- commons/proper/math/trunk/src/main/java/org/apache/commons/math/util/MultidimensionalCounter.java (added)
+++ commons/proper/math/trunk/src/main/java/org/apache/commons/math/util/MultidimensionalCounter.java Mon Jun 28 12:09:02 2010
@@ -0,0 +1,299 @@
+/*
+ * 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.Arrays;
+import org.apache.commons.math.exception.DimensionMismatchException;
+import org.apache.commons.math.exception.OutOfRangeException;
+import org.apache.commons.math.exception.NotStrictlyPositiveException;
+
+/**
+ * Converter between unidimensional storage structure and multidimensional
+ * conceptual structure.
+ * This utility will convert from indices in a multidimensional structure
+ * to the corresponding index in a one-dimensional array. For example,
+ * assuming that the ranges (in 3 dimensions) of indices are 2, 4 and 3,
+ * the following correspondences, between 3-tuples indices and unidimensional
+ * indices, will hold:
+ * <ul>
+ * <li>(0, 0, 0) corresponds to 0</li>
+ * <li>(0, 0, 1) corresponds to 1</li>
+ * <li>(0, 0, 2) corresponds to 2</li>
+ * <li>(0, 1, 0) corresponds to 3</li>
+ * <li>...</li>
+ * <li>(1, 0, 0) corresponds to 12</li>
+ * <li>...</li>
+ * <li>(1, 3, 2) corresponds to 23</li>
+ * </ul>
+ */
+public class MultidimensionalCounter implements Iterable<Integer> {
+ /**
+ * Number of dimensions.
+ */
+ private final int dimension;
+ /**
+ * Offset for each dimension.
+ */
+ private final int[] uniCounterOffset;
+ /**
+ * Counter sizes.
+ */
+ private final int[] size;
+ /**
+ * Total number of (one-dimensional) slots.
+ */
+ private final int totalSize;
+ /**
+ * Index of last dimension.
+ */
+ private final int last;
+
+ /**
+ * Perform iteration over the multidimensional counter.
+ */
+ public class Iterator implements java.util.Iterator<Integer> {
+ /**
+ * Multidimensional counter.
+ */
+ private final int[] counter = new int[dimension];
+ /**
+ * Unidimensional counter.
+ */
+ private int count = -1;
+
+ /**
+ * Create an iterator (see {@link MultidimensionalCounter#iterator()}.
+ */
+ Iterator() {
+ counter[last] = -1;
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ public boolean hasNext() {
+ for (int i = 0; i < dimension; i++) {
+ if (counter[i] != size[i] - 1) {
+ return true;
+ }
+ }
+ return false;
+ }
+
+ /**
+ * @return the unidimensional count after the counter has been
+ * incremented by {@code 1}.
+ */
+ public Integer next() {
+ for (int i = last; i >= 0; i--) {
+ if (counter[i] == size[i] - 1) {
+ counter[i] = 0;
+ } else {
+ ++counter[i];
+ break;
+ }
+ }
+
+ return ++count;
+ }
+
+ /**
+ * Get the current unidimensional counter slot.
+ *
+ * @return the index within the unidimensionl counter.
+ */
+ public int getCount() {
+ return count;
+ }
+ /**
+ * Get the current multidimensional counter slots.
+ *
+ * @return the indices within the multidimensional counter.
+ */
+ public int[] getCounts() {
+ return Arrays.copyOf(counter, dimension);
+ }
+
+ /**
+ * Get the current count in the selected dimension.
+ *
+ * @param dim Dimension index.
+ * @return the count at the corresponding index for the current state
+ * of the iterator.
+ * @throws IndexOutOfBoundsException if {@code index} is not in the
+ * correct interval (as defined by the length of the argument in the
+ * {@link MultidimensionalCounter#MultidimensionalCounter(int[])
+ * constructor of the enclosing class}).
+ */
+ public int getCount(int dim) {
+ return counter[dim];
+ }
+
+ /**
+ * @throws UnsupportedOperationException.
+ */
+ public void remove() {
+ throw new UnsupportedOperationException();
+ }
+ }
+
+ /**
+ * Create a counter.
+ *
+ * @param size Counter sizes (number of slots in each dimension).
+ * @throws {@link NotStrictlyPositiveException} if one of the sizes is
+ * negative or zero.
+ */
+ public MultidimensionalCounter(int ... size) {
+ dimension = size.length;
+ this.size = Arrays.copyOf(size, dimension);
+
+ uniCounterOffset = new int[dimension];
+
+ last = dimension - 1;
+ int tS = size[last];
+ for (int i = 0; i < last; i++) {
+ int count = 1;
+ for (int j = i + 1; j < dimension; j++) {
+ count *= size[j];
+ }
+ uniCounterOffset[i] = count;
+ tS *= size[i];
+ }
+ uniCounterOffset[last] = 0;
+
+ if (tS <= 0) {
+ throw new NotStrictlyPositiveException(tS);
+ }
+
+ totalSize = tS;
+ }
+
+ /**
+ * Create an iterator over this counter.
+ *
+ * @return the iterator.
+ */
+ public Iterator iterator() {
+ return new Iterator();
+ }
+
+ /**
+ * Get the number of dimensions of the multidimensional counter.
+ *
+ * @return the number of dimensions.
+ */
+ public int getDimension() {
+ return dimension;
+ }
+
+ /**
+ * Convert to multidimensional counter.
+ *
+ * @param index Index in unidimensional counter.
+ * @returns the multidimensional counts.
+ * @throws {@link OutOfRangeException} if {@code index} is not between
+ * {@code 0} and the value returned by {@link #getSize()} (excluded).
+ */
+ public int[] getCounts(int index) {
+ if (index < 0
+ || index >= totalSize) {
+ throw new OutOfRangeException(index, 0, totalSize);
+ }
+
+ final int[] indices = new int[dimension];
+
+ int count = 0;
+ for (int i = 0; i < last; i++) {
+ int idx = 0;
+ final int offset = uniCounterOffset[i];
+ while (count <= index) {
+ count += offset;
+ ++idx;
+ }
+ --idx;
+ count -= offset;
+ indices[i] = idx;
+ }
+
+ int idx = 1;
+ while (count < index) {
+ count += idx;
+ ++idx;
+ }
+ --idx;
+ indices[last] = idx;
+
+ return indices;
+ }
+
+ /**
+ * Convert to unidimensional counter.
+ *
+ * @param c Indices in multidimensional counter.
+ * @return the index within the unidimensionl counter.
+ * @throws {@link DimensionMismatchException} if the size of {@code c}
+ * does not match the size of the array given in the contructor.
+ * @throws {@link OutOfRangeException} if a value of {@code c} is not in
+ * the range of the corresponding dimension, as defined in the
+ * {@link #MultidimensionalCounter(int[]) constructor}.
+ */
+ public int getCount(int ... c) {
+ if (c.length != dimension) {
+ throw new DimensionMismatchException(c.length, dimension);
+ }
+ int count = 0;
+ for (int i = 0; i < dimension; i++) {
+ final int index = c[i];
+ if (index < 0
+ || index >= size[i]) {
+ throw new OutOfRangeException(index, 0, size[i] - 1);
+ }
+ count += uniCounterOffset[i] * c[i];
+ }
+ return count + c[last];
+ }
+
+ /**
+ * Get the total number of elements.
+ *
+ * @return the total size of the unidimensional counter.
+ */
+ public int getSize() {
+ return totalSize;
+ }
+ /**
+ * Get the number of multidimensional counter slots in each dimension.
+ *
+ * @return the sizes of the multidimensional counter in each dimension.
+ */
+ public int[] getSizes() {
+ return Arrays.copyOf(size, dimension);
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ public String toString() {
+ final StringBuilder sb = new StringBuilder();
+ for (int i = 0; i < dimension; i++) {
+ sb.append("[").append(getCount(i)).append("]");
+ }
+ return sb.toString();
+ }
+}
Propchange: commons/proper/math/trunk/src/main/java/org/apache/commons/math/util/MultidimensionalCounter.java
------------------------------------------------------------------------------
svn:eol-style = native
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=958552&r1=958551&r2=958552&view=diff
==============================================================================
--- commons/proper/math/trunk/src/site/xdoc/changes.xml (original)
+++ commons/proper/math/trunk/src/site/xdoc/changes.xml Mon Jun 28 12:09:02 2010
@@ -52,6 +52,9 @@ The <action> type attribute can be add,u
If the output is not quite correct, check for invisible trailing spaces!
-->
<release version="2.2" date="TBD" description="TBD">
+ <action dev="erans" type="add" issue="MATH-379">
+ Created "MultidimensionalCounter" class.
+ </action>
<action dev="erans" type="add" issue="MATH-361">
Created package "exception" to contain the new exceptions hierarchy.
</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=958552&r1=958551&r2=958552&view=diff
==============================================================================
--- commons/proper/math/trunk/src/site/xdoc/userguide/utilities.xml (original)
+++ commons/proper/math/trunk/src/site/xdoc/userguide/utilities.xml Mon Jun 28 12:09:02 2010
@@ -152,7 +152,7 @@
<a href="../apidocs/org/apache/commons/math/util/MathUtils.html">MathUtils</a>
utility class. MathUtils currently includes methods to compute the following: <ul>
<li>
- Binomial coeffiecients -- "n choose k" available as an (exact) long value,
+ Binomial coefficients -- "n choose k" available as an (exact) long value,
<code>binomialCoefficient(int, int)</code> for small n, k; as a double,
<code>binomialCoefficientDouble(int, int)</code> for larger values; and in
a "super-sized" version, <code>binomialCoefficientLog(int, int)</code>
@@ -182,6 +182,13 @@
</p>
</subsection>
+<subsection name="6.7 Miscellaneous" href="math_utils">
+ The <a href="../apidocs/org/apache/commons/math/util/MultidimensionalCounter.html">
+ MultidimensionalCounter</a> is a utility class that converts a set of indices
+ (identifying points in a multidimensional space) to a single index (e.g. identifying
+ a location in a one-dimensional array.
+</subsection>
+
</section>
</body>
Added: commons/proper/math/trunk/src/test/java/org/apache/commons/math/util/MultidimensionalCounterTest.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/test/java/org/apache/commons/math/util/MultidimensionalCounterTest.java?rev=958552&view=auto
==============================================================================
--- commons/proper/math/trunk/src/test/java/org/apache/commons/math/util/MultidimensionalCounterTest.java (added)
+++ commons/proper/math/trunk/src/test/java/org/apache/commons/math/util/MultidimensionalCounterTest.java Mon Jun 28 12:09:02 2010
@@ -0,0 +1,169 @@
+/*
+ * 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 org.apache.commons.math.exception.DimensionMismatchException;
+import org.apache.commons.math.exception.OutOfRangeException;
+import org.apache.commons.math.exception.NotStrictlyPositiveException;
+import org.junit.Assert;
+import org.junit.Test;
+
+/**
+ *
+ */
+public class MultidimensionalCounterTest {
+ @Test
+ public void testPreconditions() {
+ MultidimensionalCounter c;
+
+ try {
+ c = new MultidimensionalCounter(0, 1);
+ Assert.fail("NotStrictlyPositiveException expected");
+ } catch (NotStrictlyPositiveException e) {
+ // Expected.
+ }
+ try {
+ c = new MultidimensionalCounter(2, 0);
+ Assert.fail("NotStrictlyPositiveException expected");
+ } catch (NotStrictlyPositiveException e) {
+ // Expected.
+ }
+ try {
+ c = new MultidimensionalCounter(-1, 1);
+ Assert.fail("NotStrictlyPositiveException expected");
+ } catch (NotStrictlyPositiveException e) {
+ // Expected.
+ }
+
+ c = new MultidimensionalCounter(2, 3);
+ try {
+ c.getCount(1, 1, 1);
+ Assert.fail("DimensionMismatchException expected");
+ } catch (DimensionMismatchException e) {
+ // Expected.
+ }
+ try {
+ c.getCount(3, 1);
+ Assert.fail("OutOfRangeException expected");
+ } catch (OutOfRangeException e) {
+ // Expected.
+ }
+ try {
+ c.getCount(0, -1);
+ Assert.fail("OutOfRangeException expected");
+ } catch (OutOfRangeException e) {
+ // Expected.
+ }
+ try {
+ c.getCounts(-1);
+ Assert.fail("OutOfRangeException expected");
+ } catch (OutOfRangeException e) {
+ // Expected.
+ }
+ try {
+ c.getCounts(6);
+ Assert.fail("OutOfRangeException expected");
+ } catch (OutOfRangeException e) {
+ // Expected.
+ }
+ }
+
+ @Test
+ public void testIteratorPreconditions() {
+ MultidimensionalCounter.Iterator iter = (new MultidimensionalCounter(2, 3)).iterator();
+ try {
+ iter.getCount(-1);
+ Assert.fail("IndexOutOfBoundsException expected");
+ } catch (IndexOutOfBoundsException e) {
+ // Expected.
+ }
+ try {
+ iter.getCount(2);
+ Assert.fail("IndexOutOfBoundsException expected");
+ } catch (IndexOutOfBoundsException e) {
+ // Expected.
+ }
+ }
+
+ @Test
+ public void testMulti2UniConversion() {
+ final MultidimensionalCounter c = new MultidimensionalCounter(2, 4, 5);
+ Assert.assertEquals(c.getCount(1, 2, 3), 33);
+ }
+
+ @Test
+ public void testAccessors() {
+ final int[] originalSize = new int[] {2, 6, 5};
+ final MultidimensionalCounter c = new MultidimensionalCounter(originalSize);
+ final int nDim = c.getDimension();
+ Assert.assertEquals(nDim, originalSize.length);
+
+ final int[] size = c.getSizes();
+ for (int i = 0; i < nDim; i++) {
+ Assert.assertEquals(originalSize[i], size[i]);
+ }
+ }
+
+ @Test
+ public void testIterationConsistency() {
+ final MultidimensionalCounter c = new MultidimensionalCounter(2, 3, 2);
+ final int[][] expected = new int[][] {
+ { 0, 0, 0 },
+ { 0, 0, 1 },
+ { 0, 1, 0 },
+ { 0, 1, 1 },
+ { 0, 2, 0 },
+ { 0, 2, 1 },
+ { 1, 0, 0 },
+ { 1, 0, 1 },
+ { 1, 1, 0 },
+ { 1, 1, 1 },
+ { 1, 2, 0 },
+ { 1, 2, 1 }
+ };
+
+ final int totalSize = c.getSize();
+ final int nDim = c.getDimension();
+ final MultidimensionalCounter.Iterator iter = c.iterator();
+ for (int i = 0; i < totalSize; i++) {
+ if (!iter.hasNext()) {
+ Assert.fail("Too short");
+ }
+ final int uniDimIndex = iter.next();
+ Assert.assertEquals("Wrong iteration at " + i, i, uniDimIndex);
+
+ for (int dimIndex = 0; dimIndex < nDim; dimIndex++) {
+ Assert.assertEquals("Wrong multidimensional index for [" + i + "][" + dimIndex + "]",
+ expected[i][dimIndex], iter.getCount(dimIndex));
+ }
+
+ Assert.assertEquals("Wrong unidimensional index for [" + i + "]",
+ c.getCount(expected[i]), uniDimIndex);
+
+ final int[] indices = c.getCounts(uniDimIndex);
+ for (int dimIndex = 0; dimIndex < nDim; dimIndex++) {
+ Assert.assertEquals("Wrong multidimensional index for [" + i + "][" + dimIndex + "]",
+ expected[i][dimIndex], indices[dimIndex]);
+ }
+ }
+
+ if (iter.hasNext()) {
+ Assert.fail("Too long");
+ }
+ }
+}
Propchange: commons/proper/math/trunk/src/test/java/org/apache/commons/math/util/MultidimensionalCounterTest.java
------------------------------------------------------------------------------
svn:eol-style = native