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