#include <cstdio>
#include <ctime>
#include <cmath>
#include <vector>
#include <unordered_map>
#include <algorithm>

#include "vtr_assert.h"
#include "vtr_log.h"

#include "vpr_utils.h"
#include "vpr_types.h"
#include "vpr_error.h"

#include "globals.h"
#include "route_export.h"
#include "route_common.h"
#include "route_tree_timing.h"
#include "route_timing.h"
#include "path_delay.h"
#include "net_delay.h"
#include "stats.h"
#include "echo_files.h"
#include "draw.h"
#include "routing_predictor.h"

// all functions in profiling:: namespace, which are only activated if PROFILE is defined
#include "route_profiling.h" 

#include "timing_info.h"
#include "timing_util.h"
#include "route_budgets.h"

#include "router_lookahead_map.h"

#define CONGESTED_SLOPE_VAL -0.04

class WirelengthInfo {
public:

    WirelengthInfo(size_t available = 0u, size_t used = 0u)
    : available_wirelength_(available)
    , used_wirelength_(used) {
    }

    size_t available_wirelength() const {
        return available_wirelength_;
    }

    size_t used_wirelength() const {
        return used_wirelength_;
    }

    float used_wirelength_ratio() const {
        if (available_wirelength() > 0) {
            return float(used_wirelength()) / available_wirelength();
        } else {
            VTR_ASSERT(used_wirelength() == 0);
            return 0.;
        }
    }

private:
    size_t available_wirelength_;
    size_t used_wirelength_;
};

class OveruseInfo {
public:

    OveruseInfo(size_t total = 0u, size_t overused = 0u, size_t total_overuse_val = 0u, size_t worst_overuse_val = 0u)
    : total_nodes_(total)
    , overused_nodes_(overused)
    , total_overuse_(total_overuse_val)
    , worst_overuse_(worst_overuse_val) {
    }

    size_t total_nodes() const {
        return total_nodes_;
    }

    size_t overused_nodes() const {
        return overused_nodes_;
    }

    float overused_node_ratio() const {
        if (total_nodes() > 0) {
            return float(overused_nodes()) / total_nodes();
        } else {
            VTR_ASSERT(overused_nodes() == 0);
            return 0.;
        }
    }

    size_t total_overuse() const {
        return total_overuse_;
    }

    size_t worst_overuse() const {
        return worst_overuse_;
    }

private:
    size_t total_nodes_;
    size_t overused_nodes_;
    size_t total_overuse_;
    size_t worst_overuse_;
};

struct t_timing_driven_node_costs {
    float backward_cost = 0.;
    float total_cost = 0.;
    float R_upstream = 0.;
};

/*
 * File-scope variables
 */

#ifdef ROUTER_DEBUG
//Run-time flag to control when router debug information is printed
bool router_debug = true;

#endif

/******************** Subroutines local to route_timing.c ********************/

static t_rt_node* setup_routing_resources(int itry, ClusterNetId net_id, unsigned num_sinks, float pres_fac, int min_incremental_reroute_fanout,
        CBRR& incremental_rerouting_res, t_rt_node** rt_node_of_sink);

static bool timing_driven_route_sink(int itry, ClusterNetId net_id, unsigned itarget, int target_pin, float target_criticality,
        float pres_fac, float astar_fac, float bend_cost, t_rt_node* rt_root, t_rt_node** rt_node_of_sink, route_budgets &budgeting_inf,
        float max_delay, float min_delay, float target_delay, float short_path_crit, RouterStats& router_stats);

static void add_route_tree_to_heap(t_rt_node * rt_node, int target_node,
        float target_criticality, float astar_fac, route_budgets& budgeting_inf,
        float max_delay, float min_delay,
        float target_delay, float short_path_crit, RouterStats& router_stats);

static void timing_driven_expand_neighbours(t_heap *current,
        t_bb bounding_box, float bend_cost, float criticality_fac,
        int num_sinks, int target_node,
        float astar_fac, int highfanout_rlim, route_budgets &budgeting_inf, float max_delay, float min_delay,
        float target_delay, float short_path_crit);

static void timing_driven_add_to_heap(const float criticality_fac, const float bend_cost, const float astar_fac,
        const route_budgets& budgeting_inf, const float max_delay, const float min_delay, const float target_delay, const float short_path_crit,
        const t_heap* current, const int from_node, const int to_node, const int iconn, const int target_node);

static void timing_driven_expand_node(const float criticality_fac, const float bend_cost, const float astar_fac,
        const route_budgets& budgeting_inf, const float max_delay, const float min_delay, const float target_delay, const float short_path_crit,
        t_heap* current, const int from_node, const int to_node, const int iconn, const int target_node);

static void timing_driven_expand_node_non_configurable_recurr(const float criticality_fac, const float bend_cost, const float astar_fac,
        const route_budgets& budgeting_inf, const float max_delay, const float min_delay, const float target_delay, const float short_path_crit,
        t_heap* current, const int from_node, const int to_node, const int iconn, const int target_node,
        std::set<int>& visited);

t_timing_driven_node_costs evaluate_timing_driven_node_costs(const t_timing_driven_node_costs old_costs,
    const float criticality_fac, const float bend_cost, const float astar_fac,
    const route_budgets& budgeting_inf, const float max_delay, const float min_delay, const float target_delay, const float short_path_crit,
    const int from_node, const int to_node, const int iconn, const int target_node);

static float get_timing_driven_expected_cost(int inode, int target_node,
        float criticality_fac, float R_upstream);

static int get_expected_segs_to_target(int inode, int target_node,
        int *num_segs_ortho_dir_ptr);

static bool timing_driven_check_net_delays(vtr::vector_map<ClusterNetId, float *> &net_delay);

static int mark_node_expansion_by_bin(int source_node, int target_node,
        t_rt_node * rt_node, t_bb bounding_box, int num_sinks);

void reduce_budgets_if_congested(route_budgets &budgeting_inf,
        CBRR& connections_inf, float slope, int itry);

static bool should_route_net(ClusterNetId net_id, const CBRR& connections_inf, bool if_force_reroute);
static bool early_exit_heuristic(const WirelengthInfo& wirelength_info);

struct more_sinks_than {
    inline bool operator()(const ClusterNetId net_index1, const ClusterNetId net_index2) {
        auto& cluster_ctx = g_vpr_ctx.clustering();
        return cluster_ctx.clb_nlist.net_sinks(net_index1).size() > cluster_ctx.clb_nlist.net_sinks(net_index2).size();
    }
};

static WirelengthInfo calculate_wirelength_info();
static OveruseInfo calculate_overuse_info();

static void print_route_status_header();
static void print_route_status(int itry, double elapsed_sec, const RouterStats& router_stats,
        const OveruseInfo& overuse_info, const WirelengthInfo& wirelength_info,
        std::shared_ptr<const SetupHoldTimingInfo> timing_info,
        float est_success_iteration);
static void pretty_print_uint(const char* prefix, size_t value, int num_digits, int scientific_precision);
static int round_up(float x);

