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