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.math.util; 19 20 import org.apache.commons.math.exception.DimensionMismatchException; 21 import org.apache.commons.math.exception.OutOfRangeException; 22 import org.apache.commons.math.exception.NotStrictlyPositiveException; 23 24 /** 25 * Converter between unidimensional storage structure and multidimensional 26 * conceptual structure. 27 * This utility will convert from indices in a multidimensional structure 28 * to the corresponding index in a one-dimensional array. For example, 29 * assuming that the ranges (in 3 dimensions) of indices are 2, 4 and 3, 30 * the following correspondences, between 3-tuples indices and unidimensional 31 * indices, will hold: 32 * <ul> 33 * <li>(0, 0, 0) corresponds to 0</li> 34 * <li>(0, 0, 1) corresponds to 1</li> 35 * <li>(0, 0, 2) corresponds to 2</li> 36 * <li>(0, 1, 0) corresponds to 3</li> 37 * <li>...</li> 38 * <li>(1, 0, 0) corresponds to 12</li> 39 * <li>...</li> 40 * <li>(1, 3, 2) corresponds to 23</li> 41 * </ul> 42 * @version $Revision$ $Date$ 43 * @since 2.2 44 */ 45 public class MultidimensionalCounter implements Iterable<Integer> { 46 /** 47 * Number of dimensions. 48 */ 49 private final int dimension; 50 /** 51 * Offset for each dimension. 52 */ 53 private final int[] uniCounterOffset; 54 /** 55 * Counter sizes. 56 */ 57 private final int[] size; 58 /** 59 * Total number of (one-dimensional) slots. 60 */ 61 private final int totalSize; 62 /** 63 * Index of last dimension. 64 */ 65 private final int last; 66 67 /** 68 * Perform iteration over the multidimensional counter. 69 */ 70 public class Iterator implements java.util.Iterator<Integer> { 71 /** 72 * Multidimensional counter. 73 */ 74 private final int[] counter = new int[dimension]; 75 /** 76 * Unidimensional counter. 77 */ 78 private int count = -1; 79 80 /** 81 * Create an iterator 82 * @see #iterator() 83 */ 84 Iterator() { 85 counter[last] = -1; 86 } 87 88 /** 89 * {@inheritDoc} 90 */ 91 public boolean hasNext() { 92 for (int i = 0; i < dimension; i++) { 93 if (counter[i] != size[i] - 1) { 94 return true; 95 } 96 } 97 return false; 98 } 99 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 } 317