Review Tests for Project 8

Closes #2, #3, #4, #5, #6, #9, #10 Related to #7

There were a decent amount of changes (to interfaces and methods) to this one, so I'd appreciate a double check to make sure I didn't break anything or if there are any compatibility issues.

src/edu/caltech/cs2/datastructures/BeaverMapsGraph.java

 
 import com.google.gson.JsonElement;
 import com.google.gson.JsonParser;
-import edu.caltech.cs2.interfaces.IDeque;
-import edu.caltech.cs2.interfaces.IDictionary;
-import edu.caltech.cs2.interfaces.ISet;
+import edu.caltech.cs2.interfaces.*;

tests/edu/caltech/cs2/project08/BeavermapTests.java

 
             IDeque<Location> actualPath = bmg.dijkstra(start, target);
             List<Long> actualPathIDs = new ArrayList<>();
             if (actualPath != null) {

src/edu/caltech/cs2/datastructures/BeaverMapsGraph.java

 import edu.caltech.cs2.interfaces.IDictionary;
 import edu.caltech.cs2.interfaces.ISet;
 
-import java.io.File;
 import java.io.FileReader;
 import java.io.IOException;
 
 
 public class BeaverMapsGraph extends Graph<Long, Double> {
-    private static JsonParser JSON_PARSER = new JsonParser();
-
     private IDictionary<Long, Location> ids;
     private ISet<Location> buildings;
 
      * @return the JSON data from filename
      */
     private static JsonElement fromFile(String filename) {
-        try {
-            return JSON_PARSER.parse(
-                    new FileReader(
-                            new File(filename)
-                    )
-            );
+        try (FileReader reader = new FileReader(filename)) {
+            return JsonParser.parseReader(reader);
         } catch (IOException e) {
             return null;
         }

src/edu/caltech/cs2/datastructures/Graph.java

 package edu.caltech.cs2.datastructures;
 
-import edu.caltech.cs2.interfaces.*;
+import edu.caltech.cs2.interfaces.IDictionary;
+import edu.caltech.cs2.interfaces.IGraph;
+import edu.caltech.cs2.interfaces.ISet;
 
-public class Graph<V, E> extends IGraph<V, E> {
+public class Graph<V, E> implements IGraph<V, E> {
 
     @Override
     public boolean addVertex(V vertex) {

src/edu/caltech/cs2/interfaces/IDictionary.java

 package edu.caltech.cs2.interfaces;
 
+import edu.caltech.cs2.datastructures.LinkedDeque;
+
 public interface IDictionary<K, V> extends Iterable<K> {
 
     public static class Entry<K, V> {

src/edu/caltech/cs2/interfaces/IGraph.java

 package edu.caltech.cs2.interfaces;
 
-public abstract class IGraph<V, E> {
+public interface IGraph<V, E> {
     /**
      * Add a vertex to the graph.
      * @param vertex The vertex to add
      * @return true if vertex was not present already.
      */
-    public abstract boolean addVertex(V vertex);
+    public boolean addVertex(V vertex);
 
     /**
      * Adds edge e to the graph.
      *
      * @param e The edge to add.
      * @throws IllegalArgumentException
-     *             If e is not a valid edge (eg. refers to vertices not in the graph).
-     * @return true If e was not already present; false if it was (in which case the graph is still updated).
+     *             If src and dest are not valid vertices (eg. refers to vertices not in the graph).
+     * @return true If src and dest were not already present; false if it was (in which case the graph is still updated).
      */
-    public abstract boolean addEdge(V src, V dest, E e);
+    public boolean addEdge(V src, V dest, E e);
 
     /**
      * Adds edge e to the graph in both directionns.
      *
      * @param e The edge to add.
      * @throws IllegalArgumentException
-     *    If e is not a valid edge (eg. refers to vertices not in the graph).
-     * @return true If e was not already present in either direction; false if it was (in which case the graph is still updated).
+     *    If src and dest are not valid vertices (eg. refers to vertices not in the graph).
+     * @return true If src and dest were not already present in either direction; false if it was (in which case the graph is still updated).
      */
-    public abstract boolean addUndirectedEdge(V src, V dest, E e);
+    public boolean addUndirectedEdge(V src, V dest, E e);
 
     /**
      * Remove an edge from src to dest from the graph.
      * @throws IllegalArgumentException if src or dest is not in the graph.
      * @return true if an edge from src to dest edge was present.
      */
-    public abstract boolean removeEdge(V src, V dest);
+    public boolean removeEdge(V src, V dest);
 
     /**
      * Returns the set of vertices in the graph.
      * @return The set of all vertices in the graph.
      */
-    public abstract ISet<V> vertices();
+    public ISet<V> vertices();
 
     /**
      * Tests if vertices i and j are adjacent, returning the edge between
      * @return The edge from i to j if it exists in the graph;
      * 		   null otherwise.
      */
-    public abstract E adjacent(V i, V j);
+    public E adjacent(V i, V j);
 
     /**
      * Return the neighbours of a given vertex when this graph is treated as
      * @throws IllegalArgumentException if vertex is not in the graph.
      * @return The set of neighbors of vertex.
      */
-    public abstract ISet<V> neighbors(V vertex);
+    public ISet<V> neighbors(V vertex);
 }
\ No newline at end of file

src/edu/caltech/cs2/project08/BeaverMaps.java

 import com.sun.net.httpserver.HttpHandler;
 import com.sun.net.httpserver.HttpServer;
 import edu.caltech.cs2.datastructures.BeaverMapsGraph;
+import edu.caltech.cs2.datastructures.LinkedDeque;
 import edu.caltech.cs2.datastructures.Location;
 import edu.caltech.cs2.interfaces.IDeque;
 import edu.caltech.cs2.interfaces.ISet;

src/edu/caltech/cs2/project08/MapsAutoCompleter.java

 package edu.caltech.cs2.project08;
 
+import edu.caltech.cs2.datastructures.LinkedDeque;
 import edu.caltech.cs2.datastructures.Location;
+import edu.caltech.cs2.datastructures.TrieMap;
 import edu.caltech.cs2.interfaces.IDeque;
 import edu.caltech.cs2.interfaces.ISet;
 import edu.caltech.cs2.interfaces.ITrieMap;

tests/edu/caltech/cs2/project08/BeavermapTests.java

 import edu.caltech.cs2.helpers.Inspection;
 import edu.caltech.cs2.helpers.Reflection;
 
-import java.io.File;
 import java.io.FileNotFoundException;
 import java.io.FileReader;
 import java.io.IOException;
 import org.hamcrest.MatcherAssert;
 import org.hamcrest.collection.IsIterableContainingInAnyOrder;
 import org.hamcrest.collection.IsIterableContainingInOrder;
-import org.hamcrest.core.IsCollectionContaining;
+import org.hamcrest.core.IsIterableContaining;
 import org.junit.jupiter.api.*;
 import org.junit.jupiter.api.MethodOrderer;
 import org.junit.jupiter.api.TestMethodOrder;
 @TestMethodOrder(MethodOrderer.OrderAnnotation.class)
 public class BeavermapTests {
     private static String BEAVERMAP_GRAPH_SOURCE = "src/edu/caltech/cs2/datastructures/BeaverMapsGraph.java";
-    private static JsonParser JSON_PARSER = new JsonParser();
 
     private static JsonElement fromFile(String filename) {
-        try {
-            return JSON_PARSER.parse(
-                    new FileReader(
-                            new File(filename)
-                    )
-            );
-        } catch (IOException e) {
+        try (FileReader reader = new FileReader(filename)) {
+            return JsonParser.parseReader(reader);
+        }
+        catch (IOException e) {
             return null;
         }
     }
         }
     }
 
+    @Tag("C")
+    @DisplayName("Test addVertex() updates BeaverMapsGraph properly")
+    @Test
+    public void testAddVertexBeaverMapsGraph() {
+        BeaverMapsGraph bmg = new BeaverMapsGraph(
+                "data/caltech/caltech.buildings.json",
+                "data/caltech/caltech.waypoints.json",
+                "data/caltech/caltech.roads.json");
+        JsonElement bs = fromFile("data/pasadena/pasadena.buildings.json");
+        for (JsonElement b : bs.getAsJsonArray()) {
+            Location loc = new Location(b.getAsJsonObject());
+            bmg.addVertex(loc);
+            assertNotNull(bmg.getLocationByID(loc.id), "Location id " + loc.id + " not found by id");
+        }
+    }
+
     @Tag("C")
     @DisplayName("BeaverMapsGraph implements required public methods")
     @Test
                         .map(x -> x.getName())
                         .collect(Collectors.toList()));
         MatcherAssert.assertThat(new ArrayList<>(actual),
-                IsCollectionContaining.hasItems((expected.toArray())));
+                IsIterableContaining.hasItems((expected.toArray())));
     }
 
 
         }
     }
 
+    @Tag("A")
+    @DisplayName("Test buildings are ignored in dijkstra path")
+    @Test
+    public void testDijkstraIgnoreBuildings() {
+        BeaverMapsGraph bmg = new BeaverMapsGraph(
+                "data/caltech/caltech.buildings.json",
+                "data/caltech/caltech.waypoints.json",
+                "data/caltech/caltech.roads.json");
+        JsonElement s = fromFile("data/caltech/caltech.paths_trace.json");
+        for (JsonElement b : s.getAsJsonArray()) {
+            JsonObject curr = b.getAsJsonObject();
+            Location start = bmg.getLocationByID(curr.get("start").getAsLong());
+            Location target = bmg.getLocationByID(curr.get("target").getAsLong());
+
+            IDeque<Location> actualPath = bmg.dijkstra(start, target);
+            if (actualPath == null) {
+                continue;
+            }
+            for (Location loc : actualPath){
+                if (loc.id == start.id || loc.id == target.id) {
+                    continue;
+                }
+                ISet<Location> buildings = Reflection.getFieldValue(BeaverMapsGraph.class, "buildings", bmg);
+                assertFalse(buildings.contains(loc), "Location " + loc.id + " in path is a building");
+            }
+        }
+    }
 
     @Tag("A")
     @DisplayName("Test Dijkstra")
 
             IDeque<Location> actualPath = bmg.dijkstra(start, target);
             List<Long> actualPathIDs = new ArrayList<>();
             if (actualPath != null) {
                 for (Location l : actualPath) {
                     actualPathIDs.add(l.id);
                 }

tests/edu/caltech/cs2/project08/DijkstraTest.java

 
         Scanner s = new Scanner(new File("data/dijkstra/" + traceFile));
 
-        if (res == null) {
-            assertEquals(s.nextLine(), "null", "Path exists but was not found");
+        String line = s.nextLine();
+        if (line.equals("null")) {
+            assertNull(res, "Path does not exist but was found");
         }
         else {
+            assertNotNull(res, "Path exists but was not found");
             for (Location l : res) {
                 if (prev != null) {
                     pathLen += bmg.adjacent(prev.id, l.id);
                 prev = l;
             }
 
-            double expectedLen = s.nextDouble();
+            double expectedLen = Double.parseDouble(line);
 
             assertEquals(expectedLen, pathLen, "Path lengths are not equivalent");
         }
     @Order(3)
     @DisplayName("Tests Dijkstra on random graph and paths")
     @Test
-    public void dijkstraStressTest() throws FileNotFoundException{
+    public void dijkstraStressTest() throws FileNotFoundException {
         final int num_tests = 1000;
         IGraph<Integer, Integer> refg = new Graph<Integer, Integer>();
 
             BeaverMapsGraph bmg = GraphMaker.transformToLocations(refg);
             IDeque<Location> res = bmg.dijkstra(new Location(startvertex), new Location(endvertex));
 
-            if (res == null) {
-                assertEquals(s.nextLine(), "null", "Path exists but was not found");
+            String line = s.nextLine();
+            if (line.equals("null")) {
+                assertNull(res, "Path does not exist but was found");
             }
             else {
+                assertNotNull(res, "Path exists but was not found");
                 double pathLen = 0;
                 Location prev = null;
                 for (Location l : res) {
                     prev = l;
                 }
 
-                double expectedLen = s.nextDouble();
-                s.nextLine();
+                double expectedLen = Double.parseDouble(line);
                 assertEquals(expectedLen, pathLen, "Path lengths are not equivalent");
             }
         }

tests/edu/caltech/cs2/project08/GraphTests.java

         });
     }
 
+    @Test
+    public void undirectedEdgeTest() {
+        assertTimeout(Duration.ofMillis(SIMPLE_OP_TIMEOUT_MS), () -> {
+            IGraph<String, Integer> g = new Graph<>();
+
+            assertTrue(g.addVertex("1"), "Should be able to add a vertex");
+            assertEquals(1, g.vertices().size(), "Should have correct number of vertices");
+            assertTrue(g.addVertex("2"), "Should be able to add a vertex");
+            assertEquals(2, g.vertices().size(), "Should have correct number of vertices");
+            assertTrue(g.addVertex("3"), "Should be able to add a vertex");
+            assertEquals(3, g.vertices().size(), "Should have correct number of vertices");
+
+            assertTrue(g.addUndirectedEdge("1", "2", 1), "Should be able to add new edge");
+            assertFalse(g.addEdge("1", "2", 1), "Should not be able to add new edge");
+            assertFalse(g.addEdge("1", "2", 2), "Should not be able to add new edge");
+            assertFalse(g.addEdge("2", "1", 1), "Should not be able to add new edge");
+            assertFalse(g.addEdge("2", "1", 2), "Should not be able to add new edge");
+
+            assertTrue(g.addUndirectedEdge("1", "3", 1), "Should be able to add new edge");
+            assertFalse(g.addEdge("1", "3", 1), "Should not be able to add new edge");
+            assertFalse(g.addEdge("1", "3", 2), "Should not be able to add new edge");
+            assertFalse(g.addEdge("3", "1", 1), "Should not be able to add new edge");
+            assertFalse(g.addEdge("3", "1", 2), "Should not be able to add new edge");
+
+            assertTrue(g.addUndirectedEdge("2", "3", 1), "Should be able to add new edge");
+            assertFalse(g.addEdge("2", "3", 1), "Should not be able to add new edge");
+            assertFalse(g.addEdge("2", "3", 2), "Should not be able to add new edge");
+            assertFalse(g.addEdge("3", "2", 1), "Should not be able to add new edge");
+            assertFalse(g.addEdge("3", "2", 2), "Should not be able to add new edge");
+        });
+    }
+
     @Test
     public void stringEdgeTest() {
         assertTimeout(Duration.ofMillis(SIMPLE_OP_TIMEOUT_MS), () -> {

[Ethan Ordentlich]

No star imports (static tests)

[Archie Shahidullah]

Also fixed star import in Graph.java

[Ethan Ordentlich]

#2 applies here, I believe

[Archie Shahidullah]

This method just tests whether dijkstra actually produces a path without buildings, rather than checking it for correctness against the trace. It just uses the start and target locations from trace. So I just check for null to only check existing paths. Should I check it for correctness (since it's already done in the stress test)?

[Ethan Ordentlich]

You're thinking of #3 and testDijkstraIgnoreBuildings (thanks for adding that). This is a separate issue - if actualPath is null and there is an expected path, the failure will read "Found path... where there is none."

[Archie Shahidullah]

Also added some IDs to the error messages in DijkstraTest

[Ethan Ordentlich]

#2 applies here, I believe

[Archie Shahidullah]

This method just tests whether dijkstra actually produces a path without buildings, rather than checking it for correctness against the trace. It just uses the start and target locations from trace. So I just check for null to only check existing paths. Should I check it for correctness (since it's already done in the stress test)?

[Ethan Ordentlich]

You're thinking of #3 and testDijkstraIgnoreBuildings (thanks for adding that). This is a separate issue - if actualPath is null and there is an expected path, the failure will read "Found path... where there is none."

[Archie Shahidullah]

Also added some IDs to the error messages in DijkstraTest