001    /*
002     * Copyright (c) 1998-2014 ChemAxon Ltd. All Rights Reserved.
003     *
004     * This software is the confidential and proprietary information of
005     * ChemAxon. You shall not disclose such Confidential Information
006     * and shall use it only in accordance with the terms of the agreements
007     * you entered into with ChemAxon.
008     *
009     */
010    package com.chemaxon.clustering.util;
011    
012    import com.chemaxon.clustering.common.DissimilarityInput;
013    import com.chemaxon.clustering.common.HierarchicCluster;
014    import com.chemaxon.clustering.common.HierarchicClustering;
015    import com.chemaxon.clustering.common.IDBasedAssigner;
016    import com.chemaxon.clustering.common.IDBasedHierarchicCluster;
017    import com.chemaxon.clustering.common.IDBasedHierarchicClustering;
018    import com.chemaxon.common.annotations.PublicAPI;
019    import com.chemaxon.descriptors.metrics.MetricMetadata;
020    import com.google.common.annotations.Beta;
021    import com.google.common.base.Optional;
022    import com.google.common.collect.ImmutableList;
023    import java.util.ArrayList;
024    import java.util.Arrays;
025    import java.util.BitSet;
026    import java.util.Collection;
027    import java.util.Iterator;
028    import java.util.List;
029    
030    
031    /**
032     * Clustering related utility methods.
033     *
034     * <p>Please note that this class is marked with {@link Beta} annotation, so it can be subject of incompatible changes
035     * or removal in later releases.</p>
036     *
037     * @author Gabor Imre
038     */
039    @Beta
040    @PublicAPI
041    public final class Util {
042    
043    
044        /**
045         * No public constructor for utility class.
046         */
047        private Util() {}
048    
049        /**
050         * Provide a JSON-like representation for Web GUI widget display.
051         *
052         * <p>Please note that the provided representation is not defined, it can be changed in future releases.</p>
053         *
054         * @param clustering    Clustering to JSonify
055         * @return              JSON representation
056         */
057        public static String toJsonMixed(IDBasedHierarchicClustering clustering) {
058            final StringBuilder ret = new StringBuilder(500);
059    
060            ret.append("{ \"branches\": [");
061    
062            final IDBasedAssigner a = clustering.getPreferredAssigner();
063    
064            boolean first = true;
065            for (IDBasedHierarchicCluster c : clustering.roots()) {
066                if (!first) {
067                    ret.append(",\n"); // NOPMD
068                } else {
069                    ret.append('\n'); // NOPMD
070                    first = false;
071                }
072                toJsonMixedTraverseCluster(c, a, ret, "    ");
073            }
074    
075            ret.append("\n  ]\n}");
076    
077            return ret.toString();
078        }
079    
080        /**
081         * Internal traversal method.
082         *
083         * @param c         Cluster to traverse from
084         * @param a         Level assigner to use
085         * @param b         Output to print
086         * @param prefix    Line prefix to use for indentation
087         */
088        private static void toJsonMixedTraverseCluster(
089                IDBasedHierarchicCluster c, IDBasedAssigner a, StringBuilder b, String prefix) {
090    
091    
092            b.append(prefix);
093            b.append("{ \"clusterid\": ");
094            b.append(c.getClusterID());
095            b.append(", \"level\": ");
096            b.append(a.clusterLevel(c));
097            b.append(",\n"); // NOPMD
098    
099            b.append(prefix);
100            b.append("  \"branches\": [");
101    
102            boolean first = true;
103            for (IDBasedHierarchicCluster cc: c.clusters()) {
104                if (!first) {
105                    b.append(",\n"); // NOPMD
106                } else {
107                    b.append('\n'); // NOPMD
108                    first = false;
109                }
110                toJsonMixedTraverseCluster(cc, a, b, prefix + "    ");
111            }
112    
113            for (Integer l : c.leaves()) {
114                if (!first) {
115                    b.append(",\n"); // NOPMD
116                } else {
117                    b.append('\n'); // NOPMD
118                    first = false;
119                }
120                b.append(prefix);
121                b.append("    { \"leafid\": ").append(l).append(", \"level\": ").append(a.leafLevel(l)).append(" }");
122            }
123    
124    
125            b.append('\n'); // NOPMD
126            b.append(prefix);
127            b.append("  ]\n");
128    
129            b.append(prefix);
130            b.append('}');
131    
132        }
133    
134        /**
135         * Count number of clusters/children in a list.
136         *
137         * @param cl    List
138         * @return      Number of clusters and their children
139         */
140        private static int countNumberOfClusters(List<? extends HierarchicCluster<?>> cl) {
141            int ret = 0;
142            for (HierarchicCluster<?> c : cl) {
143                ret++;
144                ret += countNumberOfClusters(c.clusters());
145            }
146            return ret;
147        }
148    
149    
150        /**
151         * Count the number of clusters in a clustering.
152         *
153         * @param   c   A clustering
154         * @return      Total number of clusters, including singletons
155         */
156        public static int countNumberOfClusters(HierarchicClustering<?, ? extends HierarchicCluster<?>> c) {
157            return countNumberOfClusters(c.roots());
158        }
159    
160        /**
161         * Internal max depth find for a list of clusters
162         *
163         * @param   cl  Clusters list
164         * @return      Max depth found
165         */
166        private static int maxDepth(List<? extends HierarchicCluster<?>> cl) {
167            int ret = 0;
168            for (HierarchicCluster c : cl) {
169                if (!c.leaves().isEmpty()) {
170                    ret = Math.max(ret, 1);
171                }
172                ret = Math.max(ret, 1 + maxDepth(c.clusters()));
173            }
174            return ret;
175        }
176    
177        /**
178         * Find max depth.
179         *
180         * @param   c   A clustering
181         * @return      Max parent-children steps required to reach every leaf
182         */
183        public static int maxDepth(HierarchicClustering<?, ? extends HierarchicCluster<?>> c) {
184            return maxDepth(c.roots());
185        }
186    
187        /**
188         * Consruct a hierarchic index for a given member of a clustering.
189         *
190         * <p>Hierarchic index is a comma (,) separated list of 1-based indexes of the path leading to the given member
191         * from the roots. In a clustering, hierarchic index "2,3,4" means that the given member is acessible from the
192         * second root's third child cluster, as its fourth element. The previous elements can be further clusters or
193         * leaf nodes.</p>
194         *
195         * <p>This implementation orders child clusters before immediate leaves.</p>
196         *
197         * @param <T>        Type of clustered members
198         * @param member     A member
199         * @param clustering Associated clustering
200         * @return           1-based, comma separated compact (no whitespaces) hierarchic index string of the given member
201         * @throws IllegalArgumentException when the given member is not part of the given clustering
202         */
203        public static <T> String hierarchicIndexOf(
204                T member, HierarchicClustering<T, ? extends HierarchicCluster<T>> clustering) {
205    
206            // Traverse from the bottom, indices returned in reverse order
207            final List<Integer> indices = new ArrayList<Integer>();
208    
209    
210            Optional<? extends HierarchicCluster<T>> c = clustering.clusterOf(member);
211    
212            if (!c.isPresent()) {
213                throw new IllegalArgumentException("Member " + member.toString() + " not found in given clustering.");
214            }
215    
216            // Determine last index
217            final int li = c.get().leaves().indexOf(member);
218            if (li == -1) {
219                throw new IllegalStateException("Member not " + member.toString()
220                        + "found in its immediate parent cluster.");
221            }
222            indices.add(1 + c.get().clusters().size() + li);
223    
224            // traverse toward the roots
225            while (c.get().parent().isPresent()) {
226                final Optional<? extends HierarchicCluster<T>> cp = c.get().parent();
227    
228                final int ci = cp.get().clusters().indexOf(c.get());
229    
230                if (ci == -1) {
231                    throw new IllegalStateException("Child cluster not found in its respective parent.");
232                }
233    
234                indices.add(1 + ci);
235    
236                c = cp;
237            }
238    
239            // c is a root node
240            final int ri = clustering.roots().indexOf(c.get());
241    
242            if (ri == -1) {
243                throw new IllegalStateException("Root cluster not found among roots");
244            }
245    
246            indices.add(1 + ri);
247    
248            // Compose result
249            final StringBuilder ret = new StringBuilder();
250    
251            for (int i = indices.size() - 1; i >= 0; i--) {
252                ret.append(indices.get(i));
253                if (i != 0) {
254                    ret.append(',');
255                }
256            }
257    
258            return ret.toString();
259        }
260    
261        /**
262         * Construct a {@link DissimilarityInput} over a set of 1D values.
263         *
264         * @param values    Values to consider
265         * @return          Dissimilarity input representing their euclidean distances
266         */
267        public static DissimilarityInput linearEuclideanDissimilarityInput(double [] values) {
268            final double [] v = Arrays.copyOf(values, values.length);
269            return new DissimilarityInput() {
270    
271                public int size() {
272                    return v.length;
273                }
274    
275                public double dissimilarity(int targetIndex, int queryIndex) {
276                    return Math.abs(v[targetIndex] - v[queryIndex]);
277                }
278    
279                public MetricMetadata getMetricMetadata() {
280                    return new MetricMetadata() {
281    
282                        public boolean isSymmetric() {
283                            return true;
284                        }
285    
286                        public boolean isNonNegative() {
287                            return true;
288                        }
289    
290                        public boolean isDissimilarityZeroIFFEquals() {
291                            return true;
292                        }
293    
294                        public boolean isTriangeInequalityHolds() {
295                            return true;
296                        }
297    
298                        public boolean isMetricSpace() {
299                            return true;
300                        }
301                    };
302                }
303            };
304    
305        }
306    
307        /**
308         * Invoke recursive DFS post order traversal from an arbitrary level.
309         *
310         * @param <T>       Traversal result type
311         * @param visitor   Callback interface for traversal/skipping
312         * @param clusters  Clusters to visit
313         * @param depth     Depth of the given clusters
314         *
315         * @return          Result list of clusters traversal
316         */
317        private static <T> List<T> traversePostOrderDFS(
318                PostOrderDfsVisitor<T> visitor,
319                List<? extends IDBasedHierarchicCluster> clusters,
320                int depth) {
321    
322            final ImmutableList.Builder<T> retb = ImmutableList.<T>builder();
323    
324            for (IDBasedHierarchicCluster cluster : clusters) {
325                if (visitor.skipChildTraversal(cluster, depth)) {
326                    // children traversal wont be done, invoke current cluster traversal
327                    retb.add(visitor.visit(cluster, null, depth));
328                } else {
329                    // children traversal is required
330                    final List<T> cvr = traversePostOrderDFS(visitor, cluster.clusters(), depth + 1);
331                    retb.add(visitor.visit(cluster, cvr, depth));
332                }
333            }
334    
335            return retb.build();
336        }
337    
338        /**
339         * Invoke recursive DFS post order traversal on a hierarchy.
340         *
341         * @param <T>        Traversal result type
342         * @param visitor    Callback interface for traversal/skipping
343         * @param clustering Clustering to traverse
344         *
345         * @return           Result list of traversal associated to roots
346         */
347        public static <T> List<T> traversePostOrderDFS(
348                PostOrderDfsVisitor<T> visitor,
349                IDBasedHierarchicClustering clustering) {
350            return traversePostOrderDFS(visitor, clustering.roots(), 0);
351        }
352    
353    
354    
355        /**
356         * Item to represent an item of DFS traversal result
357         */
358        private static final class ClusterRenderItem {
359    
360    
361            /**
362             * First occupied row of the leaves in the rendering.
363             */
364            private final int firstRow;
365    
366            /**
367             * Represented members count, total occupied row count.
368             */
369            private final int memberCount;
370    
371    
372            /**
373             * Character column associated to the cluster vertical bar.
374             */
375            private final int clusterVColumn;
376    
377    
378            /**
379             * The first row of the vertical branching line.
380             */
381            private final int clusterVRow1;
382    
383    
384            /**
385             * The last row (inclusive) of the vertical branching line.
386             */
387            private final int clusterVRow2;
388    
389            /**
390             * Constructor.
391             *
392             * @param firstRow    First occupied row
393             * @param memberCount Member count
394             * @param clusterVColumn Column of the branching vertical line
395             * @param clusterVRow1   First row of the branching vertical line
396             * @param clusterVRow2   Last row (inclusive) of the branching vertical line
397             */
398            public ClusterRenderItem(
399                    int firstRow,
400                    int memberCount,
401                    int clusterVColumn,
402                    int clusterVRow1,
403                    int clusterVRow2) {
404    
405                this.firstRow = firstRow;
406                this.memberCount = memberCount;
407                this.clusterVColumn = clusterVColumn;
408                this.clusterVRow1 = clusterVRow1;
409                this.clusterVRow2 = clusterVRow2;
410            }
411    
412            /**
413             * Column of the branching vertical line.
414             * @return Column of the branching vertical line
415             */
416            public int getClusterVColumn() {
417                return this.clusterVColumn;
418            }
419    
420            /**
421             * First row of the branching vertical line.
422             * @return First row of the branching vertical line
423             */
424            public int getClusterVRow1() {
425                return this.clusterVRow1;
426            }
427    
428            /**
429             * Last row (inclusive) of the branching vertical line.
430             * @return Last row (inclusive) of the branching vertical line
431             */
432            public int getClusterVRow2() {
433                return this.clusterVRow2;
434            }
435    
436            /**
437             * First occupied row.
438             * @return First occupied row
439             */
440            public int getFirstRow() {
441                return this.firstRow;
442            }
443    
444            /**
445             * Member count.
446             * @return Member count
447             */
448            public int getMemberCount() {
449                return this.memberCount;
450            }
451    
452    
453        }
454    
455    
456        private static class DendrogramTextRenderer implements PostOrderDfsVisitor<ClusterRenderItem> {
457    
458            private final IDBasedHierarchicClustering clustering;
459            private final IDBasedAssigner levels;
460            private final List<String> labels;
461            private final int cols;
462    
463            /**
464             * Maximum level value to use.
465             */
466            private final double max;
467    
468            /**
469             * State.
470             */
471            private boolean finished = false;
472    
473            /**
474             * The plot built.
475             */
476            private final List<char[]> plot;
477    
478            private final int [] leafIDs;
479    
480            /**
481             * Next row to print the next child.
482             */
483            private int nextLRow = 0;
484    
485            /**
486             * Convert level value to column.
487             * @param level Level value
488             * @return      Character column
489             */
490            private int levelToColumn(double level) {
491                final int cc = (int) ((this.cols - 1) * level / this.max);
492                if (this.clustering.preferredAlignment() == HierarchicClustering.Alignment.LEAF_ALIGNED) {
493                    return this.cols - cc - 1;
494                } else {
495                    return cc;
496                }
497    
498            }
499    
500            /**
501             * Construct the renderer.
502             *
503             *
504             */
505            public DendrogramTextRenderer(
506                IDBasedHierarchicClustering clustering,
507                IDBasedAssigner levels,
508                List<String> labels,
509                int cols) {
510    
511                this.clustering = clustering;
512                this.levels = levels;
513                this.labels = labels;
514                this.cols = cols;
515    
516                this.max = levels.maxLevel() == 0.0 ? 1.0 : levels.maxLevel();
517    
518                // The dendrogram plot
519                this.plot = new ArrayList<char[]>();
520    
521                // Allocate plot -------------------------------------------------------------------------------------------
522                for (IDBasedHierarchicCluster r : clustering.roots()) {
523                    for (int i = 0; i < r.members().size(); i++) {
524                        final char [] a = new char[cols];
525                        Arrays.fill(a, ' ');
526                        this.plot.add(a);
527                    }
528                }
529    
530                this.leafIDs = new int[this.plot.size()];
531            }
532    
533    
534    
535            @Override
536            public boolean skipChildTraversal(IDBasedHierarchicCluster cluster, int depth) {
537                if (this.finished) {
538                    throw new IllegalStateException();
539                }
540                return false;
541            }
542    
543            @Override
544            public ClusterRenderItem visit(
545                    IDBasedHierarchicCluster cluster, List<ClusterRenderItem> childResults, int depth) {
546                if (this.finished) {
547                    throw new IllegalStateException();
548                }
549    
550                final int ccol = levelToColumn(this.levels.clusterLevel(cluster));
551    
552                final ClusterRenderItem ri;
553    
554                // Bottom level node
555                if (cluster.clusters().isEmpty()) {
556                    ri = new ClusterRenderItem(
557                            this.nextLRow,                                // First row is the next row we can print leaves
558                            cluster.leaves().size(),                      // Member count is the leaves count
559                            ccol,                                         // Cluster column calculated
560                            this.nextLRow,                                // Vertical line starts at first row
561                            this.nextLRow + cluster.leaves().size() - 1); // vertical line ends at last row
562                } else {
563                    // First row of the vertical line:
564                    // It is a the half point of the first childs vertical line
565                    final int r1 = (childResults.get(0).clusterVRow1 + childResults.get(0).clusterVRow2) / 2;
566                    // Last row of the vertical line:
567                    final int r2;
568                    if (cluster.leaves().isEmpty()) {
569                        // no immediate leaves, last row is determined by the last childs vertical line
570                        final ClusterRenderItem lc = childResults.get(childResults.size() - 1);
571                        r2 = (lc.clusterVRow1 + lc.clusterVRow2) / 2;
572                    } else {
573                        // have intermediate leaves, last row is determined by the last leaf printed
574                        r2 = this.nextLRow + cluster.leaves().size() - 1;
575                    }
576                    // If have immediate children t
577                    ri = new ClusterRenderItem(
578                            childResults.get(0).firstRow,                 // First row is the first row of the first child
579                            cluster.members().size(),                     // Member count
580                            ccol,                                         // Cluster column calculated
581                            r1,
582                            r2);
583                }
584    
585                // Render vertical line
586                for (int i = ri.clusterVRow1; i <= ri.clusterVRow2; i++) {
587                    final char [] c = this.plot.get(i);
588                    if (c[ccol] == ' ' || c[ccol] == '-') {
589                        c[ccol] = '|';
590                    }
591                }
592    
593                // Render child cluster connections
594                for (int i = 0; i < childResults.size(); i++) {
595                    final ClusterRenderItem cr = childResults.get(i);
596                    final int lrow = (cr.clusterVRow1 + cr.clusterVRow2) / 2;
597                    final char [] c = this.plot.get(lrow);
598    
599                    if (c[ccol] == '|') {
600                        c[ccol] = '+';
601                    }
602                    if (c[cr.clusterVColumn] == '|') {
603                        c[cr.clusterVColumn] = '+';
604                    }
605                    for (int j = ccol + 1; j < cr.clusterVColumn; j++) {
606                        if (c[j] == ' ') {
607                            c[j] = '-';
608                        }
609                    }
610                }
611    
612                // Render leaves
613                for (int i = 0; i < cluster.leaves().size(); i++) {
614                    this.leafIDs[this.nextLRow] = cluster.leaves().get(i);
615                    final char [] c = this.plot.get(this.nextLRow++);
616                    final int lcol = levelToColumn(this.levels.leafLevel(cluster.leaves().get(i)));
617                    if (c[ccol] == '|') {
618                        c[ccol] = '+';
619                    }
620                    c[lcol] = 'o';
621    
622                    for (int j = ccol + 1; j < lcol; j++) {
623                        if (c[j] == ' ') {
624                            c[j] = '-';
625                        }
626                    }
627    
628                }
629    
630                return ri;
631            }
632    
633            /**
634             * Render the dendrogram.
635             *
636             * @return  Rendered multiline representation
637             */
638            public String render() {
639                if (this.finished) {
640                    throw new IllegalStateException();
641                }
642    
643                traversePostOrderDFS(this, this.clustering.roots(), 0);
644                this.finished = true;
645    
646                final StringBuilder ret = new StringBuilder(this.plot.size() * (this.cols + 10));
647                for (int i = 0; i < this.plot.size(); i++) {
648                    ret.append(this.plot.get(i));
649                    if (this.labels != null) {
650                        ret.append(' ');
651                        ret.append(this.labels.get(this.leafIDs[i]));
652                    }
653                    ret.append('\n');
654                }
655                return ret.toString();
656    
657            }
658    
659        }
660    
661        /**
662         * Render a minimalist dendrogram from a String.
663         *
664         * @param clustering    Source clustering to use
665         * @param levels        Level assignemnt to use
666         * @param labels        Leaf labels for leaf IDs
667         * @param cols          Total columns
668         * @return              String representation of the given clustering
669         */
670        public static String hierarchyToString(
671                IDBasedHierarchicClustering clustering,
672                IDBasedAssigner levels,
673                List<String> labels,
674                int cols) {
675    
676            final DendrogramTextRenderer r = new DendrogramTextRenderer(clustering, levels, labels, cols);
677            return r.render();
678        }
679    
680        /**
681         * ASCII scatter plot.
682         */
683        public static class StringScatterPlot {
684    
685            /**
686             * Find minimal value in a collection of Doubles.
687             *
688             * @param c Collection of Doubles
689             * @return  Minimum value found or 0.0 for empty collections
690             */
691            private static double min(Collection<Double> c) {
692                if (c.isEmpty()) {
693                    return 0;
694                }
695                final Iterator<Double> it = c.iterator();
696                double ret = it.next();
697                while (it.hasNext()) {
698                    final double d = it.next();
699                    if (d < ret) {
700                        ret = d;
701                    }
702                }
703                return ret;
704            }
705    
706            /**
707             * Find maximal value in a collection of Doubles.
708             *
709             * @param c Collection of Doubles
710             * @return  Maximum value found or 0.0 for empty collections
711             */
712            private static double max(Collection<Double> c) {
713                if (c.isEmpty()) {
714                    return 0;
715                }
716                final Iterator<Double> it = c.iterator();
717                double ret = it.next();
718                while (it.hasNext()) {
719                    final double d = it.next();
720                    if (d > ret) {
721                        ret = d;
722                    }
723                }
724                return ret;
725            }
726    
727            /**
728             * Append a specific number of characters to a StringBuilder.
729             *
730             * @param sb    Target
731             * @param c     Character to append
732             * @param count Append count.
733             * @return      Reference for the passed StringBuilder
734             * @throws      IllegalArgumentException for negative counts
735             */
736            private static StringBuilder append(StringBuilder sb, char c, int count) {
737                if (count < 0) {
738                    throw new IllegalArgumentException("Negative count " + count);
739                }
740                for (int i = 0; i < count; i++) {
741                    sb.append(c);
742                }
743                return sb;
744            }
745    
746            /**
747             * X values to put.
748             */
749            private final List<Double> x;
750    
751            /**
752             * Y values to put.
753             */
754            private final List<Double> y;
755    
756            /**
757             * Construct an empty scatter plot.
758             */
759            public StringScatterPlot() {
760                this.x = new ArrayList<Double>();
761                this.y = new ArrayList<Double>();
762            }
763    
764            /**
765             * Add new point to put.
766             *
767             * @param   x   X coordinate of the point to add
768             * @param   y   Y coordinate of the point to add
769             */
770            public void addDataPoint(double x, double y) {
771                this.x.add(x);
772                this.y.add(y);
773            }
774    
775    
776    
777            /**
778             * Create a multiline representation of the given plot.
779             *
780             * @param cols  Character columns occupied
781             * @param rows  Rows occupied
782             * @param xlabels Show min/max X axis values (occupies bottom row)
783             * @param ylabels Shpw min/max Y axis values (occupies
784             * @return      A String representation of the chart
785             */
786            public String toString(int cols, int rows, boolean xlabels, boolean ylabels) {
787    
788                // Get min/max values of points
789                double xmin = min(this.x);
790                double xmax = max(this.x);
791                double ymin = min(this.y);
792                double ymax = max(this.y);
793    
794                if (xmin == xmax) {
795                    xmin -= 1.0;
796                    xmax += 1.0;
797                }
798                if (ymin == ymax) {
799                    ymin -= 1.0;
800                    ymax += 1.0;
801                }
802    
803    
804                // Returned String
805                // +1 per row for newline '\n'
806                final StringBuilder ret = new StringBuilder(cols * (rows + 1));
807    
808                // X size of plot area
809                final int px;
810    
811                // ymin value as String
812                final String ymins;
813    
814                // ymax value as String
815                final String ymaxs;
816    
817                // empty chars leading y axes;
818                final String ylead;
819    
820                if (ylabels) {
821                    final String s1 = Double.toString(ymin);
822                    final String s2 = Double.toString(ymax);
823    
824                    final StringBuilder lb = new StringBuilder();
825                    append(lb, ' ', Math.max(s1.length(), s2.length()) + 1);
826                    ylead = lb.toString();
827    
828                    final StringBuilder b1 = new StringBuilder();
829                    append(b1, ' ', ylead.length() - s1.length() - 1);
830                    b1.append(s1);
831                    b1.append(' ');
832                    ymins = b1.toString();
833    
834                    final StringBuilder b2 = new StringBuilder();
835                    append(b2, ' ', ylead.length() - s2.length() - 1);
836                    b2.append(s2);
837                    b2.append(' ');
838                    ymaxs = b2.toString();
839                    px = cols - 2 - ylead.length();
840    
841                } else {
842                    ymins = "";
843                    ymaxs = "";
844                    ylead = "";
845                    px = cols - 2;
846                }
847    
848    
849                // Y size of plot area
850                final int py;
851                if (xlabels) {
852                    py = rows - 3;
853                } else {
854                    py = rows - 2;
855                }
856    
857                // Plot area BitMap;
858                // upper left corner is 0, upper right is px-1, lower left is px*(py-1),
859                // lower right is px*(py-1)+(px-1) = px*py-1
860                final BitSet plot = new BitSet(px * py);
861    
862    
863                for (int i = 0; i < this.x.size(); i++) {
864                    final double dx = this.x.get(i);
865                    final double dy = this.y.get(i);
866                    final int xx = (int) ((px - 1) * (dx - xmin) / (xmax - xmin));
867                    final int yy = (int) ((py - 1) * (ymax - dy) / (ymax - ymin));
868                    plot.set(xx + yy * px);
869                }
870    
871    
872                ret.append(ylead);
873                ret.append('+');
874                append(ret, '-', px);
875                ret.append("+\n");
876    
877                for (int i = 0; i < py; i++) {
878                    if (i == 0) {
879                        ret.append(ymaxs);
880                    } else if (i == py - 1) {
881                        ret.append(ymins);
882                    } else {
883                        ret.append(ylead);
884                    }
885                    ret.append('|');
886                    for (int j = 0; j < px; j++) {
887                        ret.append(plot.get(px * i + j) ? '#' : ' ');
888                    }
889                    ret.append("|\n");
890                }
891    
892                ret.append(ylead);
893                ret.append('+');
894                append(ret, '-', px);
895                ret.append("+\n");
896    
897                if (xlabels) {
898                    ret.append(ylead);
899                    ret.append(' ');
900                    final String xmins = Double.toString(xmin);
901                    final String xmaxs = Double.toString(xmax);
902                    ret.append(xmins);
903                    append(ret, ' ', px - xmins.length() - xmaxs.length());
904                    ret.append(xmaxs);
905                    ret.append('\n');
906    
907                }
908                return ret.toString();
909    
910    
911            }
912        }
913    
914    
915    
916    
917    }