<commit_before>package com.conveyal.r5.profile;

import com.conveyal.r5.OneOriginResult;
import com.conveyal.r5.analyst.PathScorer;
import com.conveyal.r5.analyst.PointSet;
import com.conveyal.r5.analyst.TravelTimeReducer;
import com.conveyal.r5.analyst.WebMercatorGridPointSet;
import com.conveyal.r5.analyst.cluster.AnalysisWorkerTask;
import com.conveyal.r5.analyst.cluster.PathWriter;
import com.conveyal.r5.analyst.cluster.RegionalTask;
import com.conveyal.r5.streets.EgressCostTable;
import com.conveyal.r5.streets.LinkedPointSet;
import com.conveyal.r5.streets.StreetLayer;
import com.conveyal.r5.streets.StreetRouter;
import gnu.trove.map.TIntIntMap;
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.EnumSet;
import java.util.List;
import java.util.Set;

/**
 * Given minimum travel times from a single origin point to all transit stops, this class finds minimum travel times to
 * a grid of destinations ("targets") by walking or biking or driving from the transit stops to the targets.
 * We make one propagator instance per origin point.
 *
 * We find travel times to a single target (grid cell) at a time because we only intend to retain a few percentiles of
 * travel time at each target, rather than retaining the travel time for every Monte Carlo schedule at every departure
 * minute. Propagating the other direction (from stops out to targets) requires retaining every travel time for every
 * Monte Carlo draw/departure time combination at every target. The resulting data structure would be impractically
 * huge. To handle one target at a time rather than one stop at a time, we need to invert the table of distances from
 * stops to their nearby targets: we instead use a table of distances to targets from their nearby stops.
 *
 * Note: this class is not threadsafe. It must process one target at a time sequentially in a single thread.
 */
public class PerTargetPropagater {

    private static final Logger LOG = LoggerFactory.getLogger(PerTargetPropagater.class);

    public static final int SECONDS_PER_MINUTE = 60;
    public static final int MM_PER_METER = 1000;

    /**
     * We will not record or report travel times for paths this long or longer. To limit calculation time and avoid
     * overflow, places at least this many seconds from the origin are simply considered unreachable.
     */
    public final int maxTravelTimeSeconds;

    /** The targets, not yet linked to the street network. */
    private PointSet targets;

    /** All modes for which we want to perform egress propagation through the street network. */
    public final EnumSet<StreetMode> modes;

    /** One linkage for each street mode for which we want to extend travel times out from transit to destinations. */
    private final List<LinkedPointSet> linkedTargets;

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

    /** how travel times are summarized and written or streamed back to a client TODO inline that whole class here. */
    public TravelTimeReducer travelTimeReducer;

    /** If non-null, methods will be called on this object to select and write out paths for a static site.*/
    public PathWriter pathWriter;

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

    /** Times at transit stops for each iteration. Plus a transposed version of that same matrix as an optimization. */
    private int[][] travelTimesToStopsForIteration, travelTimesToStop;

    /**
     * The number of "iterations" (departure minutes & Monte Carlo schedules) and the number of stops and destination
     * points.
     */
    private final int nIterations, nStops, nTargets;

    /**
     * For each iteration of the raptor algorithm, an array of the path that yielded the best travel time to each
     * transit stop. May be null, only needs to be set if we're recording paths.
     */
    public List<Path[]> pathsToStopsForIteration = null;

    /** Whether the worker should calculate paths then write them to storage for use in Taui sites. */
    private final boolean writePathsForTaui;

    /**
     * Whether the worker should calculate paths to all destinations, then return them to the broker for assembly or
     * forwarding to the UI
     * */
    private final boolean calculateAllPaths;

    /**
     * Single destination for which paths should be returned (when toLat/toLon are specified in a single-point request)
     */
    private int destinationIndexForPaths = -1;

    /**
     * Whether to propagate only to a single target that corresponds to the origin (e.g. in a travel time savings
     * calculation).
     */
    private final boolean oneToOne;

    // STATE FIELDS WHICH ARE RESET WHEN PROCESSING EACH DESTINATION.
    // These track the characteristics of the best paths known to the target currently being processed.

    /**
     * Retains the best known total travel time to the current destination for each iteration of the RAPTOR algorithm.
     * TODO instead of a long-lived field this could be returned from the propagate function.
     */
    private int[] perIterationTravelTimes;

    /**
     * The transit path that yielded the best known travel time to the current destination for each iteration of the
     * raptor algorithm. Parallel to perIterationTravelTimes. Reset for each destination that is processed.
     */
    private Path[] perIterationPaths;

