001package algs24;
002import java.util.Scanner;
003import stdlib.*;
004
005public class TestPQ {
006        public static enum Order { INCREASING, DECREASING, RANDOM }
007        public static void main(String[] args) {
008                show(11, true, "1 4 3 6 8 5 11 10 7 9 2 - - 2"); // Example from text 
009                show(9, true, "1 2 3 4 5 6 7 8 9 - - - - - - - -");
010                show(9, true, "9 8 7 6 5 4 3 2 1 - - - - - - - -");
011                showRandom(10, true);
012                double prevInsert = 0;
013                double prevDelMin = 0;
014                for (int N = 128; N<=MAX; N += N) {
015                        timeTrial(N, Order.RANDOM);
016                        StdOut.format("N=%,13d Insert=%7.3f [%8.3f] DelMin=%7.3f [%8.3f]\n", N, timeInsert, timeInsert/prevInsert, timeDelMin, timeDelMin/prevDelMin);
017                        prevInsert = timeInsert;
018                        prevDelMin = timeDelMin;
019                }
020        }
021        private static int MAX=200_000;
022        private static PQ getPQ (int N) {
023                //return new FixedPQSortedIncreasing(N);
024                //return new FixedPQSortedDecreasing(N);
025                //return new FixedPQUnordered(N);
026                MAX=50_000_000; return new FixedPQHeap(N);
027        }
028
029        private static double timeInsert;
030        private static double timeDelMin;
031        private static void timeTrial(int N, Order order) {
032                SHOW_STEPS=false;
033                PQ pqTime = getPQ(N);                           
034                Stopwatch sw1 = new Stopwatch();
035                for (int i=0; i<N; i+=1) {
036                        double item = StdRandom.uniform(1,N+1);
037                        switch (order) {
038                        case INCREASING: pqTime.insert (i); break; 
039                        case DECREASING: pqTime.insert(N-i); break; 
040                        case RANDOM: pqTime.insert (item); break;
041                        }
042                }
043                timeInsert = sw1.elapsedTime();
044
045                Stopwatch sw2 = new Stopwatch();                
046                for (int i=0; i<N; i+= 1) {
047                        pqTime.delMin();
048                }       
049                timeDelMin = sw2.elapsedTime();
050        }
051
052        public static boolean SHOW_STEPS=false;
053        private static void showRandom (int N, boolean showSteps) {
054                SHOW_STEPS=showSteps;
055                PQ pq = getPQ(N);
056                pq.toGraphviz();
057                StdOut.format("               %s\n", pq);
058                for (int i=0; i<4*N; i+=1) {
059                        if (pq.size() > N/2 && (pq.size() == N || StdRandom.random()<.45)) {
060                                double item = pq.delMin();
061                                StdOut.format("-%2.0f          : %s\n", item, pq);      
062                        } else {
063                                double item = StdRandom.uniform(10,100);
064                                pq.insert(item);
065                                StdOut.format("+%2.0f          : %s\n", item, pq);
066                        }
067                }
068                StdOut.println();
069        }
070        private static void show (int N, boolean showSteps, String input) {
071                SHOW_STEPS=showSteps;
072                Scanner s = new Scanner(input);
073                PQ pq = getPQ(N);
074                pq.toGraphviz();
075                StdOut.format("               %s\n", pq);
076                while (s.hasNext()) {
077                        String next = s.next();
078                        if ("-".equals(next)) { 
079                                double item = pq.delMin();
080                                StdOut.format("-%2.0f          : %s\n", item, pq);
081                        } else {
082                                double item = Integer.parseInt(next);
083                                pq.insert(item);
084                                StdOut.format("+%2.0f          : %s\n", item, pq);
085                        }
086                        pq.toGraphviz();
087                }
088                StdOut.println();
089                s.close();
090        }
091}