001// Exercise 2.3.1 (Solution published at http://algs4.cs.princeton.edu/)
002package algs23;
003import stdlib.*;
004import java.awt.Font;
005/* ***********************************************************************
006 *  Compilation:  javac TracePartition.java
007 *  Execution:    java TracePartition string
008 *
009 *  Partitions the array of characters specified as the command-line
010 *  argument and shows the detailed trace.
011 *
012 *  % java TracePartition KRATELEPUIMQCXOS
013 *
014 *  % java TracePartition AAAAAAAAAAAAAAAA
015 *
016 *************************************************************************/
017
018public class XTracePartition {
019        private static int line = 0;
020
021        private static int partition(String[] a) {
022                int lo = 0, hi = a.length - 1;
023                int i = lo;
024                int j = hi + 1;
025                String v = a[lo];
026                while (true) {
027
028                        // find item on lo to swap
029                        int iold = i + 1;
030                        while (less(a[++i], v))
031                                if (i == hi) break;
032
033                        // find item on hi to swap
034                        int jold = j - 1;
035                        while (less(v, a[--j]))
036                                if (j == lo) break;      // redundant since a[lo] acts as sentinel
037
038                        // check if pointers cross
039                        if (i >= j) break;
040
041                        draw(a, iold, i, jold, j);
042                        line++;
043
044                        exch(a, i, j);
045                        draw(a, i, j);
046                        line++;
047                }
048
049                // put v = a[j] into position
050                exch(a, lo, j);
051                draw(a, lo, j);
052                line++;
053
054                // with a[lo .. j-1] <= a[j] <= a[j+1 .. hi]
055                return j;
056        }
057
058
059        // exchange a[i] and a[j]
060        private static void exch(String[] a, int i, int j) {
061                String swap = a[i];
062                a[i] = a[j];
063                a[j] = swap;
064        }
065
066        // is v < w ?
067        private static boolean less(String v, String w) {
068                return (v.compareTo(w) < 0);
069        }
070
071        private static void draw(String[] a, int iold, int ith, int jold, int jth) {
072                StdDraw.setPenColor(StdDraw.BLACK);
073                StdDraw.text(-2.50, line, ith  + "");
074                StdDraw.text(-1.25, line, jth  + "");
075                for (int i = 0; i < a.length; i++) {
076                        if      (i >= iold && i <= ith) StdDraw.setPenColor(StdDraw.BLACK);
077                        else if (i <= jold && i >= jth) StdDraw.setPenColor(StdDraw.BLACK);
078                        else                            StdDraw.setPenColor(StdDraw.LIGHT_GRAY);
079                        StdDraw.text(i, line, a[i]);
080                }
081        }
082
083        private static void draw(String[] a, int ith, int jth) {
084                StdDraw.setPenColor(StdDraw.BOOK_RED);
085                StdDraw.text(-2.50, line, ith  + "");
086                StdDraw.text(-1.25, line, jth  + "");
087                for (int i = 0; i < a.length; i++) {
088                        if      (i == ith || i == jth) StdDraw.setPenColor(StdDraw.BOOK_RED);
089                        else                           StdDraw.setPenColor(StdDraw.LIGHT_GRAY);
090                        StdDraw.text(i, line, a[i]);
091                }
092        }
093
094        // display header
095        private static void header(String[] a) {
096                int N = a.length;
097                StdDraw.setPenColor(StdDraw.BLACK);
098                StdDraw.text(N/2.0, -3, "a[ ]");
099                for (int i = 0; i < N; i++)
100                        StdDraw.text(i, -2, i + "");
101                StdDraw.text(-2.50, -2, "i");
102                StdDraw.text(-1.25, -2, "j");
103                StdDraw.setPenColor(StdDraw.BOOK_RED);
104                StdDraw.line(-3, -1.65, N-.5, -1.65);
105                StdDraw.setPenColor(StdDraw.BLACK);
106                for (int i = 0; i < a.length; i++)
107                        StdDraw.text(i, -1, a[i]);
108        }
109
110        // display footer
111        private static void footer(String[] a, int j) {
112                int N = a.length;
113                StdDraw.setPenColor(StdDraw.BOOK_RED);
114                StdDraw.text(-1.25, line, j + "");
115                for (int i = 0; i < N; i++) {
116                        if  (i == j) StdDraw.setPenColor(StdDraw.BOOK_RED);
117                        else         StdDraw.setPenColor(StdDraw.BLACK);
118                        StdDraw.text(i, line, a[i]);
119                }
120        }
121
122
123        // test client
124        public static void main(String[] args) {
125                args = new String[] { "SORTEXAMPLE" };
126
127                // parse command-line argument as an array of 1-character strings
128                String s = args[0];
129                int N = s.length();
130                String[] a = new String[N];
131                for (int i = 0; i < N; i++)
132                        a[i] = s.substring(i, i+1);
133
134                // set canvas size
135                StdDraw.setCanvasSize(30*(N+3), 30*(N+3));
136                StdDraw.setXscale(-4, N+1);
137                StdDraw.setYscale(N+1, -4);
138                StdDraw.setFont(new Font("SansSerif", Font.PLAIN, 13));
139
140                // display the header
141                header(a);
142
143                // sort the array and display trace
144                int j = partition(a);
145
146                // display the footer
147                footer(a, j);
148        }
149
150}