    private final PropagationTimer timer = new PropagationTimer();

    /**
     * Constructor.
     */
    public PerTargetPropagater(
            PointSet targets,
            StreetLayer streetLayer,
            EnumSet<StreetMode> modes,
            AnalysisWorkerTask task,
            int[][] travelTimesToStopsForIteration,
            int[] nonTransitTravelTimesToTargets
    ) {
        this.targets = targets;
        this.modes = modes;
        this.request = task;
        this.travelTimesToStopsForIteration = travelTimesToStopsForIteration;
        this.nonTransitTravelTimesToTargets = nonTransitTravelTimesToTargets;

        // If we're making a static site we'll break travel times down into components and make paths.
        // This expects the pathsToStopsForIteration and pathWriter fields to be set separately by the caller.
        writePathsForTaui = task.makeTauiSite;
        calculateAllPaths = task instanceof RegionalTask && task.includePathResults;

        maxTravelTimeSeconds = task.maxTripDurationMinutes * SECONDS_PER_MINUTE;
        oneToOne = request instanceof RegionalTask && ((RegionalTask) request).oneToOne;
        if (task.includePathResults && request.toLat != 0.0f && request.toLon != 0.0f){
            destinationIndexForPaths = ((WebMercatorGridPointSet) targets).indexFromWgsCoordinates(request.toLon, request.toLat,
                    ((AnalysisWorkerTask)request).zoom);
        }
        nIterations = travelTimesToStopsForIteration.length;
        nStops = travelTimesToStopsForIteration[0].length;
        nTargets = targets.featureCount();
        linkedTargets = new ArrayList<>(modes.size());

        timer.fullPropagation.start();
        timer.transposition.start();
        invertTravelTimes();
        if (nonTransitTravelTimesToTargets.length != nTargets) {
            throw new IllegalArgumentException("Non-transit travel times must have the same number of entries as there are points.");
        }
        for (StreetMode streetMode : modes) {
            LinkedPointSet linkedTargetsForMode = streetLayer.parentNetwork.linkageCache
                    .getLinkage(targets, streetLayer, streetMode);
            // Transpose the cost table for propagation. Some tables are never used for propagation (like the
            // region-wide baseline). Transposing them only when needed should save a lot of memory.
            linkedTargetsForMode.getEgressCostTable().destructivelyTransposeForPropagationAsNeeded();
            linkedTargets.add(linkedTargetsForMode);
        }
        timer.transposition.stop();
        // Prevent top-level timer from counting any intervening actions until caller calls propagate()
        timer.fullPropagation.stop();
    }

