001package algs14;
002import stdlib.*;
003public class XCountingString {  
004        // Test variants that resize additively or multiplicatively
005        // int capacity = 1 + a.length;
006        // int capacity = 2 * a.length;
007        // int capacity = (int)Math.ceil(1.5 * a.length);
008        private static char[] resize (char[] a) {
009                int capacity = 2 * a.length;
010                char[] result = new char[capacity]; 
011                for (int i = 0; i < a.length; i = i + 1) {
012                        result[i] = a[i];
013                        numOps = numOps + 1;
014                }
015                return result;
016        }
017        // f creates a string of length N, counting the total size of all strings created
018        public static String f (long N) {
019                char[] a = new char[1];
020                for (int i = 0; i < N; i = i + 1) {
021                        if (i >= a.length) 
022                                a = resize(a);
023                        a[i] = '*';
024                        numOps = numOps + 1;
025                }               
026                return String.valueOf(a); // creates a string in linear time
027        }
028        private static long numOps;
029        public static void main (String[] args) {
030                long MIN = 500L;
031                long MAX = 3200000L;
032                Stopwatch sw = new Stopwatch ();
033                numOps = 0;
034                f(MIN);
035                double prevCount = numOps;
036                double prevTime = sw.elapsedTime ();
037                for (long N = MIN*2; N <= MAX; N=N*2) {
038                        sw = new Stopwatch ();
039                        numOps = 0;
040                        f(N);
041                        long count = numOps; 
042                        double time = sw.elapsedTime ();
043                        StdOut.format ("Elapsed count f(%,13d): %,17d: %10.3f [%10.3f : %10.3f]\n", N, count, count / prevCount, time, time/prevTime);
044                        //StdOut.format ("Elapsed count f(%,13d): %,17d: %10.3f\n", N, count, count / prevCount);
045                        prevCount = count;
046                        prevTime = time;
047                }
048        }
049}