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
018package org.apache.commons.numbers.arrays;
019
020import java.util.Arrays;
021
022/**
023 * Converter between unidimensional storage structure and multidimensional
024 * conceptual structure.
025 * This utility will convert from indices in a multidimensional structure
026 * to the corresponding index in a one-dimensional array. For example,
027 * assuming that the ranges (in 3 dimensions) of indices are 2, 4 and 3,
028 * the following correspondences, between 3-tuples indices and unidimensional
029 * indices, will hold:
030 * <ul>
031 *  <li>(0, 0, 0) corresponds to 0</li>
032 *  <li>(0, 0, 1) corresponds to 1</li>
033 *  <li>(0, 0, 2) corresponds to 2</li>
034 *  <li>(0, 1, 0) corresponds to 3</li>
035 *  <li>...</li>
036 *  <li>(1, 0, 0) corresponds to 12</li>
037 *  <li>...</li>
038 *  <li>(1, 3, 2) corresponds to 23</li>
039 * </ul>
040 */
041public final class MultidimensionalCounter {
042    /**
043     * Number of dimensions.
044     */
045    private final int dimension;
046    /**
047     * Offset for each dimension.
048     */
049    private final int[] uniCounterOffset;
050    /**
051     * Counter sizes.
052     */
053    private final int[] size;
054    /**
055     * Total number of (one-dimensional) slots.
056     */
057    private final int totalSize;
058    /**
059     * Index of last dimension.
060     */
061    private final int last;
062
063    /**
064     * Creates a counter.
065     *
066     * @param size Counter sizes (number of slots in each dimension).
067     * @throws IllegalArgumentException if one of the sizes is negative
068     * or zero.
069     */
070    private MultidimensionalCounter(int... size) {
071        dimension = size.length;
072        this.size = Arrays.copyOf(size, size.length);
073
074        uniCounterOffset = new int[dimension];
075
076        last = dimension - 1;
077        uniCounterOffset[last] = 1;
078
079        int tS = 1;
080        for (int i = last - 1; i >= 0; i--) {
081            final int index = i + 1;
082            checkStrictlyPositive("index size", size[index]);
083            tS *= size[index];
084            checkStrictlyPositive("cumulative size", tS);
085            uniCounterOffset[i] = tS;
086        }
087
088        totalSize = tS * size[0];
089        checkStrictlyPositive("total size", totalSize);
090    }
091
092    /**
093     * Creates a counter.
094     *
095     * @param size Counter sizes (number of slots in each dimension).
096     * @return a new instance.
097     * @throws IllegalArgumentException if one of the sizes is negative
098     * or zero.
099     */
100    public static MultidimensionalCounter of(int... size) {
101        return new MultidimensionalCounter(size);
102    }
103
104    /**
105     * Gets the number of dimensions of the multidimensional counter.
106     *
107     * @return the number of dimensions.
108     */
109    public int getDimension() {
110        return dimension;
111    }
112
113    /**
114     * Converts to a multidimensional counter.
115     *
116     * @param index Index in unidimensional counter.
117     * @return the multidimensional counts.
118     * @throws IndexOutOfBoundsException if {@code index} is not between
119     * {@code 0} and the value returned by {@link #getSize()} (excluded).
120     */
121    public int[] toMulti(int index) {
122        if (index < 0 ||
123            index >= totalSize) {
124            throw new IndexOutOfBoundsException(createIndexOutOfBoundsMessage(totalSize, index));
125        }
126
127        final int[] indices = new int[dimension];
128
129        for (int i = 0; i < last; i++) {
130            indices[i] = index / uniCounterOffset[i];
131            // index = index % uniCounterOffset[i]
132            index = index - indices[i] * uniCounterOffset[i];
133        }
134
135        indices[last] = index;
136
137        return indices;
138    }
139
140    /**
141     * Converts to a unidimensional counter.
142     *
143     * @param c Indices in multidimensional counter.
144     * @return the index within the unidimensionl counter.
145     * @throws IllegalArgumentException if the size of {@code c}
146     * does not match the size of the array given in the constructor.
147     * @throws IndexOutOfBoundsException if a value of {@code c} is not in
148     * the range of the corresponding dimension, as defined in the
149     * {@link MultidimensionalCounter#of(int...) constructor}.
150     */
151    public int toUni(int... c) {
152        if (c.length != dimension) {
153            throw new IllegalArgumentException("Wrong number of arguments: " + c.length +
154                                               "(expected: " + dimension + ")");
155        }
156        int count = 0;
157        for (int i = 0; i < dimension; i++) {
158            final int index = c[i];
159            if (index < 0 ||
160                index >= size[i]) {
161                throw new IndexOutOfBoundsException(createIndexOutOfBoundsMessage(size[i], index));
162            }
163            count += uniCounterOffset[i] * index;
164        }
165        return count;
166    }
167
168    /**
169     * Gets the total number of elements.
170     *
171     * @return the total size of the unidimensional counter.
172     */
173    public int getSize() {
174        return totalSize;
175    }
176
177    /**
178     * Gets the number of multidimensional counter slots in each dimension.
179     *
180     * @return the number of slots in each dimension.
181     */
182    public int[] getSizes() {
183        return Arrays.copyOf(size, size.length);
184    }
185
186    /** {@inheritDoc} */
187    @Override
188    public String toString() {
189        return Arrays.toString(size);
190    }
191
192    /**
193     * Check the size is strictly positive: {@code size > 0}.
194     *
195     * @param name the name of the size
196     * @param size the size
197     */
198    private static void checkStrictlyPositive(String name, int size) {
199        if (size <= 0) {
200            throw new IllegalArgumentException("Not positive " + name + ": " + size);
201        }
202    }
203
204    /**
205     * Creates the message for the index out of bounds exception.
206     *
207     * @param size the size
208     * @param index the index
209     * @return the message
210     */
211    private static String createIndexOutOfBoundsMessage(int size, int index) {
212        return "Index out of bounds [0, " + (size - 1) + "]: " + index;
213    }
214}