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    
018    package org.apache.commons.math3.util;
019    
020    import org.apache.commons.math3.exception.DimensionMismatchException;
021    import org.apache.commons.math3.exception.NotStrictlyPositiveException;
022    import 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     */
046    public 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    }