/************************ Subroutine definitions *****************************/
bool try_timing_driven_route(t_router_opts router_opts,
        vtr::vector_map<ClusterNetId, float *> &net_delay,
        const ClusteredPinAtomPinsLookup& netlist_pin_lookup,
        std::shared_ptr<SetupHoldTimingInfo> timing_info,
#ifdef ENABLE_CLASSIC_VPR_STA
        t_slack * slacks,
        const t_timing_inf &timing_inf,
#endif
        ScreenUpdatePriority first_iteration_priority) {

    /* Timing-driven routing algorithm.  The timing graph (includes slack)   *
     * must have already been allocated, and net_delay must have been allocated. *
     * Returns true if the routing succeeds, false otherwise.                    */

    //Initialize and properly size the lookups for profiling
    profiling::profiling_initialization(get_max_pins_per_net());

    auto& cluster_ctx = g_vpr_ctx.clustering();
    auto& route_ctx = g_vpr_ctx.mutable_routing();

    //sort so net with most sinks is first.
    auto sorted_nets = vtr::vector_map<ClusterNetId,ClusterNetId>();
    for (auto net_id : cluster_ctx.clb_nlist.nets()) {
        sorted_nets.push_back(net_id);
    }
    std::sort(sorted_nets.begin(), sorted_nets.end(), more_sinks_than());

    /*
     * Configure the routing predictor
     */
    RoutingPredictor routing_predictor;
    float abort_iteration_threshold = std::numeric_limits<float>::infinity(); //Default no early abort
    if (router_opts.routing_failure_predictor == SAFE) {
        abort_iteration_threshold = ROUTING_PREDICTOR_ITERATION_ABORT_FACTOR_SAFE * router_opts.max_router_iterations;
    } else if (router_opts.routing_failure_predictor == AGGRESSIVE) {
        abort_iteration_threshold = ROUTING_PREDICTOR_ITERATION_ABORT_FACTOR_AGGRESSIVE * router_opts.max_router_iterations;
    } else {
        VTR_ASSERT_MSG(router_opts.routing_failure_predictor == OFF, "Unrecognized routing failure predictor setting");
    }

    /* Set delay of global signals to zero. Non-global net delays are set by
       update_net_delays_from_route_tree() inside timing_driven_route_net(), 
       which is only called for non-global nets. */
	for (auto net_id : cluster_ctx.clb_nlist.nets()) {
        if (cluster_ctx.clb_nlist.net_is_global(net_id)) {
            for (unsigned int ipin = 1; ipin < cluster_ctx.clb_nlist.net_pins(net_id).size(); ++ipin) {
                net_delay[net_id][ipin] = 0.;
            }
        }
    }

    CBRR connections_inf{};
    VTR_ASSERT_SAFE(connections_inf.sanity_check_lookup());

    route_budgets budgeting_inf;

    /*
     * Routing parameters
     */
    float pres_fac = router_opts.first_iter_pres_fac; /* Typically 0 -> ignore cong. */

    /*
     * Routing status and metrics
     */
    bool routing_is_successful = false;
    WirelengthInfo wirelength_info;
    OveruseInfo overuse_info;
    tatum::TimingPathInfo critical_path;
    int itry; //Routing iteration number

    /*
     * On the first routing iteration ignore congestion to get reasonable net 
     * delay estimates. Set criticalities to 1 when timing analysis is on to 
     * optimize timing, and to 0 when timing analysis is off to optimize routability. 
     * 
     * Subsequent iterations use the net delays from the previous iteration. 
     */
    print_route_status_header();
    timing_driven_route_structs route_structs;
    for (itry = 1; itry <= router_opts.max_router_iterations; ++itry) {
        clock_t begin = clock();

        /* Reset "is_routed" and "is_fixed" flags to indicate nets not pre-routed (yet) */
		for (auto net_id : cluster_ctx.clb_nlist.nets()) {
			route_ctx.net_status[net_id].is_routed = false;
			route_ctx.net_status[net_id].is_fixed = false;
		}

        std::shared_ptr<SetupTimingInfo> route_timing_info;
        if (timing_info) {
            if (itry == 1) {
                //First routing iteration, make all nets critical for a min-delay routing
                route_timing_info = make_constant_timing_info(1.);
            } else {
                //Other iterations user the true criticality
                route_timing_info = timing_info;
            }
        } else {
            //Not timing driven, force criticality to zero for a routability-driven routing
            route_timing_info = make_constant_timing_info(0.);
        }

        RouterStats router_stats;

        /*
         * Route each net
         */
        for (auto net_id : cluster_ctx.clb_nlist.nets()) {
            bool is_routable = try_timing_driven_route_net(
                    sorted_nets[net_id],
                    itry,
                    pres_fac,
                    router_opts,
                    connections_inf,
                    router_stats,
                    route_structs.pin_criticality,
                    route_structs.rt_node_of_sink,
                    net_delay,
                    netlist_pin_lookup,
                    route_timing_info, budgeting_inf);

            if (!is_routable) {
                return (false); //Impossible to route
            }
        }

        // Make sure any CLB OPINs used up by subblocks being hooked directly to them are reserved for that purpose
        bool rip_up_local_opins = (itry == 1 ? false : true);
        reserve_locally_used_opins(pres_fac, router_opts.acc_fac, rip_up_local_opins);

        float time = static_cast<float> (clock() - begin) / CLOCKS_PER_SEC;

        /*
         * Calculate metrics for the current routing
         */
        bool routing_is_feasible = feasible_routing();
        float est_success_iteration = routing_predictor.estimate_success_iteration();

        overuse_info = calculate_overuse_info();
        wirelength_info = calculate_wirelength_info();
        routing_predictor.add_iteration_overuse(itry, overuse_info.overused_nodes());

        if (timing_info) {
            //Update timing based on the new routing
            //Note that the net delays have already been updated by timing_driven_route_net
#ifdef ENABLE_CLASSIC_VPR_STA
            load_timing_graph_net_delays(net_delay);

            do_timing_analysis(slacks, timing_inf, false, true);
#endif

            timing_info->update();
            timing_info->set_warn_unconstrained(false); //Don't warn again about unconstrained nodes again during routing

            critical_path = timing_info->least_slack_critical_path();

#ifdef ENABLE_CLASSIC_VPR_STA
            float cpd_diff_ns = std::abs(get_critical_path_delay() - 1e9 * critical_path.delay());
            if (cpd_diff_ns > 0.01) {
                print_classic_cpds();
                print_tatum_cpds(timing_info->critical_paths());

                vpr_throw(VPR_ERROR_TIMING, __FILE__, __LINE__, "Classic VPR and Tatum critical paths do not match (%g and %g respectively)", get_critical_path_delay(), 1e9 * critical_path.delay());
            }
#endif
            VTR_ASSERT_SAFE(timing_driven_check_net_delays(net_delay));
        }

        //Output progress
        print_route_status(itry, time, router_stats, overuse_info, wirelength_info, timing_info, est_success_iteration);

        //Update graphics
        if (itry == 1) {
            update_screen(first_iteration_priority, "Routing...", ROUTING, timing_info);
        } else {
            update_screen(ScreenUpdatePriority::MINOR, "Routing...", ROUTING, timing_info);
        }

        /*
         * Are we finished?
         */
        routing_is_successful = routing_is_feasible; //TODO: keep going after legal routing to further optimize timing
        if (routing_is_successful) {
            break; //Finished
        }

        /*
         * Abort checks: Should we give-up because this routing problem is unlikely to converge to a legal routing?
         */
        if (itry == 1 && early_exit_heuristic(wirelength_info)) {
            //Abort
            break;
        }

        //Estimate at what iteration we will converge to a legal routing
        if (overuse_info.overused_nodes() > ROUTING_PREDICTOR_MIN_ABSOLUTE_OVERUSE_THRESHOLD) {
            //Only abort if we have a significant number of overused resources

            if (!std::isnan(est_success_iteration) && est_success_iteration > abort_iteration_threshold) {
                vtr::printf_info("Routing aborted, the predicted iteration for a successful route (%.1f) is too high.\n", est_success_iteration);
                break; //Abort
            }
        }

        /*
         * Prepare for the next iteration
         */

        //Update pres_fac and resource costs
        if (itry == 1) {
            pres_fac = router_opts.initial_pres_fac;
            pathfinder_update_cost(pres_fac, 0.); /* Acc_fac=0 for first iter. */
        } else {
            pres_fac *= router_opts.pres_fac_mult;

            /* Avoid overflow for high iteration counts, even if acc_cost is big */
            pres_fac = min(pres_fac, static_cast<float> (HUGE_POSITIVE_FLOAT / 1e5));

            pathfinder_update_cost(pres_fac, router_opts.acc_fac);
        }

        if (timing_info) {
            /*
             * Determine if any connection need to be forcibly re-routed due to timing
             */
            if (itry == 1) {
                // first iteration sets up the lower bound connection delays since only timing is optimized for
                connections_inf.set_stable_critical_path_delay(critical_path.delay());
                connections_inf.set_lower_bound_connection_delays(net_delay);

                //load budgets using information from uncongested delay information
                budgeting_inf.load_route_budgets(net_delay, timing_info, netlist_pin_lookup, router_opts);
                /*for debugging purposes*/
                //                if (budgeting_inf.if_set()) {
                //                    budgeting_inf.print_route_budget();
                //                }

            } else {
                bool stable_routing_configuration = true;
                // only need to forcibly reroute if critical path grew significantly
                if (connections_inf.critical_path_delay_grew_significantly(critical_path.delay()))
                    stable_routing_configuration = connections_inf.forcibly_reroute_connections(router_opts.max_criticality,
                        timing_info,
                        netlist_pin_lookup,
                        net_delay);

                // not stable if any connection needs to be forcibly rerouted
                if (stable_routing_configuration)
                    connections_inf.set_stable_critical_path_delay(critical_path.delay());

                /*Check if rate of convergence is high enough, if not lower the budgets of certain nets*/
                //reduce_budgets_if_congested(budgeting_inf, connections_inf, routing_predictor.get_slope(), itry);
            }
        } else {
            /* If timing analysis is not enabled, make sure that the criticalities and the
               net_delays stay as 0 so that wirelength can be optimized. */

            for (auto net_id : cluster_ctx.clb_nlist.nets()) {
                for (unsigned int ipin = 1; ipin < cluster_ctx.clb_nlist.net_pins(net_id).size(); ++ipin) {
#ifdef ENABLE_CLASSIC_VPR_STA
                    slacks->timing_criticality[(size_t)net_id][ipin] = 0.;
#endif
                    net_delay[net_id][ipin] = 0.;
                }
            }
        }


        if (router_opts.congestion_analysis) profiling::congestion_analysis();
        if (router_opts.fanout_analysis) profiling::time_on_fanout_analysis();
        // profiling::time_on_criticality_analysis();
    }

    if (routing_is_successful) {
        if (timing_info) {
            timing_driven_check_net_delays(net_delay);
            vtr::printf_info("Completed net delay value cross check successfully.\n");
            vtr::printf_info("Critical path: %g ns\n", 1e9 * critical_path.delay());
        }

        vtr::printf_info("Successfully routed after %d routing iterations.\n", itry);
    } else {
        vtr::printf_info("Routing failed.\n");
#ifdef ROUTER_DEBUG
        print_invalid_routing_info();
#endif
    }

    return routing_is_successful;
}

bool try_timing_driven_route_net(ClusterNetId net_id, int itry, float pres_fac,
        t_router_opts router_opts,
        CBRR& connections_inf,
        RouterStats& router_stats,
        float* pin_criticality,
        t_rt_node** rt_node_of_sink, vtr::vector_map<ClusterNetId, float *> &net_delay,
        const ClusteredPinAtomPinsLookup& netlist_pin_lookup,
        std::shared_ptr<SetupTimingInfo> timing_info, route_budgets &budgeting_inf) {

    auto& cluster_ctx = g_vpr_ctx.clustering();
    auto& route_ctx = g_vpr_ctx.mutable_routing();

    bool is_routed = false;

    connections_inf.prepare_routing_for_net(net_id);

    if (route_ctx.net_status[net_id].is_fixed) { /* Skip pre-routed nets. */
        is_routed = true;
    } else if (cluster_ctx.clb_nlist.net_is_global(net_id)) { /* Skip global nets. */
        is_routed = true;
    } else if (should_route_net(net_id, connections_inf, true) == false) {
        is_routed = true;
    } else {
        // track time spent vs fanout
        profiling::net_fanout_start();

        is_routed = timing_driven_route_net(net_id, itry, pres_fac,
                router_opts.max_criticality, router_opts.criticality_exp,
                router_opts.astar_fac, router_opts.bend_cost,
                connections_inf,
                router_stats,
                pin_criticality, router_opts.min_incremental_reroute_fanout,
                rt_node_of_sink,
                net_delay[net_id],
                netlist_pin_lookup,
                timing_info, budgeting_inf);

        profiling::net_fanout_end(cluster_ctx.clb_nlist.net_sinks(net_id).size());

        /* Impossible to route? (disconnected rr_graph) */
        if (is_routed) {
			route_ctx.net_status[net_id].is_routed = true;
        } else {
            vtr::printf_info("Routing failed.\n");
        }
    }
    return (is_routed);
}

/*
 * NOTE:
 * Suggest using a timing_driven_route_structs struct. Memory is managed for you
 */
void alloc_timing_driven_route_structs(float **pin_criticality_ptr,
        int **sink_order_ptr, t_rt_node *** rt_node_of_sink_ptr) {

    /* Allocates all the structures needed only by the timing-driven router.   */

    int max_pins_per_net = get_max_pins_per_net();
    int max_sinks = std::max(max_pins_per_net - 1, 0);

    float *pin_criticality = (float *) vtr::malloc(max_sinks * sizeof (float));
    *pin_criticality_ptr = pin_criticality - 1; /* First sink is pin #1. */

    int *sink_order = (int *) vtr::malloc(max_sinks * sizeof (int));
    *sink_order_ptr = sink_order - 1;

    t_rt_node **rt_node_of_sink = (t_rt_node **) vtr::malloc(max_sinks * sizeof (t_rt_node *));
    *rt_node_of_sink_ptr = rt_node_of_sink - 1;

    alloc_route_tree_timing_structs();
}

/*
 * NOTE:
 * Suggest using a timing_driven_route_structs struct. Memory is managed for you
 */
void free_timing_driven_route_structs(float *pin_criticality, int *sink_order,
        t_rt_node ** rt_node_of_sink) {

    /* Frees all the stuctures needed only by the timing-driven router.        */

    // coverity[offset_free : Intentional]
    free(pin_criticality + 1); /* Starts at index 1. */
    // coverity[offset_free : Intentional]
    free(sink_order + 1);
    // coverity[offset_free : Intentional]
    free(rt_node_of_sink + 1);
    free_route_tree_timing_structs();
}

timing_driven_route_structs::timing_driven_route_structs() {
    alloc_timing_driven_route_structs(
            &pin_criticality,
            &sink_order,
            &rt_node_of_sink
            );
}

timing_driven_route_structs::~timing_driven_route_structs() {
    free_timing_driven_route_structs(
            pin_criticality,
            sink_order,
            rt_node_of_sink
            );
}

void reduce_budgets_if_congested(route_budgets &budgeting_inf,
        CBRR& connections_inf, float slope, int itry) {
    auto& cluster_ctx = g_vpr_ctx.mutable_clustering();
    if (budgeting_inf.if_set()) {
        for (auto net_id : cluster_ctx.clb_nlist.nets()) {
            if (should_route_net(net_id, connections_inf, false)) {
                budgeting_inf.update_congestion_times(net_id);
            } else {
                budgeting_inf.not_congested_this_iteration(net_id);
            }
        }

        /*Problematic if the overuse nodes are positive or declining at a slow rate
        Must be more than 9 iterations to have a valid slope*/
        if (slope > CONGESTED_SLOPE_VAL && itry >= 9) {
            budgeting_inf.lower_budgets(1e-9);
        }
    }
}

