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.math3.util;
019
020import java.util.NoSuchElementException;
021import org.apache.commons.math3.exception.DimensionMismatchException;
022import org.apache.commons.math3.exception.NotStrictlyPositiveException;
023import org.apache.commons.math3.exception.OutOfRangeException;
024
025/**
026 * Converter between unidimensional storage structure and multidimensional
027 * conceptual structure.
028 * This utility will convert from indices in a multidimensional structure
029 * to the corresponding index in a one-dimensional array. For example,
030 * assuming that the ranges (in 3 dimensions) of indices are 2, 4 and 3,
031 * the following correspondences, between 3-tuples indices and unidimensional
032 * indices, will hold:
033 * <ul>
034 *  <li>(0, 0, 0) corresponds to 0</li>
035 *  <li>(0, 0, 1) corresponds to 1</li>
036 *  <li>(0, 0, 2) corresponds to 2</li>
037 *  <li>(0, 1, 0) corresponds to 3</li>
038 *  <li>...</li>
039 *  <li>(1, 0, 0) corresponds to 12</li>
040 *  <li>...</li>
041 *  <li>(1, 3, 2) corresponds to 23</li>
042 * </ul>
043 *
044 * @since 2.2
045 * @version $Id: MultidimensionalCounter.java 1558833 2014-01-16 15:26:29Z erans $
046 */
047public class MultidimensionalCounter implements Iterable<Integer> {
048    /**
049     * Number of dimensions.
050     */
051    private final int dimension;
052    /**
053     * Offset for each dimension.
054     */
055    private final int[] uniCounterOffset;
056    /**
057     * Counter sizes.
058     */
059    private final int[] size;
060    /**
061     * Total number of (one-dimensional) slots.
062     */
063    private final int totalSize;
064    /**
065     * Index of last dimension.
066     */
067    private final int last;
068
069    /**
070     * Perform iteration over the multidimensional counter.
071     */
072    public class Iterator implements java.util.Iterator<Integer> {
073        /**
074         * Multidimensional counter.
075         */
076        private final int[] counter = new int[dimension];
077        /**
078         * Unidimensional counter.
079         */
080        private int count = -1;
081        /**
082         * Maximum value for {@link #count}.
083         */
084        private final int maxCount = totalSize - 1;
085
086        /**
087         * Create an iterator
088         * @see #iterator()
089         */
090        Iterator() {
091            counter[last] = -1;
092        }
093
094        /**
095         * {@inheritDoc}
096         */
097        public boolean hasNext() {
098            return count < maxCount;
099        }
100
101        /**
102         * @return the unidimensional count after the counter has been
103         * incremented by {@code 1}.
104         * @throws NoSuchElementException if {@link #hasNext()} would have
105         * returned {@code false}.
106         */
107        public Integer next() {
108            if (!hasNext()) {
109                throw new NoSuchElementException();
110            }
111
112            for (int i = last; i >= 0; i--) {
113                if (counter[i] == size[i] - 1) {
114                    counter[i] = 0;
115                } else {
116                    ++counter[i];
117                    break;
118                }
119            }
120
121            return ++count;
122        }
123
124        /**
125         * Get the current unidimensional counter slot.
126         *
127         * @return the index within the unidimensionl counter.
128         */
129        public int getCount() {
130            return count;
131        }
132        /**
133         * Get the current multidimensional counter slots.
134         *
135         * @return the indices within the multidimensional counter.
136         */
137        public int[] getCounts() {
138            return MathArrays.copyOf(counter);
139        }
140
141        /**
142         * Get the current count in the selected dimension.
143         *
144         * @param dim Dimension index.
145         * @return the count at the corresponding index for the current state
146         * of the iterator.
147         * @throws IndexOutOfBoundsException if {@code index} is not in the
148         * correct interval (as defined by the length of the argument in the
149         * {@link MultidimensionalCounter#MultidimensionalCounter(int[])
150         * constructor of the enclosing class}).
151         */
152        public int getCount(int dim) {
153            return counter[dim];
154        }
155
156        /**
157         * @throws UnsupportedOperationException
158         */
159        public void remove() {
160            throw new UnsupportedOperationException();
161        }
162    }
163
164    /**
165     * Create a counter.
166     *
167     * @param size Counter sizes (number of slots in each dimension).
168     * @throws NotStrictlyPositiveException if one of the sizes is
169     * negative or zero.
170     */
171    public MultidimensionalCounter(int ... size) throws NotStrictlyPositiveException {
172        dimension = size.length;
173        this.size = MathArrays.copyOf(size);
174
175        uniCounterOffset = new int[dimension];
176
177        last = dimension - 1;
178        int tS = size[last];
179        for (int i = 0; i < last; i++) {
180            int count = 1;
181            for (int j = i + 1; j < dimension; j++) {
182                count *= size[j];
183            }
184            uniCounterOffset[i] = count;
185            tS *= size[i];
186        }
187        uniCounterOffset[last] = 0;
188
189        if (tS <= 0) {
190            throw new NotStrictlyPositiveException(tS);
191        }
192
193        totalSize = tS;
194    }
195
196    /**
197     * Create an iterator over this counter.
198     *
199     * @return the iterator.
200     */
201    public Iterator iterator() {
202        return new Iterator();
203    }
204
205    /**
206     * Get the number of dimensions of the multidimensional counter.
207     *
208     * @return the number of dimensions.
209     */
210    public int getDimension() {
211        return dimension;
212    }
213
214    /**
215     * Convert to multidimensional counter.
216     *
217     * @param index Index in unidimensional counter.
218     * @return the multidimensional counts.
219     * @throws OutOfRangeException if {@code index} is not between
220     * {@code 0} and the value returned by {@link #getSize()} (excluded).
221     */
222    public int[] getCounts(int index) throws OutOfRangeException {
223        if (index < 0 ||
224            index >= totalSize) {
225            throw new OutOfRangeException(index, 0, totalSize);
226        }
227
228        final int[] indices = new int[dimension];
229
230        int count = 0;
231        for (int i = 0; i < last; i++) {
232            int idx = 0;
233            final int offset = uniCounterOffset[i];
234            while (count <= index) {
235                count += offset;
236                ++idx;
237            }
238            --idx;
239            count -= offset;
240            indices[i] = idx;
241        }
242
243        indices[last] = index - count;
244
245        return indices;
246    }
247
248    /**
249     * Convert to unidimensional counter.
250     *
251     * @param c Indices in multidimensional counter.
252     * @return the index within the unidimensionl counter.
253     * @throws DimensionMismatchException if the size of {@code c}
254     * does not match the size of the array given in the constructor.
255     * @throws OutOfRangeException if a value of {@code c} is not in
256     * the range of the corresponding dimension, as defined in the
257     * {@link MultidimensionalCounter#MultidimensionalCounter(int...) constructor}.
258     */
259    public int getCount(int ... c)
260        throws OutOfRangeException, DimensionMismatchException {
261        if (c.length != dimension) {
262            throw new DimensionMismatchException(c.length, dimension);
263        }
264        int count = 0;
265        for (int i = 0; i < dimension; i++) {
266            final int index = c[i];
267            if (index < 0 ||
268                index >= size[i]) {
269                throw new OutOfRangeException(index, 0, size[i] - 1);
270            }
271            count += uniCounterOffset[i] * c[i];
272        }
273        return count + c[last];
274    }
275
276    /**
277     * Get the total number of elements.
278     *
279     * @return the total size of the unidimensional counter.
280     */
281    public int getSize() {
282        return totalSize;
283    }
284    /**
285     * Get the number of multidimensional counter slots in each dimension.
286     *
287     * @return the sizes of the multidimensional counter in each dimension.
288     */
289    public int[] getSizes() {
290        return MathArrays.copyOf(size);
291    }
292
293    /**
294     * {@inheritDoc}
295     */
296    @Override
297    public String toString() {
298        final StringBuilder sb = new StringBuilder();
299        for (int i = 0; i < dimension; i++) {
300            sb.append("[").append(getCount(i)).append("]");
301        }
302        return sb.toString();
303    }
304}