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