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}