# 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] = 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; } ```
``` ```
``` ```
``` ```
``` ```