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