int get_max_pins_per_net() {
	int max_pins_per_net = 0;

    auto& cluster_ctx = g_vpr_ctx.clustering();

    for (auto net_id : cluster_ctx.clb_nlist.nets()) {
        if (!cluster_ctx.clb_nlist.net_is_global(net_id))
            max_pins_per_net = max(max_pins_per_net, (int)cluster_ctx.clb_nlist.net_pins(net_id).size());
    }

    return (max_pins_per_net);
}

struct Criticality_comp {
    const float* criticality;

    Criticality_comp(const float* calculated_criticalities) : criticality{calculated_criticalities}
    {
    }

    bool operator()(int a, int b) const {
        return criticality[a] > criticality[b];
    }
};

bool timing_driven_route_net(ClusterNetId net_id, int itry, float pres_fac, float max_criticality,
        float criticality_exp, float astar_fac, float bend_cost,
        CBRR& connections_inf,
        RouterStats& router_stats,
        float *pin_criticality, int min_incremental_reroute_fanout,
        t_rt_node ** rt_node_of_sink, float *net_delay,
        const ClusteredPinAtomPinsLookup& netlist_pin_lookup,
        std::shared_ptr<const SetupTimingInfo> timing_info, route_budgets &budgeting_inf) {

    /* Returns true as long as found some way to hook up this net, even if that *
     * way resulted in overuse of resources (congestion).  If there is no way   *
     * to route this net, even ignoring congestion, it returns false.  In this  *
     * case the rr_graph is disconnected and you can give up.                   */
    auto& cluster_ctx = g_vpr_ctx.clustering();
    auto& device_ctx = g_vpr_ctx.device();
    auto& route_ctx = g_vpr_ctx.routing();

    unsigned int num_sinks = cluster_ctx.clb_nlist.net_sinks(net_id).size();

#ifdef ROUTER_DEBUG
    vtr::printf("Routing Net %zu (%zu sinks)\n", size_t(net_id), num_sinks);
#endif

    t_rt_node* rt_root = setup_routing_resources(itry, net_id, num_sinks, pres_fac, min_incremental_reroute_fanout, connections_inf, rt_node_of_sink);
    // after this point the route tree is correct
    // remaining_targets from this point on are the **pin indices** that have yet to be routed 
    auto& remaining_targets = connections_inf.get_remaining_targets();

    // calculate criticality of remaining target pins
    for (int ipin : remaining_targets) {
        if (timing_info) {
            auto clb_pin = cluster_ctx.clb_nlist.net_pin(net_id, ipin);
            pin_criticality[ipin] = calculate_clb_net_pin_criticality(*timing_info, netlist_pin_lookup, clb_pin);

            /* Pin criticality is between 0 and 1. 
             * Shift it downwards by 1 - max_criticality (max_criticality is 0.99 by default, 
             * so shift down by 0.01) and cut off at 0.  This means that all pins with small 
             * criticalities (<0.01) get criticality 0 and are ignored entirely, and everything 
             * else becomes a bit less critical. This effect becomes more pronounced if 
             * max_criticality is set lower. */
            // VTR_ASSERT(pin_criticality[ipin] > -0.01 && pin_criticality[ipin] < 1.01);
            pin_criticality[ipin] = max(pin_criticality[ipin] - (1.0 - max_criticality), 0.0);

            /* Take pin criticality to some power (1 by default). */
            pin_criticality[ipin] = pow(pin_criticality[ipin], criticality_exp);

            /* Cut off pin criticality at max_criticality. */
            pin_criticality[ipin] = min(pin_criticality[ipin], max_criticality);
        } else {
            //No timing info, implies we want a min delay routing, so use criticality of 1.
            pin_criticality[ipin] = 1.;
        }
    }

    // compare the criticality of different sink nodes
    sort(begin(remaining_targets), end(remaining_targets), Criticality_comp{pin_criticality});

    /* Update base costs according to fanout and criticality rules */
    update_rr_base_costs(num_sinks);

    // explore in order of decreasing criticality (no longer need sink_order array)
    for (unsigned itarget = 0; itarget < remaining_targets.size(); ++itarget) {
        int target_pin = remaining_targets[itarget];
        float target_criticality = pin_criticality[target_pin];

        float max_delay, min_delay, target_delay, short_path_crit;

        if (budgeting_inf.if_set()) {
            max_delay = budgeting_inf.get_max_delay_budget(net_id, target_pin);
            target_delay = budgeting_inf.get_delay_target(net_id, target_pin);
            min_delay = budgeting_inf.get_min_delay_budget(net_id, target_pin);
            short_path_crit = budgeting_inf.get_crit_short_path(net_id, target_pin);
        } else {
            /*No budgets so do not add/subtract any value to the cost function*/
            max_delay = 0;
            target_delay = 0;
            min_delay = 0;
            short_path_crit = 0;
        }

        // build a branch in the route tree to the target
        if (!timing_driven_route_sink(itry, net_id, itarget, target_pin, target_criticality,
                pres_fac, astar_fac, bend_cost, rt_root, rt_node_of_sink, budgeting_inf,
                max_delay, min_delay, target_delay, short_path_crit, router_stats))
            return false;

        // need to guarentee ALL nodes' path costs are HUGE_POSITIVE_FLOAT at the start of routing to a sink
        // do this by resetting all the path_costs that have been touched while routing to the current sink
        reset_path_costs();

        ++router_stats.connections_routed;
    } // finished all sinks

    ++router_stats.nets_routed;

    /* For later timing analysis. */

    // may have to update timing delay of the previously legally reached sinks since downstream capacitance could be changed
    update_net_delays_from_route_tree(net_delay, rt_node_of_sink, net_id);

    if (!cluster_ctx.clb_nlist.net_is_global(net_id)) {
        for (unsigned ipin = 1; ipin < cluster_ctx.clb_nlist.net_pins(net_id).size(); ++ipin) {
            if (net_delay[ipin] == 0) { // should be SOURCE->OPIN->IPIN->SINK
                VTR_ASSERT(device_ctx.rr_nodes[rt_node_of_sink[ipin]->parent_node->parent_node->inode].type() == OPIN);
            }
        }
    }

    VTR_ASSERT_MSG(route_ctx.rr_node_route_inf[rt_root->inode].occ() <= device_ctx.rr_nodes[rt_root->inode].capacity(), "SOURCE should never be congested");

    // route tree is not kept persistent since building it from the traceback the next iteration takes almost 0 time
#ifdef ROUTER_DEBUG
    vtr::printf("Routed Net %zu (%zu sinks)\n", size_t(net_id), num_sinks);
#endif
    free_route_tree(rt_root);
    return (true);
}

static bool timing_driven_route_sink(int itry, ClusterNetId net_id, unsigned itarget, int target_pin, float target_criticality,
        float pres_fac, float astar_fac, float bend_cost, t_rt_node* rt_root, t_rt_node** rt_node_of_sink, route_budgets &budgeting_inf,
        float max_delay, float min_delay, float target_delay, float short_path_crit, RouterStats& router_stats) {

    /* Build a path from the existing route tree rooted at rt_root to the target_node
     * add this branch to the existing route tree and update pathfinder costs and rr_node_route_inf to reflect this */
    auto& route_ctx = g_vpr_ctx.mutable_routing();
    auto& device_ctx = g_vpr_ctx.device();
    auto& cluster_ctx = g_vpr_ctx.clustering();

    profiling::sink_criticality_start();

    int source_node = route_ctx.net_rr_terminals[net_id][0];
    int sink_node = route_ctx.net_rr_terminals[net_id][target_pin];

    t_bb bounding_box = route_ctx.route_bb[net_id];

#ifdef ROUTER_DEBUG
    vtr::printf("Net %zu Target %d\n", size_t(net_id), itarget);
#endif

    if (itarget > 0 && itry > 5) {
        /* Enough iterations given to determine opin, to speed up legal solution, do not let net use two opins */
        VTR_ASSERT(device_ctx.rr_nodes[rt_root->inode].type() == SOURCE);
        rt_root->re_expand = false;
    }

    VTR_ASSERT_DEBUG(verify_traceback_route_tree_equivalent(route_ctx.trace_head[net_id], rt_root));

    std::vector<int> modified_rr_node_inf;

    t_heap * cheapest = timing_driven_route_connection(source_node, sink_node, target_criticality,
            astar_fac, bend_cost, rt_root, bounding_box, (int)cluster_ctx.clb_nlist.net_sinks(net_id).size(), budgeting_inf,
            max_delay, min_delay, target_delay, short_path_crit, modified_rr_node_inf, router_stats);

    if (cheapest == nullptr) {
		ClusterBlockId src_block = cluster_ctx.clb_nlist.net_driver_block(net_id);
		ClusterBlockId sink_block = cluster_ctx.clb_nlist.pin_block(*(cluster_ctx.clb_nlist.net_pins(net_id).begin() + target_pin));
        vtr::printf("Failed to route connection from '%s' to '%s' for net '%s'\n",
                    cluster_ctx.clb_nlist.block_name(src_block).c_str(),
					cluster_ctx.clb_nlist.block_name(sink_block).c_str(),
                    cluster_ctx.clb_nlist.net_name(net_id).c_str());
        return false;
    }

    profiling::sink_criticality_end(target_criticality);

    /* NB:  In the code below I keep two records of the partial routing:  the   *
     * traceback and the route_tree.  The route_tree enables fast recomputation *
     * of the Elmore delay to each node in the partial routing.  The traceback  *
     * lets me reuse all the routines written for breadth-first routing, which  *
     * all take a traceback structure as input.                                 */

    int inode = cheapest->index;
    route_ctx.rr_node_route_inf[inode].target_flag--; /* Connected to this SINK. */
    t_trace* new_route_start_tptr = update_traceback(cheapest, net_id);
    VTR_ASSERT_DEBUG(validate_traceback(route_ctx.trace_head[net_id]));

    rt_node_of_sink[target_pin] = update_route_tree(cheapest);
    VTR_ASSERT_DEBUG(verify_route_tree(rt_root));
    VTR_ASSERT_DEBUG(verify_traceback_route_tree_equivalent(route_ctx.trace_head[net_id], rt_root));

    free_heap_data(cheapest);
    pathfinder_update_path_cost(new_route_start_tptr, 1, pres_fac);
    empty_heap();
    reset_path_costs(modified_rr_node_inf);

    // routed to a sink successfully
    return true;
}

