001package org.cpsolver.ifs.util; 002 003import java.io.ByteArrayOutputStream; 004import java.io.File; 005import java.io.FileInputStream; 006import java.io.IOException; 007import java.io.OutputStream; 008import java.io.PrintStream; 009import java.util.ArrayList; 010import java.util.Collection; 011import java.util.Date; 012import java.util.Enumeration; 013import java.util.HashSet; 014import java.util.Iterator; 015import java.util.List; 016import java.util.Map; 017import java.util.Properties; 018import java.util.Random; 019import java.util.Set; 020import java.util.StringTokenizer; 021import java.util.TreeSet; 022 023import org.apache.log4j.Level; 024import org.apache.log4j.Logger; 025import org.apache.log4j.PropertyConfigurator; 026 027/** 028 * Several auxiliary static methods. 029 * 030 * @version IFS 1.3 (Iterative Forward Search)<br> 031 * Copyright (C) 2006 - 2014 Tomas Muller<br> 032 * <a href="mailto:muller@unitime.org">muller@unitime.org</a><br> 033 * <a href="http://muller.unitime.org">http://muller.unitime.org</a><br> 034 * <br> 035 * This library is free software; you can redistribute it and/or modify 036 * it under the terms of the GNU Lesser General Public License as 037 * published by the Free Software Foundation; either version 3 of the 038 * License, or (at your option) any later version. <br> 039 * <br> 040 * This library is distributed in the hope that it will be useful, but 041 * WITHOUT ANY WARRANTY; without even the implied warranty of 042 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 043 * Lesser General Public License for more details. <br> 044 * <br> 045 * You should have received a copy of the GNU Lesser General Public 046 * License along with this library; if not see 047 * <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>. 048 */ 049public class ToolBox { 050 private static long sSeed = System.currentTimeMillis(); 051 private static Random sRandom = new Random(sSeed); 052 053 /** Returns random number (int) from the set 0 .. limit - 1 054 * @param limit a limit 055 * @return a random number between 0 and limit - 1 056 **/ 057 public static int random(int limit) { 058 return (int) (random() * limit); 059 } 060 061 /** Returns random element from the given set of elements 062 * @param set collection of objects 063 * @param <E> some type 064 * @return randomly selected object 065 **/ 066 public static <E> E random(Collection<E> set) { 067 switch (set == null ? 0 : set.size()) { 068 case 0: 069 return null; 070 case 1: 071 return set.iterator().next(); 072 case 2: 073 Iterator<E> i = set.iterator(); 074 if (sRandom.nextBoolean()) i.next(); 075 return i.next(); 076 default: 077 List<E> v = (set instanceof List<?> ? (List<E>) set : new ArrayList<E>(set)); 078 return v.get(random(v.size())); 079 } 080 } 081 082 /** 083 * Returns a randomly generated subset of the given set 084 * 085 * @param set 086 * set 087 * @param part 088 * probability of selection of an element into the resultant 089 * subset 090 * @param <E> some type 091 * @return randomly selected subset 092 */ 093 public static <E> Collection<E> subSet(Collection<E> set, double part) { 094 return subSet(set, part, 1); 095 } 096 097 /** Swaps two elements in the list*/ 098 private static <E> void swap(List<E> list, int first, int second) { 099 E o = list.get(first); 100 list.set(first, list.get(second)); 101 list.set(second, o); 102 } 103 104 /** 105 * Returns a randomly generated subset of the given set 106 * 107 * @param set 108 * set 109 * @param part 110 * probability of selection of an element into the resultant 111 * subset 112 * @param minSize 113 * minimal size of the returned subset 114 * @param <E> some type 115 * @return randomly selected subset 116 */ 117 public static <E> Collection<E> subSet(Collection<E> set, double part, int minSize) { 118 if (set.size() <= minSize || part >= 1.0) 119 return set; 120 ArrayList<E> subSet = new ArrayList<E>(set); 121 int size = set.size(); 122 int numberToSelect = Math.max(minSize, (int) (part * set.size())); 123 for (int idx = 0; idx < numberToSelect; idx++) { 124 swap(subSet, idx, idx + (int) (random() * (size - idx))); 125 } 126 return subSet.subList(0, numberToSelect); 127 } 128 129 /** Trim a string to have given length 130 * @param s a string to trim 131 * @param length a length to trim to 132 * @return trimmed and padded string of the given length 133 **/ 134 public static String trim(String s, int length) { 135 if (s.length() > length) 136 return s.substring(0, length); 137 StringBuffer sb = new StringBuffer(s); 138 while (sb.length() < length) 139 sb.append(" "); 140 return sb.toString(); 141 } 142 143 /** Multiline representation of a collection 144 * @param col a collection 145 * @param tab tab size 146 * @return string representation 147 **/ 148 public static String col2string(Collection<?> col, int tab) { 149 StringBuffer tabsb = new StringBuffer(); 150 while (tabsb.length() < 2 * tab) 151 tabsb.append(" "); 152 StringBuffer sb = new StringBuffer("[\n"); 153 for (Iterator<?> i = col.iterator(); i.hasNext();) { 154 sb.append(tabsb + " " + i.next() + (i.hasNext() ? "," : "") + "\n"); 155 } 156 sb.append(tabsb + "]"); 157 return sb.toString(); 158 } 159 160 /** Multiline representation of a dictionary 161 * @param dict a map 162 * @param tab tab size 163 * @param <K> a key class 164 * @param <V> a value class 165 * @return string representation 166 */ 167 public static <K, V> String dict2string(Map<K, V> dict, int tab) { 168 StringBuffer tabsb = new StringBuffer(); 169 while (tabsb.length() < 2 * tab) 170 tabsb.append(" "); 171 StringBuffer sb = new StringBuffer("[\n"); 172 TreeSet<K> keys = new TreeSet<K>(dict.keySet()); 173 for (K key : keys) { 174 V value = dict.get(key); 175 sb.append(tabsb + " " + key + ": " + value + "\n"); 176 } 177 sb.append(tabsb + "]"); 178 return sb.toString(); 179 } 180 181 /** 182 * Root mean square 183 * 184 * @param n 185 * number of tests 186 * @param x 187 * total value of all tests 188 * @param x2 189 * total value^2 of all tests 190 * @return root mean square 191 */ 192 public static double rms(int n, double x, double x2) { 193 double var = x2 / n; 194 double mean = x / n; 195 return Math.sqrt(Math.abs(var - mean * mean)); 196 } 197 198 /** Merge source with target 199 * @param target target list 200 * @param source source list 201 * @param <E> some object 202 **/ 203 public static <E> void merge(List<E> target, Collection<E> source) { 204 for (E o : source) { 205 if (!target.contains(o)) 206 target.add(o); 207 } 208 } 209 210 /** Returns intersection of two collections 211 * @param source1 first collection 212 * @param source2 second collection 213 * @param <E> some object 214 * @return intersection 215 */ 216 public static <E> List<E> intersect(Collection<E> source1, Collection<E> source2) { 217 List<E> target = new ArrayList<E>(); 218 for (E o : source1) { 219 if (!source2.contains(o)) 220 target.add(o); 221 } 222 return target; 223 } 224 225 /** 226 * Sets seeds for {@link ToolBox#getRandom()} and {@link ToolBox#random()} 227 * methods. 228 * @param seed random seed 229 */ 230 public static void setSeed(long seed) { 231 sSeed = seed; 232 sRandom = new Random(sSeed); 233 } 234 235 /** Gets current seed 236 * @return random seed 237 **/ 238 public static long getSeed() { 239 return sSeed; 240 } 241 242 /** Gets random number generator 243 * @return random number generator 244 **/ 245 public static Random getRandom() { 246 return sRandom; 247 } 248 249 /** Generates random double number 250 * @return random number 251 **/ 252 public static double random() { 253 return sRandom.nextDouble(); 254 } 255 256 /** Configurates log4j loging */ 257 public static void configureLogging() { 258 Properties props = new Properties(); 259 props.setProperty("log4j.rootLogger", "DEBUG, A1"); 260 props.setProperty("log4j.appender.A1", "org.apache.log4j.ConsoleAppender"); 261 props.setProperty("log4j.appender.A1.layout", "org.apache.log4j.PatternLayout"); 262 props.setProperty("log4j.appender.A1.layout.ConversionPattern", "%-5p %c{2}: %m%n"); 263 props.setProperty("log4j.logger.net", "INFO"); 264 props.setProperty("log4j.logger.org.cpsolver", "DEBUG"); 265 props.setProperty("log4j.logger.org", "INFO"); 266 PropertyConfigurator.configure(props); 267 } 268 269 /** 270 * Configure log4j logging 271 * 272 * @param logDir 273 * output folder 274 * @param properties 275 * some other log4j properties 276 * @return name of the log file 277 */ 278 public static String configureLogging(String logDir, Properties properties) { 279 return configureLogging(logDir, properties, false); 280 } 281 282 /** 283 * Configure log4j logging 284 * 285 * @param logDir 286 * output folder 287 * @param properties 288 * some other log4j properties 289 * @param timeInFileName 290 * if true log file is named debug_yyyy-MM-dd_(HH.mm.ss).log, it 291 * is named debug.log otherwise 292 * @return name of the log file 293 */ 294 public static String configureLogging(String logDir, Properties properties, boolean timeInFileName) { 295 return configureLogging(logDir, properties, timeInFileName, true); 296 } 297 298 /** 299 * Configure log4j logging 300 * 301 * @param logDir 302 * output folder 303 * @param properties 304 * some other log4j properties 305 * @param timeInFileName 306 * if true log file is named debug_yyyy-MM-dd_(HH.mm.ss).log, it 307 * is named debug.log otherwise 308 * @param includeSystemOuts include system out and error in the log 309 * @return name of the log file 310 */ 311 public static String configureLogging(String logDir, Properties properties, boolean timeInFileName, boolean includeSystemOuts) { 312 String time = new java.text.SimpleDateFormat("yyyy-MM-dd_(HH.mm.ss)", java.util.Locale.US).format(new Date()); 313 (new File(logDir)).mkdirs(); 314 String fileName = logDir + File.separator + (timeInFileName ? "debug_" + time : "debug") + ".log"; 315 Properties props = (properties != null ? properties : new Properties()); 316 if (!props.containsKey("log4j.rootLogger")) { 317 props.setProperty("log4j.rootLogger", "debug, LogFile"); 318 if (timeInFileName) 319 props.setProperty("log4j.appender.LogFile", "org.apache.log4j.FileAppender"); 320 else { 321 props.setProperty("log4j.appender.LogFile", "org.apache.log4j.DailyRollingFileAppender"); 322 props.setProperty("log4j.appender.LogFile.DatePattern", "'.'yyyy-MM-dd"); 323 } 324 props.setProperty("log4j.appender.LogFile.File", fileName); 325 props.setProperty("log4j.appender.LogFile.layout", "org.apache.log4j.PatternLayout"); 326 props.setProperty("log4j.appender.LogFile.layout.ConversionPattern", 327 "%d{dd-MMM-yy HH:mm:ss.SSS} [%t] %-5p %c{2}> %m%n"); 328 } 329 PropertyConfigurator.configure(props); 330 Logger log = Logger.getRootLogger(); 331 log.info("-----------------------------------------------------------------------"); 332 log.info("IFS debug file"); 333 log.info(""); 334 log.info("Created: " + new Date()); 335 log.info(""); 336 log.info("System info:"); 337 log.info("System: " + System.getProperty("os.name") + " " + System.getProperty("os.version") + " " 338 + System.getProperty("os.arch")); 339 log.info("CPU: " + System.getProperty("sun.cpu.isalist") + " endian:" 340 + System.getProperty("sun.cpu.endian") + " encoding:" + System.getProperty("sun.io.unicode.encoding")); 341 log.info("Java: " + System.getProperty("java.vendor") + ", " + System.getProperty("java.runtime.name") 342 + " " + System.getProperty("java.runtime.version", System.getProperty("java.version"))); 343 log.info("User: " + System.getProperty("user.name")); 344 log.info("Timezone: " + System.getProperty("user.timezone")); 345 log.info("Working dir: " + System.getProperty("user.dir")); 346 log.info("Classpath: " + System.getProperty("java.class.path")); 347 log.info(""); 348 if (includeSystemOuts) { 349 System.setErr(new PrintStream(new LogOutputStream(System.err, Logger.getLogger("STDERR"), Level.ERROR))); 350 System.setOut(new PrintStream(new LogOutputStream(System.out, Logger.getLogger("STDOUT"), Level.DEBUG))); 351 } 352 return fileName; 353 } 354 355 /** 356 * Loads data properties. If there is INCLUDE property available, it is 357 * interpreted as semi-colon separated list of porperty files which should 358 * be also loaded (works recursively). 359 * @param propertyFile a file to read 360 * @return solver configuration 361 * 362 */ 363 public static DataProperties loadProperties(File propertyFile) { 364 FileInputStream is = null; 365 try { 366 DataProperties ret = new DataProperties(); 367 is = new FileInputStream(propertyFile); 368 ret.load(is); 369 is.close(); 370 is = null; 371 if (ret.getProperty("INCLUDE") != null) { 372 373 StringTokenizer stk = new StringTokenizer(ret.getProperty("INCLUDE"), ";"); 374 while (stk.hasMoreTokens()) { 375 String aFile = stk.nextToken(); 376 System.out.println(" Loading included file '" + aFile + "' ... "); 377 if ((new File(aFile)).exists()) 378 is = new FileInputStream(aFile); 379 if ((new File(propertyFile.getParent() + File.separator + aFile)).exists()) 380 is = new FileInputStream(propertyFile.getParent() + File.separator + aFile); 381 if (is == null) 382 System.err.println("Unable to find include file '" + aFile + "'."); 383 ret.load(is); 384 is.close(); 385 is = null; 386 } 387 ret.remove("INCLUDE"); 388 } 389 return ret; 390 } catch (Exception e) { 391 System.err.println("Unable to load property file " + propertyFile); 392 e.printStackTrace(); 393 return new DataProperties(); 394 } finally { 395 try { 396 if (is != null) 397 is.close(); 398 } catch (IOException e) { 399 } 400 } 401 } 402 403 public static boolean equals(Object o1, Object o2) { 404 return (o1 == null ? o2 == null : o1.equals(o2)); 405 } 406 407 private static class LogOutputStream extends OutputStream { 408 private Logger iLogger = null; 409 private Level iLevel = null; 410 private OutputStream iOldOutputStream; 411 private ByteArrayOutputStream iOut = new ByteArrayOutputStream(); 412 413 public LogOutputStream(OutputStream oldOutputStream, Logger logger, Level level) { 414 iLogger = logger; 415 iLevel = level; 416 iOldOutputStream = oldOutputStream; 417 } 418 419 @Override 420 public void write(int b) throws IOException { 421 iOldOutputStream.write(b); 422 if (b == '\r') 423 return; 424 if (b == '\n') { 425 iOut.flush(); 426 iLogger.log(iLevel, new String(iOut.toByteArray())); 427 iOut.reset(); 428 } else 429 iOut.write(b); 430 } 431 } 432 433 /** 434 * Convert array of elements into a list 435 * @param obj array of elements 436 * @return list of elements 437 */ 438 public static <E> List<E> toList(E... obj) { 439 List<E> ret = new ArrayList<E>(obj == null ? 0 : obj.length); 440 if (obj != null) 441 for (E e: obj) 442 ret.add(e); 443 return ret; 444 } 445 446 /** 447 * Compute number of K-tuples of N elements 448 * @param N number of elements (e.g., number of room locations in a domain) 449 * @param K size of a tuple (e.g., number of rooms a class needs) 450 * @return number of different K-tupples of N elements 451 */ 452 public static long binomial(int N, int K) { 453 long ret = 1; 454 for (int k = 0; k < K; k++) 455 ret = ret * (N-k) / (k+1); 456 return ret; 457 } 458 459 /** 460 * Create random sample (m-tuple) of given list of elements 461 * @param items list of elements 462 * @param m size of a tuple 463 * @return random subset of the list of size m 464 */ 465 public static <E> Set<E> sample(List<E> items, int m) { 466 HashSet<E> res = new HashSet<E>(m); 467 int n = items.size(); 468 for(int i = n - m; i < n; i++){ 469 int pos = getRandom().nextInt(i+1); 470 E item = items.get(pos); 471 if (res.contains(item)) 472 res.add(items.get(i)); 473 else 474 res.add(item); 475 } 476 return res; 477 } 478 479 /** 480 * Generate given permutation 481 * @param items list of elements 482 * @param m size of a tuple (permutation) 483 * @param id position of the permutation in the list of all permutations of m-tuples of the given list of elements 484 * @return given subset of the list of size m 485 */ 486 public static <E> List<E> permutation(final List<E> items, int m, long id) { 487 List<E> ret = new ArrayList<E>(); 488 int n = items.size(); 489 int p = -1; 490 for (int i = 0; i < m - 1; i++) { 491 p ++; 492 for (long r = binomial(n - p - 1, m - i - 1); r <= id; r = binomial(n - p - 1, m - i - 1)) { 493 id -= r; p ++; 494 } 495 ret.add(items.get(p)); 496 } 497 ret.add(items.get(p + 1 + (int)id)); 498 return ret; 499 } 500 501 /** 502 * Generate a list of samples of the given list 503 * @param items list of elements 504 * @param m size of a sample 505 * @param count number of samples 506 * @return list of samples (m-tuples) of the given items 507 */ 508 public static <E> Enumeration<Collection<E>> sample(final List<E> items, final int m, final int count) { 509 final long limit = binomial(items.size(), m); 510 if (count >= limit) return permutations(items, m); 511 return new Enumeration<Collection<E>>() { 512 int el = 0; 513 Set<Long> used = new HashSet<Long>(); 514 515 @Override 516 public boolean hasMoreElements() { 517 return el < count && el < limit; 518 } 519 520 @Override 521 public Set<E> nextElement() { 522 int n = items.size(); 523 for (;;) { 524 HashSet<E> res = new HashSet<E>(m); 525 TreeSet<Integer> ids = new TreeSet<Integer>(); 526 for(int i = n - m; i < n; i++){ 527 int pos = getRandom().nextInt(i+1); 528 E item = items.get(pos); 529 if (res.contains(item)) { 530 res.add(items.get(i)); 531 ids.add(i); 532 } else { 533 res.add(item); 534 ids.add(pos); 535 } 536 } 537 long fp = 0; 538 for (Integer id: ids) { 539 fp = (n * fp) + id; 540 } 541 if (used.add(fp)) { 542 el ++; 543 return res; 544 } 545 } 546 } 547 }; 548 } 549 550 /** 551 * Generate a list of all permutations of size m of the given list 552 * @param items list of elements 553 * @param m size of a permutation 554 * @return list of all permutations (m-tuples) of the given items 555 */ 556 public static <E> Enumeration<Collection<E>> permutations(final List<E> items, final int m) { 557 return new Enumeration<Collection<E>>() { 558 int n = items.size(); 559 int[] p = null; 560 561 @Override 562 public boolean hasMoreElements() { 563 return p == null || p[0] < n - m; 564 } 565 566 @Override 567 public Collection<E> nextElement() { 568 if (p == null) { 569 p = new int[m]; 570 for (int i = 0; i < m; i++) 571 p[i] = i; 572 } else { 573 for (int i = m - 1; i >= 0; i--) { 574 p[i] = p[i] + 1; 575 for (int j = i + 1; j < m; j++) 576 p[j] = p[j - 1] + 1; 577 if (i == 0 || p[i] <= n - (m - i)) break; 578 } 579 } 580 List<E> ret = new ArrayList<E>(); 581 for (int i = 0; i < m; i++) 582 ret.add(items.get(p[i])); 583 return ret; 584 } 585 }; 586 } 587 588 /** 589 * Generate a list of random samples combined of the given two lists 590 * @param items1 list of first elements 591 * @param m1 size of a first sample 592 * @param items2 list of second elements 593 * @param m2 size of a second sample 594 * @param count number of samples 595 * @return list of samples where each sample contains m1 elements of the first list and m2 elements of the second list 596 */ 597 private static <E> Enumeration<Collection<E>> sample(final List<E> items1, final int m1, final List<E> items2, final int m2, final int count) { 598 final long c1 = binomial(items1.size(), m1); 599 final long c2 = binomial(items2.size(), m2); 600 final long limit = c1 * c2; 601 if (limit <= 10l * count && 10l * count < Integer.MAX_VALUE) { 602 return new Enumeration<Collection<E>>() { 603 Set<Integer> used = new HashSet<Integer>(); 604 605 @Override 606 public boolean hasMoreElements() { 607 return used.size() < count && used.size() < limit; 608 } 609 610 @Override 611 public Collection<E> nextElement() { 612 int id; 613 do { 614 id = getRandom().nextInt((int)limit); 615 } while (!used.add(id)); 616 List<E> res = new ArrayList<E>(m1 + m2); 617 if (m1 > 0) 618 res.addAll(permutation(items1, m1, id / c2)); 619 if (m2 > 0) 620 res.addAll(permutation(items2, m2, id % c2)); 621 return res; 622 } 623 }; 624 } else { 625 return new Enumeration<Collection<E>>() { 626 int n1 = items1.size(), n2 = items2.size(); 627 int el = 0; 628 Set<Long> used = new HashSet<Long>(); 629 630 @Override 631 public boolean hasMoreElements() { 632 return el < count && el < limit; 633 } 634 635 @Override 636 public Collection<E> nextElement() { 637 for (;;) { 638 HashSet<E> res = new HashSet<E>(m1 + m2); 639 TreeSet<Integer> ids1 = new TreeSet<Integer>(); 640 if (m1 == n1) { 641 // Special case 1: first permutation contains all elements 642 res.addAll(items1); 643 } else if (m1 + 1 == n1) { 644 // Special case 2: first permutation contains all elements but one 645 int pos = getRandom().nextInt(n1); 646 for (int i = 0; i < n1; i++) 647 if (i != pos) res.add(items1.get(i)); 648 ids1.add(pos); 649 } else { 650 for(int i = n1 - m1; i < n1; i++){ 651 int pos = getRandom().nextInt(i+1); 652 E item = items1.get(pos); 653 if (res.contains(item)) { 654 res.add(items1.get(i)); 655 ids1.add(i); 656 } else { 657 res.add(item); 658 ids1.add(pos); 659 } 660 } 661 } 662 TreeSet<Integer> ids2 = new TreeSet<Integer>(); 663 if (m2 == n2) { 664 // Special case 1: second permutation contains all elements 665 res.addAll(items2); 666 } else if (m2 + 1 == n2) { 667 // Special case 2: second permutation contains all elements but one 668 int pos = getRandom().nextInt(n2); 669 for (int i = 0; i < n2; i++) 670 if (i != pos) res.add(items2.get(i)); 671 ids2.add(pos); 672 } else { 673 for(int i = n2 - m2; i < n2; i++){ 674 int pos = getRandom().nextInt(i+1); 675 E item = items2.get(pos); 676 if (res.contains(item)) { 677 res.add(items2.get(i)); 678 ids2.add(n1 + i); 679 } else { 680 res.add(item); 681 ids2.add(n1 + pos); 682 } 683 } 684 } 685 long fp = 0; 686 for (Integer id: ids1) fp = (n1 * fp) + id; 687 for (Integer id: ids2) fp = (n2 * fp) + id; 688 if (used.add(fp)) { 689 el ++; 690 return res; 691 } 692 } 693 } 694 }; 695 } 696 } 697 698 /** 699 * Generate a list of random samples combined of the given two lists 700 * @param preferred list of preferred elements 701 * @param additional list of additional elements 702 * @param m size of a sample 703 * @param count number of samples 704 * @return list of samples of size m, preferring as many elements of the preferred list as possible 705 */ 706 public static <E> Enumeration<Collection<E>> sample(final List<E> preferred, final List<E> additional, final int m, final int count) { 707 return new Enumeration<Collection<E>>() { 708 long limit = Math.min(count, binomial(preferred.size() + additional.size(), m)); 709 int k = Math.min(m, preferred.size()); 710 int el = 0; 711 Enumeration<Collection<E>> e = sample(preferred, k, additional, m - k, count); 712 713 @Override 714 public boolean hasMoreElements() { 715 return el < limit; 716 } 717 718 @Override 719 public Collection<E> nextElement() { 720 if (e.hasMoreElements()) { 721 el ++; 722 return e.nextElement(); 723 } 724 k = Math.max(Math.min(k - 1, preferred.size() - 1), 0); 725 e = sample(preferred, k, additional, m - k, count); 726 el ++; 727 return e.nextElement(); 728 } 729 }; 730 } 731}