willsabich

import java.util.ArrayList;
import java.util.List;
import java.util.Set;
import java.util.stream.Collectors;

/**
 * Filename:   Graph.java
 * Project:    p4
 * Authors:    Alex Restifo (restifo@wisc.edu)
 * <p>
 * Directed and unweighted graph implementation
 */

public class Graph implements GraphADT {
  List<Package> packages;

  /*
   * Default no-argument constructor
   */
  public Graph() {
    this.packages = new ArrayList<>();
  }

  /**
   * Add new vertex to the graph.
   * <p>
   * If vertex is null or already exists,
   * method ends without adding a vertex or
   * throwing an exception.
   * <p>
   * Valid argument conditions:
   * 1. vertex is non-null
   * 2. vertex is not already in the graph
   */
  public void addVertex(String vertex) {
    // Validate input
    if (vertex == null || vertex.isEmpty() || containsPackage(vertex)) return;

    // Create package
    Package newVertex = new Package();
    newVertex.setDependencies(new String[10]);
    newVertex.setName(vertex);

    packages.add(newVertex);
  }

  /**
   * Remove a vertex and all associated
   * edges from the graph.
   * <p>
   * If vertex is null or does not exist,
   * method ends without removing a vertex, edges,
   * or throwing an exception.
   * <p>
   * Valid argument conditions:
   * 1. vertex is non-null
   * 2. vertex is not already in the graph
   */
  public void removeVertex(String vertex) {
    if (vertex == null || !containsPackage(vertex)) return;

    // Remove all edges associated with the given vertex
    for (Package p : packages) {
      String[] pEdges = p.getDependencies();
      for (int i = 0; i < pEdges.length; i++) {
        if (pEdges[i] != null) {
          // If any edge points to the given vertex, remove it
          if (pEdges[i].equals(vertex)) {
            pEdges[i] = null;
          }
        }
      }
    }

    // After removing all edges referring to the package, remove the package itself
    Package toBeRemoved = getPackageFromName(vertex);
    packages.remove(toBeRemoved);
  }

  /**
   * Add the edge from vertex1 to vertex2
   * to this graph.  (edge is directed and unweighted)
   * If either vertex does not exist,
   * add vertex, and add edge, no exception is thrown.
   * If the edge exists in the graph,
   * no edge is added and no exception is thrown.
   * <p>
   * Valid argument conditions:
   * 1. neither vertex is null
   * 2. both packages are in the graph
   * 3. the edge is not in the graph
   */
  public void addEdge(String vertex1, String vertex2) {
    if (vertex1 == null || vertex1.isEmpty() || vertex2 == null || vertex2.isEmpty()) return;

    if (!containsPackage(vertex1)) addVertex(vertex1);
    if (!containsPackage(vertex2)) addVertex(vertex2);

    if (!packageHasDependency(vertex1, vertex2)) addEdgeHelper(vertex1, vertex2);
  }

  /**
   * Remove the edge from vertex1 to vertex2
   * from this graph.  (edge is directed and unweighted)
   * If either vertex does not exist,
   * or if an edge from vertex1 to vertex2 does not exist,
   * no edge is removed and no exception is thrown.
   * <p>
   * Valid argument conditions:
   * 1. neither vertex is null
   * 2. both packages are in the graph
   * 3. the edge from vertex1 to vertex2 is in the graph
   */
  public void removeEdge(String vertex1, String vertex2) {
    // Input validation
    if (vertex1 == null || vertex1.isEmpty() || vertex2 == null || vertex2.isEmpty()) return;
    if (!containsPackage(vertex1) || !containsPackage(vertex2)) return;
    if (!packageHasDependency(vertex1, vertex2)) return;

    Package pack = getPackageFromName(vertex1);
    String[] depends = pack.getDependencies();
    // Iterate through each edge and if it matches, delete it
    for (int i = 0; i < depends.length; i++) {
      if (depends[i] != null) {
        if (depends[i].equals(vertex2)) {
          depends[i] = null;
        }
      }
    }
  }

  /**
   * Returns a Set that contains all the packages
   */
  public Set<String> getAllVertices() {
    // Turns our List of Packages into a Set of Strings.
    return packages.stream() // Get stream of packages
            .map(Package::getName) // Apply Package.getName() to each member of the stream
            .collect(Collectors.toSet()); // Collect all the package names into a Set
  }

  /**
   * Get all the neighbor (adjacent) packages of a vertex
   */
  public List<String> getAdjacentVerticesOf(String vertex) {
    List<String> adjVert = new ArrayList<>();

    Package pack = getPackageFromName(vertex);
    String[] depends = pack.getDependencies();
    // Iterate through all dependencies of the given vertex. These are our adjacent vertices.
    for (int i = 0; i < depends.length; i++) {
      if (depends[i] != null) {
        adjVert.add(depends[i]);
      }
    }
    return adjVert;
  }

  /**
   * Returns the number of edges in this graph.
   */
  public int size() {
    int edges = 0;
    // Look at each vertex to count the number of edges
    for (Package p : packages) {
      String[] depends = p.getDependencies();
      for (int i = 0; i < depends.length; i++) {
        if (depends[i] != null) {
          edges++;
        }
      }
    }
    return edges;
  }

  /**
   * Returns the number of packages in this graph.
   */
  public int order() {
    return packages.size();
  }


  // All the following methods are private helper methods
  private boolean containsPackage(String packageName) {
    for (Package p : packages) {
      if (p.getName().equals(packageName)) {
        return true;
      }
    }
    return false;
  }

  private Package getPackageFromName(String packageName) {
    for (Package p : packages) {
      if (p.getName().equals(packageName)) {
        return p;
      }
    }
    return null;
  }

  private void addEdgeHelper(String vertex1, String vertex2) {
    // Need to use this annoying work around because Package requires us to use an array instead
    // of ArrayList...
    Package p = getPackageFromName(vertex1);
    String[] packEdges = p.getDependencies();

    // This loop finds the next available index for a dependency
    int index;
    for (index = 0; index < packEdges.length && packEdges[index] != null; index++);

    packEdges[index] = vertex2;
    p.setDependencies(packEdges);
  }

  private boolean packageHasDependency(String p, String dependency) {
    Package pack = getPackageFromName(p);
    String[] packDepends = pack.getDependencies();
    for (String depend : packDepends) {
      if (depend != null) {
        if (depend.equals(dependency)) {
          return true;
        }
      }
    }
    return false;
  }

  private void printPackageList(List<Package> packages) {
    for (Package p : packages) {
      System.out.print(p.getName() + ": ");
      for (String depend : p.getDependencies()) {
        if (depend != null) {
          System.out.print(depend + ", ");
        }
      }
      System.out.println();
    }
  }
}