    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    }