001// Exercise 2.2.2 (Solution published at http://algs4.cs.princeton.edu/)
002package algs24;
003import stdlib.*;
004import java.awt.Font;
005/* ***********************************************************************
006 *  Compilation:  javac TraceMerge.java
007 *  Execution:    java  TraceMerge input
008 *
009 *  Mergesort the sequence of strings specified as the command-line
010 *  arguments and show the detailed trace.
011 *
012 *  % java TraceMerge MERGESORTEXAMPLE
013 *
014 *************************************************************************/
015
016public class XTraceHeap {
017        private static int line = 0;
018
019        public static void sort(String[] pq) {
020                int N = pq.length;
021                for (int k = N/2; k >= 1; k--) {
022                        sink(pq, k, N);
023                        draw (pq, N, k); line++;
024                }
025                while (N > 1) {
026                        exch(pq, 1, N--);
027                        sink(pq, 1, N);
028                        draw (pq, N, 1); line++;
029                }
030        }
031
032        /* *********************************************************************
033         * Helper functions to restore the heap invariant.
034         **********************************************************************/
035
036        private static void sink(String[] pq, int k, int N) {
037                while (2*k <= N) {
038                        int j = 2*k;
039                        if (j < N && less(pq, j, j+1)) j++;
040                        if (!less(pq, k, j)) break;
041                        exch(pq, k, j);
042                        k = j;
043                }
044        }
045
046        /* *********************************************************************
047         * Helper functions for comparisons and swaps.
048         * Indices are "off-by-one" to support 1-based indexing.
049         **********************************************************************/
050        private static boolean less(String[] pq, int i, int j) {
051                return pq[i-1].compareTo(pq[j-1]) < 0;
052        }
053
054        private static void exch(String[] pq, int i, int j) {
055                String swap = pq[i-1];
056                pq[i-1] = pq[j-1];
057                pq[j-1] = 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
067        private static void draw(String[] a, int N, int k) {
068                StdDraw.setPenColor(StdDraw.BLACK);
069                StdDraw.text(-2.50, line, N  + "");
070                StdDraw.text(-1.25, line, k + "");
071                for (int i = 0; i < a.length; i++) {
072                        StdDraw.text(i, line, a[i]);
073                }
074        }
075
076        // display header
077        private static void header(String[] a) {
078                int N = a.length;
079                StdDraw.setPenColor(StdDraw.BLACK);
080                StdDraw.text(N/2, -3, "a[ ]");
081                for (int i = 0; i < N; i++)
082                        StdDraw.text(i, -2, i + "");
083                StdDraw.text(-2.50, -2, "N");
084                StdDraw.text(-1.25, -2, "k");
085                StdDraw.setPenColor(StdDraw.BOOK_RED);
086                StdDraw.line(-4, -1.65, N-.5, -1.65);
087                StdDraw.setPenColor(StdDraw.BLACK);
088                for (int i = 0; i < a.length; i++)
089                        StdDraw.text(i, -1, a[i]);
090        }
091
092        // display footer
093        private static void footer(String[] a) {
094                int N = a.length;
095                StdDraw.setPenColor(StdDraw.BLACK);
096                for (int i = 0; i < a.length; i++)
097                        StdDraw.text(i, line, a[i]);
098        }
099
100
101        // test client
102        public static void main(String[] args) {
103                args = new String[] { "SORTEXAMPLE" };
104
105                // parse command-line argument as an array of 1-character strings
106                String s = args[0];
107                int N = s.length();
108                String[] a = new String[N];
109                for (int i = 0; i < N; i++)
110                        a[i] = s.substring(i, i+1);
111
112                // set canvas size
113                StdDraw.setCanvasSize(30*(N+3), (int) (30*(1.5*N+3)));
114                StdDraw.setXscale(-4, N+1);
115                StdDraw.setYscale(1.5*N+1, -4);
116                StdDraw.setFont(new Font("SansSerif", Font.PLAIN, 13));
117
118                // display the header
119                header(a);
120
121                // sort the array and display trace
122                sort(a);
123
124                // display the footer
125                footer(a);
126        }
127
128}