View Javadoc
1   /*
2    * Licensed to the Apache Software Foundation (ASF) under one or more
3    * contributor license agreements.  See the NOTICE file distributed with
4    * this work for additional information regarding copyright ownership.
5    * The ASF licenses this file to You under the Apache License, Version 2.0
6    * (the "License"); you may not use this file except in compliance with
7    * the License.  You may obtain a copy of the License at
8    *
9    *      http://www.apache.org/licenses/LICENSE-2.0
10   *
11   * Unless required by applicable law or agreed to in writing, software
12   * distributed under the License is distributed on an "AS IS" BASIS,
13   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14   * See the License for the specific language governing permissions and
15   * limitations under the License.
16   */
17  
18  package org.apache.commons.numbers.arrays;
19  
20  import java.util.Arrays;
21  
22  /**
23   * Converter between unidimensional storage structure and multidimensional
24   * conceptual structure.
25   * This utility will convert from indices in a multidimensional structure
26   * to the corresponding index in a one-dimensional array. For example,
27   * assuming that the ranges (in 3 dimensions) of indices are 2, 4 and 3,
28   * the following correspondences, between 3-tuples indices and unidimensional
29   * indices, will hold:
30   * <ul>
31   *  <li>(0, 0, 0) corresponds to 0</li>
32   *  <li>(0, 0, 1) corresponds to 1</li>
33   *  <li>(0, 0, 2) corresponds to 2</li>
34   *  <li>(0, 1, 0) corresponds to 3</li>
35   *  <li>...</li>
36   *  <li>(1, 0, 0) corresponds to 12</li>
37   *  <li>...</li>
38   *  <li>(1, 3, 2) corresponds to 23</li>
39   * </ul>
40   */
41  public final class MultidimensionalCounter {
42      /**
43       * Number of dimensions.
44       */
45      private final int dimension;
46      /**
47       * Offset for each dimension.
48       */
49      private final int[] uniCounterOffset;
50      /**
51       * Counter sizes.
52       */
53      private final int[] size;
54      /**
55       * Total number of (one-dimensional) slots.
56       */
57      private final int totalSize;
58      /**
59       * Index of last dimension.
60       */
61      private final int last;
62  
63      /**
64       * Creates a counter.
65       *
66       * @param size Counter sizes (number of slots in each dimension).
67       * @throws IllegalArgumentException if one of the sizes is negative
68       * or zero.
69       */
70      private MultidimensionalCounter(int... size) {
71          dimension = size.length;
72          this.size = Arrays.copyOf(size, size.length);
73  
74          uniCounterOffset = new int[dimension];
75  
76          last = dimension - 1;
77          uniCounterOffset[last] = 1;
78  
79          int tS = 1;
80          for (int i = last - 1; i >= 0; i--) {
81              final int index = i + 1;
82              checkStrictlyPositive("index size", size[index]);
83              tS *= size[index];
84              checkStrictlyPositive("cumulative size", tS);
85              uniCounterOffset[i] = tS;
86          }
87  
88          totalSize = tS * size[0];
89          checkStrictlyPositive("total size", totalSize);
90      }
91  
92      /**
93       * Creates a counter.
94       *
95       * @param size Counter sizes (number of slots in each dimension).
96       * @return a new instance.
97       * @throws IllegalArgumentException if one of the sizes is negative
98       * or zero.
99       */
100     public static MultidimensionalCounter of(int... size) {
101         return new MultidimensionalCounter(size);
102     }
103 
104     /**
105      * Gets the number of dimensions of the multidimensional counter.
106      *
107      * @return the number of dimensions.
108      */
109     public int getDimension() {
110         return dimension;
111     }
112 
113     /**
114      * Converts to a multidimensional counter.
115      *
116      * @param index Index in unidimensional counter.
117      * @return the multidimensional counts.
118      * @throws IndexOutOfBoundsException if {@code index} is not between
119      * {@code 0} and the value returned by {@link #getSize()} (excluded).
120      */
121     public int[] toMulti(int index) {
122         if (index < 0 ||
123             index >= totalSize) {
124             throw new IndexOutOfBoundsException(createIndexOutOfBoundsMessage(totalSize, index));
125         }
126 
127         final int[] indices = new int[dimension];
128 
129         for (int i = 0; i < last; i++) {
130             indices[i] = index / uniCounterOffset[i];
131             // index = index % uniCounterOffset[i]
132             index = index - indices[i] * uniCounterOffset[i];
133         }
134 
135         indices[last] = index;
136 
137         return indices;
138     }
139 
140     /**
141      * Converts to a unidimensional counter.
142      *
143      * @param c Indices in multidimensional counter.
144      * @return the index within the unidimensionl counter.
145      * @throws IllegalArgumentException if the size of {@code c}
146      * does not match the size of the array given in the constructor.
147      * @throws IndexOutOfBoundsException if a value of {@code c} is not in
148      * the range of the corresponding dimension, as defined in the
149      * {@link MultidimensionalCounter#of(int...) constructor}.
150      */
151     public int toUni(int... c) {
152         if (c.length != dimension) {
153             throw new IllegalArgumentException("Wrong number of arguments: " + c.length +
154                                                "(expected: " + dimension + ")");
155         }
156         int count = 0;
157         for (int i = 0; i < dimension; i++) {
158             final int index = c[i];
159             if (index < 0 ||
160                 index >= size[i]) {
161                 throw new IndexOutOfBoundsException(createIndexOutOfBoundsMessage(size[i], index));
162             }
163             count += uniCounterOffset[i] * index;
164         }
165         return count;
166     }
167 
168     /**
169      * Gets the total number of elements.
170      *
171      * @return the total size of the unidimensional counter.
172      */
173     public int getSize() {
174         return totalSize;
175     }
176 
177     /**
178      * Gets the number of multidimensional counter slots in each dimension.
179      *
180      * @return the number of slots in each dimension.
181      */
182     public int[] getSizes() {
183         return Arrays.copyOf(size, size.length);
184     }
185 
186     /** {@inheritDoc} */
187     @Override
188     public String toString() {
189         return Arrays.toString(size);
190     }
191 
192     /**
193      * Check the size is strictly positive: {@code size > 0}.
194      *
195      * @param name the name of the size
196      * @param size the size
197      */
198     private static void checkStrictlyPositive(String name, int size) {
199         if (size <= 0) {
200             throw new IllegalArgumentException("Not positive " + name + ": " + size);
201         }
202     }
203 
204     /**
205      * Creates the message for the index out of bounds exception.
206      *
207      * @param size the size
208      * @param index the index
209      * @return the message
210      */
211     private static String createIndexOutOfBoundsMessage(int size, int index) {
212         return "Index out of bounds [0, " + (size - 1) + "]: " + index;
213     }
214 }