    001package net.sf.cpsolver.studentsct;
    002
    003import java.text.DecimalFormat;
    004import java.util.Comparator;
    005import java.util.HashMap;
    006import java.util.Iterator;
    007import java.util.TreeSet;
    008
    009import net.sf.cpsolver.ifs.util.JProf;
    010
    011/**
    012 * A test class to demonstrate and compare different online sectioning
    013 * approaches. It assumes only a single course with just one instructional type
    014 * (subpart) and that we know the correct expected demand in advance. <br>
    015 * <br>
    016 * With the given configuration (e.g., two sections of size 5), it tries all
    017 * combinations of students how they can be enrolled and compute average and
    018 * worst case scenarios. <br>
    019 * <br>
    020 * Execution:<br>
    021 * &nbsp;&nbsp;&nbsp;&nbsp;java -cp cpsolver-all-1.1.jar
    022 * net.sf.cpsolver.studentsct.OnlineSectProof n1 n2 n3 ...<br>
    023 * where n1, n2, etc. are the sizes of particular sections, e.g., 10 10 for two
    024 * sections of size 10. <br>
    025 * <br>
    026 *
    027 * @version StudentSct 1.2 (Student Sectioning)<br>
    028 *          Copyright (C) 2007 - 2010 Tomáš Müller<br>
    029 *          <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
    030 *          <a href="http://muller.unitime.org">http://muller.unitime.org</a><br>
    031 * <br>
    032 *          This library is free software; you can redistribute it and/or modify
    033 *          it under the terms of the GNU Lesser General Public License as
    034 *          published by the Free Software Foundation; either version 3 of the
    035 *          License, or (at your option) any later version. <br>
    036 * <br>
    037 *          This library is distributed in the hope that it will be useful, but
    038 *          WITHOUT ANY WARRANTY; without even the implied warranty of
    039 *          MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
    040 *          Lesser General Public License for more details. <br>
    041 * <br>
    042 *          You should have received a copy of the GNU Lesser General Public
    043 *          License along with this library; if not see
    044 *          <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>.
    045 */
    046public class OnlineSectProof {
    047    private static DecimalFormat sDF = new DecimalFormat("0.000");
    048
    049    /** A representation of a long number of given base. */
    050    public static class Sequence {
    051        private int iBase;
    052        private int[] iSequence;
    053        private int[] iCnt;
    054
    055        /**
    056         * Constructor
    057         *
    058         * @param length
    059         *            size of the vector
    060         * @param base
    061         *            base (e.g., 2 for a binary vector)
    062         */
    063        public Sequence(int length, int base) {
    064            iSequence = new int[length];
    065            for (int i = 0; i < iSequence.length; i++)
    066                iSequence[i] = 0;
    067            iCnt = new int[base];
    068            for (int i = 0; i < iCnt.length; i++)
    069                iCnt[i] = 0;
    070            iCnt[0] = length;
    071            iBase = base;
    072        }
    073
    074        /**
    075         * Increment vector by 1, returns false it flips from the highest
    076         * possible number to zero
    077         */
    078        public boolean inc() {
    079            return inc(0);
    080        }
    081
    082        /** Base of the sequence */
    083        public int base() {
    084            return iBase;
    085        }
    086
    087        private boolean inc(int pos) {
    088            if (pos >= iSequence.length)
    089                return false;
    090            iCnt[iSequence[pos]]--;
    091            iSequence[pos] = (iSequence[pos] + 1) % iBase;
    092            iCnt[iSequence[pos]]++;
    093            if (iSequence[pos] == 0)
    094                return inc(pos + 1);
    095            return true;
    096        }
    097
    098        /** Count number of occurrences of given number in the sequence */
    099        public int count(int i) {
    100            return iCnt[i];
    101        }
    102
    103        /** Size of the sequence */
    104        public int size() {
    105            return iSequence.length;
    106        }
    107
    108        /**
    109         * Return number on the given position, zero is the number of the least
    110         * significant value, size()-1 is the highest one
    111         */
    112        public int seq(int i) {
    113            return iSequence[i];
    114        }
    115
    116        /**
    117         * Set the sequence from a string representation (A..0, B..1, C..2,
    118         * etc.)
    119         */
    120        public void set(String seq) {
    121            for (int i = 0; i < iCnt.length; i++)
    122                iCnt[i] = 0;
    123            for (int i = 0; i < iSequence.length; i++) {
    124                iSequence[i] = (seq.charAt(i) - 'A');
    125                iCnt[iSequence[i]]++;
    126            }
    127        }
    128
    129        /**
    130         * String representation (A..0, B..1, C..2, etc.) going from the least
    131         * significant value to the highest
    132         */
    133        @Override
    134        public String toString() {
    135            StringBuffer s = new StringBuffer();
    136            for (int i = 0; i < iSequence.length; i++)
    137                s.append((char) ('A' + iSequence[i]));
    138            return s.toString();
    139        }
    140
    141        /**
    142         * If a sequence of all zeros is considered as 0, and the highest
    143         * possible sequence (sequence of all base-1) is 1, this returns the
    144         * position of the current sequence between these two bounds.
    145         */
    146        public double progress() {
    147            double ret = 0.0;
    148            double mx = 1.0;
    149            for (int i = size() - 1; i >= 0; i--) {
    150                ret += mx * (iSequence[i]) / iBase;
    151                mx *= 1.0 / iBase;
    152            }
    153            return ret;
    154        }
    155
    156        /**
    157         * Category of a sequence, i.e., a string representation of the count of
    158         * each number in the sequence. E.g., A5B3C1 means that there are 5
    159         * zeros, 3 ones, and 1 two int the sequence.
    160         */
    161        public String cat() {
    162            StringBuffer s = new StringBuffer();
    163            for (int i = 0; i < iBase; i++)
    164                if (iCnt[i] > 0) {
    165                    s.append((char) ('A' + i));
    166                    s.append(iCnt[i]);
    167                }
    168            return s.toString();
    169        }
    170    }
    171
    172    /**
    173     * Extension of {@link OnlineSectProof.Sequence} that represents an ordered
    174     * set of students as they are to be enrolled into a course (given set of
    175     * sections).
    176     */
    177    public static class StudentSequence extends Sequence {
    178        private int[] iColumns;
    179        private int[] iMaxCnt;
    180
    181        /**
    182         * Constructor
    183         *
    184         * @param columns
    185         *            limits of sections of a course (e.g., new int[] {5, 10}
    186         *            for two sections, first of the size 5, second of the size
    187         *            of 10)
    188         */
    189        public StudentSequence(int[] columns) {
    190            super(length(columns), base(columns.length));
    191            iColumns = columns;
    192            iMaxCnt = new int[base()];
    193            for (int i = 0; i < iMaxCnt.length; i++)
    194                iMaxCnt[i] = maxCnt(i);
    195        }
    196
    197        /*
    198         * Number of columns, i.e., number of sections in a course.
    199         */
    200        public int nrColumns() {
    201            return iColumns.length;
    202        }
    203
    204        /**
    205         * Limit of a column (section of a course).
    206         */
    207        public int limit(int col) {
    208            return iColumns[col];
    209        }
    210
    211        /**
    212         * Check that the underlying sequence is a valid sequence of students.
    213         * I.e., that each student can be enrolled into a section.
    214         *
    215         * @return true, if valid
    216         */
    217        public boolean check() {
    218            for (int i = 0; i < base(); i++)
    219                if (maxCnt(i) < count(i))
    220                    return false;
    221            for (int c = 0; c < nrColumns(); c++) {
    222                int allowed = 0;
    223                for (int i = 0; i < size() && allowed < limit(c); i++)
    224                    if (allow(seq(i), c))
    225                        allowed++;
    226                if (allowed < limit(c))
    227                    return false;
    228            }
    229            return true;
    230        }
    231
    232        private static int length(int columns[]) {
    233            int len = 0;
    234            for (int i = 0; i < columns.length; i++)
    235                len += columns[i];
    236            return len;
    237        }
    238
    239        private static int base(int nrColumns) {
    240            return (1 << nrColumns) - 1;
    241        }
    242
    243        /**
    244         * Check whether it is possible to allow student of given type into the
    245         * given section. Student type can be seen as a binary string that has 1
    246         * for each section into which a student can be enrolled. I.e., student
    247         * of type 0 can be enrolled into the fist section, type 2 into the
    248         * second section, type 3 into both first and section section, type 4
    249         * into the third section, type 5 into the first and third section etc.
    250         */
    251        public boolean allow(int x, int col) {
    252            return ((x + 1) & (1 << col)) != 0;
    253        }
    254
    255        /**
    256         * Number of sections into which a student of a given type can be
    257         * enrolled (see {@link OnlineSectProof.StudentSequence#allow(int, int)}
    258         * ).
    259         */
    260        public int nrAllow(int x) {
    261            int ret = 0;
    262            for (int i = 0; i < nrColumns(); i++)
    263                if (allow(x, i))
    264                    ret++;
    265            return ret;
    266        }
    267
    268        /**
    269         * Maximum number of student of the given type that can be enrolled into
    270         * the provided sections (i.e., sum of limits of sections that are
    271         * allowed fot the student of the given type, see
    272         * {@link OnlineSectProof.StudentSequence#allow(int, int)}).
    273         */
    274        public int maxCnt(int x) {
    275            int ret = 0;
    276            for (int i = 0; i < nrColumns(); i++)
    277                if (allow(x, i))
    278                    ret += limit(i);
    279            return ret;
    280        }
    281    }
    282
    283    /** Implemented online algorithms (heuristics) */
    284    public static String sOnlineAlgs[] = new String[] { "Max(Available)", "Min(Used/Limit)", "Min(Expected-Available)",
    285            "Min(Expected/Available)", "Min((Expected-Available)/Limit)", "Min(Expected/(Available*Limit))" };
    286
    287    /**
    288     * Return true, if the given heuristics should be skipped (not evaluated).
    289     *
    290     * @param computeExpectations
    291     *            true, if expected demand should be computed in advance
    292     * @param alg
    293     *            online algorithm (see {@link OnlineSectProof#sOnlineAlgs})
    294     * @param allTheSame
    295     *            true, if all the sections are of the same size
    296     * @return true if the given heuristics does not need to be computed (e.g.,
    297     *         it is the same of some other)
    298     */
    299    public static boolean skip(boolean computeExpectations, int alg, boolean allTheSame) {
    300        switch (alg) {
    301            case 0:
    302                return !computeExpectations;
    303            case 1:
    304                return !computeExpectations;
    305        }
    306        return false;
    307    }
    308
    309    /**
    310     * Implementation of the sectioning algorithms.
    311     *
    312     * @param limit
    313     *            section limit
    314     * @param used
    315     *            number of space already used
    316     * @param expected
    317     *            expected demand for the given section
    318     * @param alg
    319     *            online algorithm (see {@link OnlineSectProof#sOnlineAlgs})
    320     * @return value that is to be minimized (i.e., a section with the lowest
    321     *         number will be picked for the student)
    322     */
    323    public static double onlineObjective(double limit, double used, double expected, int alg) {
    324        double available = limit - used;
    325        switch (alg) {
    326            case 0:
    327                return -available;
    328            case 1:
    329                return used / limit;
    330            case 2:
    331                return expected - available;
    332            case 3:
    333                return expected / available;
    334            case 4:
    335                return (expected - available) / limit;
    336            case 5:
    337                return expected / (available * limit);
    338        }
    339        return 0.0;
    340    }
    341
    342    /**
    343     * Section given sequence of students into the course and return the number
    344     * of students that cannot be sectioned.
    345     *
    346     * @param sq
    347     *            sequence of studends
    348     * @param computeExpectations
    349     *            true, if expected demand for each section should be computed
    350     *            in advance (otherwise, it is initially set to zero)
    351     * @param alg
    352     *            online algorithm (see {@link OnlineSectProof#sOnlineAlgs})
    353     * @param debug
    354     *            if true, some debug messages are printed
    355     * @return number of students that will not be sectioned in such a case
    356     */
    357    public static int checkOnline(StudentSequence sq, boolean computeExpectations, int alg, boolean debug) {
    358        int used[] = new int[sq.nrColumns()];
    359        double exp[] = new double[sq.nrColumns()];
    360        for (int i = 0; i < sq.nrColumns(); i++) {
    361            used[i] = 0;
    362            exp[i] = 0.0;
    363        }
    364        if (computeExpectations) {
    365            for (int i = 0; i < sq.size(); i++) {
    366                int x = sq.seq(i);
    367                double ex = 1.0 / sq.nrAllow(x);
    368                for (int c = 0; c < sq.nrColumns(); c++) {
    369                    if (!sq.allow(x, c))
    370                        continue;
    371                    exp[c] += ex;
    372                }
    373            }
    374        }
    375        if (debug) {
    376            StringBuffer sbExp = new StringBuffer();
    377            StringBuffer sbUse = new StringBuffer();
    378            for (int c = 0; c < sq.nrColumns(); c++) {
    379                if (c > 0) {
    380                    sbExp.append(",");
    381                    sbUse.append(",");
    382                }
    383                sbExp.append(sDF.format(exp[c]));
    384                sbUse.append(used[c]);
    385            }
    386            System.out.println("      -- initial USE:[" + sbUse + "], EXP:[" + sbExp + "], SQ:" + sq.toString()
    387                    + ", ALG:" + sOnlineAlgs[alg]);
    388        }
    389        int ret = 0;
    390        for (int i = 0; i < sq.size(); i++) {
    391            int x = sq.seq(i);
    392            int bestCol = -1;
    393            double bestObj = 0.0;
    394            for (int c = 0; c < sq.nrColumns(); c++) {
    395                if (!sq.allow(x, c))
    396                    continue;
    397                if (used[c] >= sq.limit(c))
    398                    continue;
    399                double obj = onlineObjective(sq.limit(c), used[c], exp[c], alg);
    400                if (debug)
    401                    System.out.println("      -- test " + ((char) ('A' + x)) + " --> " + (c + 1) + " (OBJ="
    402                            + sDF.format(obj) + ")");
    403                if (bestCol < 0 || bestObj > obj) {
    404                    bestCol = c;
    405                    bestObj = obj;
    406                }
    407            }
    408            if (bestCol >= 0) {
    409                used[bestCol]++;
    410                double ex = 1.0 / sq.nrAllow(x);
    411                for (int c = 0; c < sq.nrColumns(); c++) {
    412                    if (!sq.allow(x, c))
    413                        continue;
    414                    exp[c] -= ex;
    415                }
    416                if (debug) {
    417                    StringBuffer sbExp = new StringBuffer();
    418                    StringBuffer sbUse = new StringBuffer();
    419                    for (int c = 0; c < sq.nrColumns(); c++) {
    420                        if (c > 0) {
    421                            sbExp.append(",");
    422                            sbUse.append(",");
    423                        }
    424                        sbExp.append(sDF.format(exp[c]));
    425                        sbUse.append(used[c]);
    426                    }
    427                    System.out.println("    " + ((char) ('A' + x)) + " --> " + (bestCol + 1) + " (OBJ="
    428                            + sDF.format(bestObj) + ", USE:[" + sbUse + "], EXP:[" + sbExp + "])");
    429                }
    430            } else {
    431                if (debug)
    432                    System.out.println("    " + ((char) ('A' + x)) + " --> FAIL");
    433                ret++;
    434            }
    435        }
    436        return ret;
    437    }
    438
    439    /** Simple integer counter */
    440    public static class Counter {
    441        private int iCnt = 0;
    442
    443        /** A counter starting from zero */
    444        public Counter() {
    445        }
    446
    447        /** A counter starting from the given number */
    448        public Counter(int init) {
    449            iCnt = init;
    450        }
    451
    452        /** Increase counter by one */
    453        public void inc() {
    454            iCnt++;
    455        }
    456
    457        /** Increase counter by the given value */
    458        public void inc(int val) {
    459            iCnt += val;
    460        }
    461
    462        /** Return counter value */
    463        public int intValue() {
    464            return iCnt;
    465        }
    466    }
    467
    468    /** Comparison of two categories */
    469    public static class CatCmp implements Comparator<String> {
    470        HashMap<String, Integer> iWorstCaseCat;
    471        HashMap<String, Counter> iTotalCat, iCountCat;
    472
    473        /**
    474         * Constructor
    475         *
    476         * @param countCat
    477         *            table (category, number of sequences of that category)
    478         * @param totalCat
    479         *            table (category, total number of students that were not
    480         *            sectioned of a sequence from this category)
    481         * @param worstCaseCat
    482         *            (category, worst number of students that were not
    483         *            sectioned of a sequence from this category)
    484         */
    485        public CatCmp(HashMap<String, Counter> countCat, HashMap<String, Counter> totalCat,
    486                HashMap<String, Integer> worstCaseCat) {
    487            iWorstCaseCat = worstCaseCat;
    488            iTotalCat = totalCat;
    489            iCountCat = countCat;
    490        }
    491
    492        /**
    493         * Higher number of not-sectioned students in the worst case goes first.
    494         * If the same, higher average number of not-sectioned students goes
    495         * first. If the same, compare by category.
    496         */
    497        @Override
    498        public int compare(String c1, String c2) {
    499            int wc1 = (iWorstCaseCat.get(c1)).intValue();
    500            int wc2 = (iWorstCaseCat.get(c2)).intValue();
    501            int cmp = Double.compare(wc2, wc1);
    502            if (cmp != 0)
    503                return cmp;
    504            int cc1 = (iCountCat.get(c1)).intValue();
    505            int tc1 = (iTotalCat.get(c1)).intValue();
    506            int cc2 = (iCountCat.get(c2)).intValue();
    507            int tc2 = (iTotalCat.get(c2)).intValue();
    508            cmp = Double.compare(((double) tc2) / cc2, ((double) tc1) / cc1);
    509            if (cmp != 0)
    510                return cmp;
    511            return c1.compareTo(c2);
    512        }
    513    }
    514
    515    /**
    516     * Test given course (set of sections)
    517     *
    518     * @param args
    519     *            set of integers -- limits of each sections
    520     */
    521    @SuppressWarnings("unchecked")
    522    public static void main(String[] args) {
    523        int[] x = new int[args.length];
    524        for (int i = 0; i < args.length; i++)
    525            x[i] = Integer.parseInt(args[i]);
    526        if (args.length == 0)
    527            x = new int[] { 5, 5 };
    528        boolean categories = "true".equals(System.getProperty("cat", "true"));
    529        boolean allTheSameSize = true;
    530        String filter = System.getProperty("filter");
    531
    532        StudentSequence sq = new StudentSequence(x);
    533        System.out.println("base: " + sq.base());
    534        System.out.println("columns:");
    535        int sameSize = -1;
    536        for (int col = 0; col < x.length; col++) {
    537            System.out.println("  " + (col + 1) + ". column of limit " + sq.limit(col));
    538            if (sameSize < 0)
    539                sameSize = sq.limit(col);
    540            else if (sameSize != sq.limit(col))
    541                allTheSameSize = false;
    542        }
    543        System.out.println("combinations:");
    544        for (int i = 0; i < sq.base(); i++) {
    545            System.out.println("  case " + (char) ('A' + i) + ": ");
    546            System.out.println("    max: " + sq.maxCnt(i));
    547            for (int col = 0; col < x.length; col++) {
    548                if (sq.allow(i, col))
    549                    System.out.println("      " + (col + 1) + ". column allowed");
    550            }
    551        }
    552
    553        if (System.getProperty("check") != null) {
    554            sq.set(System.getProperty("check"));
    555            if (System.getProperty("case") != null) {
    556                int i = Integer.parseInt(System.getProperty("case")) - 1;
    557                System.out.println("Online sectioning #" + (i + 1) + " " + sOnlineAlgs[i / 2]
    558                        + ((i % 2) == 0 ? "" : " w/o precomputed expectations"));
    559                checkOnline(sq, (i % 2) == 0, i / 2, true);
    560            } else {
    561                for (int i = 0; i < 2 * sOnlineAlgs.length; i++) {
    562                    if (skip((i % 2) == 0, i / 2, allTheSameSize))
    563                        continue;
    564                    System.out.println("Online sectioning #" + (i + 1) + " " + sOnlineAlgs[i / 2]
    565                            + ((i % 2) == 0 ? "" : " w/o precomputed expectations"));
    566                    checkOnline(sq, (i % 2) == 0, i / 2, true);
    567                }
    568            }
    569            return;
    570        }
    571
    572        TreeSet<String>[] worstCaseSq = new TreeSet[2 * sOnlineAlgs.length];
    573        int[] worstCase = new int[2 * sOnlineAlgs.length];
    574        int[] total = new int[2 * sOnlineAlgs.length];
    575        HashMap<String, String>[] worstCaseSqCat = new HashMap[2 * sOnlineAlgs.length];
    576        HashMap<String, Integer>[] worstCaseCat = new HashMap[2 * sOnlineAlgs.length];
    577        HashMap<String, Counter>[] totalCat = new HashMap[2 * sOnlineAlgs.length];
    578        HashMap<String, Counter>[] countCat = new HashMap[2 * sOnlineAlgs.length];
    579        for (int i = 0; i < 2 * sOnlineAlgs.length; i++) {
    580            total[i] = 0;
    581            worstCase[i] = -1;
    582            worstCaseSq[i] = null;
    583            worstCaseSqCat[i] = new HashMap<String, String>();
    584            worstCaseCat[i] = new HashMap<String, Integer>();
    585            totalCat[i] = new HashMap<String, Counter>();
    586            countCat[i] = new HashMap<String, Counter>();
    587        }
    588        long nrCases = 0;
    589        System.out.println("N=" + sDF.format(Math.pow(sq.base(), sq.size())));
    590        long t0 = JProf.currentTimeMillis();
    591        long mark = t0;
    592        long nc = 0, hc = 0;
    593        do {
    594            // System.out.println(sq+" (cat="+sq.cat()+", check="+sq.check()+")");
    595            if ((filter == null || filter.equals(sq.cat())) && sq.check()) {
    596                for (int i = 0; i < 2 * sOnlineAlgs.length; i++) {
    597                    if (skip((i % 2) == 0, i / 2, allTheSameSize))
    598                        continue;
    599                    int onl = checkOnline(sq, (i % 2) == 0, i / 2, false);
    600                    total[i] += onl;
    601                    if (worstCaseSq[i] == null || worstCase[i] < onl) {
    602                        if (worstCaseSq[i] == null)
    603                            worstCaseSq[i] = new TreeSet<String>();
    604                        else
    605                            worstCaseSq[i].clear();
    606                        worstCaseSq[i].add(sq.toString());
    607                        worstCase[i] = onl;
    608                    } else if (worstCase[i] == onl && onl > 0 && worstCaseSq[i].size() < 100) {
    609                        worstCaseSq[i].add(sq.toString());
    610                    }
    611                    if (categories) {
    612                        String cat = sq.cat();
    613                        Counter cc = countCat[i].get(cat);
    614                        if (cc == null) {
    615                            countCat[i].put(cat, new Counter(1));
    616                        } else {
    617                            cc.inc();
    618                        }
    619                        if (onl > 0) {
    620                            Counter tc = totalCat[i].get(cat);
    621                            if (tc == null) {
    622                                totalCat[i].put(cat, new Counter(onl));
    623                            } else {
    624                                tc.inc(onl);
    625                            }
    626                            Integer wc = worstCaseCat[i].get(cat);
    627                            if (wc == null || wc.intValue() < onl) {
    628                                worstCaseCat[i].put(cat, new Integer(onl));
    629                                worstCaseSqCat[i].put(cat, sq.toString());
    630                            }
    631                        }
    632                    }
    633                }
    634                nrCases++;
    635                hc++;
    636            }
    637            nc++;
    638            if ((nc % 1000000) == 0) {
    639                mark = JProf.currentTimeMillis();
    640                double progress = sq.progress();
    641                double exp = ((1.0 - progress) / progress) * (mark - t0);
    642                System.out.println("  " + sDF.format(100.0 * progress) + "% done in "
    643                        + sDF.format((mark - t0) / 60000.0) + " min (" + sDF.format(exp / 60000.0) + " min to go, hit "
    644                        + sDF.format(100.0 * hc / nc) + "%)");
    645            }
    646        } while (sq.inc());
    647        System.out.println("Number of combinations:" + nrCases + " (hit " + sDF.format(100.0 * hc / nc) + "%)");
    648        for (int i = 0; i < 2 * sOnlineAlgs.length; i++) {
    649            if (skip((i % 2) == 0, i / 2, allTheSameSize))
    650                continue;
    651            System.out.println("Online sectioning #" + (i + 1) + " " + sOnlineAlgs[i / 2]
    652                    + ((i % 2) == 0 ? "" : " w/o precomputed expectations"));
    653            System.out.println("  worst case: " + sDF.format((100.0 * worstCase[i]) / sq.size()) + "% (" + worstCase[i]
    654                    + " of " + sq.size() + ", sequence " + worstCaseSq[i] + ")");
    655            System.out.println("  average case: " + sDF.format((100.0 * total[i]) / (sq.size() * nrCases)) + "%");
    656            sq.set(worstCaseSq[i].first());
    657            checkOnline(sq, (i % 2) == 0, i / 2, true);
    658            TreeSet<String> cats = new TreeSet<String>(new CatCmp(countCat[i], totalCat[i], worstCaseCat[i]));
    659            cats.addAll(totalCat[i].keySet());
    660            for (Iterator<String> j = cats.iterator(); j.hasNext();) {
    661                String cat = j.next();
    662                int cc = (countCat[i].get(cat)).intValue();
    663                int tc = (totalCat[i].get(cat)).intValue();
    664                int wc = (worstCaseCat[i].get(cat)).intValue();
    665                String wcsq = worstCaseSqCat[i].get(cat);
    666                System.out.println("  Category " + cat + " (size=" + cc + ")");
    667                System.out.println("    worst case: " + sDF.format((100.0 * wc) / sq.size()) + "% (" + wc + " of "
    668                        + sq.size() + ", sequence " + wcsq + ")");
    669                System.out.println("    average case: " + sDF.format((100.0 * tc) / (sq.size() * cc)) + "%");
    670            }
    671        }
    672        /*
    673         * sq.set("EEEBBBAAA");
    674         * System.out.println(sq+" (cat="+sq.cat()+", check="+sq.check()+")");
    675         * sq.set("CACACAAABB"); checkOnline(sq, true, 2, true);
    676         */
    677    }
    678
    679}