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 }