LOl.java

  /**
     * Returns the first occurrence of the character given by parameter in the queue given using
     * a binary search.
     *
     * @param pChar the character being searched
     * @param lo    the low boundary for the search
     * @param hi    the upper boundary for the search
     * @return the index at which the character first appears in the queue
     */
    private int findFirst(int pChar, int lo, int hi) {

        if (hi >= lo) {
            int mid = lo + (hi - lo) / 2;
            int midChar = tripsbyWeek.getNode(mid).getSourceId();

            // Since the arrays inside the priority queues that use this method are 1-indexed, we
            // must check the case in which mid = lo. If we execute "int = midMinusOne" before
            // checking if we've reached the start of the array, we could get an exception.
            if (mid == lo && midChar == pChar)
                return mid;

            int midMinusOne = tripsbyWeek.getNode(mid - 1).getSourceId();

            if (((mid == 1 || pChar > midMinusOne)) && midChar == pChar)
                return mid;

            else if (pChar > midChar)
                return findFirst(pChar, mid + 1, hi);
            else
                return findFirst(pChar, lo, mid - 1);
        }
        return -1;
    }

    /**
     * Calculates the second cost arc between two vertices
     *
     * @param pStart the start vertex
     * @param pEnd   the end vertex
     * @return the second cost arc (average velocity between two vertices)
     */
    private Double calculateCost2(GraphVertex pStart, GraphVertex pEnd)
            throws NullPointerException {

        // array containing the average travel times
        DynamicArray<Double> times = new DynamicArray<>();

        // zones from the vertices
        int zoneA = pStart.getZone();
        int zoneB = pEnd.getZone();

        // the last index of the queue
        int endIndex = tripsbyWeek.getLastIndex();

        // the average of travel times
        double averageTime = 0.0;

        // find the first occurrence of the given startZone
        int index = findFirst(zoneA, 1, endIndex);

        boolean diff = false;

        // search from the start of first occurrence of the sourceId (don't exceed the last
        // index)
        while (!diff && index != -1 && index <= tripsbyWeek.getLastIndex()) {

            UberTrip currTrip = tripsbyWeek.getNode(index);


            int currSourceId = currTrip.getSourceId();
            int currDestId = currTrip.getDestinationId();

            if (currDestId == zoneB)
                times.add(currTrip.getMeanTravelTime());

            // exit the loop if the startId is different from zoneA
            if (currSourceId != zoneA)
                diff = true;

            index++;
        }

        // if the zones are equal and no trips were found
        if ((zoneA == zoneB) && times.size() == 0) {
            averageTime = 10.0; //(ex 574,574)
        }

        // if the zones are distinct and no trips were found
        else if ((zoneA != zoneB) && times.size() == 0) {
            averageTime = 100.0; // (ex 73,1020)
        }

        // if the trips are equal or distinct, find the average of times
        else {
            for (int i = 0; i < times.size(); i++) {
                averageTime += times.get(i);
            }
            averageTime /= times.size();
        }

        return averageTime;
    }

   // -------------------------------------------------------------
    // Point 10
    // -------------------------------------------------------------

    /**
     * Creates a graph containing the uber zones as vertices. The edge cost are calculated in the
     * following way:
     * (1) From zoneA to zoneB there will only be one edge.
     * (2) For any edge x, if it isn't in the hash table, find all trips in the csv file
     * that match the respective start & end zones and take the average of their travel times.
     * (3) For the same edge, find all trips in the csv file that match the respective start
     * & end zones but in the reverse direction and take the average of their travel times.
     * (4) Take the average of both of these trips.
     * Additional notes: If an edge from the original graph is located inside the same zone,
     * don't consider it for the zones graph.
     */
    public Graph<Integer, GraphVertex> createZoneGraph() {
        zonesGraph = new Graph<>(5);

        // hash tables to keep track of what has already added to the graph
        HashTable<Integer, Integer> vertexMap = new HashTable<>();
        HashTable<String, Integer> edgeMap = new HashTable<>();

        // dynamic array that stores edges with no trips
        DynamicArray<String> noUberTrips = new DynamicArray<>();

        // list of edges in the current graph
        DynamicArray<Edge<Integer>> edgeList = graph.getMapEdgeList();

        // iterate over every edge
        for (int i = 0; i < edgeList.size(); i++) {
            // current vertices of the current edge
            GraphVertex startVertex = graph.getVertexInfo(edgeList.get(i).getStartVertex());
            GraphVertex endVertex = graph.getVertexInfo(edgeList.get(i).getEndVertex());

            int startZone = startVertex.getZone();
            int endZone = endVertex.getZone();

            // go to next edge if the zones are the same
            if (startZone != endZone) {

                // comparison booleans for the latter decisions
                boolean startVExists = vertexMap.containsKey(startZone);
                boolean endVExists = vertexMap.containsKey(endZone);
                boolean edgeExists = edgeMap.containsKey(startZone + "$" + endZone) && edgeMap
                        .containsKey(endZone + "$" + startZone);

                // if start vertex isn't in the map (don't care about the value)
                if (!startVExists) {

                    vertexMap.putNode(startZone, 0);
                    startVertex.setId(startZone);
                    zonesGraph.addVertex(startZone, startVertex);
                }

                // if end vertex isn't in the map (don't care about the value)
                if (!endVExists) {
                    vertexMap.putNode(endZone, 0);
                    endVertex.setId(endZone);
                    zonesGraph.addVertex(endZone, endVertex);
                }

                // if the edge exists (A->B & B->A)
                if (!edgeExists) {

                    // calculate the average of the bidirectional costs
                    double costAtoB = calculateCost2(startVertex, endVertex);
                    double costBtoA = calculateCost2(endVertex, startVertex);

                    // average of costs. (from A->B and B->A)
                    double newAvgTime = (costAtoB + costBtoA) / 2;

                    // if the avg is 100, that means there were no trips in either direction
                    // add this edge to the list of noTrips
                    if (newAvgTime == 100.0) {
                        newAvgTime = 200.0;
                        noUberTrips.add(startZone + "-" + endZone);
                    }

                    zonesGraph.addEdge(startZone, endZone, 0, newAvgTime, 0);
                    edgeMap.putNode(startZone + "$" + endZone, 0);
                    edgeMap.putNode(endZone + "$" + startZone, 0);
                }
            }
        }
        return zonesGraph;
    }

    public void drawZoneGraph(DynamicArray<Edge<Integer>> pEdges) {

        DynamicArray<LatLng[]> edgeVerts = new DynamicArray<>();
        for (int i = 0; i < pEdges.size(); i++) {
            int startId = pEdges.get(i).getStartVertex();
            int endId = pEdges.get(i).getEndVertex();

            GraphVertex startVertex = zonesGraph.getVertexInfo(startId);
            GraphVertex endVertex = zonesGraph.getVertexInfo(endId);

            double startLat = startVertex.getLatitude();
            double startLong = startVertex.getLongitude();

            double endLat = endVertex.getLatitude();
            double endLong = endVertex.getLongitude();

            LatLng start = new LatLng(startLat, startLong);
            LatLng end = new LatLng(endLat, endLong);

            LatLng[] locations = {start, end};
            edgeVerts.add(locations);
        }
        new Mapa("zones", edgeVerts);
    }

    public void drawPathGraph(DynamicArray<Edge<Integer>> pEdges) {

        DynamicArray<LatLng[]> edgeVerts = new DynamicArray<>();
        for (int i = 0; i < pEdges.size(); i++) {
            int startId = pEdges.get(i).getStartVertex();
            int endId = pEdges.get(i).getEndVertex();

            GraphVertex startVertex = graph.getVertexInfo(startId);
            GraphVertex endVertex = graph.getVertexInfo(endId);

            double startLat = startVertex.getLatitude();
            double startLong = startVertex.getLongitude();

            double endLat = endVertex.getLatitude();
            double endLong = endVertex.getLongitude();

            LatLng start = new LatLng(startLat, startLong);
            LatLng end = new LatLng(endLat, endLong);

            LatLng[] locations = {start, end};
            edgeVerts.add(locations);
        }
        Mapa map = new Mapa("zones", edgeVerts);
    }


    public void drawPath1Graph(DynamicArray<Integer> pVerts) {
        DynamicArray<LatLng[]> edgeVerts = new DynamicArray<>();
        for (int i = pVerts.size() - 1; i > 0; i--) {
            Edge<Integer> edge = new Edge<>(pVerts.get(i), pVerts.get(i - 1), 0, 0, 0);

            int startId = edge.getStartVertex();
            int endId = edge.getEndVertex();

            GraphVertex startVertex = graph.getVertexInfo(startId);
            GraphVertex endVertex = graph.getVertexInfo(endId);

            double startLat = startVertex.getLatitude();
            double startLong = startVertex.getLongitude();

            double endLat = endVertex.getLatitude();
            double endLong = endVertex.getLongitude();

            LatLng start = new LatLng(startLat, startLong);
            LatLng end = new LatLng(endLat, endLong);

            LatLng[] locations = {start, end};
            edgeVerts.add(locations);
        }
        new Mapa("zones", edgeVerts);
    }

    /**
     * Returns the zone graph
     *
     * @return the zone graph
     */
    public Graph<Integer, GraphVertex> getZoneGraph() {
        return zonesGraph;
    }

    /**
     * Returns the graph
     *
     * @return the graph
     */
    public Graph<Integer, GraphVertex> getGraph() {
        return graph;
    }

    // -------------------------------------------------------------
    // Point 11
    // -------------------------------------------------------------


    public DynamicArray<Integer> minPath(int pStartVertex, int pEndVertex) {

        // if the zone graph is loaded, there are fewer vertices in that graph than there are
        // total possible zones. So, add an offset to the size to prevent a null pointer exception.
        int diff = Math.abs(graph.getVertices() - maxZoneId) + 1;

        DynamicArray<Double> distTo = new DynamicArray<>(graph.getVertices() + diff);

        DynamicArray<Integer> vertexFrom = new DynamicArray<>(graph.getVertices() + diff);

        LinkedList<Integer, Integer> queue = new LinkedList<>();
        for (int i = 0; i < graph.getVertices(); i++) {
            distTo.add(Double.POSITIVE_INFINITY);
        }

        graph.uncheckAll();
        VertexNode<Integer, GraphVertex> start = graph.getVertexNode(pStartVertex);
        start.setVisited();
        vertexFrom.set(pStartVertex, -1);
        distTo.set(pStartVertex, 0.0);

        queue.append(new Node<>(pStartVertex, 0));
        while (!queue.isEmpty()) {

            Node<Integer, Integer> curr = queue.removeHead();
            VertexNode<Integer, GraphVertex> currVertex = graph.getVertexNode(curr.getId());
            DynamicArray<Node<Integer, Double[]>> adjacentVertices =
                    currVertex.getAdjacentVerticesList();

            // iterate over adjacent vertices
            for (int i = 0; i < adjacentVertices.size(); i++) {
                int currId = adjacentVertices.get(i).getId();

                VertexNode<Integer, GraphVertex> currAdj = graph.getVertexNode(currId);

                if (!currAdj.isVisited()) {
                    currAdj.setVisited();
                    vertexFrom.set(currId, curr.getId());
                    distTo.set(currId, distTo.get(curr.getId()) + 1);
                    queue.append(new Node<>(currAdj.getId(), 0));
                }
            }
        }


        DynamicArray<Integer> fromList = new DynamicArray<>();
        Integer startP = vertexFrom.get(pEndVertex);
        if (startP != null) {

            fromList.add(pEndVertex);
            int curr = startP;
            while (curr != -1) {
                fromList.add(curr);
                curr = vertexFrom.get(curr);
            }
        }
        return fromList;
    }

    /**
     * Returns the longest path out of the shortest possible paths from a vertex to any of its
     * reachable vertices
     *
     * @param pStartZone the start zone
     * @return
     */
    public DynamicArray<Edge<Integer>> longestReachablePath(int pStartZone) {
        DynamicArray<Edge<Integer>> edges = new DynamicArray<>();

        // queue to store the paths
        PriorityQueue<QueueNode<Integer, DynamicArray<Integer>>> pathsQueue = new PriorityQueue<>();

        // reachable vertices
        DynamicArray<Integer> reachableVertices = graph.getReachableVertices(pStartZone);

        // iterate over all reachable vertices
        for (int i = 0; i < reachableVertices.size(); i++) {
            int end = reachableVertices.get(i);
            DynamicArray<Integer> path = minPath(pStartZone, end);
            int cost = path.size() - 1;
            pathsQueue.add(new QueueNode<>(cost, path), false);
        }

        if (pathsQueue.size() != 0) {
            DynamicArray<Integer> maxPath = pathsQueue.delMax().getValue();
            for (int i = maxPath.size() - 1; i > 0; i--) {
                int start = graph.getVertexNode(maxPath.get(i)).getValue().getId();
                int end = graph.getVertexNode(maxPath.get(i - 1)).getValue().getId();

                Edge<Integer> edge = new Edge<>(start, end, 0, 0, 0);
                edges.add(edge);
            }
        }

        return edges;
    }

    // -------------------------------------------------------------
    // Point 12
    // -------------------------------------------------------------

    public DynamicArray<Integer> djikstra(int pStartVertex, int pEndVertex) {
        // if the zone graph is loaded, there are fewer vertices in that graph than there are
        // total possible zones. So, add an offset to the size to prevent a null pointer exception.

        totalCost = 0;
        int diff = Math.abs(graph.getVertices() - maxZoneId) + 1;

        DynamicArray<Double> distTo = new DynamicArray<>(graph.getVertices() * 2 + diff);

        DynamicArray<Integer> vertexFrom = new DynamicArray<>(graph.getVertices() + diff);

        IndexPQ<QueueNode2<Double, Integer>> queue = new IndexPQ<>(graph.getVertices() + diff);

        // keep track of the added vertices
        HashTable<Integer, Integer> vertexTable = new HashTable<>();

        // Set distTo to infinity for all vertices

        for (int i = 0; i < graph.getVertices() * 2 + diff; i++) {
            distTo.add(Double.POSITIVE_INFINITY);
        }

        // uncheck all as visited just in case we already executed it earlier
        graph.uncheckAll();

        VertexNode<Integer, GraphVertex> start = graph.getVertexNode(pStartVertex);

        vertexFrom.set(pStartVertex, -1);
        distTo.set(pStartVertex, 0.0);

        queue.insert(pStartVertex, new QueueNode2<>(distTo.get(pStartVertex), pStartVertex));
        int test = 0;
        while (!queue.isEmpty()) {

            int curr = queue.delMin();

            VertexNode<Integer, GraphVertex> currVertex = graph.getVertexNode(curr);
            currVertex.setVisited();

            DynamicArray<Node<Integer, Double[]>> adjacentVertices =
                    currVertex.getAdjacentVerticesList();
            int test1 = 0;
            // iterate over adjacent vertices
            for (int i = 0; i < adjacentVertices.size(); i++) {

                Node<Integer, Double[]> currNode = adjacentVertices.get(i);
                int currId = currNode.getId();

                double prevWeight = distTo.get(currId);

                // calculate distance to father plus distance to child
                double currWeight = distTo.get(curr) + currNode.getValue()[1];

                VertexNode<Integer, GraphVertex> currAdj = graph.getVertexNode(currId);

                if (!currAdj.isVisited()) {
                    if (prevWeight > currWeight) {
                        distTo.set(currId, currWeight);
                        vertexFrom.set(currId, curr);
                        if (queue.contains(currId)) {
                            queue.decreaseKey(currId, new QueueNode2<>(currWeight, currId));
                        }
                        else
                            queue.insert(currId, new QueueNode2<>(currWeight, currId));
                    }

                    // keep track if it exists or not
                    vertexTable.putNode(currAdj.getId(), 0);
                }
            }
        }

        DynamicArray<Integer> fromList = new DynamicArray<>();
        Integer startP = vertexFrom.get(pEndVertex);
        if (startP != null) {

            fromList.add(pEndVertex);
            int curr = startP;
            while (curr != -1) {
                fromList.add(curr);
                curr = vertexFrom.get(curr);
            }
        }

        for (int i = 1; i < fromList.size(); i++) {
            totalCost +=distTo.get(fromList.get(i));
        }

        return fromList;

    }