package com.conveyal.r5.profile;

import com.conveyal.r5.streets.LinkedPointSet;
import gnu.trove.map.TIntIntMap;
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

import java.util.Arrays;

/**
 * This class propagates from times at transit stops to times at destinations (targets). It is called with a function
 * that will be called with the target index (which is the row-major 1D index of the destination that is being
 * propagated to) and the array of whether the target was reached within the travel time cutoff in each Monte Carlo
 * draw. This is used in GridComputer to perform bootstrapping of accessibility given median travel time. This function
 * is only called for targets that were ever reached. It may seem needlessly generic to use a lambda function, but it
 * allows us to confine the bootstrapping code to GridComputer.
 *
 * We propagate to a single target (grid cell) at a time because we only intend to store a few percentiles of travel time
 * at each target. Propagating the other direction, from stops out to targets, requires storing every travel time for
 * every MC draw/departure time, at every target. This would be impractically huge. To handle one target at a time we
 * need to invert the table of distances from stops to nearby targets: we instead use a table of distances from targets
 * to nearby stops.
 */
public class PerTargetPropagater {
    private static final Logger LOG = LoggerFactory.getLogger(PerTargetPropagater.class);

    /** Times at transit stops for each iteration */
    public final int[][] travelTimesToStopsEachIteration;

    /** Times at targets using the street network */
    public final int[] nonTransitTravelTimesToTargets;

    /** The travel time cutoff in this regional analysis */
    public final int cutoffSeconds;

    /** The linked targets */
    public final LinkedPointSet targets;

    /** the profilerequest (used for walk speed etc.) */
    public final ProfileRequest request;

    public PerTargetPropagater (int[][] travelTimesToStopsEachIteration, int[] nonTransitTravelTimesToTargets, LinkedPointSet targets, ProfileRequest request, int cutoffSeconds) {
        this.travelTimesToStopsEachIteration = travelTimesToStopsEachIteration;
        this.nonTransitTravelTimesToTargets = nonTransitTravelTimesToTargets;
        this.targets = targets;
        this.request = request;
        this.cutoffSeconds = cutoffSeconds;
    }

