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