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