001package algs24; 002import stdlib.*; 003import java.util.Arrays; 004 005public class FixedPQUnordered implements PQ { 006 private int N; 007 private double[] a; 008 009 public FixedPQUnordered(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 } 021 private int minPosition() { 022 if (N<=0) throw new Error("Underflow"); 023 int result = 1; 024 for (int i=2; i<=N; i++) 025 if (a[i] < a[result]) result = i; 026 return result; 027 } 028 public double min() { 029 int m = minPosition(); 030 return a[m]; 031 } 032 public double delMin() { 033 int m = minPosition(); 034 double result = a[m]; 035 exch2(m, N); 036 a[N] = 0.0; 037 N--; 038 return result; 039 } 040 private void exch2(int i, int j) { 041 double oldi = a[i]; 042 double oldj = a[j]; 043 if (TestPQ.SHOW_STEPS) { StdOut.format(" exch(%2.0f,%2.0f)> %s\n", oldi, oldj, this); toGraphviz(); } 044 a[i] = oldj; 045 a[j] = oldi; 046 } 047}