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 }