    /**
     * Call with either a reducer or a travelTimeReducer, but never both. One of the two must be null.
     * A reducer is only told whether the target was reached within the travel time threshold, which allows some
     * optimizations in certain cases. A travelTimeReducer receives a full list of travel times to the given
     * destination.
     */
    public void propagate (TravelTimeReducer travelTimeReducer) {
        targets.makePointToStopDistanceTablesIfNeeded();

        long startTimeMillis = System.currentTimeMillis();
        // avoid float math in loop below
        // float math was previously observed to slow down this loop, however it's debatable whether that was due to
        // casts, the operations themselves, or the fact that the operations were being completed with doubles rather
        // than floats.
        int speedMillimetersPerSecond = (int) (request.walkSpeed * 1000);

        int[] perIterationTravelTimes = new int[travelTimesToStopsEachIteration.length];

        // Invert the travel times to stops array, to provide better memory locality in the tight loop below. Confirmed
        // that this provides a significant speedup, which makes sense; Java doesn't have true multidimensional arrays
        // but rather represents int[][] as Object[int[]], which means that each of the arrays "on the inside" is stored
        // separately in memory and may not be contiguous, also meaning the CPU can't efficiently predict and prefetch
        // what we need next. When we invert the array, we then have all travel times to a particular stop for all iterations
        // in a single array. The CPU will only page the data that is relevant for the current target, i.e. the travel
        // times to nearby stops. Since we are also looping over the targets in a geographic manner (in row-major order),
        // it is likely the stops relevant to a particular target will already be in memory from the previous target.
        // This should not increase memory consumption very much as we're only storing the travel times to stops. The
        // Netherlands has about 70,000 stops, if you do 1,000 iterations to 70,000 stops, the array being duplicated is
        // only 70,000 * 1000 * 4 bytes per int ~= 267 megabytes. I don't think it will be worthwhile to change the
        // algorithm to output already-transposed data as that will create other memory locality problems (since the
        // pathfinding algorithm solves one iteration for all stops simultaneously).
        int[][] invertedTravelTimesToStops = new int[travelTimesToStopsEachIteration[0].length][travelTimesToStopsEachIteration.length];

        for (int iteration = 0; iteration < travelTimesToStopsEachIteration.length; iteration++) {
            for (int stop = 0; stop < travelTimesToStopsEachIteration[0].length; stop++) {
                invertedTravelTimesToStops[stop][iteration] = travelTimesToStopsEachIteration[iteration][stop];
            }
        }

        for (int targetIdx = 0; targetIdx < targets.size(); targetIdx++) {
            // clear previous results, fill with whether target is reached within the cutoff without transit (which does
            // not vary with monte carlo draw)
            Arrays.fill(perIterationTravelTimes, nonTransitTravelTimesToTargets[targetIdx]);

            TIntIntMap pointToStopDistanceTable = targets.pointToStopDistanceTables.get(targetIdx);

            // all variables used in lambdas must be "effectively final"; arrays are effectively final even if their
            // values change
            boolean[] targetEverReached = new boolean[] { nonTransitTravelTimesToTargets[targetIdx] <= cutoffSeconds };

            // don't try to propagate transit if there are no nearby transit stops,
            // but still call the reducer below with the non-transit times, because you can walk even where there is no
            // transit
            if (pointToStopDistanceTable != null) {
                pointToStopDistanceTable.forEachEntry((stop, distanceMillimeters) -> {
                    for (int iteration = 0; iteration < perIterationTravelTimes.length; iteration++) {
                        int timeAtStop = invertedTravelTimesToStops[stop][iteration];

                        if (timeAtStop > cutoffSeconds || timeAtStop > perIterationTravelTimes[iteration]) continue; // avoid overflow

                        int timeAtTargetThisStop = timeAtStop + distanceMillimeters / speedMillimetersPerSecond;

                        if (timeAtTargetThisStop < cutoffSeconds) {
                            if (timeAtTargetThisStop < perIterationTravelTimes[iteration]) {
                                perIterationTravelTimes[iteration] = timeAtTargetThisStop;
                                targetEverReached[0] = true;
                            }
                        }
                    }
                    return true;
                });
            }

            travelTimeReducer.accept(targetIdx, perIterationTravelTimes);
        }

        long totalTimeMillis = System.currentTimeMillis() - startTimeMillis;
        LOG.info("Propagating {} iterations from {} stops to {} targets took {}s",
                travelTimesToStopsEachIteration.length,
                travelTimesToStopsEachIteration[0].length,
                targets.size(),
                totalTimeMillis / 1000d
                );

        travelTimeReducer.finish();
    }

    public interface TravelTimeReducer {
        /** Receive the travel times for all iterations of the algorithm to a particular target specified by targetIndex */
        void accept (int targetIndex, int[] travelTimesForTargets);

        /** Called when propagation is done, used to signal the reducer that it can upload its results to s3 etc; optional */
        default void finish () {};
    }
}

@@ -5853,275 +5853,8 @@
 );%0A%0A
-            // all variables used in lambdas must be %22effectively final%22; arrays are effectively final even if their%0A            // values change%0A            boolean%5B%5D targetEverReached = new boolean%5B%5D %7B nonTransitTravelTimesToTargets%5BtargetIdx%5D %3C= cutoffSeconds %7D;%0A%0A
     
@@ -5933,16 +5933,16 @@
  stops,%0A
+
         
@@ -6911,69 +6911,8 @@
 op;%0A
-                                targetEverReached%5B0%5D = true;%0A
     
@@ -7709,24 +7709,24 @@
 getIndex */%0A
+
         void
@@ -7777,17 +7777,16 @@
 orTarget
-s
 );%0A%0A    

Simplify propagation.