001package algs24;
002import stdlib.*;
003import java.util.Arrays;
004
005public class FixedPQSortedIncreasing implements PQ {
006        private int N;
007        private double[] a;
008        
009        public FixedPQSortedIncreasing(int capacity){ N = 0; a = new double[capacity+1]; }      
010        public void toGraphviz()          { }
011        public String toString ()         { return Arrays.toString(a).replaceAll(" 0\\.0", " ").replaceAll("\\[0\\.0", "[ ").replaceAll("\\.0", ""); }
012        public int size()                 { return N; }
013        public boolean isEmpty()          { return N == 0; }
014        
015        public void insert(double x) {
016                if (x == 0) throw new Error ("No zeroes allowed");
017                if (N >= a.length-1) throw new Error("Overflow");
018                N++;
019                a[N] = x;
020                for (int j = N; j > 1 && a[j] < a[j-1]; j--)
021                        exch2(j, j-1);
022        }
023        public double min() {
024                return a[1];
025        }
026        public double delMin() {
027                double result = a[1]; 
028                for (int j = 2; j <= N; j++)
029                        exch(j, j-1);
030                a[N] = 0.0;
031                N--;
032                return result;
033        }
034        private void exch(int i, int j) {
035                double oldi = a[i];
036                double oldj = a[j];
037                a[i] = oldj;
038                a[j] = oldi;
039                if (TestPQ.SHOW_STEPS) { StdOut.format("  exch(%2.0f,%2.0f)> %s\n", oldi, oldj, this); toGraphviz(); }
040        }
041        private void exch2(int i, int j) {
042                double oldi = a[i];
043                double oldj = a[j];
044                if (TestPQ.SHOW_STEPS) { StdOut.format("  exch(%2.0f,%2.0f)> %s\n", oldi, oldj, this); toGraphviz(); }
045                a[i] = oldj;
046                a[j] = oldi;
047        }
048        
049        private boolean isSorted() {
050                for (int i = 2; i < N; i++)
051                        if (a[i] < a[i-1]) return false;
052                return true;
053        }
054}