t_heap * timing_driven_route_connection(int source_node, int sink_node, float target_criticality,
        float astar_fac, float bend_cost, t_rt_node* rt_root, t_bb bounding_box, int num_sinks, route_budgets &budgeting_inf,
        float max_delay, float min_delay, float target_delay, float short_path_crit, std::vector<int>& modified_rr_node_inf,
        RouterStats& router_stats) {
    auto& route_ctx = g_vpr_ctx.mutable_routing();

    int highfanout_rlim = mark_node_expansion_by_bin(source_node, sink_node, rt_root, bounding_box, num_sinks);

    // re-explore route tree from root to add any new nodes (buildheap afterwards)
    // route tree needs to be repushed onto the heap since each node's cost is target specific
    add_route_tree_to_heap(rt_root, sink_node, target_criticality, astar_fac, budgeting_inf,
            max_delay, min_delay, target_delay, short_path_crit, router_stats);
    heap_::build_heap(); // via sifting down everything

    VTR_ASSERT_SAFE(heap_::is_valid());

    // cheapest s_heap (gives index to device_ctx.rr_nodes) in current route tree to be expanded on
    t_heap * cheapest{get_heap_head()};
    ++router_stats.heap_pops;

    if (cheapest == nullptr) {
        auto& device_ctx = g_vpr_ctx.device();
        const t_rr_node* source_rr_node = &device_ctx.rr_nodes[source_node];
        const t_rr_node* sink_rr_node = &device_ctx.rr_nodes[sink_node];

        std::string msg = "Cannot route from ";

        if (source_rr_node->type() != CHANX || source_rr_node->type() != CHANY) {
            t_type_ptr src_type = device_ctx.grid[source_rr_node->xlow()][source_rr_node->ylow()].type;
            msg += block_type_pin_index_to_name(src_type, source_rr_node->ptc_num());
        }
        msg += vtr::string_fmt(" (rr_node: %d type: %s ptc: %d xlow: %d ylow: %d) to ",
                source_node, source_rr_node->type_string(), source_rr_node->ptc_num(), source_rr_node->xlow(), source_rr_node->ylow());

        if (sink_rr_node->type() != CHANX || sink_rr_node->type() != CHANY) {
            t_type_ptr src_type = device_ctx.grid[sink_rr_node->xlow()][sink_rr_node->ylow()].type;
            msg += block_type_pin_index_to_name(src_type, sink_rr_node->ptc_num());
        }
        msg += vtr::string_fmt(" (rr_node: %d type: %s ptc: %d xlow: %d ylow: %d) to ",
                sink_node, sink_rr_node->type_string(), sink_rr_node->ptc_num(), sink_rr_node->xlow(), sink_rr_node->ylow());

        msg += "-- no possible path\n";

        vtr::printf_info("%s", msg.c_str());

        reset_path_costs();
        free_route_tree(rt_root);
        return nullptr;
    }


    int inode = cheapest->index;
#ifdef ROUTER_DEBUG
    if (router_debug) vtr::printf("  Popping node %d\n", inode);
#endif
    while (inode != sink_node) {
        float old_total_cost = route_ctx.rr_node_route_inf[inode].path_cost;
        float old_back_cost = route_ctx.rr_node_route_inf[inode].backward_path_cost;

        float new_total_cost = cheapest->cost;
        float new_back_cost = cheapest->backward_path_cost;

        /* I only re-expand a node if both the "known" backward cost is lower  *
         * in the new expansion (this is necessary to prevent loops from       *
         * forming in the routing and causing havoc) *and* the expected total  *
         * cost to the sink is lower than the old value.  Different R_upstream *
         * values could make a path with lower back_path_cost less desirable   *
         * than one with higher cost.  Test whether or not I should disallow   *
         * re-expansion based on a higher total cost.                          */

        if (old_total_cost > new_total_cost && old_back_cost > new_back_cost) {

#ifdef ROUTER_DEBUG
            if (router_debug) vtr::printf("    Better cost to %d\n", inode);
#endif
            for (t_heap_prev prev : cheapest->previous) {
#ifdef ROUTER_DEBUG
                if (router_debug) vtr::printf("      Setting path costs for assicated node %d (from %d edge %d)\n", prev.to_node, prev.from_node, prev.from_edge);
#endif
                add_to_mod_list(prev.to_node, modified_rr_node_inf);

                route_ctx.rr_node_route_inf[prev.to_node].prev_node = prev.from_node;
                route_ctx.rr_node_route_inf[prev.to_node].prev_edge = prev.from_edge;
                route_ctx.rr_node_route_inf[prev.to_node].path_cost = new_total_cost;
                route_ctx.rr_node_route_inf[prev.to_node].backward_path_cost = new_back_cost;
            }

            timing_driven_expand_neighbours(cheapest, bounding_box, bend_cost,
                    target_criticality, num_sinks, sink_node, astar_fac,
                    highfanout_rlim, budgeting_inf, max_delay, min_delay,
                    target_delay, short_path_crit);
        }

        free_heap_data(cheapest);
        cheapest = get_heap_head();
        ++router_stats.heap_pops;

        if (cheapest == nullptr) { /* Impossible routing.  No path for net. */
            auto& device_ctx = g_vpr_ctx.device();
            const t_rr_node* source_rr_node = &device_ctx.rr_nodes[source_node];
            const t_rr_node* sink_rr_node = &device_ctx.rr_nodes[sink_node];

            std::string msg = "Cannot route from ";

            if (source_rr_node->type() != CHANX || source_rr_node->type() != CHANY) {
                t_type_ptr src_type = device_ctx.grid[source_rr_node->xlow()][source_rr_node->ylow()].type;
                msg += block_type_pin_index_to_name(src_type, source_rr_node->ptc_num());
            }
            msg += vtr::string_fmt(" (rr_node: %d type: %s ptc: %d xlow: %d ylow: %d) to ",
                    source_node, source_rr_node->type_string(), source_rr_node->ptc_num(), source_rr_node->xlow(), source_rr_node->ylow());

            if (sink_rr_node->type() != CHANX || sink_rr_node->type() != CHANY) {
                t_type_ptr src_type = device_ctx.grid[sink_rr_node->xlow()][sink_rr_node->ylow()].type;
                msg += block_type_pin_index_to_name(src_type, sink_rr_node->ptc_num());
            }
            msg += vtr::string_fmt(" (rr_node: %d type: %s ptc: %d xlow: %d ylow: %d) to ",
                    sink_node, sink_rr_node->type_string(), sink_rr_node->ptc_num(), sink_rr_node->xlow(), sink_rr_node->ylow());

            msg += "-- no possible path\n";

            vtr::printf_info("%s", msg.c_str());

            reset_path_costs();
            free_route_tree(rt_root);
            return nullptr;
        }

        inode = cheapest->index;
#ifdef ROUTER_DEBUG
        if (router_debug) vtr::printf("  Popping node %d\n", inode);
#endif
    }
#ifdef ROUTER_DEBUG
    if (router_debug) vtr::printf("  Found target %d\n", inode);
#endif

    return cheapest;
}

static t_rt_node* setup_routing_resources(int itry, ClusterNetId net_id, unsigned num_sinks, float pres_fac, int min_incremental_reroute_fanout,
        CBRR& connections_inf, t_rt_node** rt_node_of_sink) {

    /* Build and return a partial route tree from the legal connections from last iteration.
     * along the way do:
     * 	update pathfinder costs to be accurate to the partial route tree
     *	update the net's traceback to be accurate to the partial route tree
     * 	find and store the pins that still need to be reached in incremental_rerouting_resources.remaining_targets
     * 	find and store the rt nodes that have been reached in incremental_rerouting_resources.reached_rt_sinks
     *	mark the rr_node sinks as targets to be reached */

    auto& route_ctx = g_vpr_ctx.routing();

    t_rt_node* rt_root;

    // for nets below a certain size (min_incremental_reroute_fanout), rip up any old routing
    // otherwise, we incrementally reroute by reusing legal parts of the previous iteration
    // convert the previous iteration's traceback into the starting route tree for this iteration
    if ((int) num_sinks < min_incremental_reroute_fanout || itry == 1) {

        profiling::net_rerouted();

        // rip up the whole net
        pathfinder_update_path_cost(route_ctx.trace_head[net_id], -1, pres_fac);
        free_traceback(net_id);

        rt_root = init_route_tree_to_source(net_id);
        for (unsigned int sink_pin = 1; sink_pin <= num_sinks; ++sink_pin)
            connections_inf.toreach_rr_sink(sink_pin);
        // since all connections will be rerouted for this net, clear all of net's forced reroute flags
        connections_inf.clear_force_reroute_for_net();

        // when we don't prune the tree, we also don't know the sink node indices 
        // thus we'll use functions that act on pin indices like mark_ends instead
        // of their versions that act on node indices directly like mark_remaining_ends
        mark_ends(net_id);
    } else {
        auto& reached_rt_sinks = connections_inf.get_reached_rt_sinks();
        auto& remaining_targets = connections_inf.get_remaining_targets();

        profiling::net_rebuild_start();

        // convert the previous iteration's traceback into a route tree
        rt_root = traceback_to_route_tree(net_id);

        //Santiy check that route tree and traceback are equivalent before pruning
        VTR_ASSERT_DEBUG(verify_traceback_route_tree_equivalent(route_ctx.trace_head[net_id], rt_root));

        // check for edge correctness
        VTR_ASSERT_SAFE(is_valid_skeleton_tree(rt_root));
        VTR_ASSERT_SAFE(should_route_net(net_id, connections_inf, true));

        //Prune the branches of the tree that don't legally lead to sinks
        rt_root = prune_route_tree(rt_root, connections_inf);

        //Now that the tree has been pruned, we can free the old traceback
        // NOTE: this must happen *after* pruning since it changes the 
        //       recorded congestion
        pathfinder_update_path_cost(route_ctx.trace_head[net_id], -1, pres_fac);
        free_traceback(net_id);

        if (rt_root) { //Partially pruned
            profiling::route_tree_preserved();

            //Since we have a valid partial routing (to at least one SINK)
            //we need to make sure the traceback is synchronized to the route tree
            traceback_from_route_tree(net_id, rt_root, reached_rt_sinks.size());

            //Sanity check the traceback for self-consistency
            VTR_ASSERT_DEBUG(validate_traceback(route_ctx.trace_head[net_id]));

            //Santiy check that route tree and traceback are equivalent after pruning
            VTR_ASSERT_DEBUG(verify_traceback_route_tree_equivalent(route_ctx.trace_head[net_id], rt_root));

            // put the updated costs of the route tree nodes back into pathfinder
            pathfinder_update_path_cost(route_ctx.trace_head[net_id], 1, pres_fac);

        } else { //Fully destroyed
            profiling::route_tree_pruned();

            //Initialize only to source
            rt_root = init_route_tree_to_source(net_id);

            //NOTE: We leave the traceback uninitiailized, so update_traceback()
            //      will correctly add the SOURCE node when the branch to
            //      the first SINK is found.
            VTR_ASSERT(route_ctx.trace_head[net_id] == nullptr);
            VTR_ASSERT(route_ctx.trace_tail[net_id] == nullptr);
            VTR_ASSERT(route_ctx.trace_nodes[net_id].empty());
        }

        //Update R/C
        load_new_subtree_R_upstream(rt_root);
        load_new_subtree_C_downstream(rt_root);

        VTR_ASSERT(reached_rt_sinks.size() + remaining_targets.size() == num_sinks);

        //Record current routing
        add_route_tree_to_rr_node_lookup(rt_root);

        // give lookup on the reached sinks
        connections_inf.put_sink_rt_nodes_in_net_pins_lookup(reached_rt_sinks, rt_node_of_sink);

        profiling::net_rebuild_end(num_sinks, remaining_targets.size());

        // check for R_upstream C_downstream and edge correctness
        VTR_ASSERT_SAFE(is_valid_route_tree(rt_root));
        // congestion should've been pruned away
        VTR_ASSERT_SAFE(is_uncongested_route_tree(rt_root));

        // use the nodes to directly mark ends before they get converted to pins
        mark_remaining_ends(remaining_targets);

        // everything dealing with a net works with it in terms of its sink pins; need to convert its sink nodes to sink pins
        connections_inf.convert_sink_nodes_to_net_pins(remaining_targets);

        // still need to calculate the tree's time delay (0 Tarrival means from SOURCE)
        load_route_tree_Tdel(rt_root, 0);
        // mark the lookup (rr_node_route_inf) for existing tree elements as NO_PREVIOUS so add_to_path stops when it reaches one of them
        load_route_tree_rr_route_inf(rt_root);
    }
    // completed constructing the partial route tree and updated all other data structures to match
    return rt_root;
}

