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}