001 /**
002 * Copyright (c) 2010, SIB. All rights reserved.
003 *
004 * SIB (Swiss Institute of Bioinformatics) - http://www.isb-sib.ch Host -
005 * https://sourceforge.net/projects/javaprotlib/
006 *
007 * Redistribution and use in source and binary forms, with or without
008 * modification, are permitted provided that the following conditions are met:
009 * Redistributions of source code must retain the above copyright notice, this
010 * list of conditions and the following disclaimer. Redistributions in binary
011 * form must reproduce the above copyright notice, this list of conditions and
012 * the following disclaimer in the documentation and/or other materials provided
013 * with the distribution. Neither the name of the SIB/GENEBIO nor the names of
014 * its contributors may be used to endorse or promote products derived from this
015 * software without specific prior written permission.
016 *
017 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
018 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
019 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
020 * ARE DISCLAIMED. IN NO EVENT SHALL SIB/GENEBIO BE LIABLE FOR ANY DIRECT,
021 * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
022 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
023 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
024 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
025 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
026 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
027 */
028 package org.expasy.jpl.commons.base.math;
029
030
031 import java.util.ArrayList;
032 import java.util.Arrays;
033 import java.util.List;
034 import org.apache.commons.collections15.Transformer;
035
036
037 /**
038 * This class generates generalized n-tuples.
039 *
040 * @author nikitin
041 *
042 * @version 1.0
043 *
044 */
045 public final class MixedRadixNtupleFactory implements
046 Transformer<int[], List<int[]>> {
047
048 /** 0..9a..z (maximum radix is Character.MAX_RADIX) */
049 private static final int CHAR_SHIFT = 'a' - 10;
050 private static final int DIGIT_SHIFT = '0';
051
052 /** each tuple have to be lesser than filter to be validated (binary mode) */
053 private int filter = Integer.MAX_VALUE;
054
055 private boolean isFilterEnabled;
056
057 private MixedRadixNtupleFactory() {}
058
059 /**
060 * Generate all tuples considering the given strict limits (excluded).
061 *
062 * @return the list of tuples from [0, ..., 0] to [l0-1, ..., ln-1]
063 */
064 public static MixedRadixNtupleFactory newInstance() {
065 return new MixedRadixNtupleFactory();
066 }
067
068 public static MixedRadixNtupleFactory newInstance(int limit) {
069 MixedRadixNtupleFactory factory = new MixedRadixNtupleFactory();
070 factory.isFilterEnabled = true;
071 factory.filter = limit;
072 return factory;
073 }
074
075 /**
076 * Compute the number of all the t-uples given the radices.
077 *
078 * @param radices the radices by position.
079 *
080 * @return the total number of t-uples.
081 */
082 public static long computeTupleNumber(final int[] radices) {
083 long product = 1;
084 for (final int limit : radices) {
085 product *= limit;
086 }
087 return product;
088 }
089
090 /**
091 * Convert a tuple from radix to radix 10 (decimal).
092 *
093 * @param radix the fixed radix (max Character.MAX_RADIX).
094 * @param tuple the tuple to compute the code from.
095 * @return the code for the given tuple.
096 *
097 * @throws BadRadixException if radix is > Character.MAX_RADIX.
098 */
099 public static int convertTuple2Decimal(final int[] tuple, final int radix)
100 throws BadRadixException {
101 final StringBuilder tupleString = new StringBuilder();
102
103 if (radix > Character.MAX_RADIX) {
104 throw new IllegalArgumentException(radix + " : radix must not"
105 + " be greater than " + Character.MAX_RADIX);
106 }
107
108 for (final int value : tuple) {
109 if (value >= 10) {
110 if (value <= Character.MAX_RADIX) {
111 // convert to char
112 tupleString.append((char) (value + CHAR_SHIFT));
113 } else {
114 throw new BadRadixException(value);
115 }
116 } else {
117 tupleString.append("" + value);
118 }
119 }
120
121 return Integer.parseInt(tupleString.toString(), radix);
122 }
123
124 /**
125 * Convert decimal to t-uple of given radix.
126 *
127 * @param radix the fixed radix (max 36)
128 * @param code the code to compute the tuple from
129 * @return the tuple for the given code
130 *
131 * @throws BadRadixException if radix > 36
132 */
133 public static int[] convertDecimal2Tuple(final int code, final int radix)
134 throws BadRadixException {
135
136 if (radix > Character.MAX_RADIX) {
137 throw new BadRadixException(radix);
138 }
139
140 return convertString2Tuple(Integer.toString(code, radix));
141 }
142
143 /**
144 * Convert decimal to t-uple of given radix.
145 *
146 * @param radix the fixed radix (max 36)
147 * @param code the code to compute the tuple from
148 * @param size the size of the returned tuple rq: if size > tuple then
149 * add '0' else truncate.
150 * @return the tuple for the given code
151 *
152 * @throws BadRadixException if radix > 36
153 */
154 public static int[] convertDecimal2Tuple(final int radix, final int code,
155 final int size) throws BadRadixException {
156
157 if (radix > Character.MAX_RADIX) {
158 throw new BadRadixException(radix);
159 }
160
161 String tuple = Integer.toString(code, radix);
162
163 final int nb0 = size - tuple.length();
164 final StringBuilder sb = new StringBuilder();
165
166 if (nb0 > 0) {
167 // add '0'
168 for (int i = 0; i < nb0; i++) {
169 sb.append('0');
170 }
171 sb.append(tuple);
172 tuple = sb.toString();
173 } else {
174 // truncate
175 tuple = tuple.substring(-nb0);
176 }
177
178 return convertString2Tuple(tuple);
179 }
180
181 /**
182 * Convert string to t-uple.
183 *
184 * @param tuple the string to convert.
185 * @return a t-uple.
186 */
187 public static int[] convertString2Tuple(final String tuple) {
188 final int[] ints = new int[tuple.length()];
189 for (int i = 0; i < ints.length; i++) {
190 final int value = tuple.charAt(i);
191 if ((value >= 'a') && (value <= 'z')) {
192 // 97 is 'a' but here equivalent to 11
193 ints[i] = tuple.charAt(i) - CHAR_SHIFT;
194 } else {
195 ints[i] = tuple.charAt(i) - DIGIT_SHIFT;
196 }
197 }
198 return ints;
199 }
200
201 /**
202 * This algorithm generate all {@code n}-tuples with same {@code radix} for
203 * any positions.
204 *
205 * @param n the number of digits.
206 * @param radix the radix for each digit.
207 *
208 * @return t-uples.
209 */
210 public List<int[]> transform(int n, int radix) {
211 int[] radices = new int[n];
212
213 for (int i = 0; i < n; i++) {
214 radices[i] = radix;
215 }
216
217 return transform(radices);
218 }
219
220 /**
221 * This algorithm generate all n-tuples where each ai have different upper
222 * limit li.
223 *
224 * [from knuth the AOCP, section 7.1.1 : Algorithm M]
225 *
226 * @param radices the limits [l0, ..., ln] such as ai in [0, li[.
227 * @return t-uples.
228 */
229 public List<int[]> transform(int[] radices) {
230 /**
231 * In mathematics, a tuple is a sequence (or ordered list) of finite
232 * length. A n-tuple is a tuple with n elements.
233 */
234 List<int[]> ntuples = new ArrayList<int[]>();
235 final int[] upperLimitsExtended = new int[radices.length + 1];
236 System.arraycopy(radices, 0, upperLimitsExtended, 1, radices.length);
237 final int[] ntuple = new int[upperLimitsExtended.length];
238
239 // M1. init
240 upperLimitsExtended[0] = 2;
241 for (int i = 0; i < ntuple.length; i++) {
242 ntuple[i] = 0;
243 }
244
245 while (true) {
246 // M2. visit current tuple : add new ntuple
247 final int[] copy = new int[ntuple.length - 1];
248 System.arraycopy(ntuple, 1, copy, 0, copy.length);
249
250 if (isFilterEnabled) {
251 if (getBitNum(copy) <= filter) {
252 ntuples.add(copy);
253 }
254 } else {
255 ntuples.add(copy);
256 }
257
258 // M3. prepare to add one
259 int i = ntuple.length - 1;
260
261 // M4. test limits
262 while (ntuple[i] == upperLimitsExtended[i] - 1) {
263 ntuple[i] = 0;
264 i--;
265 }
266
267 // M5.
268 if (i == 0) {
269 break;
270 } else {
271 ntuple[i]++;
272 }
273 }
274 return ntuples;
275 }
276
277 private static int getBitNum(int[] bits) {
278 int count = 0;
279 for (int bit : bits) {
280 count += (bit > 0) ? 1 : 0;
281 }
282 return count;
283 }
284
285 /**
286 * A simple string converter for n-tuples.
287 *
288 * @param ntuples the n-tuples to convert.
289 * @return a string representation of n-tuples.
290 */
291 public static String toString(List<int[]> ntuples) {
292 final StringBuilder sb = new StringBuilder();
293
294 // Tuples are usually written within parenthesis.
295 // For example, (2, 7, 4, 1, 7) is a 5-tuple.
296 sb.append("[");
297 for (final int[] ntuple : ntuples) {
298 sb.append(Arrays.toString(ntuple) + ", ");
299 }
300 sb.delete(sb.length() - 2, sb.length());
301 sb.append("]");
302 return sb.toString();
303 }
304
305 public static class BadRadixException extends Exception {
306
307 private static final long serialVersionUID = 4576827468762428439L;
308
309 private static final String mess =
310 "valid radix interval: [" + Character.MIN_RADIX + ", "
311 + Character.MAX_RADIX + "]";
312
313 /**
314 * @param message the exception message.
315 */
316 public BadRadixException(final int radix) {
317 super("Bad radix: " + radix + ", " + mess);
318 }
319
320 /**
321 * @param message the exception message.
322 * @param cause the cause exception.
323 */
324 public BadRadixException(final int radix, final Throwable cause) {
325 super("Bad radix: " + radix, cause);
326 }
327 }
328 }