Start Here!

Welcome to your interactive code viewer. Access code snippets via the terminal below by clicking next to the carat below "java links". Type "run" and a list of commands will appear. Press enter (or click) to select a command, then again to run it.

Code snippets are displayed in the other terminal and code notes will appear right here. All code comes from work done at UMass Boston (under Professor Iyer), and utilizes the great work and libraries of the Princeton University CS department.

> java links


  => ["home", "web samples", problem solving blog"]

>

import edu.princeton.cs.algs4.MaxPQ;
import edu.princeton.cs.algs4.Point2D;
import edu.princeton.cs.algs4.Queue;
import edu.princeton.cs.algs4.RectHV;
import edu.princeton.cs.algs4.StdIn;
import edu.princeton.cs.algs4.StdOut;

public class KdTreePointST implements PointST {
    private Node root; // root of the KdTree
    private int N;     // number of nodes in the KdTree

    // 2d-tree (generalization of a BST in 2d) representation.
    private class Node {
        private Point2D p;   // the point
        private Value val;   // the symbol table maps the point to this value
        private RectHV rect; // the axis-aligned rectangle corresponding to 
                             // this node
        private Node lb;     // the left/bottom subtree
        private Node rt;     // the right/top subtree

        // Construct a node given the point, the associated value, and the 
        // axis-aligned rectangle corresponding to the node.
        Node(Point2D p, Value val, RectHV rect) {
            //instantiate the node
            this.p = p;
            this.val = val;
            this.rect = rect;
            //set rb and lb to null, will populate later
            this.lb = null;
            this.rt = null;
        }
    }

    // Construct an empty symbol table of points.
    public KdTreePointST() {
        this.N = 0;
        this.root = null;
    }

    // Is the symbol table empty?
    public boolean isEmpty() { 
        return N == 0;
    }

    // Number of points in the symbol table.
    public int size() {
        return N;
    }

    // Associate the value val with point p.
    public void put(Point2D p, Value val) {
        if (val == null || p == null) { 
            throw new IllegalArgumentException("first arg is null");
        }
        //set a rect to base values for use in put
        RectHV rect = new RectHV(0, 0, 1, 1);
        //root equals call to put, starting with a true flag
        root = put(root, p, val, rect, true);
    }

    // Helper for put(Point2D p, Value val).
    private Node put(Node x, Point2D p, Value val, RectHV rect, boolean lr) {
        if (x == null) {  //if no node then create one
            N++;
            return new Node(p, val, rect);
        }
        if (x.p.equals(p)) { // if the keys are the same then return the node
            x.val = val;
            return x;
        }
        //if lr is true, compare the x values to place the new node
        if (lr) {
          //if new point has smaller x, recursive call to put in left branch
          if (p.x() < x.p.x()) {
            //new rect is put to begin at limits of parent rect
            RectHV rect1 =  new RectHV(rect.xmin(), rect.ymin(), 
                 x.p.x(), rect.ymax());
            //recursive call to left branch with new rectangle
            x.lb = put(x.lb, p, val, rect1, !lr);
            }
          //if new point has greater x, call to put in right branch
          else if (p.x() >= x.p.x()) {
           //new rect begins at the limits of parent rect
           RectHV rect1 = new RectHV(x.p.x(), rect.ymin(), 
               rect.xmax(), rect.ymax());
           //recursive call to right tree with new rectangle
           x.rt = put(x.rt, p, val, rect1, !lr);
            }
        }
        //if lr is false, only compare the y values to place node
        if (!lr) {
          //if new point has smaller y, make call to put in  left branch
          if (p.y() < x.p.y()) {
             //set the rect to begin at limits of parent
             RectHV rect1 = new RectHV(rect.xmin(), rect.ymin(), 
                 rect.xmax(), x.p.y());
             //put in left branch with recursive call
             x.lb = put(x.lb, p, val, rect1, !lr);
           }
           //if new point has larger y, put in right tree
          else if (p.y() >= x.p.y()) {
             //rect begins at parents limits
             RectHV rect1 = new RectHV(rect.xmin(), x.p.y(), 
                 rect.xmax(), rect.ymax());
             //put in the right tree with recursive call
             x.rt = put(x.rt, p, val, rect1, !lr);
            }
        }
        return x;    //return node x
    }
    
    // Value associated with point p.
    public Value get(Point2D p) {
        return get(root, p, true);
    }

    // Helper for get(Point2D p).
    private Value get(Node x, Point2D p, boolean lr) {
        //if no node, return null
        if (x == null) {
            return null;
        }
        //if asking for the current nodes point, return that
        if (x.p.equals(p)) {
            return x.val;
        }
        //if true, compare to x values to find the correct branch
        if (lr) {
            //if x is smaller, prune right branch
            if (p.x() < x.p.x()) {
                return get(x.lb, p, !lr);
            }
            //if x is larger, prune left branch
            if (p.x() >= x.p.x()) {
                return get(x.rt, p, !lr);
            }
        }
        //if false, compare to y values to find right branch
        if (!lr) {
            //if y is smaller, prune right branch
            if (p.y() < x.p.y()) {
                return get(x.lb, p, !lr);
            }
            //if x is small, prune left branch
            if (p.y() >= x.p.y()) {
                return get(x.rt, p, !lr);
            }
        }
        return x.val;
    }

    // Does the symbol table contain the point p?
    public boolean contains(Point2D p) {
        if (p == null) {
            throw new IllegalArgumentException("argument is null");
        }
        return get(p) != null;
    }

    // All points in the symbol table, in level order.
    public Iterable points() {
        //create a queue to hold nodes, one for points
        Queue keys = new Queue();
        Queue queue = new Queue();
        //begin with the root
        queue.enqueue(root);
        //while the node queue has something in it...
        while (!queue.isEmpty()) {
            //set the temp node x
            Node x = queue.dequeue();
            //if its null, get out of there!
            if (x == null) continue;
            //enqueue the temps point values
            keys.enqueue(x.p);
            //enqueue the right and left child nodes to begin again
            queue.enqueue(x.lb);
            queue.enqueue(x.rt);
        }
        //return the keys
        return keys;
    }

    // All points in the symbol table that are inside the rectangle rect.
    public Iterable range(RectHV rect) {
        //create the queue
        Queue results = new Queue(); 
        if (!isEmpty()) {
            //make call to helper function
            range(root, rect, results); 
        }
        return results; 
    }
    
    // Helper for public range(RectHV rect).
    private void range(Node x, RectHV rect, Queue q) {
        //base case using rect api
        if (rect.contains(x.p)) {
            q.enqueue(x.p);
        }
        //if left branch exists and the rectangles overlap, 
        //search within the left branch for points
        if (x.lb != null) {
            if (rect.intersects(x.lb.rect)) {
                range(x.lb, rect, q);
            }
        }
        //if the right branch exists and the rectangles overlap,
        //search within the right branch
        if (x.rt != null) {
            if (rect.intersects(x.rt.rect)) {
                range(x.rt, rect, q);
            }
        }
   }
    // A nearest neighbor to point p; null if the symbol table is empty.
    public Point2D nearest(Point2D p) {
        if (isEmpty()) {
            return null;
        }
        //set values to pass to the helper fucntion
        return nearest(root, p, null, 0.0, true);
    }
    
    // Helper for public nearest(Point2D p).
    private Point2D nearest(Node x, Point2D p, Point2D nearest, 
                            double nearestDistance, boolean lr) {
        //set the current nearest
        Point2D currentNearest = nearest;  
        //base case 1, if no x, return last nearest
        if (x == null) {
            return nearest;
        }
        //second basecase. Currentnearest null checks for empty branches
        //if new nearest is farther away, and the distance isnt zero
        //which ensures you dont return the searching point, 
        //then return the x.p
        if ((currentNearest == null) 
                || (currentNearest.distanceSquaredTo(p) 
                    > x.p.distanceSquaredTo(p)) 
                       && x.p.distanceSquaredTo(p) != 0) { 
            currentNearest = x.p; 
        } 
        //set up stand ins for the rt and lb.
        Node first, second; 
        //if true, compare with x values to determine branch order
        if (lr) { 
            //sets normal order branches for recursive searching
            if (p.x() < x.p.x()) { 
                first = x.lb; 
                second = x.rt; 
            } 
            //sets opposite order branches for recursive searching
            else { 
                first = x.rt; 
                second = x.lb; 
            } 
        } 
        //if false, compare y values to determine branch order
        else { 
            //sets normal order branches for recursive searching
            if (p.y() < x.p.y()) { 
                first = x.lb; 
                second = x.rt; 
            } 
            //sets opposite order branches for recursive searching
            else {     
                first = x.rt; 
                second = x.lb; 
            } 
        } 
        //if the branch exists, and the distance is greater
        //go down the smaller valued branch 
        if (first != null) { 
            if (currentNearest.distanceSquaredTo(p) 
                    > first.rect.distanceSquaredTo(p)) { 
                currentNearest = nearest(first, p, currentNearest, 
                     first.rect.distanceSquaredTo(p), !lr); 
            } 
        } 
        //if the branch exists, and the distance is greater
        //go down the smaller valued branch 
        if (second != null) { 
            if (currentNearest.distanceSquaredTo(p) 
                    > second.rect.distanceSquaredTo(p)) { 
                currentNearest = nearest(second, p, currentNearest, 
                     second.rect.distanceSquaredTo(p), !lr); 
            } 
        }
       return currentNearest; 
    }
    
    // k points that are closest to point p.
    public Iterable nearest(Point2D p, int k) {
        //create all values for helper function
        MaxPQ pq = new MaxPQ(p.distanceToOrder()); 
        nearest(root, p, k, pq, true);
        return pq;
    }

    // Helper for public nearest(Point2D p, int k).
    private void nearest(Node x, Point2D p, int k, MaxPQ pq, 
                         boolean lr) {
      //if no null or k, return
      if (x == null || k == 0) {
          return;
      }
      //if the pq is too large, delete some!
      if (pq.size() > k) {
          pq.delMax();
      }
      //if the size is big and the top is closer, its all wrong
      if (pq.size() >= k && pq.max().distanceSquaredTo(p) 
           <= x.rect.distanceSquaredTo(p)) {
          return;
      }
      //as long as the point isnt the search point, insert!
      if (!x.p.equals(p)) {
          pq.insert(x.p);  
      }
      //recursive calls to check the branches
      nearest(x.lb, p, k, pq, !lr);
      nearest(x.rt, p, k, pq, !lr);
    }
import java.awt.Color;
import edu.princeton.cs.algs4.Picture;

public class SeamCarver {
    private Picture picture; // current picture.
    private double[][] energyTracker;
    private int[][] positionTracker;
    /*
     * To implement my seam carver, I created three new helper methods
     * that were not in the original file. I did this to create more 
     * compact and modular code. The three methods were all related 
     * to energy. I made yColor and xColor methods in order to modularize
     * finding the delta x of color at a given x. I did the same with y
     * 
     * The other method is relax edge. I made this because it would need
     * to be called many times, and making it into a method seemed like the 
     * most efficient approach. 
    */
    
    // Create a seam carver object based on the given picture, making a 
    // defensive copy of picture.
    public SeamCarver(Picture picture) {
        this.picture = new Picture(picture);
    }

    // Current picture.
    public Picture picture() {
        return this.picture;
    }

    // Width of current picture.
    public int width() {
        return picture.width();
    }

    // Height of current picture.
    public int height() {
        return picture.height();
    }

    // Energy of pixel at column x and row y.
    public double energy(int x, int y) {
        //handle the obvious exception cases
        if (x < 0 || x >= width()) {
            throw new IndexOutOfBoundsException();
        }
        if (y < 0 || y >= height()) {
            throw new IndexOutOfBoundsException();
        }
        //returns the sum of the delta y values and delta x values
        //surrounding the given pixel
        return xColor(x, y) + yColor(x, y);
    }
    
    private double xColor(int x, int y) {
        //returns difference between adjancent x pixel color values squared
        //helper values to allow for varibale x positions
        int c1x = x-1;
        int c2x = x+1;
        //if x is first x, c1 uses last x for its adjacent x-1
        if (x == 0) {
           c1x = width() -1;
           c2x = x+1;
        }
        //if x is last value, c2 uses first x for its adjacent x+1
        else if (x == width()-1) {
           c1x = x-1;
           c2x = 0;
        }
        //get the color values of adjacent x pixels
        Color c1 = picture.get(c1x, y);
        Color c2 = picture.get(c2x, y);
        //find the deltas in each color group
        int deltaRed = Math.abs(c2.getRed() - c1.getRed());
        int deltaBlue = Math.abs(c2.getBlue() - c1.getBlue());
        int deltaGreen = Math.abs(c2.getGreen() - c1.getGreen());
        //find the delta squared, done separately for speed
        int redSquare = deltaRed * deltaRed;
        int blueSquare = deltaBlue * deltaBlue;
        int greenSquare = deltaGreen * deltaGreen;
        //return the sum of the squares for energy
        return redSquare + blueSquare + greenSquare;
    }

    private double yColor(int x, int y) {
        //returns difference between adjancent y pixel color values squared
        //helper values to allow for varibale y positions
        int c1y = y-1;
        int c2y = y+1;
        //if y is first y, c1 uses last y for its adjacent y-1
        if (y == 0) {
           c1y = height()-1;
           c2y = y+1;
        }
        //if y is last value, c2 uses first y for its adjacent y+1
        else if (y == height()-1) {
           c1y = y-1;
           c2y = 0;
        }
        //else use normal y+1, y-1 for adjacents
        Color c1 = picture.get(x, c1y);
        Color c2 = picture.get(x, c2y);
        
        //find the deltas in each color group
        int deltaRed = Math.abs(c1.getRed() - c2.getRed());
        int deltaBlue = Math.abs(c1.getBlue() - c2.getBlue());
        int deltaGreen = Math.abs(c1.getGreen() - c2.getGreen());
        //find the delta squared, done separately for speed
        int redSquare = deltaRed * deltaRed;
        int blueSquare = deltaBlue * deltaBlue;
        int greenSquare = deltaGreen * deltaGreen;
        //return the sum of the squares for energy
        return redSquare + blueSquare + greenSquare;
    }
    
    // Sequence of indices for horizontal seam.
    public int[] findHorizontalSeam() {
        /*
         *horizontal seam leans on the vertical seam method
         *we simply transpose the image to reverse x and y, then 
         *remove the vertical seam, then transpose back.
         */
        //create our picture objects for manipulation
        Picture original = picture;
        //tranpose the image
        Picture transposed = transpose(original);
        //set the object image as the transposed image
        this.picture = transposed;
        //identify the vertical seam in tranposed picture
        int[] seam = findVerticalSeam();
        //return to original orientation
        this.picture = original;
        //return the found seam
        return seam;
    }

    // Sequence of indices for vertical seam.
    public int[] findVerticalSeam() {
        //init two 2D arrays
        //energy tracker hold energy values at given pixels
        energyTracker = new double[width()][height()];
        //positionTracker used to ID seams 
        positionTracker = new int[width()][height()];
        //init all energies to inifinity
        for (int x = 0; x < width(); x++) {
            for (int y = 0; y < height(); y++) {
                energyTracker[x][y] = Double.POSITIVE_INFINITY;
            }
        }
        //init top row to proper energy vlaues
        for (int x = 0; x < width(); x++) {
            energyTracker[x][0] = energy(x, 0);
        }
        //Call the relax mehtod on every pixel in the image
        //making sure only to call on legal pixels
        for (int y = 0; y < height() - 1; y++) {
            for (int x = 0; x < width(); x++) {
                if (x > 0) {
                    relaxEdge(x, y, x - 1, y + 1);
                }
                relaxEdge(x, y, x, y + 1);
                if (x < width() - 1) {
                    relaxEdge(x, y, x + 1, y + 1);
                }
            }
        }
        
        // find minimum energy path
        double minEnergy = Double.POSITIVE_INFINITY;
        //lowest energy pixel tracks where the seam will be
        int lowestEnergyPixel = 0;
        //for every pixel across the last line of pixels
        for (int w = 0; w < width(); w++) {
            //find the lowest energy position and store that 
            if (energyTracker[w][height() - 1] < minEnergy) {
                lowestEnergyPixel = w;
                minEnergy = energyTracker[w][height() - 1];
            }
        }
        //create the seam array
        int[] seam = new int[height()];
        //the last pixel is the lowest energy position in the last row
        seam[height() - 1] = lowestEnergyPixel;
        //next pixel beings at the lowest energy pixel
        int nextPixel = positionTracker[lowestEnergyPixel][height() - 1];
        //starting at second to last row, transfer values from positon 
        //tracker into the seam array, finding the lowest energy path
        //REMEMBER  ***positionTracker is updated in the relax method***
        for (int h = height() - 2; h >= 0; h--) {
            seam[h] = nextPixel;
            nextPixel = positionTracker[nextPixel][h];
        }
        return seam;
    }
    
    /*
     * Relax edge does the main work of finding the lowest energy seam by 
     * updating energy values based on the lowest energy path in the adjacent
     * pixels. Once found, it updates the position tracker to reflect the lowest
     * energy positon at that juncture
     */
    private void relaxEdge(int x1, int y1, int x2, int y2) {
        if (energyTracker[x2][y2] > energyTracker[x1][y1] + energy(x2, y2)) {
            energyTracker[x2][y2] = energyTracker[x1][y1] + energy(x2, y2);
            positionTracker[x2][y2] = x1;
        }
    }
    
    // Remove horizontal seam from current picture.
    public void removeHorizontalSeam(int[] seam) {
       //leans on vertical seam removal and transposing
       //Set picture objects for manipulation
       Picture original = picture();
       //change the orientation of the picture
       Picture transposed = transpose(original);
       //set the object picture as the newly tranposed image 
       this.picture = transposed;
       //remove the vertical seam
       removeVerticalSeam(seam);
       //change original to the newly carved image
       original = picture();
       //tranpose original back to the original orientation
       transposed = transpose(original);
       //set the object image to the newly carved and tranposed image
       this.picture = transposed;
    }

    // Remove vertical seam from current picture.
    public void removeVerticalSeam(int[] seam) {
       //Handle basic edge cases
       if (seam == null) {
           throw new NullPointerException();    
       }
       if (seam.length != height()) {
           throw new NullPointerException();    
       }
       //create two picture objects, original and the new image
       Picture original = picture();
       Picture resized = new Picture(original.width() -1, original.height());
       /*
       iterate through every row. For each pixel(column) in the row 
       tranpose the pixel until you reach thr seam. At the seam, skip
       the seam pixel and continue transposing
       */
       //for every row...
       for (int i = 0; i < resized.height(); i++) {
          //for every column until the seam...
          for (int j = 0; j < seam[i]; j++) {
              //tanspose pixels
              resized.set(j, i, original.get(j, i));    
          }
          //for every column after the seam
          for (int j = seam[i]; j < resized.width(); j++) {
              //transpose pixels
              resized.set(j, i, original.get(j+1, i));
          }
       }
       this.picture = resized;
    }

    // Return y - 1 if x < 0; 0 if x >= y; and x otherwise.
    private static int wrap(int x, int y) {
        if (x < 0) {
            return y - 1;
        }
        else if (x >= y) {
            return 0;
        }
        return x;
    }
    /* TRANSPOSE METHOD WAS PROVIDED, I DID NOT WRITE IT! */
    // Return a new picture that is a transpose of the given picture.
    private static Picture transpose(Picture picture) {
        Picture transpose = new Picture(picture.height(), picture.width());
        for (int i = 0; i < transpose.width(); i++) {
            for (int j = 0; j < transpose.height(); j++) {
                transpose.set(i, j, picture.get(j, i));
            }
        }        
        return transpose;
    }
}
import edu.princeton.cs.algs4.In;
import edu.princeton.cs.algs4.StdOut;
import java.util.Arrays;
import java.util.Comparator;

// Implements binary search for clients that may want to know the index of 
// either the first or last key in a (sorted) collection of keys.
public class BinarySearchDeluxe {
    // The index of the first key in a[] that equals the search key, 
    // or -1 if no such key.
    public static  int firstIndexOf(Key[] a, Key key, 
                                         Comparator comparator) {
        //error handling per the PDF requirements
        if (a == null || key == null || comparator == null) {
            throw new java.lang.NullPointerException();
        }
        //set the low pointer to 0
        int low = 0;
        //set high pointer to the end
        int high = a.length - 1;
        
        //while low is less than high, Search!
        while (low + 1 < high) {
            //set mid equal to the difference of high and low
            int mid = low + (high - low)/2;
            //if key is less than or equal to mid indice
            if (comparator.compare(key, a[mid]) <= 0) {
                //set high to mid, its before mid
                high = mid;
            } 
            else {
                //else set low to mid, its after mid
                low = mid;
            }
        }
        
        //if the key indice is the low indice, return it
        if (comparator.compare(key, a[low]) == 0) {
            return low;
        }
        //if the key indice is the high indice, return it
        if (comparator.compare(key, a[high]) == 0) {
            return high;
        }
        //if all else fails, return -1 because the key isnt
        //present in the array
        return -1;
    }

    // The index of the last key in a[] that equals the search key, 
    // or -1 if no such key.
    public static  int lastIndexOf(Key[] a, Key key, 
                                        Comparator comparator) {
        //exception handling per the PDF
        if (a == null || key == null || comparator == null) {
            throw new java.lang.NullPointerException();
        }
        
        //set low indice to zero
        int low = 0;
        //set high indice to the end
        int high = a.length - 1;
        //while low is less than the end, Search!
        while (low + 1 < high) {
            //set mid equal to differnece between low and high
            int mid = low + (high - low)/2;
            //if the key is before mid...
            if (comparator.compare(key, a[mid]) < 0) {
                //set high to mid, its before it
                high = mid;
            } 
            else {
                //set low to mid, its after it
                low = mid;
            }
        }
        //returns the high position first, which should return
        //the last position found if more than one exists
        if (comparator.compare(key, a[high]) == 0) {
            return high;
        }
        //otherwise returns the low position because it is the 
        //only one that exists in the array
        if (comparator.compare(key, a[low]) == 0) {
            return low;
        }
        //if all else fails, return -1 because it doesnt exist 
        //in the array
        return -1;
     }
import edu.princeton.cs.algs4.In;
import edu.princeton.cs.algs4.LinkedBag;
import edu.princeton.cs.algs4.Point2D;
import edu.princeton.cs.algs4.SeparateChainingHashST;
import edu.princeton.cs.algs4.StdOut;

public class EuclideanEdgeWeightedGraph {
    private int V;
    private int E;
    private SeparateChainingHashST> adj;

    // Initialize an empty Euclidean edge-weighted graph from an input stream.
    public EuclideanEdgeWeightedGraph(In in) {
        this.V = in.readInt();
        this.E = in.readInt();
        this.adj = new SeparateChainingHashST
           >();
        if (E < 0) { 
         throw new IllegalArgumentException(
               "Number of edges must be nonnegative");
        }
         for (int i = 0; i < E; i++) {
           Point2D p1 = new Point2D(in.readDouble(), in.readDouble()); 
           Point2D p2 = new Point2D(in.readDouble(), in.readDouble()); 
           EuclideanEdge e = new EuclideanEdge(p1, p2);         
           addEdge(e);
        }
    }
    
    // Number of vertices in this Euclidean edge-weighted graph.
    public int V() {
        return V;
    }

    // Number of edges in this Euclidean edge-weighted graph.
    public int E() {
        return E;
    }

    // Add an undirected edge to this Euclidean edge-weighted graph.
    public void addEdge(EuclideanEdge e) {
        Point2D v = e.either();
        Point2D w = e.other(v);
        if (!adj.contains(v)) {
            LinkedBag bag =  new LinkedBag();
            bag.add(e);
            adj.put(v, bag);
        }
        else if (adj.contains(v)) {
           LinkedBag bag = adj.get(v);
           bag.add(e);
        }
        if (!adj.contains(w)) {
            LinkedBag bag =  new LinkedBag();
            bag.add(e);
            adj.put(w, bag);
        }
        else if (adj.contains(w)) {
           LinkedBag bag = adj.get(w);
           bag.add(e);
        }
    }

    // Edges incident on vertex v.
    public Iterable adj(Point2D v) {
        return adj.get(v);
    }

    // All the edges in this Euclidean edge-weighted graph.
    public Iterable edges() {
        LinkedBag bag = new LinkedBag();
        for (Point2D v : adj.keys()) {
            int selfLoops = 0;
            for (EuclideanEdge e : adj(v)) {
                if (e.other(v).hashCode() > v.hashCode()) {
                    bag.add(e);
                }
                else if (e.other(v).equals(v)) {
                    if (selfLoops % 2 == 0) bag.add(e);
                    selfLoops++;
                }
            }
        }
        return bag;
    }

    // A string representation of this Euclidean edge-weighted graph.
    public String toString() {
        StringBuilder s = new StringBuilder();
        s.append(V + " " + E + "\n");
        for (Point2D v : adj.keys()) {
            s.append(v + ": ");
            for (EuclideanEdge e : adj(v)) {
                s.append(e + "  ");
            }
            s.append("\n");
        }
        return s.toString();
    }	
import edu.princeton.cs.algs4.In;
import edu.princeton.cs.algs4.LinkedQueue;
import edu.princeton.cs.algs4.MinPQ;
import edu.princeton.cs.algs4.Point2D;
import edu.princeton.cs.algs4.SeparateChainingHashST;
import edu.princeton.cs.algs4.StdOut;
import edu.princeton.cs.algs4.UF;

public class EuclideanKruskalMST {
    private double weight; 
    private LinkedQueue mst; 

    // Compute a minimum spanning tree (or forest) of an Euclidean 
    // edge-weighted graph.
    public EuclideanKruskalMST(EuclideanEdgeWeightedGraph G) {
        //init the pq for smallest edges first
        MinPQ pq = new MinPQ();
        //init the mst 
        this.mst = new LinkedQueue();
        //create hast table to assign points integers
        SeparateChainingHashST hasher = 
             new SeparateChainingHashST();
        //insert all edges into both pq and hash table
        for (EuclideanEdge e : G.edges()) {
            pq.insert(e);
            Point2D v = e.either();
            Point2D w = e.other(v);
            hasher.put(v, 1);
            hasher.put(w, 1);
        }
        //assign all points integer keys
        int i = 0;
        for (Point2D v : hasher.keys()) {
            hasher.put(v, i);
            i++;
        }
        // run greedy algorithm
        UF uf = new UF(G.V());
        while (!pq.isEmpty() && mst.size() < G.V()-1) {
            EuclideanEdge e = pq.delMin();
            Point2D v = e.either();
            Point2D w = e.other(v);
            int vInt = hasher.get(v);
            int wInt = hasher.get(w);
            if (!uf.connected(vInt, wInt)) { // v-w does not create a cycle
                uf.union(vInt, wInt);  // merge v and w components
                mst.enqueue(e);  // add edge e to mst
                weight += e.weight();
            }
        }
        StdOut.println();
    }

    // Edges in a minimum spanning tree (or forest).
    public Iterable edges() {
        return mst;
    }

    // Sum of the edge weights in a minimum spanning tree (or forest).
    public double weight() {
        return weight;
    }