static void add_route_tree_to_heap(t_rt_node * rt_node, int target_node,
        float target_criticality, float astar_fac, route_budgets& budgeting_inf,
        float max_delay, float min_delay,
        float target_delay, float short_path_crit, RouterStats& router_stats) {

    /* Puts the entire partial routing below and including rt_node onto the heap *
     * (except for those parts marked as not to be expanded) by calling itself   *
     * recursively.                                                              */

    int inode;
    t_rt_node *child_node;
    t_linked_rt_edge *linked_rt_edge;
    float tot_cost, backward_path_cost, R_upstream;

    /* Pre-order depth-first traversal */
    // IPINs and SINKS are not re_expanded
    if (rt_node->re_expand) {
        inode = rt_node->inode;
        backward_path_cost = target_criticality * rt_node->Tdel;

        R_upstream = rt_node->R_upstream;
        tot_cost = backward_path_cost
                + astar_fac
                * get_timing_driven_expected_cost(inode, target_node,
                target_criticality, R_upstream);

        float zero = 0.0;
        //after budgets are loaded, calculate delay cost as described by RCV paper
        /*R. Fung, V. Betz and W. Chow, "Slack Allocation and Routing to Improve FPGA Timing While 
         * Repairing Short-Path Violations," in IEEE Transactions on Computer-Aided Design of 
         * Integrated Circuits and Systems, vol. 27, no. 4, pp. 686-697, April 2008.*/
        if (budgeting_inf.if_set()) {
            tot_cost += (short_path_crit + target_criticality) * max(zero, target_delay - tot_cost);
            tot_cost += pow(max(zero, tot_cost - max_delay), 2) / 100e-12;
            tot_cost += pow(max(zero, min_delay - tot_cost), 2) / 100e-12;
        }

#ifdef ROUTER_DEBUG
        if (router_debug) vtr::printf("Adding node %d to heap from init route tree\n", inode);
#endif

        heap_::push_back_node(inode, tot_cost, NO_PREVIOUS, NO_PREVIOUS,
                backward_path_cost, R_upstream);

        ++router_stats.heap_pushes;
    }

    linked_rt_edge = rt_node->u.child_list;

    while (linked_rt_edge != nullptr) {
        child_node = linked_rt_edge->child;
        add_route_tree_to_heap(child_node, target_node, target_criticality,
                astar_fac, budgeting_inf, max_delay, min_delay,
                target_delay, short_path_crit, router_stats);
        linked_rt_edge = linked_rt_edge->next;
    }
}

static void timing_driven_expand_neighbours(t_heap *current,
        t_bb bounding_box, float bend_cost, float criticality_fac,
        int num_sinks, int target_node,
        float astar_fac, int highfanout_rlim, route_budgets& budgeting_inf, float max_delay, float min_delay,
        float target_delay, float short_path_crit) {

    /* Puts all the rr_nodes adjacent to current on the heap.  rr_nodes outside *
     * the expanded bounding box specified in bounding_box are not added to the     *
     * heap.                                                                    */

    auto& device_ctx = g_vpr_ctx.device();

    int inode = current->index;

    int target_xlow = device_ctx.rr_nodes[target_node].xlow();
    int target_ylow = device_ctx.rr_nodes[target_node].ylow();
    int target_xhigh = device_ctx.rr_nodes[target_node].xhigh();
    int target_yhigh = device_ctx.rr_nodes[target_node].yhigh();

    bool high_fanout = num_sinks >= HIGH_FANOUT_NET_LIM;

    int num_edges = device_ctx.rr_nodes[inode].num_edges();
    for (int iconn = 0; iconn < num_edges; iconn++) {
        int to_node = device_ctx.rr_nodes[inode].edge_sink_node(iconn);

        int to_xlow = device_ctx.rr_nodes[to_node].xlow();
        int to_ylow = device_ctx.rr_nodes[to_node].ylow();
        int to_xhigh = device_ctx.rr_nodes[to_node].xhigh();
        int to_yhigh = device_ctx.rr_nodes[to_node].yhigh();

        if (high_fanout) {
            if (   to_xhigh < target_xhigh - highfanout_rlim
                || to_xlow > target_xlow + highfanout_rlim
                || to_yhigh < target_yhigh - highfanout_rlim
                || to_ylow > target_ylow + highfanout_rlim) {
                continue; /* Node is outside high fanout bin. */
            }
        } else if (to_xhigh < bounding_box.xmin
                   || to_xlow > bounding_box.xmax
                   || to_yhigh < bounding_box.ymin
                   || to_ylow > bounding_box.ymax) {
            continue; /* Node is outside (expanded) bounding box. */
        }


        /* Prune away IPINs that lead to blocks other than the target one.  Avoids  *
         * the issue of how to cost them properly so they don't get expanded before *
         * more promising routes, but makes route-throughs (via CLBs) impossible.   *
         * Change this if you want to investigate route-throughs.                   */
        t_rr_type to_type = device_ctx.rr_nodes[to_node].type();
        if (to_type == IPIN) {
            //Check if this IPIN leads to the target block
            // IPIN's of the target block should be contained within it's bounding box
            if (   to_xlow < target_xlow 
                || to_ylow < target_ylow
                || to_xhigh > target_xhigh 
                || to_yhigh > target_yhigh) {
                continue;
            }
        }

        timing_driven_add_to_heap(criticality_fac, bend_cost, astar_fac,
                budgeting_inf, max_delay, min_delay, target_delay, short_path_crit,
                current, inode, to_node, iconn, target_node);
    } /* End for all neighbours */
}

//Add to_node to the heap, and also add any nodes which are connected by non-configurable edges
static void timing_driven_add_to_heap(const float criticality_fac, const float bend_cost, const float astar_fac,
        const route_budgets& budgeting_inf, const float max_delay, const float min_delay, const float target_delay, const float short_path_crit,
        const t_heap* current, const int from_node, const int to_node, const int iconn, const int target_node) {

    t_heap* next = alloc_heap_data();
    next->index = to_node;

    //Costs initialized to current
    next->cost = std::numeric_limits<float>::infinity(); //Not used directly
    next->backward_path_cost = current->backward_path_cost;
    next->R_upstream = current->R_upstream;

    auto& device_ctx = g_vpr_ctx.device();
    if (device_ctx.rr_nodes[to_node].num_non_configurable_edges() == 0) {
        //The common case where there are no non-configurable edges
        timing_driven_expand_node(criticality_fac, bend_cost, astar_fac,
                budgeting_inf, max_delay, min_delay, target_delay, short_path_crit,
                next, from_node, to_node, iconn, target_node);
    } else {
        //The 'to_node' which we just expanded to has non-configurable 
        //out-going edges which must also be expanded.
        //
        //Note that we only call the recursive version if there *are* non-configurable
        //edges since creating/destroying the 'visited' tracker is very expensive (since 
        //it is in the router's inner loop). Since non-configurable edges are relatively
        //rare this is reasonable.
        //
        //TODO: use a more efficient method of tracking visited nodes (e.g. if 
        //      non-configurable edges become more common)
        std::set<int> visited;
        timing_driven_expand_node_non_configurable_recurr(criticality_fac, bend_cost, astar_fac,
                budgeting_inf, max_delay, min_delay, target_delay, short_path_crit,
                next, from_node, to_node, iconn, target_node,
                visited);
    }

    add_to_heap(next);
}

//Updates current (path step and costs) to account for the step taken to reach to_node
static void timing_driven_expand_node(const float criticality_fac, const float bend_cost, const float astar_fac,
        const route_budgets& budgeting_inf, const float max_delay, const float min_delay, const float target_delay, const float short_path_crit,
        t_heap* current, const int from_node, const int to_node, const int iconn, const int target_node) {


#ifdef ROUTER_DEBUG
    if (router_debug) {
        auto& device_ctx = g_vpr_ctx.device();
        bool reached_via_non_configurable_edge = !device_ctx.rr_nodes[from_node].edge_is_configurable(iconn);
        if (reached_via_non_configurable_edge) {
            vtr::printf("        Force Expanding to node %d", to_node);
        } else {
            vtr::printf("      Expanding to node %d", to_node);
        }
        vtr::printf("\n");
    }
#endif

    t_timing_driven_node_costs old_costs;
    old_costs.backward_cost = current->backward_path_cost;
    old_costs.total_cost = current->cost;
    old_costs.R_upstream = current->R_upstream;

    auto new_costs = evaluate_timing_driven_node_costs(old_costs,
                        criticality_fac, bend_cost, astar_fac,
                        budgeting_inf, max_delay, min_delay, target_delay, short_path_crit,
                        from_node, to_node, iconn, target_node);

    //Record how we reached this node
    current->previous.emplace_back(to_node, from_node, iconn);

    //Since this heap element may represent multiple (non-configurably connected) nodes,
    //keep the minimum cost to the target
    if (new_costs.total_cost < current->cost) {
        current->cost = new_costs.total_cost;
        current->backward_path_cost = new_costs.backward_cost;
        current->R_upstream = new_costs.R_upstream;
        current->index = to_node;
    }
}

//Updates current (path stage and costs) to account for the step taken to reach to_node,
//and any of it's non-configurably connected nodes
static void timing_driven_expand_node_non_configurable_recurr(const float criticality_fac, const float bend_cost, const float astar_fac,
        const route_budgets& budgeting_inf, const float max_delay, const float min_delay, const float target_delay, const float short_path_crit,
        t_heap* current, const int from_node, const int to_node, const int iconn, const int target_node,
        std::set<int>& visited
        ) {

    VTR_ASSERT(current);

    if (visited.count(to_node)) {
        return;
    }

    visited.insert(to_node);

    auto& device_ctx = g_vpr_ctx.device();

    timing_driven_expand_node(criticality_fac, bend_cost, astar_fac,
            budgeting_inf, max_delay, min_delay, target_delay, short_path_crit,
            current, from_node, to_node, iconn, target_node);

    //Consider any non-configurable edges which must be expanded for correctness
    for (int iconn_next : device_ctx.rr_nodes[to_node].non_configurable_edges()) {
        VTR_ASSERT_SAFE(!device_ctx.rr_nodes[to_node].edge_is_configurable(iconn_next)); //Forced expansion

        int to_to_node = device_ctx.rr_nodes[to_node].edge_sink_node(iconn_next);

        timing_driven_expand_node_non_configurable_recurr(criticality_fac, bend_cost, astar_fac,
                budgeting_inf, max_delay, min_delay, target_delay, short_path_crit,
                current, to_node, to_to_node, iconn_next, target_node, visited);
    }
}

