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