001    package net.sf.cpsolver.studentsct;
002    
003    import java.text.DecimalFormat;
004    import java.util.Comparator;
005    import java.util.HashMap;
006    import java.util.Iterator;
007    import java.util.TreeSet;
008    
009    import 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 Tomas Muller<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     */
046    public 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    }