001// Exercise 2.2.3 (Solution published at http://algs4.cs.princeton.edu/)
002package algs22;
003import stdlib.*;
004import java.awt.Font;
005/* ***********************************************************************
006 *  Compilation:  javac TraceMergeBU.java
007 *  Execution:    java  TraceMergeBU input
008 *
009 *  Mergesort the sequence of strings specified as the command-line
010 *  arguments and show the detailed trace.
011 *
012 *  % java TraceMergeBU MERGESORTEXAMPLE
013 *
014 *************************************************************************/
015
016public class XTraceMergeBU {
017
018        private static void merge(String[] a, String[] aux, int lo, int m, int hi) {
019
020                // copy to aux[]
021                for (int k = lo; k <= hi; k++) {
022                        aux[k] = a[k];
023                }
024
025                // merge back to a[]
026                int i = lo, j = m+1;
027                for (int k = lo; k <= hi; k++) {
028                        if      (i > m)                a[k] = aux[j++];
029                        else if (j > hi)               a[k] = aux[i++];
030                        else if (less(aux[j], aux[i])) a[k] = aux[j++];
031                        else                           a[k] = aux[i++];
032                }
033
034        }
035
036        // bottom-up mergesort
037        public static void sort(String[] a) {
038                int line = 0;
039                int N = a.length;
040                String[] aux = new String[N];
041                for (int n = 1; n < N; n = n+n) {
042                        for (int i = 0; i < N-n; i += n+n) {
043                                int lo = i;
044                                int m  = i + n - 1;
045                                int hi = Math.min(i + n + n - 1, N - 1);
046                                merge(a, aux, lo, m, hi);
047                                draw(a, line, lo, m, hi);
048                                line++;
049                        }
050                }
051        }
052
053        // exchange a[i] and a[j]
054        private static void exch(String[] a, int i, int j) {
055                String swap = a[i];
056                a[i] = a[j];
057                a[j] = swap;
058        }
059
060        // is v < w ?
061        private static boolean less(String v, String w) {
062                return (v.compareTo(w) < 0);
063        }
064
065
066        // draw the contents of the array, with a[lo] to a[hi] in black
067        private static void draw(String[] a, int line, int lo, int m, int hi) {
068                StdDraw.setPenColor(StdDraw.BLACK);
069                StdDraw.text(-2.50, line, m  + "");
070                StdDraw.setPenColor(StdDraw.BOOK_RED);
071                StdDraw.text(-3.75, line, lo + "");
072                StdDraw.text(-1.25, line, hi + "");
073                for (int i = 0; i < a.length; i++) {
074                        if (i >= lo && i <= hi) StdDraw.setPenColor(StdDraw.BLACK);
075                        else                    StdDraw.setPenColor(StdDraw.LIGHT_GRAY);
076                        StdDraw.text(i, line, a[i]);
077                }
078        }
079
080        // display header
081        private static void header(String[] a) {
082                int N = a.length;
083                StdDraw.setPenColor(StdDraw.BLACK);
084                StdDraw.text(N/2, -3, "a[ ]");
085                for (int i = 0; i < N; i++)
086                        StdDraw.text(i, -2, i + "");
087                StdDraw.text(-3.75, -2, "lo");
088                StdDraw.text(-2.50, -2, "m");
089                StdDraw.text(-1.25, -2, "hi");
090                StdDraw.setPenColor(StdDraw.BOOK_RED);
091                StdDraw.line(-4, -1.65, N-.5, -1.65);
092                StdDraw.setPenColor(StdDraw.BLACK);
093                for (int i = 0; i < a.length; i++)
094                        StdDraw.text(i, -1, a[i]);
095        }
096
097        // display footer
098        private static void footer(String[] a) {
099                int N = a.length;
100                StdDraw.setPenColor(StdDraw.BLACK);
101                for (int i = 0; i < a.length; i++)
102                        StdDraw.text(i, N-1, a[i]);
103        }
104
105
106        // test client
107        public static void main(String[] args) {
108                args = new String[] { "SORTEXAMPLE" };
109
110                // parse command-line argument as an array of 1-character strings
111                String s = args[0];
112                int N = s.length();
113                String[] a = new String[N];
114                for (int i = 0; i < N; i++)
115                        a[i] = s.substring(i, i+1);
116
117                // set canvas size
118                StdDraw.setCanvasSize(30*(N+3), 30*(N+3));
119                StdDraw.setXscale(-4, N+1);
120                StdDraw.setYscale(N+1, -4);
121                StdDraw.setFont(new Font("SansSerif", Font.PLAIN, 13));
122
123                // display the header
124                header(a);
125
126                // sort the array and display trace
127                sort(a);
128
129                // display the footer
130                footer(a);
131        }
132
133}