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 2019/12/16 12:28:25 UTC
[commons-numbers] 04/04: NUMBERS-140: Multidimensional counter.
This is an automated email from the ASF dual-hosted git repository.
erans pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/commons-numbers.git
commit 0d66b94d4096793a9ce457eb841a20ef74410899
Author: Gilles Sadowski <gi...@harfang.homelinux.org>
AuthorDate: Mon Dec 16 13:23:21 2019 +0100
NUMBERS-140: Multidimensional counter.
Ported from "Commons Math".
---
.../numbers/arrays/MultidimensionalCounter.java | 198 +++++++++++++++++++++
.../arrays/MultidimensionalCounterTest.java | 160 +++++++++++++++++
2 files changed, 358 insertions(+)
diff --git a/commons-numbers-arrays/src/main/java/org/apache/commons/numbers/arrays/MultidimensionalCounter.java b/commons-numbers-arrays/src/main/java/org/apache/commons/numbers/arrays/MultidimensionalCounter.java
new file mode 100644
index 0000000..bf30849
--- /dev/null
+++ b/commons-numbers-arrays/src/main/java/org/apache/commons/numbers/arrays/MultidimensionalCounter.java
@@ -0,0 +1,198 @@
+/*
+ * 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.numbers.arrays;
+
+import java.util.Arrays;
+
+/**
+ * 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 {
+ /**
+ * 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;
+
+ /**
+ * Creates a counter.
+ *
+ * @param size Counter sizes (number of slots in each dimension).
+ * @throws IllegalArgumentException if one of the sizes is negative
+ * or zero.
+ */
+ private MultidimensionalCounter(int ... size) {
+ dimension = size.length;
+ this.size = Arrays.copyOf(size, size.length);
+
+ uniCounterOffset = new int[dimension];
+
+ last = dimension - 1;
+ uniCounterOffset[last] = 1;
+
+ int tS = 1;
+ for (int i = last - 1; i >= 0; i--) {
+ final int index = i + 1;
+ tS *= size[index];
+ uniCounterOffset[i] = tS;
+ }
+
+ totalSize = tS * size[0];
+ if (totalSize <= 0) {
+ throw new IllegalArgumentException("Negative size: " + totalSize);
+ }
+ }
+
+ /**
+ * Creates a counter.
+ *
+ * @param size Counter sizes (number of slots in each dimension).
+ * @return a new instance.
+ * @throws IllegalArgumentException if one of the sizes is negative
+ * or zero.
+ */
+ public static MultidimensionalCounter of(int ... size) {
+ return new MultidimensionalCounter(size);
+ }
+
+ /**
+ * Gets the number of dimensions of the multidimensional counter.
+ *
+ * @return the number of dimensions.
+ */
+ public int getDimension() {
+ return dimension;
+ }
+
+ /**
+ * Converts to multidimensional counter.
+ *
+ * @param index Index in unidimensional counter.
+ * @return the multidimensional counts.
+ * @throws IndexOutOfBoundsException if {@code index} is not between
+ * {@code 0} and the value returned by {@link #getSize()} (excluded).
+ */
+ public int[] toMulti(int index) {
+ if (index < 0 ||
+ index >= totalSize) {
+ throw new IndexOutOfBoundsException("Index out of bounds [0, " + (totalSize - 1) + "]: " + index);
+ }
+
+ 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;
+ }
+
+ indices[last] = index - count;
+
+ return indices;
+ }
+
+ /**
+ * Converts to unidimensional counter.
+ *
+ * @param c Indices in multidimensional counter.
+ * @return the index within the unidimensionl counter.
+ * @throws IllegalArgumentException if the size of {@code c}
+ * does not match the size of the array given in the constructor.
+ * @throws IndexOutOfBoundsException if a value of {@code c} is not in
+ * the range of the corresponding dimension, as defined in the
+ * {@link MultidimensionalCounter#MultidimensionalCounter(int...) constructor}.
+ */
+ public int toUni(int ... c) {
+ if (c.length != dimension) {
+ throw new IllegalArgumentException("Wrong number of arguments: " + c.length +
+ "(expected: " + dimension + ")");
+ }
+ int count = 0;
+ for (int i = 0; i < dimension; i++) {
+ final int index = c[i];
+ if (index < 0 ||
+ index >= size[i]) {
+ throw new IndexOutOfBoundsException("Index out of bounds [0, " + (size[i] - 1) + "]: " + index);
+ }
+ count += uniCounterOffset[i] * index;
+ }
+ return count;
+ }
+
+ /**
+ * Gets the total number of elements.
+ *
+ * @return the total size of the unidimensional counter.
+ */
+ public int getSize() {
+ return totalSize;
+ }
+
+ /**
+ * Gets the number of multidimensional counter slots in each dimension.
+ *
+ * @return the number of slots in each dimension.
+ */
+ public int[] getSizes() {
+ return Arrays.copyOf(size, size.length);
+ }
+
+ /** {@inheritDoc} */
+ @Override
+ public String toString() {
+ return Arrays.toString(size);
+ }
+}
diff --git a/commons-numbers-arrays/src/test/java/org/apache/commons/numbers/arrays/MultidimensionalCounterTest.java b/commons-numbers-arrays/src/test/java/org/apache/commons/numbers/arrays/MultidimensionalCounterTest.java
new file mode 100644
index 0000000..746cfeb
--- /dev/null
+++ b/commons-numbers-arrays/src/test/java/org/apache/commons/numbers/arrays/MultidimensionalCounterTest.java
@@ -0,0 +1,160 @@
+/*
+ * 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.numbers.arrays;
+
+import java.util.Arrays;
+import org.junit.jupiter.api.Assertions;
+import org.junit.jupiter.api.Test;
+
+/**
+ * Test cases for the {@link MultidimensionalCounter} class.
+ *
+ */
+public class MultidimensionalCounterTest {
+ @Test
+ public void testPreconditions() {
+ MultidimensionalCounter c;
+
+ try {
+ c = MultidimensionalCounter.of(0, 1);
+ Assertions.fail("IllegalArgumentException expected");
+ } catch (IllegalArgumentException e) {
+ // Expected.
+ }
+ try {
+ c = MultidimensionalCounter.of(2, 0);
+ Assertions.fail("IllegalArgumentException expected");
+ } catch (IllegalArgumentException e) {
+ // Expected.
+ }
+ try {
+ c = MultidimensionalCounter.of(-1, 1);
+ Assertions.fail("IllegalArgumentException expected");
+ } catch (IllegalArgumentException e) {
+ // Expected.
+ }
+
+ c = MultidimensionalCounter.of(2, 3);
+ try {
+ c.toUni(1, 1, 1);
+ Assertions.fail("IllegalArgumentException expected");
+ } catch (IllegalArgumentException e) {
+ // Expected.
+ }
+ try {
+ c.toUni(3, 1);
+ Assertions.fail("IndexOutOfBoundsException expected");
+ } catch (IndexOutOfBoundsException e) {
+ // Expected.
+ }
+ try {
+ c.toUni(0, -1);
+ Assertions.fail("IndexOutOfBoundsException expected");
+ } catch (IndexOutOfBoundsException e) {
+ // Expected.
+ }
+ try {
+ c.toMulti(-1);
+ Assertions.fail("IndexOutOfBoundsException expected");
+ } catch (IndexOutOfBoundsException e) {
+ // Expected.
+ }
+ try {
+ c.toMulti(6);
+ Assertions.fail("IndexOutOfBoundsException expected");
+ } catch (IndexOutOfBoundsException e) {
+ // Expected.
+ }
+ }
+
+ @Test
+ public void testMulti2UniConversion() {
+ final MultidimensionalCounter c = MultidimensionalCounter.of(2, 4, 5);
+ Assertions.assertEquals(33, c.toUni(1, 2, 3));
+
+ for (int i = 0, max = c.getSize(); i < max; i++) {
+ Assertions.assertEquals(i, c.toUni(c.toMulti(i)));
+ }
+ }
+
+ @Test
+ public void testAccessors() {
+ final int[] originalSize = new int[] {2, 6, 5};
+ final MultidimensionalCounter c = MultidimensionalCounter.of(originalSize);
+ final int nDim = c.getDimension();
+ Assertions.assertEquals(nDim, originalSize.length);
+
+ final int[] size = c.getSizes();
+ for (int i = 0; i < nDim; i++) {
+ Assertions.assertEquals(originalSize[i], size[i]);
+ }
+ }
+
+ @Test
+ public void testIterationConsistency() {
+ final MultidimensionalCounter c = MultidimensionalCounter.of(2, 3, 4);
+ final int[][] expected = new int[][] {
+ { 0, 0, 0 },
+ { 0, 0, 1 },
+ { 0, 0, 2 },
+ { 0, 0, 3 },
+ { 0, 1, 0 },
+ { 0, 1, 1 },
+ { 0, 1, 2 },
+ { 0, 1, 3 },
+ { 0, 2, 0 },
+ { 0, 2, 1 },
+ { 0, 2, 2 },
+ { 0, 2, 3 },
+ { 1, 0, 0 },
+ { 1, 0, 1 },
+ { 1, 0, 2 },
+ { 1, 0, 3 },
+ { 1, 1, 0 },
+ { 1, 1, 1 },
+ { 1, 1, 2 },
+ { 1, 1, 3 },
+ { 1, 2, 0 },
+ { 1, 2, 1 },
+ { 1, 2, 2 },
+ { 1, 2, 3 }
+ };
+
+ final int totalSize = c.getSize();
+ Assertions.assertEquals(expected.length, totalSize);
+
+ final int nDim = c.getDimension();
+ for (int i = 0; i < totalSize; i++) {
+ Assertions.assertEquals(i, c.toUni(expected[i]),
+ "Wrong unidimensional index for [" + i + "]");
+
+ final int[] indices = c.toMulti(i);
+ for (int dimIndex = 0; dimIndex < nDim; dimIndex++) {
+ Assertions.assertEquals(expected[i][dimIndex], indices[dimIndex],
+ "Wrong multidimensional index for [" + i + "][" + dimIndex + "]");
+ }
+ }
+ }
+
+ @Test
+ public void testToString() {
+ final int[] sizes = new int[] { 7, 5, 3, 1 };
+ final MultidimensionalCounter c = MultidimensionalCounter.of(sizes);
+ Assertions.assertEquals(Arrays.toString(sizes), c.toString());
+ }
+}