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 XPairingPQ(N);
027                MAX=50_000_000; return new FixedPQHeap(N);
028        }
029
030        private static double timeInsert;
031        private static double timeDelMin;
032        private static void timeTrial(int N, Order order) {
033                SHOW_STEPS=false;
034                PQ pqTime = getPQ(N);                           
035                Stopwatch sw1 = new Stopwatch();
036                for (int i=0; i<N; i+=1) {
037                        double item = StdRandom.uniform(1,N+1);
038                        switch (order) {
039                        case INCREASING: pqTime.insert (i); break; 
040                        case DECREASING: pqTime.insert(N-i); break; 
041                        case RANDOM: pqTime.insert (item); break;
042                        }
043                }
044                timeInsert = sw1.elapsedTime();
045
046                Stopwatch sw2 = new Stopwatch();                
047                for (int i=0; i<N; i+= 1) {
048                        pqTime.delMin();
049                }       
050                timeDelMin = sw2.elapsedTime();
051        }
052
053        public static boolean SHOW_STEPS=false;
054        private static void showRandom (int N, boolean showSteps) {
055                SHOW_STEPS=showSteps;
056                PQ pq = getPQ(N);
057                pq.toGraphviz();
058                StdOut.format("               %s\n", pq);
059                for (int i=0; i<4*N; i+=1) {
060                        if (pq.size() > N/2 && (pq.size() == N || StdRandom.random()<.45)) {
061                                double item = pq.delMin();
062                                StdOut.format("-%2.0f          : %s\n", item, pq);      
063                        } else {
064                                double item = StdRandom.uniform(10,100);
065                                pq.insert(item);
066                                StdOut.format("+%2.0f          : %s\n", item, pq);
067                        }
068                }
069                StdOut.println();
070        }
071        private static void show (int N, boolean showSteps, String input) {
072                SHOW_STEPS=showSteps;
073                Scanner s = new Scanner(input);
074                PQ pq = getPQ(N);
075                pq.toGraphviz();
076                StdOut.format("               %s\n", pq);
077                while (s.hasNext()) {
078                        String next = s.next();
079                        if ("-".equals(next)) { 
080                                double item = pq.delMin();
081                                StdOut.format("-%2.0f          : %s\n", item, pq);
082                        } else {
083                                double item = Integer.parseInt(next);
084                                pq.insert(item);
085                                StdOut.format("+%2.0f          : %s\n", item, pq);
086                        }
087                        pq.toGraphviz();
088                }
089                StdOut.println();
090                s.close();
091        }
092}