//Calculates the cost of reaching to_node
t_timing_driven_node_costs evaluate_timing_driven_node_costs(const t_timing_driven_node_costs old_costs,
    const float criticality_fac, const float bend_cost, const float astar_fac,
    const route_budgets& budgeting_inf, const float max_delay, const float min_delay, const float target_delay, const float short_path_crit,
    const int from_node, const int to_node, const int iconn, const int target_node) {
    /* new_costs.backward_cost: is the "known" part of the cost to this node -- the
     * congestion cost of all the routing resources back to the existing route
     * plus the known delay of the total path back to the source.
     *
     * new_costs.total_cost: is this "known" backward cost + an expected cost to get to the target.   
     *
     * new_costs.R_upstream: is the upstream resistance at the end of this node
     */
    auto& device_ctx = g_vpr_ctx.device();

    t_timing_driven_node_costs new_costs;

    //Switch info
    int iswitch = device_ctx.rr_nodes[from_node].edge_switch(iconn);
    bool switch_buffered = device_ctx.rr_switch_inf[iswitch].buffered;
    float switch_R = device_ctx.rr_switch_inf[iswitch].R;
    float switch_Tdel = device_ctx.rr_switch_inf[iswitch].Tdel;

    //Node info
    float node_C = device_ctx.rr_nodes[to_node].C();
    float node_R = device_ctx.rr_nodes[to_node].R();

    //Update R_upstream
    if (switch_buffered) {
        new_costs.R_upstream = 0.; //No upstream resistance
    } else {
        new_costs.R_upstream = old_costs.R_upstream; //Upstream resistance
    }
    new_costs.R_upstream += switch_R; //Switch resistance
    new_costs.R_upstream += node_R; //Node resistance

    //Calculate delay
    float Rdel = new_costs.R_upstream - 0.5 * node_R; //Only consider half node's resistance for delay
    float Tdel = switch_Tdel + Rdel * node_C;

    //Update the backward cost
    new_costs.backward_cost = old_costs.backward_cost; //Back cost to 'from_node'
    new_costs.backward_cost += (1. - criticality_fac) * get_rr_cong_cost(to_node); //Congestion cost
    new_costs.backward_cost += criticality_fac * Tdel; //Delay cost
    if (bend_cost != 0.) {
        t_rr_type from_type = device_ctx.rr_nodes[from_node].type();
        t_rr_type to_type = device_ctx.rr_nodes[to_node].type();
        if ((from_type == CHANX && to_type == CHANY) || (from_type == CHANY && to_type == CHANX)) {
            new_costs.backward_cost += bend_cost; //Bend cost
        }
    }

    if (budgeting_inf.if_set()) {
        //If budgets specified calculate cost as described by RCV paper:
        //    R. Fung, V. Betz and W. Chow, "Slack Allocation and Routing to Improve FPGA Timing While 
        //     Repairing Short-Path Violations," in IEEE Transactions on Computer-Aided Design of 
        //     Integrated Circuits and Systems, vol. 27, no. 4, pp. 686-697, April 2008.

        //TODO: Since these targets are delays, shouldn't we be using Tdel instead of new_costs.total_cost on RHS?
        new_costs.total_cost += (short_path_crit + criticality_fac) * max(0.f, target_delay - new_costs.total_cost);
        new_costs.total_cost += pow(max(0.f, new_costs.total_cost - max_delay), 2) / 100e-12;
        new_costs.total_cost += pow(max(0.f, min_delay - new_costs.total_cost), 2) / 100e-12;
    }

    //Update total cost
    float expected_cost = get_timing_driven_expected_cost(to_node, target_node, criticality_fac, new_costs.R_upstream);
    new_costs.total_cost = new_costs.backward_cost + astar_fac * expected_cost;

    return new_costs;
}

static float get_timing_driven_expected_cost(int inode, int target_node, float criticality_fac, float R_upstream) {

    /* Determines the expected cost (due to both delay and resource cost) to reach *
     * the target node from inode.  It doesn't include the cost of inode --       *
     * that's already in the "known" path_cost.                                   */

    auto& device_ctx = g_vpr_ctx.device();

    t_rr_type rr_type = device_ctx.rr_nodes[inode].type();

    if (rr_type == CHANX || rr_type == CHANY) {

#ifdef USE_MAP_LOOKAHEAD
        return get_lookahead_map_cost(inode, target_node, criticality_fac);
#else
        int num_segs_ortho_dir = 0;
        int num_segs_same_dir = get_expected_segs_to_target(inode, target_node, &num_segs_ortho_dir);

        int cost_index = device_ctx.rr_nodes[inode].cost_index();
        int ortho_cost_index = device_ctx.rr_indexed_data[cost_index].ortho_cost_index;

        const auto& same_data = device_ctx.rr_indexed_data[cost_index];
        const auto& ortho_data = device_ctx.rr_indexed_data[ortho_cost_index];
        const auto& ipin_data = device_ctx.rr_indexed_data[IPIN_COST_INDEX];
        const auto& sink_data = device_ctx.rr_indexed_data[SINK_COST_INDEX];

        float cong_cost =   num_segs_same_dir * same_data.base_cost
                          + num_segs_ortho_dir * ortho_data.base_cost
                          + ipin_data.base_cost
                          + sink_data.base_cost;

        float Tdel =   num_segs_same_dir * same_data.T_linear
                     + num_segs_ortho_dir * ortho_data.T_linear
                     + num_segs_same_dir * num_segs_same_dir * same_data.T_quadratic
                     + num_segs_ortho_dir * num_segs_ortho_dir * ortho_data.T_quadratic
                     + R_upstream * (  num_segs_same_dir * same_data.C_load 
                                     + num_segs_ortho_dir * ortho_data.C_load)
                     + ipin_data.T_linear;

        float expected_cost = criticality_fac * Tdel + (1. - criticality_fac) * cong_cost;
        return (expected_cost);
#endif
    } else if (rr_type == IPIN) { /* Change if you're allowing route-throughs */
        return (device_ctx.rr_indexed_data[SINK_COST_INDEX].base_cost);
    } else { /* Change this if you want to investigate route-throughs */
        return (0.);
    }
}

/* Used below to ensure that fractions are rounded up, but floating   *
 * point values very close to an integer are rounded to that integer.       */
static int round_up(float x) {
    return std::ceil(x - 0.001);
}

static int get_expected_segs_to_target(int inode, int target_node,
        int *num_segs_ortho_dir_ptr) {

    /* Returns the number of segments the same type as inode that will be needed *
     * to reach target_node (not including inode) in each direction (the same    *
     * direction (horizontal or vertical) as inode and the orthogonal direction).*/

    auto& device_ctx = g_vpr_ctx.device();

    t_rr_type rr_type;
    int target_x, target_y, num_segs_same_dir, cost_index, ortho_cost_index;
    int no_need_to_pass_by_clb;
    float inv_length, ortho_inv_length, ylow, yhigh, xlow, xhigh;


    target_x = device_ctx.rr_nodes[target_node].xlow();
    target_y = device_ctx.rr_nodes[target_node].ylow();
    cost_index = device_ctx.rr_nodes[inode].cost_index();
    inv_length = device_ctx.rr_indexed_data[cost_index].inv_length;
    ortho_cost_index = device_ctx.rr_indexed_data[cost_index].ortho_cost_index;
    ortho_inv_length = device_ctx.rr_indexed_data[ortho_cost_index].inv_length;
    rr_type = device_ctx.rr_nodes[inode].type();

    if (rr_type == CHANX) {
        ylow = device_ctx.rr_nodes[inode].ylow();
        xhigh = device_ctx.rr_nodes[inode].xhigh();
        xlow = device_ctx.rr_nodes[inode].xlow();

        /* Count vertical (orthogonal to inode) segs first. */

        if (ylow > target_y) { /* Coming from a row above target? */
            *num_segs_ortho_dir_ptr = round_up((ylow - target_y + 1.) * ortho_inv_length);
            no_need_to_pass_by_clb = 1;
        } else if (ylow < target_y - 1) { /* Below the CLB bottom? */
            *num_segs_ortho_dir_ptr = round_up((target_y - ylow) * ortho_inv_length);
            no_need_to_pass_by_clb = 1;
        } else { /* In a row that passes by target CLB */
            *num_segs_ortho_dir_ptr = 0;
            no_need_to_pass_by_clb = 0;
        }


        /* Now count horizontal (same dir. as inode) segs. */

        if (xlow > target_x + no_need_to_pass_by_clb) {
            num_segs_same_dir = round_up((xlow - no_need_to_pass_by_clb -
                    target_x) * inv_length);
        } else if (xhigh < target_x - no_need_to_pass_by_clb) {
            num_segs_same_dir = round_up((target_x - no_need_to_pass_by_clb -
                    xhigh) * inv_length);
        } else {
            num_segs_same_dir = 0;
        }
    } else { /* inode is a CHANY */
        ylow = device_ctx.rr_nodes[inode].ylow();
        yhigh = device_ctx.rr_nodes[inode].yhigh();
        xlow = device_ctx.rr_nodes[inode].xlow();

        /* Count horizontal (orthogonal to inode) segs first. */

        if (xlow > target_x) { /* Coming from a column right of target? */
            *num_segs_ortho_dir_ptr = round_up((xlow - target_x + 1.) * ortho_inv_length);
            no_need_to_pass_by_clb = 1;
        } else if (xlow < target_x - 1) { /* Left of and not adjacent to the CLB? */
            *num_segs_ortho_dir_ptr = round_up((target_x - xlow) *
                    ortho_inv_length);
            no_need_to_pass_by_clb = 1;
        } else { /* In a column that passes by target CLB */
            *num_segs_ortho_dir_ptr = 0;
            no_need_to_pass_by_clb = 0;
        }

        /* Now count vertical (same dir. as inode) segs. */

        if (ylow > target_y + no_need_to_pass_by_clb) {
            num_segs_same_dir = round_up((ylow - no_need_to_pass_by_clb -
                    target_y) * inv_length);
        } else if (yhigh < target_y - no_need_to_pass_by_clb) {
            num_segs_same_dir = round_up((target_y - no_need_to_pass_by_clb -
                    yhigh) * inv_length);
        } else {
            num_segs_same_dir = 0;
        }

    }

    return (num_segs_same_dir);
}

void update_rr_base_costs(int fanout) {

    /* Changes the base costs of different types of rr_nodes according to the  *
     * criticality, fanout, etc. of the current net being routed (net_id).       */
    auto& device_ctx = g_vpr_ctx.device();

    float factor;
    int index;

    /* Other reasonable values for factor include fanout and 1 */
    factor = sqrt(fanout);

    for (index = CHANX_COST_INDEX_START; index < device_ctx.num_rr_indexed_data; index++) {
        if (device_ctx.rr_indexed_data[index].T_quadratic > 0.) { /* pass transistor */
            device_ctx.rr_indexed_data[index].base_cost =
                    device_ctx.rr_indexed_data[index].saved_base_cost * factor;
        } else {
            device_ctx.rr_indexed_data[index].base_cost =
                    device_ctx.rr_indexed_data[index].saved_base_cost;
        }
    }
}

/* Nets that have high fanout can take a very long time to route. Routing for sinks that are part of high-fanout nets should be
   done within a rectangular 'bin' centered around a target (as opposed to the entire net bounding box) the size of which is returned by this function. */
