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}