    /**
     * After constructing a propagator and setting any additional options or optional fields,
     * call this method to actually perform the travel time propagation.
     */
    public OneOriginResult propagate () {

        timer.fullPropagation.start();

        // perIterationTravelTimes and perIterationDetails are reused when processing each target.
        perIterationTravelTimes = new int[nIterations];

        // Retain additional information about how the target was reached to report travel time breakdown and paths to targets.
        if (writePathsForTaui || calculateAllPaths || destinationIndexForPaths != -1) {
            perIterationPaths = new Path[nIterations];
        }

        // In most tasks, we want to propagate travel times for each origin out to all the destinations.
        int startTarget = 0;
        int endTarget = nTargets;

        // However, in one-to-one tasks, each origin in a freeform pointset corresponds to a single destination at
        // the same position in the destinations pointset. So our target range is restricted to only one target.
        if (oneToOne) {
            startTarget = ((RegionalTask) request).taskId;
            endTarget = startTarget + 1;
        }

        for (int targetIdx = startTarget; targetIdx < endTarget; targetIdx++) {

            // Initialize the travel times to that achieved without transit (if any).
            // These travel times do not vary with departure time or MC draw, so they are all the same at a given target.
            Arrays.fill(perIterationTravelTimes, nonTransitTravelTimesToTargets[targetIdx]);

            // Clear out the Path array if we're building one. These are transit solution details, so they remain
            // null until we find a good transit solution.
            if (writePathsForTaui || calculateAllPaths || targetIdx == destinationIndexForPaths) {<commit_msg>fix(paths): get destination index from grid pointset only for single-point analyses<commit_after>package com.conveyal.r5.profile;

import com.conveyal.r5.OneOriginResult;
import com.conveyal.r5.analyst.PathScorer;
import com.conveyal.r5.analyst.PointSet;
import com.conveyal.r5.analyst.TravelTimeReducer;
import com.conveyal.r5.analyst.WebMercatorGridPointSet;
import com.conveyal.r5.analyst.cluster.AnalysisWorkerTask;
import com.conveyal.r5.analyst.cluster.PathWriter;
import com.conveyal.r5.analyst.cluster.RegionalTask;
import com.conveyal.r5.analyst.cluster.TravelTimeSurfaceTask;
import com.conveyal.r5.streets.EgressCostTable;
import com.conveyal.r5.streets.LinkedPointSet;
import com.conveyal.r5.streets.StreetLayer;
import com.conveyal.r5.streets.StreetRouter;
import gnu.trove.map.TIntIntMap;
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.EnumSet;
import java.util.List;
import java.util.Set;

/**
 * Given minimum travel times from a single origin point to all transit stops, this class finds minimum travel times to
 * a grid of destinations ("targets") by walking or biking or driving from the transit stops to the targets.
 * We make one propagator instance per origin point.
 *
 * We find travel times to a single target (grid cell) at a time because we only intend to retain a few percentiles of
 * travel time at each target, rather than retaining the travel time for every Monte Carlo schedule at every departure
 * minute. Propagating the other direction (from stops out to targets) requires retaining every travel time for every
 * Monte Carlo draw/departure time combination at every target. The resulting data structure would be impractically
 * huge. To handle one target at a time rather than one stop at a time, we need to invert the table of distances from
 * stops to their nearby targets: we instead use a table of distances to targets from their nearby stops.
 *
 * Note: this class is not threadsafe. It must process one target at a time sequentially in a single thread.
 */
public class PerTargetPropagater {

    private static final Logger LOG = LoggerFactory.getLogger(PerTargetPropagater.class);

    public static final int SECONDS_PER_MINUTE = 60;
    public static final int MM_PER_METER = 1000;

    /**
     * We will not record or report travel times for paths this long or longer. To limit calculation time and avoid
     * overflow, places at least this many seconds from the origin are simply considered unreachable.
     */
    public final int maxTravelTimeSeconds;

    /** The targets, not yet linked to the street network. */
    private PointSet targets;

    /** All modes for which we want to perform egress propagation through the street network. */
    public final EnumSet<StreetMode> modes;

    /** One linkage for each street mode for which we want to extend travel times out from transit to destinations. */
    private final List<LinkedPointSet> linkedTargets;

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

    /** how travel times are summarized and written or streamed back to a client TODO inline that whole class here. */
    public TravelTimeReducer travelTimeReducer;

    /** If non-null, methods will be called on this object to select and write out paths for a static site.*/
    public PathWriter pathWriter;

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

    /** Times at transit stops for each iteration. Plus a transposed version of that same matrix as an optimization. */
    private int[][] travelTimesToStopsForIteration, travelTimesToStop;

    /**
     * The number of "iterations" (departure minutes & Monte Carlo schedules) and the number of stops and destination
     * points.
     */
    private final int nIterations, nStops, nTargets;

    /**
     * For each iteration of the raptor algorithm, an array of the path that yielded the best travel time to each
     * transit stop. May be null, only needs to be set if we're recording paths.
     */
    public List<Path[]> pathsToStopsForIteration = null;

    /** Whether the worker should calculate paths then write them to storage for use in Taui sites. */
    private final boolean writePathsForTaui;

    /** Whether the worker should calculate paths to all destinations, then return them to the broker for assembly */
    private final boolean calculateAllPaths;

    /**
     * Whether the worker should calculate paths to one specific destination, then return them to the broker for
     * forwarding to the UI
     */
    private final boolean calculateOnePath;

    /**
     * Single destination for which paths should be returned (when toLat/toLon are specified in a single-point request)
     */
    private int destinationIndexForPaths;

    /**
     * Whether to propagate only to a single target that corresponds to the origin (e.g. in a travel time savings
     * calculation).
     */
    private final boolean oneToOne;

    // STATE FIELDS WHICH ARE RESET WHEN PROCESSING EACH DESTINATION.
    // These track the characteristics of the best paths known to the target currently being processed.

    /**
     * Retains the best known total travel time to the current destination for each iteration of the RAPTOR algorithm.
     * TODO instead of a long-lived field this could be returned from the propagate function.
     */
    private int[] perIterationTravelTimes;

    /**
     * The transit path that yielded the best known travel time to the current destination for each iteration of the
     * raptor algorithm. Parallel to perIterationTravelTimes. Reset for each destination that is processed.
     */
    private Path[] perIterationPaths;

    private final PropagationTimer timer = new PropagationTimer();

    /**
     * Constructor.
     */
    public PerTargetPropagater(
            PointSet targets,
            StreetLayer streetLayer,
            EnumSet<StreetMode> modes,
            AnalysisWorkerTask task,
            int[][] travelTimesToStopsForIteration,
            int[] nonTransitTravelTimesToTargets
    ) {
        this.targets = targets;
        this.modes = modes;
        this.request = task;
        this.travelTimesToStopsForIteration = travelTimesToStopsForIteration;
        this.nonTransitTravelTimesToTargets = nonTransitTravelTimesToTargets;

        // If we're making a static site we'll break travel times down into components and make paths.
        // This expects the pathsToStopsForIteration and pathWriter fields to be set separately by the caller.
        writePathsForTaui = task.makeTauiSite;
        calculateAllPaths = task instanceof RegionalTask && task.includePathResults;
        calculateOnePath = task instanceof TravelTimeSurfaceTask && task.includePathResults;
        maxTravelTimeSeconds = task.maxTripDurationMinutes * SECONDS_PER_MINUTE;
        oneToOne = request instanceof RegionalTask && ((RegionalTask) request).oneToOne;
        if (calculateOnePath){
            destinationIndexForPaths = ((WebMercatorGridPointSet) targets).indexFromWgsCoordinates(
                    task.toLon,
                    task.toLat,
                    task.zoom
            );
        }
        nIterations = travelTimesToStopsForIteration.length;
        nStops = travelTimesToStopsForIteration[0].length;
        nTargets = targets.featureCount();
        linkedTargets = new ArrayList<>(modes.size());

        timer.fullPropagation.start();
        timer.transposition.start();
        invertTravelTimes();
        if (nonTransitTravelTimesToTargets.length != nTargets) {
            throw new IllegalArgumentException("Non-transit travel times must have the same number of entries as there are points.");
        }
        for (StreetMode streetMode : modes) {
            LinkedPointSet linkedTargetsForMode = streetLayer.parentNetwork.linkageCache
                    .getLinkage(targets, streetLayer, streetMode);
            // Transpose the cost table for propagation. Some tables are never used for propagation (like the
            // region-wide baseline). Transposing them only when needed should save a lot of memory.
            linkedTargetsForMode.getEgressCostTable().destructivelyTransposeForPropagationAsNeeded();
            linkedTargets.add(linkedTargetsForMode);
        }
        timer.transposition.stop();
        // Prevent top-level timer from counting any intervening actions until caller calls propagate()
        timer.fullPropagation.stop();
    }

    /**
     * After constructing a propagator and setting any additional options or optional fields,
     * call this method to actually perform the travel time propagation.
     */
    public OneOriginResult propagate () {

        timer.fullPropagation.start();

        // perIterationTravelTimes and perIterationDetails are reused when processing each target.
        perIterationTravelTimes = new int[nIterations];

        // Retain additional information about how the target was reached to report travel time breakdown and paths to targets.
        if (writePathsForTaui || calculateAllPaths || calculateOnePath) {
            perIterationPaths = new Path[nIterations];
        }

        // In most tasks, we want to propagate travel times for each origin out to all the destinations.
        int startTarget = 0;
        int endTarget = nTargets;

        // However, in one-to-one tasks, each origin in a freeform pointset corresponds to a single destination at
        // the same position in the destinations pointset. So our target range is restricted to only one target.
        if (oneToOne) {
            startTarget = ((RegionalTask) request).taskId;
            endTarget = startTarget + 1;
        }

        for (int targetIdx = startTarget; targetIdx < endTarget; targetIdx++) {

            // Initialize the travel times to that achieved without transit (if any).
            // These travel times do not vary with departure time or MC draw, so they are all the same at a given target.
            Arrays.fill(perIterationTravelTimes, nonTransitTravelTimesToTargets[targetIdx]);

            // Clear out the Path array if we're building one. These are transit solution details, so they remain
            // null until we find a good transit solution.
            if (writePathsForTaui || calculateAllPaths || targetIdx == destinationIndexForPaths) {
{'fraction_non_alphanumeric': 0.06382875448985535, 'fraction_numerical': 0.0026696437239103, 'mean_word_length': 3.136318008432042, 'pattern_counts': {'":': 0, '<': 15, '<?xml version=': 0, '>': 13, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '531275', 'n_tokens_mistral': 5336, 'n_tokens_neox': 5100, 'n_words': 2112}