static int mark_node_expansion_by_bin(int source_node, int target_node,
        t_rt_node * rt_node, t_bb bounding_box, int num_sinks) {

    auto& device_ctx = g_vpr_ctx.device();

    int target_xlow, target_ylow, target_xhigh, target_yhigh;
    int rlim = 1;
    int max_grid_dim = max(device_ctx.grid.width(), device_ctx.grid.height());
    int inode;
    float area;
    bool success;
    t_linked_rt_edge *linked_rt_edge;
    t_rt_node * child_node;

    target_xlow = device_ctx.rr_nodes[target_node].xlow();
    target_ylow = device_ctx.rr_nodes[target_node].ylow();
    target_xhigh = device_ctx.rr_nodes[target_node].xhigh();
    target_yhigh = device_ctx.rr_nodes[target_node].yhigh();

    if (num_sinks < HIGH_FANOUT_NET_LIM) {
        /* This algorithm only applies to high fanout nets */
        return 1;
    }
    if (rt_node == nullptr || rt_node->u.child_list == nullptr) {
        /* If unknown traceback, set radius of bin to be size of chip */
        rlim = max_grid_dim;
        return rlim;
    }

    area = (bounding_box.xmax - bounding_box.xmin)
            * (bounding_box.ymax - bounding_box.ymin);
    if (area <= 0) {
        area = 1;
    }

    VTR_ASSERT(num_sinks > 0);

    rlim = (int) (ceil(sqrt((float) area / (float) num_sinks)));

    success = false;
    /* determine quickly a feasible bin radius to route sink for high fanout nets 
     this is necessary to prevent super long runtimes for high fanout nets; in best case, a reduction in complexity from O(N^2logN) to O(NlogN) (Swartz fast router)
     */
    linked_rt_edge = rt_node->u.child_list;
    while (success == false && linked_rt_edge != nullptr) {
        while (linked_rt_edge != nullptr && success == false) {
            child_node = linked_rt_edge->child;
            inode = child_node->inode;
            if (!(device_ctx.rr_nodes[inode].type() == IPIN || device_ctx.rr_nodes[inode].type() == SINK)) {
                if (device_ctx.rr_nodes[inode].xlow() <= target_xhigh + rlim
                        && device_ctx.rr_nodes[inode].xhigh() >= target_xhigh - rlim
                        && device_ctx.rr_nodes[inode].ylow() <= target_yhigh + rlim
                        && device_ctx.rr_nodes[inode].yhigh() >= target_yhigh - rlim) {
                    success = true;
                }
            }
            linked_rt_edge = linked_rt_edge->next;
        }

        if (success == false) {
            if (rlim > max_grid_dim) {
                vpr_throw(VPR_ERROR_ROUTE, __FILE__, __LINE__,
                        "VPR internal error, the source node %d has paths that are not found in traceback.\n", source_node);
            }
            /* if sink not in bin, increase bin size until fit */
            rlim *= 2;
        } else {
            /* Sometimes might just catch a wire in the end segment, need to give it some channel space to explore */
            rlim += 4;
        }
        linked_rt_edge = rt_node->u.child_list;
    }

    /* adjust rlim to account for width/height of block containing the target sink */
    int target_span = max(target_xhigh - target_xlow, target_yhigh - target_ylow);
    rlim += target_span;

    /* redetermine expansion based on rlim */
    linked_rt_edge = rt_node->u.child_list;
    while (linked_rt_edge != nullptr) {
        child_node = linked_rt_edge->child;
        inode = child_node->inode;
        if (!(device_ctx.rr_nodes[inode].type() == IPIN || device_ctx.rr_nodes[inode].type() == SINK)) {
            if (device_ctx.rr_nodes[inode].xlow() <= target_xhigh + rlim
                    && device_ctx.rr_nodes[inode].xhigh() >= target_xhigh - rlim
                    && device_ctx.rr_nodes[inode].ylow() <= target_yhigh + rlim
                    && device_ctx.rr_nodes[inode].yhigh() >= target_yhigh - rlim) {
                child_node->re_expand = true;
            } else {
                child_node->re_expand = false;
            }
        }
        linked_rt_edge = linked_rt_edge->next;
    }
    return rlim;
}

static bool timing_driven_check_net_delays(vtr::vector_map<ClusterNetId, float *> &net_delay) {
    constexpr float ERROR_TOL = 0.0001;

    /* Checks that the net delays computed incrementally during timing driven    *
     * routing match those computed from scratch by the net_delay.c module.      */
    auto& cluster_ctx = g_vpr_ctx.clustering();

    unsigned int ipin;
	vtr::vector_map<ClusterNetId, float *> net_delay_check;

    vtr::t_chunk list_head_net_delay_check_ch;

    net_delay_check = alloc_net_delay(&list_head_net_delay_check_ch);
    load_net_delay_from_routing(net_delay_check);

	for (auto net_id : cluster_ctx.clb_nlist.nets()) {
        for (ipin = 1; ipin < cluster_ctx.clb_nlist.net_pins(net_id).size(); ipin++) {
            if (net_delay_check[net_id][ipin] == 0.) { /* Should be only GLOBAL nets */
                if (fabs(net_delay[net_id][ipin]) > ERROR_TOL) {
                    vpr_throw(VPR_ERROR_ROUTE, __FILE__, __LINE__,
                            "in timing_driven_check_net_delays: net %lu pin %d.\n"
                            "\tIncremental calc. net_delay is %g, but from scratch net delay is %g.\n",
							size_t(net_id), ipin, net_delay[net_id][ipin], net_delay_check[net_id][ipin]);
                }
            } else {
                float error = fabs(1.0 - net_delay[net_id][ipin] / net_delay_check[net_id][ipin]);
                if (error > ERROR_TOL) {
                    vpr_throw(VPR_ERROR_ROUTE, __FILE__, __LINE__,
                            "in timing_driven_check_net_delays: net %d pin %lu.\n"
                            "\tIncremental calc. net_delay is %g, but from scratch net delay is %g.\n",
							size_t(net_id), ipin, net_delay[net_id][ipin], net_delay_check[net_id][ipin]);
                }
            }
        }
    }

    free_net_delay(net_delay_check, &list_head_net_delay_check_ch);
    return true;
}

/* Detect if net should be routed or not */
static bool should_route_net(ClusterNetId net_id, const CBRR& connections_inf, bool if_force_reroute) {
    auto& route_ctx = g_vpr_ctx.routing();
    auto& device_ctx = g_vpr_ctx.device();

    t_trace * tptr = route_ctx.trace_head[net_id];

    if (tptr == nullptr) {
        /* No routing yet. */
        return true;
    }

    for (;;) {
        int inode = tptr->index;
        int occ = route_ctx.rr_node_route_inf[inode].occ();
        int capacity = device_ctx.rr_nodes[inode].capacity();

        if (occ > capacity) {
            return true; /* overuse detected */
        }

        if (tptr->iswitch == OPEN) { //End of a branch
            // even if net is fully routed, not complete if parts of it should get ripped up (EXPERIMENTAL)
            if (if_force_reroute) {
                if (connections_inf.should_force_reroute_connection(inode)) {
                    return true;
                }
            }
            tptr = tptr->next; /* Skip next segment (duplicate of original branch node). */
            if (tptr == nullptr)
                break;
        }

        tptr = tptr->next;

    } /* End while loop -- did an entire traceback. */

    return false; /* Current route has no overuse */
}

static bool early_exit_heuristic(const WirelengthInfo& wirelength_info) {
    /* Early exit code for cases where it is obvious that a successful route will not be found 
       Heuristic: If total wirelength used in first routing iteration is X% of total available wirelength, exit */

    if (wirelength_info.used_wirelength_ratio() > FIRST_ITER_WIRELENTH_LIMIT) {
        vtr::printf_info("Wire length usage ratio %g exceeds limit of %g, fail routing.\n",
                wirelength_info.used_wirelength_ratio(),
                FIRST_ITER_WIRELENTH_LIMIT);
        return true;
    }
    return false;
}

// incremental rerouting resources class definitions
Connection_based_routing_resources::Connection_based_routing_resources() :
current_inet(NO_PREVIOUS), // not routing to a specific net yet (note that NO_PREVIOUS is not unsigned, so will be largest unsigned)
last_stable_critical_path_delay{0.0f},
critical_path_growth_tolerance{1.001f},
connection_criticality_tolerance{0.9f},
connection_delay_optimality_tolerance{1.1f}
{

    /* Initialize the persistent data structures for incremental rerouting
     * this includes rr_sink_node_to_pin, which provides pin lookup given a
     * sink node for a specific net.
     *
     * remaining_targets will reserve enough space to ensure it won't need
     * to grow while storing the sinks that still need routing after pruning
     *
     * reached_rt_sinks will also reserve enough space, but instead of
     * indices, it will store the pointers to route tree nodes */

    auto& cluster_ctx = g_vpr_ctx.clustering();
    auto& route_ctx = g_vpr_ctx.routing();

    // can have as many targets as sink pins (total number of pins - SOURCE pin)
    // supposed to be used as persistent vector growing with push_back and clearing at the start of each net routing iteration
    auto max_sink_pins_per_net = std::max(get_max_pins_per_net() - 1, 0);
    remaining_targets.reserve(max_sink_pins_per_net);
    reached_rt_sinks.reserve(max_sink_pins_per_net);

    size_t routing_num_nets = cluster_ctx.clb_nlist.nets().size();
    rr_sink_node_to_pin.resize(routing_num_nets);
    lower_bound_connection_delay.resize(routing_num_nets);
    forcible_reroute_connection_flag.resize(routing_num_nets);

	for (auto net_id : cluster_ctx.clb_nlist.nets()) {
        // unordered_map<int,int> net_node_to_pin;
        auto& net_node_to_pin = rr_sink_node_to_pin[net_id];
        auto& net_lower_bound_connection_delay = lower_bound_connection_delay[net_id];
        auto& net_forcible_reroute_connection_flag = forcible_reroute_connection_flag[net_id];

        unsigned int num_pins = cluster_ctx.clb_nlist.net_pins(net_id).size();
        net_node_to_pin.reserve(num_pins - 1); // not looking up on the SOURCE pin
        net_lower_bound_connection_delay.reserve(num_pins - 1); // will be filled in after the 1st iteration's
        net_forcible_reroute_connection_flag.reserve(num_pins - 1); // all false to begin with

        for (unsigned int ipin = 1; ipin < num_pins; ++ipin) {
            // rr sink node index corresponding to this connection terminal
            auto rr_sink_node = route_ctx.net_rr_terminals[net_id][ipin];

            net_node_to_pin.insert({rr_sink_node, ipin});
            net_forcible_reroute_connection_flag.insert({rr_sink_node, false});
        }
    }
}

void Connection_based_routing_resources::convert_sink_nodes_to_net_pins(vector<int>& rr_sink_nodes) const {

    /* Turn a vector of device_ctx.rr_nodes indices, assumed to be of sinks for a net *
     * into the pin indices of the same net. */

    VTR_ASSERT(current_inet != ClusterNetId::INVALID()); // not uninitialized

    const auto& node_to_pin_mapping = rr_sink_node_to_pin[current_inet];

    for (size_t s = 0; s < rr_sink_nodes.size(); ++s) {

        auto mapping = node_to_pin_mapping.find(rr_sink_nodes[s]);
        if (mapping != node_to_pin_mapping.end()) {
            rr_sink_nodes[s] = mapping->second;
        } else {
            VTR_ASSERT_SAFE_MSG(false, "Should always expect it find a pin mapping for its own net");
        }
    }
}

void Connection_based_routing_resources::put_sink_rt_nodes_in_net_pins_lookup(const vector<t_rt_node*>& sink_rt_nodes,
        t_rt_node** rt_node_of_sink) const {

    /* Load rt_node_of_sink (which maps a PIN index to a route tree node)
     * with a vector of route tree sink nodes. */

    VTR_ASSERT(current_inet != ClusterNetId::INVALID());

    // a net specific mapping from node index to pin index
    const auto& node_to_pin_mapping = rr_sink_node_to_pin[current_inet];

    for (t_rt_node* rt_node : sink_rt_nodes) {
        auto mapping = node_to_pin_mapping.find(rt_node->inode);

        if (mapping != node_to_pin_mapping.end()) {
            rt_node_of_sink[mapping->second] = rt_node;
        } else {
            VTR_ASSERT_SAFE_MSG(false, "element should be able to find itself");
        }
    }
}

bool Connection_based_routing_resources::sanity_check_lookup() const {
    auto& cluster_ctx = g_vpr_ctx.clustering();
    auto& route_ctx = g_vpr_ctx.routing();

    for (auto net_id : cluster_ctx.clb_nlist.nets()) {
        const auto& net_node_to_pin = rr_sink_node_to_pin[net_id];

        for (auto mapping : net_node_to_pin) {
            auto sanity = net_node_to_pin.find(mapping.first);
            if (sanity == net_node_to_pin.end()) {
                vtr::printf_info("%d cannot find itself (net %lu)\n", mapping.first, size_t(net_id));
                return false;
            }
            VTR_ASSERT(route_ctx.net_rr_terminals[net_id][mapping.second] == mapping.first);
        }
    }
    return true;
}

void Connection_based_routing_resources::set_lower_bound_connection_delays(vtr::vector_map<ClusterNetId, float *> &net_delay) {

    /* Set the lower bound connection delays after first iteration, which only optimizes for timing delay.
       This will be used later to judge the optimality of a connection, with suboptimal ones being candidates
       for forced reroute */

    auto& cluster_ctx = g_vpr_ctx.clustering();

	for (auto net_id : cluster_ctx.clb_nlist.nets()) {
        auto& net_lower_bound_connection_delay = lower_bound_connection_delay[net_id];

        for (unsigned int ipin = 1; ipin < cluster_ctx.clb_nlist.net_pins(net_id).size(); ++ipin) {
            net_lower_bound_connection_delay.push_back(net_delay[net_id][ipin]);
        }
    }
}

/* Run through all non-congested connections of all nets and see if any need to be forcibly rerouted.
       The connection must satisfy all following criteria:
                    1. the connection is critical enough
                    2. the connection is suboptimal, in comparison to lower_bound_connection_delay  */
bool Connection_based_routing_resources::forcibly_reroute_connections(float max_criticality,
        std::shared_ptr<const SetupTimingInfo> timing_info,
        const ClusteredPinAtomPinsLookup& netlist_pin_lookup,
        vtr::vector_map<ClusterNetId, float *> &net_delay) {
    auto& cluster_ctx = g_vpr_ctx.clustering();
    auto& route_ctx = g_vpr_ctx.routing();

    bool any_connection_rerouted = false; // true if any connection has been marked for rerouting

    for (auto net_id : cluster_ctx.clb_nlist.nets()) {
        for (auto pin_id : cluster_ctx.clb_nlist.net_sinks(net_id)) {
            int ipin = cluster_ctx.clb_nlist.pin_net_index(pin_id);

            // rr sink node index corresponding to this connection terminal
            auto rr_sink_node = route_ctx.net_rr_terminals[net_id][ipin];

            //Clear any forced re-routing from the previuos iteration
            forcible_reroute_connection_flag[net_id][rr_sink_node] = false;


            // skip if connection is internal to a block such that SOURCE->OPIN->IPIN->SINK directly, which would have 0 time delay
            if (lower_bound_connection_delay[net_id][ipin - 1] == 0)
                continue;

            // update if more optimal connection found
            if (net_delay[net_id][ipin] < lower_bound_connection_delay[net_id][ipin - 1]) {
                lower_bound_connection_delay[net_id][ipin - 1] = net_delay[net_id][ipin];
                continue;
            }

            // skip if connection criticality is too low (not a problem connection)
            float pin_criticality = calculate_clb_net_pin_criticality(*timing_info, netlist_pin_lookup, pin_id);
            if (pin_criticality < (max_criticality * connection_criticality_tolerance))
                continue;

            // skip if connection's delay is close to optimal
            if (net_delay[net_id][ipin] < (lower_bound_connection_delay[net_id][ipin - 1] * connection_delay_optimality_tolerance))
                continue;

            forcible_reroute_connection_flag[net_id][rr_sink_node] = true;
            // note that we don't set forcible_reroute_connection_flag to false when the converse is true
            // resetting back to false will be done during tree pruning, after the sink has been legally reached
            any_connection_rerouted = true;

            profiling::mark_for_forced_reroute();
        }
    }

    // non-stable configuration if any connection has to be rerouted, otherwise stable
    return !any_connection_rerouted;
}

void Connection_based_routing_resources::clear_force_reroute_for_connection(int rr_sink_node) {
    forcible_reroute_connection_flag[current_inet][rr_sink_node] = false;
    profiling::perform_forced_reroute();
}

void Connection_based_routing_resources::clear_force_reroute_for_net() {

    VTR_ASSERT(current_inet != ClusterNetId::INVALID());

    auto& net_flags = forcible_reroute_connection_flag[current_inet];
    for (auto& force_reroute_flag : net_flags) {
        if (force_reroute_flag.second) {
            force_reroute_flag.second = false;
            profiling::perform_forced_reroute();
        }
    }
}

static OveruseInfo calculate_overuse_info() {
    auto& device_ctx = g_vpr_ctx.device();
    auto& route_ctx = g_vpr_ctx.routing();

    size_t overused_nodes = 0;
    size_t total_overuse = 0;
    size_t worst_overuse = 0;
    int inode;
    for (inode = 0; inode < device_ctx.num_rr_nodes; inode++) {
        int overuse = route_ctx.rr_node_route_inf[inode].occ() - device_ctx.rr_nodes[inode].capacity();
        if (overuse > 0) {
            overused_nodes += 1;

            total_overuse += overuse;
            worst_overuse = std::max(worst_overuse, size_t(overuse));
        }
    }
    return OveruseInfo(device_ctx.num_rr_nodes, overused_nodes, total_overuse, worst_overuse);
}

static WirelengthInfo calculate_wirelength_info() {
    auto& device_ctx = g_vpr_ctx.device();
    auto& cluster_ctx = g_vpr_ctx.clustering();

    size_t used_wirelength = 0;
    size_t available_wirelength = 0;

    for (int i = 0; i < device_ctx.num_rr_nodes; ++i) {
        if (device_ctx.rr_nodes[i].type() == CHANX || device_ctx.rr_nodes[i].type() == CHANY) {
            available_wirelength += device_ctx.rr_nodes[i].capacity() +
                    device_ctx.rr_nodes[i].xhigh() - device_ctx.rr_nodes[i].xlow() +
                    device_ctx.rr_nodes[i].yhigh() - device_ctx.rr_nodes[i].ylow();
        }
    }

	for (auto net_id : cluster_ctx.clb_nlist.nets()) {
        if (!cluster_ctx.clb_nlist.net_is_global(net_id)
                && cluster_ctx.clb_nlist.net_sinks(net_id).size() != 0) { /* Globals don't count. */
            int bends, wirelength, segments;
            get_num_bends_and_length(net_id, &bends, &wirelength, &segments);

            used_wirelength += wirelength;
        }
    }
    VTR_ASSERT(available_wirelength > 0);

    return WirelengthInfo(available_wirelength, used_wirelength);
}

static void print_route_status_header() {
    vtr::printf("---- ------ ------- ------- ------- ------- ----------------- --------------- -------- ---------- ---------- ---------- ---------- --------\n");
    vtr::printf("Iter   Time    Heap    Heap  Re-Rtd  Re-Rtd Overused RR Nodes      Wirelength      CPD       sTNS       sWNS       hTNS       hWNS Est Succ\n");
    vtr::printf("      (sec)    push     pop    Nets   Conns                                       (ns)       (ns)       (ns)       (ns)       (ns)     Iter\n");
    vtr::printf("---- ------ ------- ------- ------- ------- ----------------- --------------- -------- ---------- ---------- ---------- ---------- --------\n");
}

static void print_route_status(int itry, double elapsed_sec, const RouterStats& router_stats,
        const OveruseInfo& overuse_info, const WirelengthInfo& wirelength_info,
        std::shared_ptr<const SetupHoldTimingInfo> timing_info,
        float est_success_iteration) {

    //Iteration
    vtr::printf("%4d", itry);

    //Elapsed Time
    vtr::printf(" %6.1f", elapsed_sec);

    //Heap push/pop
    constexpr int HEAP_OP_DIGITS = 7;
    constexpr int HEAP_OP_SCI_PRECISION = 2;
    pretty_print_uint(" ", router_stats.heap_pushes, HEAP_OP_DIGITS, HEAP_OP_SCI_PRECISION);
    pretty_print_uint(" ", router_stats.heap_pops, HEAP_OP_DIGITS, HEAP_OP_SCI_PRECISION);

    //Rerouted nets
    constexpr int NET_ROUTED_DIGITS = 7;
    constexpr int NET_ROUTED_SCI_PRECISION = 2;
    pretty_print_uint(" ", router_stats.nets_routed, NET_ROUTED_DIGITS, NET_ROUTED_SCI_PRECISION);

    //Rerouted connections
    constexpr int CONN_ROUTED_DIGITS = 7;
    constexpr int CONN_ROUTED_SCI_PRECISION = 2;
    pretty_print_uint(" ", router_stats.connections_routed, CONN_ROUTED_DIGITS, CONN_ROUTED_SCI_PRECISION);

    //Overused RR nodes
    constexpr int OVERUSE_DIGITS = 7;
    constexpr int OVERUSE_SCI_PRECISION = 2;
    pretty_print_uint(" ", overuse_info.overused_nodes(), OVERUSE_DIGITS, OVERUSE_SCI_PRECISION);
    vtr::printf(" (%6.3f%)", overuse_info.overused_node_ratio()*100);

    //Wirelength
    constexpr int WL_DIGITS = 7;
    constexpr int WL_SCI_PRECISION = 2;
    pretty_print_uint(" ", wirelength_info.used_wirelength(), WL_DIGITS, WL_SCI_PRECISION);
    vtr::printf(" (%4.1f%)", wirelength_info.used_wirelength_ratio()*100);

    //CPD
    if (timing_info) {
        float cpd = timing_info->least_slack_critical_path().delay();
        vtr::printf(" %#8.3f", 1e9 * cpd);
    } else {
        vtr::printf(" %8s", "N/A");
    }

    //sTNS
    if (timing_info) {
        float sTNS = timing_info->setup_total_negative_slack();
        vtr::printf(" % #10.4g", 1e9 * sTNS);
    } else {
        vtr::printf(" %10s", "N/A");
    }

    //sWNS
    if (timing_info) {
        float sWNS = timing_info->setup_worst_negative_slack();
        vtr::printf(" % #10.3f", 1e9 * sWNS);
    } else {
        vtr::printf(" %10s", "N/A");
    }

    //hTNS
    if (timing_info) {
        float hTNS = timing_info->hold_total_negative_slack();
        vtr::printf(" % #10.4g", 1e9 * hTNS);
    } else {
        vtr::printf(" %10s", "N/A");
    }

    //hWNS
    if (timing_info) {
        float hWNS = timing_info->hold_worst_negative_slack();
        vtr::printf(" % #10.3f", 1e9 * hWNS);
    } else {
        vtr::printf(" %10s", "N/A");
    }

    //Estimated success iteration
    if (std::isnan(est_success_iteration)) {
        vtr::printf(" %8s", "N/A");
    } else {
        vtr::printf(" %8.0f", est_success_iteration);
    }

    vtr::printf("\n");

    fflush(stdout);
}

static void pretty_print_uint(const char* prefix, size_t value, int num_digits, int scientific_precision) {
    //Print as integer if it will fit in the width, other wise scientific
    if (value <= std::pow(10, num_digits) - 1) {
        //Direct
        vtr::printf("%s%*zu", prefix, num_digits, value);
    } else {
        //Scientific
        vtr::printf("%s%#*.*g", prefix, num_digits, scientific_precision, float(value));
    }
}