text:
/*
 *  nextpnr -- Next Generation Place and Route
 *
 *  Copyright (C) 2021  Symbiflow Authors
 *
 *
 *  Permission to use, copy, modify, and/or distribute this software for any
 *  purpose with or without fee is hereby granted, provided that the above
 *  copyright notice and this permission notice appear in all copies.
 *
 *  THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
 *  WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
 *  MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
 *  ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
 *  WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
 *  ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
 *  OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
 *
 */

#include "lookahead.h"

#include <boost/filesystem.hpp>
#include <boost/safe_numerics/safe_integer.hpp>
#include <capnp/message.h>
#include <capnp/serialize.h>
#include <kj/filesystem.h>
#include <kj/std/iostream.h>
#include <queue>
#include <sstream>
#include <zlib.h>

#include "context.h"
#include "flat_wire_map.h"
#include "log.h"
#include "sampler.h"
#include "scope_lock.h"

#if defined(NEXTPNR_USE_TBB)
#include <tbb/parallel_for_each.h>
#endif

NEXTPNR_NAMESPACE_BEGIN

static constexpr size_t kNumberSamples = 4;
static constexpr int32_t kMaxExploreDist = 20;

// Initial only explore with a depth of this.
static constexpr int32_t kInitialExploreDepth = 30;

struct RoutingNode
{
    WireId wire_to_expand;
    delay_t cost;
    int32_t depth;

    bool operator<(const RoutingNode &other) const { return cost < other.cost; }
};

struct PipAndCost
{
    PipId upstream_pip;
    delay_t cost_from_src;
    int32_t depth;
};

static void expand_input(const Context *ctx, WireId input_wire, HashTables::HashMap<TypeWireId, delay_t> *input_costs)
{
    HashTables::HashSet<WireId> seen;
    std::priority_queue<RoutingNode> to_expand;

    RoutingNode initial;
    initial.cost = 0;
    initial.wire_to_expand = input_wire;

    to_expand.push(initial);

    while (!to_expand.empty()) {
        RoutingNode node = to_expand.top();
        to_expand.pop();

        auto result = seen.emplace(node.wire_to_expand);
        if (!result.second) {
            // We've already done an expansion at this wire.
            continue;
        }

        for (PipId pip : ctx->getPipsUphill(node.wire_to_expand)) {
            if (ctx->is_pip_synthetic(pip)) {
                continue;
            }
            WireId new_wire = ctx->getPipSrcWire(pip);
            if (new_wire == WireId()) {
                continue;
            }

            RoutingNode next_node;
            next_node.wire_to_expand = new_wire;
            next_node.cost = node.cost + ctx->getPipDelay(pip).maxDelay() + ctx->getWireDelay(new_wire).maxDelay();

            if (ctx->is_site_port(pip)) {
                // Done with expansion, record the path if cheaper.
                // Only the first path to each wire will be the cheapest.

                // Get local tile wire at pip dest. Using getPipSrcWire may
                // return a node wire, which is not correct here.
                TypeWireId route_to;
                route_to.type = ctx->chip_info->tiles[pip.tile].type;
                route_to.index = loc_info(ctx->chip_info, pip).pip_data[pip.index].src_index;
                if (route_to.index >= 0) {
                    auto result = input_costs->emplace(route_to, next_node.cost);
                    if (!result.second && result.first->second > next_node.cost) {
                        result.first->second = next_node.cost;
                    }
                }
            } else {
                to_expand.push(next_node);
            }
        }
    }
}

static void update_site_to_site_costs(const Context *ctx, WireId first_wire,
                                      const HashTables::HashMap<WireId, PipAndCost> &best_path,
                                      HashTables::HashMap<TypeWirePair, delay_t> *site_to_site_cost)
{
    for (auto &best_pair : best_path) {
        WireId last_wire = best_pair.first;
        TypeWirePair pair;
        pair.dst = TypeWireId(ctx, last_wire);

        PipAndCost pip_and_cost = best_pair.second;
        delay_t cost_from_src = pip_and_cost.cost_from_src;

        WireId cursor;
        do {
            cursor = ctx->getPipSrcWire(pip_and_cost.upstream_pip);

            pair.src = TypeWireId(ctx, cursor);

            delay_t cost = cost_from_src;

            // Only use the delta cost from cursor to last_wire, not the full
            // cost from first_wire to last_wire.
            if (cursor != first_wire) {
                pip_and_cost = best_path.at(cursor);
                cost -= pip_and_cost.cost_from_src;
            }

            NPNR_ASSERT(cost >= 0);

            auto cost_result = site_to_site_cost->emplace(pair, cost);
            if (!cost_result.second) {
                // Update point to point cost if cheaper.
                if (cost_result.first->second > cost) {
                    cost_result.first->second = cost;
                }
            }
        } while (cursor != first_wire);
    }
}

static void expand_output(const Context *ctx, WireId output_wire, Lookahead::OutputSiteWireCost *output_cost,
                          HashTables::HashMap<TypeWirePair, delay_t> *site_to_site_cost)
{
    HashTables::HashSet<WireId> seen;
    std::priority_queue<RoutingNode> to_expand;

    RoutingNode initial;
    initial.cost = 0;
    initial.wire_to_expand = output_wire;

    to_expand.push(initial);

    HashTables::HashMap<WireId, PipAndCost> best_path;

    while (!to_expand.empty()) {
        RoutingNode node = to_expand.top();
        to_expand.pop();

        auto result = seen.emplace(node.wire_to_expand);
        if (!result.second) {
            // We've already done an expansion at this wire.
            continue;
        }

        for (PipId pip : ctx->getPipsDownhill(node.wire_to_expand)) {
            if (ctx->is_pip_synthetic(pip)) {
                continue;
            }
            WireId new_wire = ctx->getPipDstWire(pip);
            if (new_wire == WireId()) {
                continue;
            }

            RoutingNode next_node;
            next_node.wire_to_expand = new_wire;
            next_node.cost = node.cost + ctx->getPipDelay(pip).maxDelay() + ctx->getWireDelay(new_wire).maxDelay();

            if (ctx->is_site_port(pip)) {
                // Done with expansion, record the path if cheaper.

                // Get local tile wire at pip dest. Using getPipDstWire may
                // return a node wire, which is not correct here.
                TypeWireId route_from;
                route_from.type = ctx->chip_info->tiles[pip.tile].type;
                route_from.index = loc_info(ctx->chip_info, pip).pip_data[pip.index].dst_index;
                if (route_from.index != -1 && output_cost != nullptr && next_node.cost < output_cost->cost) {
                    output_cost->cost = next_node.cost;
                    output_cost->cheapest_route_from = route_from;
                }
            } else {
                to_expand.push(next_node);

                auto result = best_path.emplace(new_wire, PipAndCost());
                PipAndCost &pip_and_cost = result.first->second;
                if (result.second || pip_and_cost.cost_from_src > next_node.cost) {
                    pip_and_cost.upstream_pip = pip;
                    pip_and_cost.cost_from_src = next_node.cost;
                }
            }
        }
    }

    update_site_to_site_costs(ctx, output_wire, best_path, site_to_site_cost);
}

static void expand_input_type(const Context *ctx, DeterministicRNG *rng, const Sampler &tiles_of_type,
                              TypeWireId input_wire, std::vector<Lookahead::InputSiteWireCost> *input_costs)
{
    HashTables::HashMap<TypeWireId, delay_t> input_costs_map;
    for (size_t region = 0; region < tiles_of_type.number_of_regions(); ++region) {
        size_t tile = tiles_of_type.get_sample_from_region(region, [rng]() -> int32_t { return rng->rng(); });

        NPNR_ASSERT(ctx->chip_info->tiles[tile].type == input_wire.type);
        WireId wire = canonical_wire(ctx->chip_info, tile, input_wire.index);

        expand_input(ctx, wire, &input_costs_map);
    }

    input_costs->clear();
    input_costs->reserve(input_costs_map.size());
    for (const auto &input_pair : input_costs_map) {
        input_costs->emplace_back();
        auto &input_cost = input_costs->back();
        input_cost.route_to = input_pair.first;
        input_cost.cost = input_pair.second;
    }
}

struct DelayStorage
{
    HashTables::HashMap<TypeWirePair, HashTables::HashMap<std::pair<int32_t, int32_t>, delay_t, PairHash>> storage;
    int32_t max_explore_depth;
};

static bool has_multiple_inputs(const Context *ctx, WireId wire)
{
    size_t pip_count = 0;
    for (PipId pip : ctx->getPipsUphill(wire)) {
        (void)pip;
        pip_count += 1;
    }

    return pip_count > 1;
}

static void update_results(const Context *ctx, const FlatWireMap<PipAndCost> &best_path, WireId src_wire,
                           WireId sink_wire, DelayStorage *storage)
{
    TypeWireId src_wire_type(ctx, src_wire);

    int src_tile;
    if (src_wire.tile == -1) {
        src_tile = ctx->chip_info->nodes[src_wire.index].tile_wires[0].tile;
    } else {
        src_tile = src_wire.tile;
    }

    int32_t src_x, src_y;
    ctx->get_tile_x_y(src_tile, &src_x, &src_y);

    TypeWirePair wire_pair;
    wire_pair.src = src_wire_type;

    // The first couple wires from the site pip are usually boring, don't record
    // them.
    bool out_of_infeed = false;

    // Starting from end of result, walk backwards and record the path into
    // the delay storage.
    WireId cursor = sink_wire;
    HashTables::HashSet<WireId> seen;
    while (cursor != src_wire) {
        // No loops allowed in routing!
        auto result = seen.emplace(cursor);
        NPNR_ASSERT(result.second);

        if (!out_of_infeed && has_multiple_inputs(ctx, cursor)) {
            out_of_infeed = true;
        }

        TypeWireId dst_wire_type(ctx, cursor);
        wire_pair.dst = dst_wire_type;

        int dst_tile;
        if (cursor.tile == -1) {
            dst_tile = ctx->chip_info->nodes[cursor.index].tile_wires[0].tile;
        } else {
            dst_tile = cursor.tile;
        }
        int32_t dst_x;
        int32_t dst_y;
        ctx->get_tile_x_y(dst_tile, &dst_x, &dst_y);

        std::pair<int32_t, int32_t> dx_dy;
        dx_dy.first = dst_x - src_x;
        dx_dy.second = dst_y - src_y;

        const PipAndCost &pip_and_cost = best_path.at(cursor);
        if (out_of_infeed) {
            auto &delta_data = storage->storage[wire_pair];
            auto result2 = delta_data.emplace(dx_dy, pip_and_cost.cost_from_src);
            if (!result2.second) {
                if (result2.first->second > pip_and_cost.cost_from_src) {
                    result2.first->second = pip_and_cost.cost_from_src;
                }
            }
        }

        cursor = ctx->getPipSrcWire(pip_and_cost.upstream_pip);
    }
}

static void expand_routing_graph_from_wire(const Context *ctx, WireId first_wire, FlatWireMap<PipAndCost> *best_path,
                                           DelayStorage *storage)
{
    HashTables::HashSet<WireId> seen;
    std::priority_queue<RoutingNode> to_expand;

    int src_tile;
    if (first_wire.tile == -1) {
        src_tile = ctx->chip_info->nodes[first_wire.index].tile_wires[0].tile;
    } else {
        src_tile = first_wire.tile;
    }

    int32_t src_x, src_y;
    ctx->get_tile_x_y(src_tile, &src_x, &src_y);

    RoutingNode initial;
    initial.cost = 0;
    initial.wire_to_expand = first_wire;
    initial.depth = 0;

    to_expand.push(initial);

    best_path->clear();
    size_t skip_count = 0;

    while (!to_expand.empty()) {
        RoutingNode node = to_expand.top();
        to_expand.pop();

        auto result = seen.emplace(node.wire_to_expand);
        if (!result.second) {
            // We've already done an expansion at this wire.
            skip_count += 1;
            continue;
        }

        bool has_site_pip = false;
        for (PipId pip : ctx->getPipsDownhill(node.wire_to_expand)) {
            if (ctx->is_pip_synthetic(pip)) {
                continue;
            }

            // Don't expand edges that are site pips, but do record how we
            // got to the pip before the site pip!
            if (ctx->is_site_port(pip)) {
                has_site_pip = true;
                continue;
            }

            WireId new_wire = ctx->getPipDstWire(pip);
            if (new_wire == WireId()) {
                continue;
            }

            RoutingNode next_node;
            next_node.wire_to_expand = new_wire;
            next_node.cost = node.cost + ctx->getPipDelay(pip).maxDelay() + ctx->getWireDelay(new_wire).maxDelay();
            next_node.depth = node.depth + 1;

            // Record best path.
            PipAndCost pip_and_cost;
            pip_and_cost.upstream_pip = pip;
            pip_and_cost.cost_from_src = next_node.cost;
            pip_and_cost.depth = next_node.depth;
            auto result = best_path->emplace(new_wire, pip_and_cost);
            bool is_best_path = true;
            if (!result.second) {
                if (result.first.second->cost_from_src > next_node.cost) {
                    result.first.second->cost_from_src = next_node.cost;
                    result.first.second->upstream_pip = pip;
                    result.first.second->depth = next_node.depth;
                } else {
                    is_best_path = false;
                }
            }

            Loc dst = ctx->getPipLocation(pip);
            int32_t dst_x = dst.x;
            int32_t dst_y = dst.y;
            if (is_best_path && std::abs(dst_x - src_x) < kMaxExploreDist &&
                std::abs(dst_y - src_y) < kMaxExploreDist && next_node.depth < storage->max_explore_depth) {
                to_expand.push(next_node);
            }
        }

        if (has_site_pip) {
            update_results(ctx, *best_path, first_wire, node.wire_to_expand, storage);
        }
    }
}

static bool has_multiple_outputs(const Context *ctx, WireId wire)
{
    size_t pip_count = 0;
    for (PipId pip : ctx->getPipsDownhill(wire)) {
        (void)pip;
        pip_count += 1;
    }

    return pip_count > 1;
}

static void expand_routing_graph(const Context *ctx, DeterministicRNG *rng, const Sampler &tiles_of_type,
                                 TypeWireId wire_type, HashTables::HashSet<TypeWireSet> *types_explored,
                                 DelayStorage *storage, HashTables::HashSet<TypeWireId> *types_deferred,
                                 FlatWireMap<PipAndCost> *best_path)
{
    HashTables::HashSet<TypeWireSet> new_types_explored;

    for (size_t region = 0; region < tiles_of_type.number_of_regions(); ++region) {
        size_t tile = tiles_of_type.get_sample_from_region(region, [rng]() -> int32_t { return rng->rng(); });

        NPNR_ASSERT(ctx->chip_info->tiles[tile].type == wire_type.type);

        WireId wire = canonical_wire(ctx->chip_info, tile, wire_type.index);
        TypeWireSet wire_set(ctx, wire);

        if (!has_multiple_outputs(ctx, wire)) {
            types_deferred->emplace(wire_type);
            continue;
        }

        new_types_explored.emplace(wire_set);

        expand_routing_graph_from_wire(ctx, wire, best_path, storage);
    }

    for (const TypeWireSet &new_wire_set : new_types_explored) {
        types_explored->emplace(new_wire_set);
    }
}

static WireId follow_pip_chain(const Context *ctx, WireId wire, delay_t *delay_out)
{
    delay_t delay = 0;
    WireId cursor = wire;
    while (true) {
        WireId next;
        size_t pip_count = 0;
        delay_t next_delay = delay;
        for (PipId pip : ctx->getPipsDownhill(cursor)) {
            pip_count += 1;
            next = ctx->getPipDstWire(pip);
            next_delay += ctx->getPipDelay(pip).maxDelay() + ctx->getWireDelay(next).maxDelay();
        }

        if (pip_count > 1) {
            *delay_out = delay;
            return cursor;
        }

        if (next == WireId()) {
            return WireId();
        }

        delay = next_delay;

        cursor = next;
    }

    // Unreachable?
    NPNR_ASSERT(false);
}

static WireId follow_pip_chain_target(const Context *ctx, WireId wire, WireId target, delay_t *delay_out)
{
    delay_t delay = 0;
    WireId cursor = wire;
    while (cursor != target) {
        WireId next;
        size_t pip_count = 0;
        delay_t next_delay = delay;
        for (PipId pip : ctx->getPipsDownhill(cursor)) {
            pip_count += 1;
            next = ctx->getPipDstWire(pip);
            next_delay += ctx->getPipDelay(pip).maxDelay() + ctx->getWireDelay(next).maxDelay();
        }

        if (pip_count > 1) {
            *delay_out = delay;
            return cursor;
        }

        if (next == WireId()) {
            return WireId();
        }

        delay = next_delay;

        cursor = next;
    }

    *delay_out = delay;
    return cursor;
}

static WireId follow_pip_chain_up(const Context *ctx, WireId wire, delay_t *delay_out)
{
    delay_t delay = 0;
    WireId cursor = wire;
    while (true) {
        WireId next;
        size_t pip_count = 0;
        delay_t next_delay = delay;
        for (PipId pip : ctx->getPipsUphill(cursor)) {
            pip_count += 1;
            next = ctx->getPipSrcWire(pip);
            next_delay += ctx->getPipDelay(pip).maxDelay() + ctx->getWireDelay(next).maxDelay();
        }

        if (pip_count > 1) {
            *delay_out = delay;
            return cursor;
        }

        if (next == WireId()) {
            return WireId();
        }

        delay = next_delay;

        cursor = next;
    }

    // Unreachable?
    NPNR_ASSERT(false);
}

static void expand_deferred_routing_graph(const Context *ctx, DeterministicRNG *rng, const Sampler &tiles_of_type,
                                          TypeWireId wire_type, HashTables::HashSet<TypeWireSet> *types_explored,
                                          DelayStorage *storage, FlatWireMap<PipAndCost> *best_path)
{
    HashTables::HashSet<TypeWireSet> new_types_explored;

    for (size_t region = 0; region < tiles_of_type.number_of_regions(); ++region) {
        size_t tile = tiles_of_type.get_sample_from_region(region, [rng]() -> int32_t { return rng->rng(); });

        NPNR_ASSERT(ctx->chip_info->tiles[tile].type == wire_type.type);

        WireId wire = canonical_wire(ctx->chip_info, tile, wire_type.index);
        TypeWireSet wire_set(ctx, wire);
        if (types_explored->count(wire_set)) {
            // Check if this wire set has been expanded.
            continue;
        }

        delay_t delay;
        WireId routing_wire = follow_pip_chain(ctx, wire, &delay);

        // This wire doesn't go anywhere!
        if (routing_wire == WireId()) {
            continue;
        }

        TypeWireSet routing_wire_set(ctx, routing_wire);
        if (types_explored->count(routing_wire_set)) {
            continue;
        }

        new_types_explored.emplace(wire_set);
        expand_routing_graph_from_wire(ctx, wire, best_path, storage);
    }

    for (const TypeWireSet &new_wire_set : new_types_explored) {
        types_explored->emplace(new_wire_set);
    }
}

static void expand_output_type(const Context *ctx, DeterministicRNG *rng, const Sampler &tiles_of_type,
                               TypeWireId output_wire, Lookahead::OutputSiteWireCost *output_cost,
                               HashTables::HashMap<TypeWirePair, delay_t> *site_to_site_cost)
{
    for (size_t region = 0; region < tiles_of_type.number_of_regions(); ++region) {
        size_t tile = tiles_of_type.get_sample_from_region(region, [rng]() -> int32_t { return rng->rng(); });

        NPNR_ASSERT(ctx->chip_info->tiles[tile].type == output_wire.type);
        WireId wire = canonical_wire(ctx->chip_info, tile, output_wire.index);

        expand_output(ctx, wire, output_cost, site_to_site_cost);
    }
}

static constexpr bool kWriteLookaheadCsv = false;

void write_lookahead_csv(const Context *ctx, const DelayStorage &all_tiles_storage)
{
    FILE *lookahead_data = fopen("lookahead.csv", "w");
    NPNR_ASSERT(lookahead_data != nullptr);
    fprintf(lookahead_data, "src_type,src_wire,dest_type,dest_wire,delta_x,delta_y,delay\n");
    for (const auto &type_pair : all_tiles_storage.storage) {
        auto &src_wire_type = type_pair.first.src;
        auto &src_type_data = ctx->chip_info->tile_types[src_wire_type.type];
        IdString src_type(src_type_data.name);
        IdString src_wire(src_type_data.wire_data[src_wire_type.index].name);

        auto &dst_wire_type = type_pair.first.dst;
        auto &dst_type_data = ctx->chip_info->tile_types[dst_wire_type.type];
        IdString dst_type(dst_type_data.name);
        IdString dst_wire(dst_type_data.wire_data[dst_wire_type.index].name);

        for (const auto &delta_pair : type_pair.second) {
            fprintf(lookahead_data, "%s,%s,%s,%s,%d,%d,%d\n", src_type.c_str(ctx), src_wire.c_str(ctx),
                    dst_type.c_str(ctx), dst_wire.c_str(ctx), delta_pair.first.first, delta_pair.first.second,
                    delta_pair.second);
        }
    }

    fclose(lookahead_data);
}

// Storage for tile type expansion for lookahead.
struct ExpandLocals
{
    virtual ~ExpandLocals() {}
    const std::vector<Sampler> *tiles_of_type;
    DeterministicRNG *rng;
    FlatWireMap<PipAndCost> *best_path;
    DelayStorage *storage;
    HashTables::HashSet<TypeWireSet> *explored;
    HashTables::HashSet<TypeWireId> *deferred;

    virtual void lock() {}
    virtual void unlock() {}
    virtual void copy_back(int32_t tile_type) {}
};

// Do tile type expansion for 1 tile.
static void expand_tile_type(const Context *ctx, int32_t tile_type, ExpandLocals *locals)
{
    auto &type_data = ctx->chip_info->tile_types[tile_type];
    if (ctx->verbose) {
        ScopeLock<ExpandLocals> lock(locals);
        log_info("Expanding all wires in type %s\n", IdString(type_data.name).c_str(ctx));
    }

    auto &tile_sampler = (*locals->tiles_of_type)[tile_type];
    for (size_t wire_index = 0; wire_index < type_data.wire_data.size(); ++wire_index) {
        auto &wire_data = type_data.wire_data[wire_index];
        if (wire_data.site != -1) {
            // Skip site wires
            continue;
        }

        if (ctx->debug) {
            ScopeLock<ExpandLocals> lock(locals);
            log_info("Expanding wire %s in type %s (%d/%zu, seen %zu types, deferred %zu types)\n",
                     IdString(wire_data.name).c_str(ctx), IdString(type_data.name).c_str(ctx), tile_type,
                     ctx->chip_info->tile_types.size(), locals->explored->size(), locals->deferred->size());
        }

        TypeWireId wire;
        wire.type = tile_type;
        wire.index = wire_index;

        expand_routing_graph(ctx, locals->rng, tile_sampler, wire, locals->explored, locals->storage, locals->deferred,
                             locals->best_path);
    }

    locals->copy_back(tile_type);
}

// Function that does all tile expansions serially.
static void expand_tile_type_serial(const Context *ctx, const std::vector<int32_t> &tile_types,
                                    const std::vector<Sampler> &tiles_of_type, DeterministicRNG *rng,
                                    FlatWireMap<PipAndCost> *best_path, DelayStorage *storage,
                                    HashTables::HashSet<TypeWireSet> *explored,
                                    HashTables::HashSet<TypeWireId> *deferred, HashTables::HashSet<int32_t> *tiles_left)
{

    for (int32_t tile_type : tile_types) {
        ExpandLocals locals;

        locals.tiles_of_type = &tiles_of_type;
        locals.rng = rng;
        locals.best_path = best_path;
        locals.storage = storage;
        locals.explored = explored;
        expand_tile_type(ctx, tile_type, &locals);

        NPNR_ASSERT(tiles_left->erase(tile_type) == 1);
    }

    NPNR_ASSERT(tiles_left->empty());
}

// Additional storage for doing tile type expansion in parallel.
struct TbbExpandLocals : public ExpandLocals
{
    const Context *ctx;
    std::mutex *all_costs_mutex;

    DelayStorage *all_tiles_storage;
    HashTables::HashSet<TypeWireSet> *types_explored;
    HashTables::HashSet<TypeWireId> *types_deferred;
    HashTables::HashSet<int32_t> *tiles_left;

    void lock() override { all_costs_mutex->lock(); }

    void unlock() override { all_costs_mutex->unlock(); }

    void copy_back(int32_t tile_type) override
    {
        ScopeLock<TbbExpandLocals> locker(this);

        auto &type_data = ctx->chip_info->tile_types[tile_type];

        // Copy per tile data by to over all data structures.
        if (ctx->verbose) {
            log_info("Expanded all wires in type %s, merging data back\n", IdString(type_data.name).c_str(ctx));
            log_info("Testing %zu wires, saw %zu types, deferred %zu types\n", type_data.wire_data.size(),
                     explored->size(), deferred->size());
        }

        // Copy cheapest explored paths back to all_tiles_storage.
        for (const auto &type_pair : storage->storage) {
            auto &type_pair_data = all_tiles_storage->storage[type_pair.first];
            for (const auto &delta_pair : type_pair.second) {
                // See if this dx/dy already has data.
                auto result = type_pair_data.emplace(delta_pair.first, delta_pair.second);
                if (!result.second) {
                    // This was already in the map, check if this new result is
                    // better
                    if (delta_pair.second < result.first->second) {
                        result.first->second = delta_pair.second;
                    }
                }
            }
        }

        // Update explored and deferred sets.
        for (auto &key : *explored) {
            types_explored->emplace(key);
        }
        for (auto &key : *deferred) {
            types_deferred->emplace(key);
        }

        NPNR_ASSERT(tiles_left->erase(tile_type));

        if (ctx->verbose) {
            log_info("Done merging data from type %s, %zu tiles left\n", IdString(type_data.name).c_str(ctx),
                     tiles_left->size());
        }
    }
};

// Wrapper method used if running expansion in parallel.
//
// expand_tile_type is invoked using thread local data, and then afterwards
// the data is joined with the global data.
static void expand_tile_type_parallel(const Context *ctx, int32_t tile_type, const std::vector<Sampler> &tiles_of_type,
                                      DeterministicRNG *rng, std::mutex *all_costs_mutex,
                                      DelayStorage *all_tiles_storage, HashTables::HashSet<TypeWireSet> *types_explored,
                                      HashTables::HashSet<TypeWireId> *types_deferred,
                                      HashTables::HashSet<int32_t> *tiles_left)
{
    TbbExpandLocals locals;

    DeterministicRNG rng_copy = *rng;
    FlatWireMap<PipAndCost> best_path(ctx);
    HashTables::HashSet<TypeWireSet> explored;
    HashTables::HashSet<TypeWireId> deferred;
    DelayStorage storage;
    storage.max_explore_depth = all_tiles_storage->max_explore_depth;

    locals.tiles_of_type = &tiles_of_type;
    locals.rng = &rng_copy;
    locals.best_path = &best_path;
    locals.storage = &storage;
    locals.explored = &explored;
    locals.deferred = &deferred;

    locals.ctx = ctx;
    locals.all_costs_mutex = all_costs_mutex;
    locals.all_tiles_storage = all_tiles_storage;
    locals.types_explored = types_explored;
    locals.types_deferred = types_deferred;
    locals.tiles_left = tiles_left;

    expand_tile_type(ctx, tile_type, &locals);
}

void Lookahead::build_lookahead(const Context *ctx, DeterministicRNG *rng)
{
    auto start = std::chrono::high_resolution_clock::now();

    if (ctx->verbose) {
        log_info("Building lookahead, first gathering input and output site wires\n");
    }

    HashTables::HashSet<TypeWireId> input_site_ports;
    for (BelId bel : ctx->getBels()) {
        const auto &bel_data = bel_info(ctx->chip_info, bel);

        for (IdString pin : ctx->getBelPins(bel)) {
            WireId pin_wire = ctx->getBelPinWire(bel, pin);
            if (pin_wire == WireId()) {
                continue;
            }

            PortType type = ctx->getBelPinType(bel, pin);

            if (type == PORT_IN && bel_data.category == BEL_CATEGORY_LOGIC) {
                input_site_wires.emplace(TypeWireId(ctx, pin_wire), std::vector<InputSiteWireCost>());
            } else if (type == PORT_OUT && bel_data.category == BEL_CATEGORY_LOGIC) {
                output_site_wires.emplace(TypeWireId(ctx, pin_wire), OutputSiteWireCost());
            } else if (type == PORT_OUT && bel_data.category == BEL_CATEGORY_SITE_PORT) {
                input_site_ports.emplace(TypeWireId(ctx, pin_wire));
            }
        }
    }

    if (ctx->verbose) {
        log_info("Have %zu input and %zu output site wire types. Creating tile type samplers\n",
                 input_site_wires.size(), output_site_wires.size());
    }

    std::vector<Sampler> tiles_of_type;
    tiles_of_type.resize(ctx->chip_info->tile_types.ssize());

    std::vector<size_t> indicies;
    std::vector<std::pair<int32_t, int32_t>> xys;
    indicies.reserve(ctx->chip_info->tiles.size());
    xys.reserve(ctx->chip_info->tiles.size());

    for (int32_t tile_type = 0; tile_type < ctx->chip_info->tile_types.ssize(); ++tile_type) {
        indicies.clear();
        xys.clear();

        for (size_t tile = 0; tile < ctx->chip_info->tiles.size(); ++tile) {
            if (ctx->chip_info->tiles[tile].type != tile_type) {
                continue;
            }

            std::pair<size_t, size_t> xy;
            ctx->get_tile_x_y(tile, &xy.first, &xy.second);

            indicies.push_back(tile);
            xys.push_back(xy);
        }

        auto &tile_sampler = tiles_of_type[tile_type];
        tile_sampler.divide_samples(kNumberSamples, xys);

        // Remap Sampler::indicies from 0 to number of tiles of type to
        // absolute tile indicies.
        for (size_t i = 0; i < indicies.size(); ++i) {
            tile_sampler.indicies[i] = indicies[tile_sampler.indicies[i]];
        }
    }

    if (ctx->verbose) {
        log_info("Expanding input site wires\n");
    }

    // Expand backwards from each input site wire to find the cheapest
    // non-site wire.
    for (auto &input_pair : input_site_wires) {
        expand_input_type(ctx, rng, tiles_of_type[input_pair.first.type], input_pair.first, &input_pair.second);
    }

    if (ctx->verbose) {
        log_info("Expanding output site wires\n");
    }

    // Expand forward from each output site wire to find the cheapest
    // non-site wire.
    for (auto &output_pair : output_site_wires) {
        output_pair.second.cost = std::numeric_limits<delay_t>::max();
        expand_output_type(ctx, rng, tiles_of_type[output_pair.first.type], output_pair.first, &output_pair.second,
                           &site_to_site_cost);
    }
    for (TypeWireId input_site_port : input_site_ports) {
        expand_output_type(ctx, rng, tiles_of_type[input_site_port.type], input_site_port, nullptr, &site_to_site_cost);
    }

    if (ctx->verbose) {
        log_info("Expanding all wire types\n");
    }

    DelayStorage all_tiles_storage;
    all_tiles_storage.max_explore_depth = kInitialExploreDepth;

    // These are wire types that have been explored.
    HashTables::HashSet<TypeWireSet> types_explored;

    // These are wire types that have been deferred because they are trival
    // copies of another wire type.  These can be cheaply computed after the
    // graph has been explored.
    HashTables::HashSet<TypeWireId> types_deferred;

    std::vector<int32_t> tile_types;
    HashTables::HashSet<int32_t> tiles_left;
    tile_types.reserve(ctx->chip_info->tile_types.size());
    for (int32_t tile_type = 0; tile_type < ctx->chip_info->tile_types.ssize(); ++tile_type) {
        tile_types.push_back(tile_type);
        tiles_left.emplace(tile_type);
    }

    FlatWireMap<PipAndCost> best_path(ctx);

    // Walk each tile type, and expand all non-site wires in the tile.
    // Wires that are nodes will expand as if the node type is the first node
    // in the wire.
    //
    // Wires that only have 1 output pip are deferred until the next loop,
    // because generally those wires will get explored via another wire.
    // The deferred will be expanded if this assumption doesn't hold.
    bool expand_serially = true;
#if defined(NEXTPNR_USE_TBB) // Run parallely
    {
        std::mutex all_costs_mutex;

        expand_serially = false;
        tbb::parallel_for_each(tile_types, [&](int32_t tile_type) {
            expand_tile_type_parallel(ctx, tile_type, tiles_of_type, rng, &all_costs_mutex, &all_tiles_storage,
                                      &types_explored, &types_deferred, &tiles_left);
        });
    }
#else
    // Supress warning that expand_tile_type_parallel if not running in
    // parallel.
    (void)expand_tile_type_parallel;
#endif
    if (expand_serially) {
        expand_tile_type_serial(ctx, tile_types, tiles_of_type, rng, &best_path, &all_tiles_storage, &types_explored,
                                &types_deferred, &tiles_left);
    }

    // Check to see if deferred wire types were expanded.  If they were not
    // expanded, expand them now.  If they were expanded, copy_types is
    // populated with the wire types that can just copy the relevant data from
    // another wire type.
    for (TypeWireId wire_type : types_deferred) {
        auto &type_data = ctx->chip_info->tile_types[wire_type.type];
        auto &tile_sampler = tiles_of_type[wire_type.type];
        auto &wire_data = type_data.wire_data[wire_type.index];

        if (ctx->verbose) {
            log_info("Expanding deferred wire %s in type %s (seen %zu types)\n", IdString(wire_data.name).c_str(ctx),
                     IdString(type_data.name).c_str(ctx), types_explored.size());
        }

        expand_deferred_routing_graph(ctx, rng, tile_sampler, wire_type, &types_explored, &all_tiles_storage,
                                      &best_path);
    }

    auto end = std::chrono::high_resolution_clock::now();
    if (ctx->verbose) {
        log_info("Done with expansion, dt %02fs\n", std::chrono::duration<float>(end - start).count());
    }

    if (kWriteLookaheadCsv) {
        write_lookahead_csv(ctx, all_tiles_storage);
        end = std::chrono::high_resolution_clock::now();
        if (ctx->verbose) {
            log_info("Done writing data to disk, dt %02fs\n", std::chrono::duration<float>(end - start).count());
        }
    }

#if defined(NEXTPNR_USE_TBB) // Run parallely
    tbb::parallel_for_each(
            all_tiles_storage.storage,
            [&](const std::pair<TypeWirePair, HashTables::HashMap<std::pair<int32_t, int32_t>, delay_t, PairHash>>
                        &type_pair) {
#else
    for (const auto &type_pair : all_tiles_storage.storage) {
#endif
                cost_map.set_cost_map(ctx, type_pair.first, type_pair.second);
#if defined(NEXTPNR_USE_TBB) // Run parallely
            });
#else
    }
#endif

    end = std::chrono::high_resolution_clock::now();
    if (ctx->verbose) {
        log_info("build_lookahead time %.02fs\n", std::chrono::duration<float>(end - start).count());
    }
}

constexpr static bool kUseGzipForLookahead = false;

static void write_message(::capnp::MallocMessageBuilder &message, const std::string &filename)
{
    kj::Array<capnp::word> words = messageToFlatArray(message);
    kj::ArrayPtr<kj::byte> bytes = words.asBytes();

    boost::filesystem::path temp = boost::filesystem::unique_path();
    log_info("Writing tempfile to %s\n", temp.c_str());

    if (kUseGzipForLookahead) {
        gzFile file = gzopen(temp.c_str(), "w");
        NPNR_ASSERT(file != Z_NULL);

        size_t bytes_written = 0;
        int result;
        while (bytes_written < bytes.size()) {
            size_t bytes_remaining = bytes.size() - bytes_written;
            size_t bytes_to_write = bytes_remaining;
            if (bytes_to_write >= std::numeric_limits<int>::max()) {
                bytes_to_write = std::numeric_limits<int>::max();
            }
            result = gzwrite(file, &bytes[0] + bytes_written, bytes_to_write);
            if (result < 0) {
                break;
            }

            bytes_written += result;
        }

        int error;
        std::string error_str;
        if (result < 0) {
            error_str.assign(gzerror(file, &error));
        }
        NPNR_ASSERT(gzclose(file) == Z_OK);
        if (bytes_written != bytes.size()) {
            // Remove failed writes before reporting error.
            boost::filesystem::remove(temp);
        }

        if (result < 0) {
            log_error("Failed to write lookahead, error from gzip %s\n", error_str.c_str());
        } else {
            if (bytes_written != bytes.size()) {
                log_error("Failed to write lookahead, wrote %d bytes, had %zu bytes\n", result, bytes.size());
            } else {
                // Written, move file into place
                boost::filesystem::rename(temp, filename);
            }
        }
    } else {
        {
            kj::Own<kj::Filesystem> fs = kj::newDiskFilesystem();

            auto path = kj::Path::parse(temp);
            auto file = fs->getCurrent().openFile(path, kj::WriteMode::CREATE);
            file->writeAll(bytes);
        }

        boost::filesystem::rename(temp, filename);
    }
}

bool Lookahead::read_lookahead(const std::string &chipdb_hash, const std::string &filename)
{
    capnp::ReaderOptions reader_options;
    reader_options.traversalLimitInWords = 32llu * 1024llu * 1024llu * 1024llu;

    if (kUseGzipForLookahead) {
        gzFile file = gzopen(filename.c_str(), "r");
        if (file == Z_NULL) {
            return false;
        }

        std::vector<uint8_t> output_data;
        output_data.resize(4096);
        std::stringstream sstream(std::ios_base::in | std::ios_base::out | std::ios_base::binary);
        while (true) {
            int ret = gzread(file, output_data.data(), output_data.size());
            NPNR_ASSERT(ret >= 0);
            if (ret > 0) {
                sstream.write((const char *)output_data.data(), ret);
                NPNR_ASSERT(sstream);
            } else {
                NPNR_ASSERT(ret == 0);
                int error;
                gzerror(file, &error);
                NPNR_ASSERT(error == Z_OK);
                break;
            }
        }

        NPNR_ASSERT(gzclose(file) == Z_OK);

        sstream.seekg(0);
        kj::std::StdInputStream istream(sstream);
        capnp::InputStreamMessageReader message_reader(istream, reader_options);

        lookahead_storage::Lookahead::Reader lookahead = message_reader.getRoot<lookahead_storage::Lookahead>();
        return from_reader(chipdb_hash, lookahead);
    } else {
        boost::iostreams::mapped_file_source file;
        try {
            file.open(filename.c_str());
        } catch (std::ios_base::failure &fail) {
            return false;
        }

        if (!file.is_open()) {
            return false;
        }

        const char *data = reinterpret_cast<const char *>(file.data());
        const kj::ArrayPtr<const ::capnp::word> words =
                kj::arrayPtr(reinterpret_cast<const ::capnp::word *>(data), file.size() / sizeof(::capnp::word));
        ::capnp::FlatArrayMessageReader reader(words, reader_options);
        lookahead_storage::Lookahead::Reader lookahead = reader.getRoot<lookahead_storage::Lookahead>();
        return from_reader(chipdb_hash, lookahead);
    }
}

void Lookahead::write_lookahead(const std::string &chipdb_hash, const std::string &file) const
{
    ::capnp::MallocMessageBuilder message;

    lookahead_storage::Lookahead::Builder lookahead = message.initRoot<lookahead_storage::Lookahead>();
    to_builder(chipdb_hash, lookahead);
    write_message(message, file);
}

void Lookahead::init(const Context *ctx, DeterministicRNG *rng)
{
    std::string lookahead_filename;
    if (kUseGzipForLookahead) {
        lookahead_filename = ctx->args.chipdb + ".lookahead.tgz";
    } else {
        lookahead_filename = ctx->args.chipdb + ".lookahead";
    }

    std::string chipdb_hash = ctx->get_chipdb_hash();

    if (ctx->args.rebuild_lookahead || !read_lookahead(chipdb_hash, lookahead_filename)) {
        build_lookahead(ctx, rng);
        if (!ctx->args.dont_write_lookahead) {
            write_lookahead(chipdb_hash, lookahead_filename);
        }
    }
}

static bool safe_add_i32(int32_t a, int32_t b, int32_t *out)
{
#if defined(__GNUG__) || defined(__clang__)
    // GCC and clang have had __builtin_add_overflow for a while.
    return !__builtin_add_overflow(a, b, out);
#else
    // MSVC and other don't have an intrinsic.  Emit some more code.
    bool safe_to_add;
    if (b < 0) {
        safe_to_add = a >= std::numeric_limits<int32_t>::min() - b;
    } else {
        safe_to_add = a <= std::numeric_limits<int32_t>::max() - b;
    }
    if (!safe_to_add) {
        return false;
    }
    *out = a + b;
    return true;
#endif
}

static void saturating_incr(int32_t *acc, int32_t value)
{
    if (!safe_add_i32(*acc, value, acc)) {
        if (value > 0) {
            *acc = std::numeric_limits<int32_t>::max();
        } else {
            *acc = std::numeric_limits<int32_t>::min();
        }
    }
}

#define DEBUG_LOOKUP

delay_t Lookahead::estimateDelay(const Context *ctx, WireId src, WireId dst) const
{
#ifdef DEBUG_LOOKUP
    if (ctx->debug) {
        log_info("Looking up %s to %s\n", ctx->nameOfWire(src), ctx->nameOfWire(dst));
    }
#endif
    delay_t delay = 0;

    // Follow chain down, chasing wires with only 1 pip.  Stop if dst is
    // reached.
    WireId orig_src = src;
    src = follow_pip_chain_target(ctx, src, dst, &delay);
    NPNR_ASSERT(delay >= 0);
    if (src == WireId()) {
        // This src wire is a dead end, tell router to avoid it!
#ifdef DEBUG_LOOKUP
        if (ctx->debug) {
            log_info("Source %s is a dead end!\n", ctx->nameOfWire(orig_src));
        }
#endif
        return std::numeric_limits<delay_t>::max();
    }

#ifdef DEBUG_LOOKUP
    if (ctx->debug && src != orig_src) {
        log_info("Moving src from %s to %s, delay = %d\n", ctx->nameOfWire(orig_src), ctx->nameOfWire(src), delay);
    }
#endif

    if (src == dst) {
        // Reached target already, done!
        return delay;
    }

    if (ctx->is_same_site(src, dst)) {
        // Check for site to site direct path.
        TypeWirePair pair;

        TypeWireId src_type(ctx, src);
        pair.src = src_type;

        TypeWireId dst_type(ctx, dst);
        pair.dst = dst_type;

        auto iter = site_to_site_cost.find(pair);
        if (iter != site_to_site_cost.end()) {
            NPNR_ASSERT(iter->second >= 0);
            saturating_incr(&delay, iter->second);
#ifdef DEBUG_LOOKUP
            if (ctx->debug) {
                log_info("Found site to site direct path %s -> %s = %d\n", ctx->nameOfWire(src), ctx->nameOfWire(dst),
                         delay);
            }
#endif
            return delay;
        }
    }

    // At this point we know that the routing interconnect is needed, or
    // the pair is unreachable.
    orig_src = src;
    TypeWireId src_type(ctx, src);

    // Find the first routing wire from the src_type.
    auto src_iter = output_site_wires.find(src_type);
    if (src_iter != output_site_wires.end()) {
        NPNR_ASSERT(src_iter->second.cost >= 0);
        saturating_incr(&delay, src_iter->second.cost);
        src_type = src_iter->second.cheapest_route_from;

        src = canonical_wire(ctx->chip_info, src.tile, src_type.index);
#ifdef DEBUG_LOOKUP
        if (ctx->debug) {
            log_info("Moving src from %s to %s, delay = %d\n", ctx->nameOfWire(orig_src), ctx->nameOfWire(src), delay);
        }
#endif
    }

    // Make sure that the new wire is in the routing graph.
    if (ctx->is_wire_in_site(src)) {
#ifdef DEBUG_LOOKUP
        // We've already tested for direct site to site routing, if src cannot
        // reach outside of the routing network, this path is impossible.
        if (ctx->debug) {
            log_warning("Failed to reach routing network for src %s, got to %s\n", ctx->nameOfWire(orig_src),
                        ctx->nameOfWire(src));
        }
#endif
        return std::numeric_limits<delay_t>::max();
    }

    if (src == dst) {
        // Reached target already, done!
        return delay;
    }

    // Find the first routing wire that reaches dst_type.
    WireId orig_dst = dst;
    TypeWireId dst_type(ctx, dst);

    auto dst_iter = input_site_wires.find(dst_type);
    if (dst_iter == input_site_wires.end()) {
        // dst_type isn't an input site wire, just add point to point delay.
        auto &dst_data = ctx->wire_info(dst);
        if (dst_data.site != -1) {
#ifdef DEBUG_LOOKUP
            // We've already tested for direct site to site routing, if dst cannot
            // be reached from the routing network, this path is impossible.
            if (ctx->debug) {
                log_warning("Failed to reach routing network for dst %s, got to %s\n", ctx->nameOfWire(orig_dst),
                            ctx->nameOfWire(dst));
            }
#endif
            return std::numeric_limits<delay_t>::max();
        }

        // Follow chain up
        WireId orig_dst = dst;
        (void)orig_dst;

        delay_t chain_delay;
        dst = follow_pip_chain_up(ctx, dst, &chain_delay);
        NPNR_ASSERT(chain_delay >= 0);
        saturating_incr(&delay, chain_delay);
#ifdef DEBUG_LOOKUP
        if (ctx->debug && dst != orig_dst) {
            log_info("Moving dst from %s to %s, delay = %d\n", ctx->nameOfWire(orig_dst), ctx->nameOfWire(dst), delay);
        }
#endif

        if (src == dst) {
            // Reached target already, done!
            return delay;
        }

        // Both src and dst are in the routing graph, lookup approx cost to go
        // from src to dst.
        int32_t delay_from_map = cost_map.get_delay(ctx, src, dst);
        NPNR_ASSERT(delay_from_map >= 0);
        saturating_incr(&delay, delay_from_map);

#ifdef DEBUG_LOOKUP
        if (ctx->debug) {
            log_info("Final delay = %d\n", delay);
        }
#endif

        return delay;
    } else {
        // dst_type is an input site wire, try each possible routing path.
        delay_t base_delay = delay;
        delay_t cheapest_path = std::numeric_limits<delay_t>::max();

        for (const InputSiteWireCost &input_cost : dst_iter->second) {
            dst = orig_dst;
            delay = base_delay;

            NPNR_ASSERT(input_cost.cost >= 0);
            saturating_incr(&delay, input_cost.cost);
            dst_type = input_cost.route_to;

            NPNR_ASSERT(dst_type.index != -1);
            dst = canonical_wire(ctx->chip_info, dst.tile, dst_type.index);
            NPNR_ASSERT(dst != WireId());

#ifdef DEBUG_LOOKUP
            if (ctx->debug) {
                log_info("Moving dst from %s to %s, delay = %d\n", ctx->nameOfWire(orig_dst), ctx->nameOfWire(dst),
                         delay);
            }
#endif

            if (dst == src) {
#ifdef DEBUG_LOOKUP
                if (ctx->debug) {
                    log_info("Possible delay = %d\n", delay);
                }
#endif
                // Reached target already, done!
                cheapest_path = std::min(delay, cheapest_path);
                continue;
            }

            auto &dst_data = ctx->wire_info(dst);
            if (dst_data.site != -1) {
#ifdef DEBUG_LOOKUP
                // We've already tested for direct site to site routing, if dst cannot
                // be reached from the routing network, this path is impossible.
                if (ctx->debug) {
                    log_warning("Failed to reach routing network for dst %s, got to %s\n", ctx->nameOfWire(orig_dst),
                                ctx->nameOfWire(dst));
                }
#endif
                continue;
            }

            // Follow chain up
            WireId orig_dst = dst;
            (void)orig_dst;

            delay_t chain_delay;
            dst = follow_pip_chain_up(ctx, dst, &chain_delay);
            NPNR_ASSERT(chain_delay >= 0);
            saturating_incr(&delay, chain_delay);
#ifdef DEBUG_LOOKUP
            if (ctx->debug && dst != orig_dst) {
                log_info("Moving dst from %s to %s, delay = %d\n", ctx->nameOfWire(orig_dst), ctx->nameOfWire(dst),
                         delay);
            }
#endif

            if (dst == WireId()) {
                // This dst wire is a dead end, don't examine it!
#ifdef DEBUG_LOOKUP
                if (ctx->debug) {
                    log_info("Dest %s is a dead end!\n", ctx->nameOfWire(dst));
                }
#endif
                continue;
            }

            if (src == dst) {
#ifdef DEBUG_LOOKUP
                if (ctx->debug) {
                    log_info("Possible delay = %d\n", delay);
                }
#endif
                // Reached target already, done!
                cheapest_path = std::min(delay, cheapest_path);
                continue;
            }

            // Both src and dst are in the routing graph, lookup approx cost to go
            // from src to dst.
            int32_t delay_from_map = cost_map.get_delay(ctx, src, dst);
            NPNR_ASSERT(delay_from_map >= 0);
            saturating_incr(&delay, delay_from_map);
            cheapest_path = std::min(delay, cheapest_path);
#ifdef DEBUG_LOOKUP
            if (ctx->debug) {
                log_info("Possible delay = %d\n", delay);
            }
#endif
        }

#ifdef DEBUG_LOOKUP
        if (ctx->debug) {
            log_info("Final delay = %d\n", delay);
        }
#endif

        return cheapest_path;
    }
}

bool Lookahead::from_reader(const std::string &chipdb_hash, lookahead_storage::Lookahead::Reader reader)
{
    std::string expected_hash = reader.getChipdbHash();
    if (chipdb_hash != expected_hash) {
        return false;
    }

    input_site_wires.clear();
    output_site_wires.clear();
    site_to_site_cost.clear();

    for (auto input_reader : reader.getInputSiteWires()) {
        TypeWireId key(input_reader.getKey());

        auto result = input_site_wires.emplace(key, std::vector<InputSiteWireCost>());
        NPNR_ASSERT(result.second);
        std::vector<InputSiteWireCost> &costs = result.first->second;
        auto value = input_reader.getValue();
        costs.reserve(value.size());
        for (auto cost : value) {
            costs.emplace_back(InputSiteWireCost{TypeWireId(cost.getRouteTo()), cost.getCost()});
        }
    }

    for (auto output_reader : reader.getOutputSiteWires()) {
        TypeWireId key(output_reader.getKey());

        auto result = output_site_wires.emplace(
                key, OutputSiteWireCost{TypeWireId(output_reader.getCheapestRouteFrom()), output_reader.getCost()});
        NPNR_ASSERT(result.second);
    }

    for (auto site_to_site_reader : reader.getSiteToSiteCost()) {
        TypeWirePair key(site_to_site_reader.getKey());
        auto result = site_to_site_cost.emplace(key, site_to_site_reader.getCost());
        NPNR_ASSERT(result.second);
    }

    cost_map.from_reader(reader.getCostMap());

    return true;
}

void Lookahead::to_builder(const std::string &chipdb_hash, lookahead_storage::Lookahead::Builder builder) const
{
    builder.setChipdbHash(chipdb_hash);

    auto input_out = builder.initInputSiteWires(input_site_wires.size());
    auto in = input_site_wires.begin();
    for (auto out = input_out.begin(); out != input_out.end(); ++out, ++in) {
        NPNR_ASSERT(in != input_site_wires.end());

        const TypeWireId &key = in->first;
        key.to_builder(out->getKey());

        const std::vector<InputSiteWireCost> &costs = in->second;
        auto value = out->initValue(costs.size());

        auto value_in = costs.begin();
        for (auto value_out = value.begin(); value_out != value.end(); ++value_out, ++value_in) {
            value_in->route_to.to_builder(value_out->getRouteTo());
            value_out->setCost(value_in->cost);
        }
    }

    auto output_out = builder.initOutputSiteWires(output_site_wires.size());
    auto out = output_site_wires.begin();
    for (auto out2 = output_out.begin(); out2 != output_out.end(); ++out, ++out2) {
        NPNR_ASSERT(out != output_site_wires.end());

        const TypeWireId &key = out->first;
        key.to_builder(out2->getKey());

        const TypeWireId &cheapest_route_from = out->second.cheapest_route_from;
        cheapest_route_from.to_builder(out2->getCheapestRouteFrom());

        out2->setCost(out->second.cost);
    }

    auto site_out = builder.initSiteToSiteCost(site_to_site_cost.size());
    auto site = site_to_site_cost.begin();
    for (auto out2 = site_out.begin(); out2 != site_out.end(); ++out2, ++site) {
        NPNR_ASSERT(site != site_to_site_cost.end());

        const TypeWirePair &key = site->first;
        key.to_builder(out2->getKey());
        out2->setCost(site->second);
    }

    cost_map.to_builder(builder.getCostMap());
}

NEXTPNR_NAMESPACE_END

ext: cc

max_issues_repo_name: gatecat/nextpnr

max_forks_repo_name: timvideos/nextpnr


text:
// MIT License
//
// Copyright (c) 2020 Lennart Braun
//
// Permission is hereby granted, free of charge, to any person obtaining a copy
// of this software and associated documentation files (the "Software"), to deal
// in the Software without restriction, including without limitation the rights
// to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
// copies of the Software, and to permit persons to whom the Software is
// furnished to do so, subject to the following conditions:
//
// The above copyright notice and this permission notice shall be included in all
// copies or substantial portions of the Software.
//
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
// OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
// SOFTWARE.

#include "linear_algebra.h"

#include <cassert>

#include <Eigen/Core>
#include <unsupported/Eigen/CXX11/Tensor>

#include "tensor/tensor_op.h"

namespace MOTION {

template <typename T>
void matrix_multiply(std::size_t dim_l, std::size_t dim_m, std::size_t dim_n, const T* A,
                     const T* B, T* output) {
  using MatrixType = Eigen::Matrix<T, Eigen::Dynamic, Eigen::Dynamic, Eigen::RowMajor>;
  Eigen::Map<MatrixType> matrix_output(output, dim_l, dim_n);
  Eigen::Map<const MatrixType> matrix_A(A, dim_l, dim_m);
  Eigen::Map<const MatrixType> matrix_B(B, dim_m, dim_n);
  matrix_output = matrix_A * matrix_B;
}

template <typename T>
std::vector<T> matrix_multiply(std::size_t dim_l, std::size_t dim_m, std::size_t dim_n,
                               const std::vector<T>& A, const std::vector<T>& B) {
  assert(A.size() == dim_l * dim_m);
  assert(B.size() == dim_m * dim_n);
  std::vector<T> output(dim_l * dim_n);
  matrix_multiply(dim_l, dim_m, dim_n, A.data(), B.data(), output.data());
  return output;
}

template <typename T>
void matrix_multiply(const tensor::GemmOp& gemm_op, const T* A, const T* B, T* output) {
  using MatrixType = Eigen::Matrix<T, Eigen::Dynamic, Eigen::Dynamic, Eigen::RowMajor>;
  assert(gemm_op.verify());
  Eigen::Map<MatrixType> matrix_output(output, gemm_op.output_shape_[0], gemm_op.output_shape_[1]);
  Eigen::Map<const MatrixType> matrix_A(A, gemm_op.input_A_shape_[0], gemm_op.input_A_shape_[1]);
  Eigen::Map<const MatrixType> matrix_B(B, gemm_op.input_B_shape_[0], gemm_op.input_B_shape_[1]);

  if (gemm_op.transA_ && gemm_op.transB_) {
    matrix_output = matrix_A.transpose() * matrix_B.transpose();
  } else if (gemm_op.transA_) {
    matrix_output = matrix_A.transpose() * matrix_B;
  } else if (gemm_op.transB_) {
    matrix_output = matrix_A * matrix_B.transpose();
  } else {
    matrix_output = matrix_A * matrix_B;
  }
}

template void matrix_multiply(std::size_t, std::size_t, std::size_t, const std::uint8_t*,
                              const std::uint8_t*, std::uint8_t*);
template void matrix_multiply(std::size_t, std::size_t, std::size_t, const std::uint16_t*,
                              const std::uint16_t*, std::uint16_t*);
template void matrix_multiply(std::size_t, std::size_t, std::size_t, const std::uint32_t*,
                              const std::uint32_t*, std::uint32_t*);
template void matrix_multiply(std::size_t, std::size_t, std::size_t, const std::uint64_t*,
                              const std::uint64_t*, std::uint64_t*);
template std::vector<std::uint8_t> matrix_multiply(std::size_t, std::size_t, std::size_t,
                                                   const std::vector<std::uint8_t>&,
                                                   const std::vector<std::uint8_t>&);
template std::vector<std::uint16_t> matrix_multiply(std::size_t, std::size_t, std::size_t,
                                                    const std::vector<std::uint16_t>&,
                                                    const std::vector<std::uint16_t>&);
template std::vector<std::uint32_t> matrix_multiply(std::size_t, std::size_t, std::size_t,
                                                    const std::vector<std::uint32_t>&,
                                                    const std::vector<std::uint32_t>&);
template std::vector<std::uint64_t> matrix_multiply(std::size_t, std::size_t, std::size_t,
                                                    const std::vector<std::uint64_t>&,
                                                    const std::vector<std::uint64_t>&);
template std::vector<__uint128_t> matrix_multiply(std::size_t, std::size_t, std::size_t,
                                                  const std::vector<__uint128_t>&,
                                                  const std::vector<__uint128_t>&);
template void matrix_multiply(const tensor::GemmOp&, const std::uint8_t*, const std::uint8_t*,
                              std::uint8_t*);
template void matrix_multiply(const tensor::GemmOp&, const std::uint16_t*, const std::uint16_t*,
                              std::uint16_t*);
template void matrix_multiply(const tensor::GemmOp&, const std::uint32_t*, const std::uint32_t*,
                              std::uint32_t*);
template void matrix_multiply(const tensor::GemmOp&, const std::uint64_t*, const std::uint64_t*,
                              std::uint64_t*);
template void matrix_multiply(const tensor::GemmOp&, const __uint128_t*, const __uint128_t*,
                              __uint128_t*);

template <typename T>
void convolution(const tensor::Conv2DOp& conv_op, const T* input_buffer, const T* kernel_buffer,
                 T* output_buffer) {
  using TensorType3 = Eigen::Tensor<T, 3, Eigen::RowMajor>;
  using CTensorType3 = Eigen::Tensor<const T, 3, Eigen::RowMajor>;
  using CTensorType4 = Eigen::Tensor<const T, 4, Eigen::RowMajor>;
  assert(conv_op.verify());
  const auto& output_shape = conv_op.output_shape_;
  const auto& input_shape = conv_op.input_shape_;
  const auto& kernel_shape = conv_op.kernel_shape_;

  Eigen::TensorMap<CTensorType3> input(input_buffer, input_shape[0], input_shape[1],
                                       input_shape[2]);
  Eigen::TensorMap<CTensorType4> kernel(kernel_buffer, kernel_shape[0], kernel_shape[1],
                                        kernel_shape[2], kernel_shape[3]);
  Eigen::TensorMap<TensorType3> output(output_buffer, output_shape[0], output_shape[1],
                                       output_shape[2]);
  const std::array<Eigen::Index, 2> kernel_matrix_dimensions = {
      static_cast<Eigen::Index>(kernel_shape[1] * kernel_shape[2] * kernel_shape[3]),
      static_cast<Eigen::Index>(kernel_shape[0])};
  const std::array<Eigen::Index, 2> input_matrix_dimensions = {
      static_cast<Eigen::Index>(output_shape[1] * output_shape[2]),
      static_cast<Eigen::Index>(kernel_shape[1] * kernel_shape[2] * kernel_shape[3])};

  auto kernel_matrix =
      kernel.shuffle(std::array<int, 4>{3, 2, 1, 0}).reshape(kernel_matrix_dimensions);

  auto input_matrix =
      input.shuffle(Eigen::array<Eigen::Index, 3>{2, 1, 0})
          .extract_image_patches(kernel_shape[2], kernel_shape[3], conv_op.strides_[0],
                                 conv_op.strides_[1], conv_op.dilations_[0], conv_op.dilations_[1],
                                 1, 1, conv_op.pads_[0], conv_op.pads_[2], conv_op.pads_[1],
                                 conv_op.pads_[3], 0)
          .reshape(input_matrix_dimensions);

  const std::array<Eigen::IndexPair<Eigen::Index>, 1> contraction_dimensions = {
      Eigen::IndexPair<Eigen::Index>(1, 0)};
  auto output_matrix =
      kernel_matrix.shuffle(std::array<Eigen::Index, 2>{1, 0})
          .contract(input_matrix.shuffle(std::array<Eigen::Index, 2>{1, 0}), contraction_dimensions)
          .shuffle(std::array<Eigen::Index, 2>{1, 0});

  const std::array<Eigen::Index, 3> rev_output_dimensions = {
      output.dimension(2), output.dimension(1), output.dimension(0)};
  output =
      output_matrix.reshape(rev_output_dimensions).shuffle(Eigen::array<Eigen::Index, 3>{2, 1, 0});
}

template <typename T>
std::vector<T> convolution(const tensor::Conv2DOp& conv_op, const std::vector<T>& input_buffer,
                           const std::vector<T>& kernel_buffer) {
  assert(conv_op.verify());
  assert(input_buffer.size() == conv_op.compute_input_size());
  assert(kernel_buffer.size() == conv_op.compute_kernel_size());
  std::vector<T> output_buffer(conv_op.compute_output_size());
  convolution(conv_op, input_buffer.data(), kernel_buffer.data(), output_buffer.data());
  return output_buffer;
}

void convolution(const tensor::Conv2DOp&, const std::uint8_t*, const std::uint8_t*, std::uint8_t*);
void convolution(const tensor::Conv2DOp&, const std::uint16_t*, const std::uint16_t*,
                 std::uint16_t*);
void convolution(const tensor::Conv2DOp&, const std::uint32_t*, const std::uint32_t*,
                 std::uint32_t*);
void convolution(const tensor::Conv2DOp&, const std::uint64_t*, const std::uint64_t*,
                 std::uint64_t*);
template std::vector<std::uint8_t> convolution(const tensor::Conv2DOp&,
                                               const std::vector<std::uint8_t>&,
                                               const std::vector<std::uint8_t>&);
template std::vector<std::uint16_t> convolution(const tensor::Conv2DOp&,
                                                const std::vector<std::uint16_t>&,
                                                const std::vector<std::uint16_t>&);
template std::vector<std::uint32_t> convolution(const tensor::Conv2DOp&,
                                                const std::vector<std::uint32_t>&,
                                                const std::vector<std::uint32_t>&);
template std::vector<std::uint64_t> convolution(const tensor::Conv2DOp&,
                                                const std::vector<std::uint64_t>&,
                                                const std::vector<std::uint64_t>&);
template std::vector<__uint128_t> convolution(const tensor::Conv2DOp&,
                                              const std::vector<__uint128_t>&,
                                              const std::vector<__uint128_t>&);

template <typename T>
void sum_pool(const tensor::AveragePoolOp& avgpool_op, const T* input, T* output) {
  assert(avgpool_op.verify());
  using TensorType3C = Eigen::Tensor<const T, 3, Eigen::RowMajor>;
  using TensorType3 = Eigen::Tensor<T, 3, Eigen::RowMajor>;
  const auto in_channels = static_cast<Eigen::Index>(avgpool_op.input_shape_[0]);
  const auto in_rows = static_cast<Eigen::Index>(avgpool_op.input_shape_[1]);
  const auto in_columns = static_cast<Eigen::Index>(avgpool_op.input_shape_[2]);
  const auto out_channels = static_cast<Eigen::Index>(avgpool_op.output_shape_[0]);
  const auto out_rows = static_cast<Eigen::Index>(avgpool_op.output_shape_[1]);
  const auto out_columns = static_cast<Eigen::Index>(avgpool_op.output_shape_[2]);
  const auto kernel_rows = static_cast<Eigen::Index>(avgpool_op.kernel_shape_[0]);
  const auto kernel_columns = static_cast<Eigen::Index>(avgpool_op.kernel_shape_[1]);
  const auto stride_rows = static_cast<Eigen::Index>(avgpool_op.strides_[0]);
  const auto stride_columns = static_cast<Eigen::Index>(avgpool_op.strides_[1]);

  Eigen::TensorMap<TensorType3C> tensor_src(input, in_channels, in_rows, in_columns);
  Eigen::TensorMap<TensorType3> tensor_dst(output, out_channels, out_rows, out_columns);

  tensor_dst = tensor_src.shuffle(Eigen::array<Eigen::Index, 3>{2, 1, 0})
                   .extract_image_patches(kernel_rows, kernel_columns, stride_rows, stride_columns,
                                          1, 1, 1, 1, 0, 0, 0, 0, T(0))
                   .sum(Eigen::array<Eigen::Index, 2>{1, 2})
                   .reshape(Eigen::array<Eigen::Index, 3>{out_columns, out_rows, out_channels})
                   .shuffle(Eigen::array<Eigen::Index, 3>{2, 1, 0});
}

template void sum_pool(const tensor::AveragePoolOp&, const std::uint8_t*, std::uint8_t*);
template void sum_pool(const tensor::AveragePoolOp&, const std::uint16_t*, std::uint16_t*);
template void sum_pool(const tensor::AveragePoolOp&, const std::uint32_t*, std::uint32_t*);
template void sum_pool(const tensor::AveragePoolOp&, const std::uint64_t*, std::uint64_t*);
template void sum_pool(const tensor::AveragePoolOp&, const __uint128_t*, __uint128_t*);

}  // namespace MOTION

ext: cpp


text:
#include <iostream>

#include <boost/program_options.hpp>
#include <QApplication>

#include "sampler.hpp"
#include "tiling.hpp"
#include "gui/window.hpp"

namespace boostPO = boost::program_options;

void validate(boost::any& v,
		const std::vector<std::string>& values,
		QString*, int)
{
	boostPO::validators::check_first_occurrence(v);
	const std::string& s = boostPO::validators::get_single_string(values);
	v = boost::any(QString::fromLocal8Bit(s.c_str()));
}

int main(int argc, char** argv)
{
	/* ARG PARSER *****************************************************/
	QString fn_rules;
	QString fn_bary;
	QString fn_offset;
	QString fn_out;

	boostPO::variables_map vm;
	boostPO::options_description desc("Allowed options");
	desc.add_options()
		("help,h",
		 "produce help message")
		("rule,r",
		 boostPO::value(&fn_rules)->required(),
		 "REQUIRED | subdivision rule filename")
		("bary,b",
		 boostPO::value(&fn_bary),
		 "barycenter offset filename (for each rule id)")
		("dev,d",
		 boostPO::value(&fn_offset),
		 "offset filename (for each structural indices)")
		("out,o",
		 boostPO::value(&fn_out),
		 "output filename")
		;

	try
	{
		boostPO::store(
				boostPO::command_line_parser(argc, argv).
				options(desc).run(), vm);
		boostPO::notify(vm);
	}
	catch(boost::program_options::error& e)
	{
		std::cerr << e.what() << std::endl;
		std::cout << desc << "\n";
		exit(EXIT_FAILURE);
	}

	if(vm.count("help"))
	{
		std::cout << desc << "\n";
		exit(EXIT_SUCCESS);
	}

	/* PROG ***********************************************************/
	Sampler sampler(fn_rules.toStdString(), fn_bary.toStdString(), fn_offset.toStdString());

	QApplication app(argc, argv);
	MainWindow* window = new MainWindow(&sampler);
	window->show();
	app.exec();
}

max_stars_repo_name: polyhex-sampling/sampler

max_issues_repo_name: polyhex-sampling/sampler

max_forks_repo_name: polyhex-sampling/sampler


text:
// http://turtle.sourceforge.net
//
// Copyright Mathieu Champlon 2008
//
// Distributed under the Boost Software License, Version 1.0.
// (See accompanying file LICENSE_1_0.txt or copy at
// http://www.boost.org/LICENSE_1_0.txt)

#include <turtle/detail/invocation.hpp>
#include <boost/test/auto_unit_test.hpp>

BOOST_AUTO_TEST_CASE( unlimited )
{
    mock::detail::unlimited invocation;
    BOOST_CHECK( invocation.verify() );
    BOOST_CHECK( ! invocation.exhausted() );
    BOOST_CHECK( invocation.invoke() );
    BOOST_CHECK( invocation.verify() );
    BOOST_CHECK( ! invocation.exhausted() );
    BOOST_CHECK( invocation.invoke() );
}

BOOST_AUTO_TEST_CASE( once )
{
    mock::detail::once invocation;
    BOOST_CHECK( ! invocation.verify() );
    BOOST_CHECK( ! invocation.exhausted() );
    BOOST_CHECK( invocation.invoke() );
    BOOST_CHECK( invocation.verify() );
    BOOST_CHECK( invocation.exhausted() );
    BOOST_CHECK( ! invocation.invoke() );
}

BOOST_AUTO_TEST_CASE( never )
{
    mock::detail::never invocation;
    BOOST_CHECK( invocation.verify() );
    BOOST_CHECK( invocation.exhausted() );
    BOOST_CHECK( ! invocation.invoke() );
}

BOOST_AUTO_TEST_CASE( at_most )
{
    mock::detail::at_most invocation( 1 );
    BOOST_CHECK( invocation.verify() );
    BOOST_CHECK( ! invocation.exhausted() );
    BOOST_CHECK( invocation.invoke() );
    BOOST_CHECK( invocation.verify() );
    BOOST_CHECK( invocation.exhausted() );
    BOOST_CHECK( ! invocation.invoke() );
}

BOOST_AUTO_TEST_CASE( at_least )
{
    mock::detail::at_least invocation( 1 );
    BOOST_CHECK( ! invocation.verify() );
    BOOST_CHECK( ! invocation.exhausted() );
    BOOST_CHECK( invocation.invoke() );
    BOOST_CHECK( invocation.verify() );
    BOOST_CHECK( ! invocation.exhausted() );
    BOOST_CHECK( invocation.invoke() );
}

BOOST_AUTO_TEST_CASE( between )
{
    mock::detail::between invocation( 1, 2 );
    BOOST_CHECK( ! invocation.verify() );
    BOOST_CHECK( ! invocation.exhausted() );
    BOOST_CHECK( invocation.invoke() );
    BOOST_CHECK( invocation.verify() );
    BOOST_CHECK( ! invocation.exhausted() );
    BOOST_CHECK( invocation.invoke() );
    BOOST_CHECK( invocation.verify() );
    BOOST_CHECK( invocation.exhausted() );
    BOOST_CHECK( ! invocation.invoke() );
}


text:
#ifndef B0__GRAPH__GRAPHVIZ_H
#define B0__GRAPH__GRAPHVIZ_H

#include <b0/graph/graphviz.h>
#include <b0/config.h>

#include "resolver.pb.h"

#include <cstdlib>
#include <fstream>
#include <iostream>
#include <boost/algorithm/string.hpp>
#include <boost/format.hpp>
#ifdef HAVE_BOOST_PROCESS
#include <boost/process.hpp>
#endif

namespace b0
{

namespace graph
{

static std::string id(std::string t, std::string name)
{
    boost::format fmt("%s_%s");
    boost::replace_all(name, "-", "_");
    return (fmt % t % name).str();
}

void toGraphviz(const b0::resolver_msgs::Graph &graph, std::string filename, std::string outline_color, std::string topic_color, std::string service_color)
{
    std::ofstream f;
    f.open(filename);
    std::set<std::string> nodes;
    std::set<std::string> topics;
    std::set<std::string> services;
    for(auto x : graph.nodes())
    {
        nodes.insert(x);
    }
    for(auto x : graph.node_topic())
    {
        nodes.insert(x.a());
        topics.insert(x.b());
    }
    for(auto x : graph.node_service())
    {
        nodes.insert(x.a());
        services.insert(x.b());
    }
    f << "digraph G {" << std::endl;
    f << "    graph [overlap=false, splines=true, bgcolor=\"transparent\"];";
    f << "    node [shape=box, color=" << outline_color << ", fontcolor=" << outline_color << "];";
    for(auto x : nodes) f << id("N", x) << " [label=\"" << x << "\"];";
    f << std::endl;
    f << "    node [shape=ellipse, color=" << topic_color << "];";
    for(auto x : topics) f << id("T", x) << " [label=\"" << x << "\", fontcolor=" << topic_color << "];";
    f << std::endl;
    f << "    node [shape=diamond, color=" << service_color << "];";
    for(auto x : services) f << id("S", x) << " [label=\"" << x << "\", fontcolor=" << service_color << "];";
    f << std::endl;
    f << "    edge [color=" << outline_color << "];" << std::endl;
    for(auto x : graph.node_topic())
        if(x.reversed())
            f << "    " << id("T", x.b()) << " -> " << id("N", x.a()) << ";" << std::endl;
        else
            f << "    " << id("N", x.a()) << " -> " << id("T", x.b()) << ";" << std::endl;
    for(auto x : graph.node_service())
        if(x.reversed())
            f << "    " << id("S", x.b()) << " -> " << id("N", x.a()) << ";" << std::endl;
        else
            f << "    " << id("N", x.a()) << " -> " << id("S", x.b()) << ";" << std::endl;
    f << "}" << std::endl;
    f.close();
}

int renderGraphviz(std::string input, std::string output)
{
#ifdef HAVE_BOOST_PROCESS
    boost::process::child c(boost::process::search_path("neato"), "-Tpng", boost::process::std_out > output, boost::process::std_in < input);
    c.wait();
    return c.exit_code();
#else
    std::cerr << "boost/process.hpp is needed for executing neato" << std::endl;
    return 1;
#endif
}

} // namespace graph

} // namespace b0

#endif // B0__GRAPH__GRAPHVIZ_H

max_stars_repo_name: DanialLiu/bluezero

max_issues_repo_name: DanialLiu/bluezero

max_forks_repo_name: DanialLiu/bluezero


text:
#include <val_str.h>
#include <boost/python.hpp>
using namespace boost::python;

void export_val_str()
{
  class_<Val_Str, bases<Value>, boost::shared_ptr<Val_Str> >
        ("Val_Str", no_init)
    .def("toConfString", &Val_Str::toConfString)

    .def("mk",  &Val_Str::mk)
    .staticmethod("mk")

    .def("cast",  &Val_Str::cast)
    .staticmethod("cast")
  ;
}


text:
// Copyright (c) 2016
// Author: Chrono Law
#include <std.hpp>
using namespace std;

#include <boost/multi_index_container.hpp>
#include <boost/multi_index/sequenced_index.hpp>
using namespace boost::multi_index;

int main()
{
    std::cout << "hello sequenced_index" << std::endl;

    typedef multi_index_container<int,
            indexed_by<sequenced<
                tag<int, struct int_seq> > >
                > mic_t;

    //using namespace boost::assign;
    //mic_t mic = (list_of(2),3,5,7,11);
    mic_t mic = {2,3,5,7,11};

    assert(!mic.empty() && mic.size() == 5);

    assert(mic.front() == 2);
    assert(mic.back() == 11);

    assert(mic.push_front(2).second);
    assert(mic.push_back(19).second);

    auto& seq_index = mic.get<int_seq>();

    seq_index.insert(seq_index.begin(), 5, 100);
    assert(std::count(seq_index.begin(), mic.end(), 100) == 5);

    seq_index.unique();
    assert(std::count(seq_index.begin(), mic.end(), 100) == 1);

    //mic_t mic1 = (list_of(2),3,5,7,11);
    mic_t mic1 = {2,3,5,7,11};

    mic_t mic2 = mic1;
    assert(mic1 == mic2);

    mic2.push_back(3);
    assert(mic1 < mic2);

    //*seq_index.begin() = 9;

    auto& x = mic.front();
    assert(mic.begin() == mic.iterator_to(x));
    assert(mic.begin() != mic.iterator_to(2));

}


text:
/*
 * UnknownWordPenalty.cpp
 *
 *  Created on: 28 Oct 2015
 *      Author: hieu
 */
#include <boost/foreach.hpp>
#include "UnknownWordPenalty.h"
#include "../System.h"
#include "../Scores.h"
#include "../InputType.h"
#include "../PhraseBased/Manager.h"
#include "../PhraseBased/TargetPhraseImpl.h"
#include "../PhraseBased/InputPath.h"
#include "../PhraseBased/TargetPhrases.h"
#include "../PhraseBased/Sentence.h"
#include "../SCFG/InputPath.h"
#include "../SCFG/TargetPhraseImpl.h"
#include "../SCFG/Manager.h"
#include "../SCFG/Sentence.h"
#include "../SCFG/ActiveChart.h"

using namespace std;

namespace Moses2
{

UnknownWordPenalty::UnknownWordPenalty(size_t startInd, const std::string &line)
  :PhraseTable(startInd, line)
  ,m_drop(false)
{
  m_tuneable = false;
  ReadParameters();
}

UnknownWordPenalty::~UnknownWordPenalty()
{
  // TODO Auto-generated destructor stub
}

void UnknownWordPenalty::SetParameter(const std::string& key, const std::string& value)
{
  if (key == "drop") {
    m_drop = Scan<bool>(value);
  } else if (key == "prefix") {
    m_prefix = value;
  } else if (key == "suffix") {
    m_suffix = value;
  } else {
    PhraseTable::SetParameter(key, value);
  }
}

void UnknownWordPenalty::ProcessXML(
  const Manager &mgr,
  MemPool &pool,
  const Sentence &sentence,
  InputPaths &inputPaths) const
{
  const Vector<const InputType::XMLOption*> &xmlOptions = sentence.GetXMLOptions();
  BOOST_FOREACH(const InputType::XMLOption *xmlOption, xmlOptions) {
    TargetPhraseImpl *target = TargetPhraseImpl::CreateFromString(pool, *this, mgr.system, xmlOption->GetTranslation());

    if (xmlOption->prob) {
      Scores &scores = target->GetScores();
      scores.PlusEquals(mgr.system, *this, Moses2::TransformScore(xmlOption->prob));
    }

    InputPath *path = inputPaths.GetMatrix().GetValue(xmlOption->startPos, xmlOption->phraseSize - 1);
    const SubPhrase<Moses2::Word> &source = path->subPhrase;

    mgr.system.featureFunctions.EvaluateInIsolation(pool, mgr.system, source, *target);

    TargetPhrases *tps = new (pool.Allocate<TargetPhrases>()) TargetPhrases(pool, 1);

    tps->AddTargetPhrase(*target);
    mgr.system.featureFunctions.EvaluateAfterTablePruning(pool, *tps, source);

    path->AddTargetPhrases(*this, tps);
  }
}

void UnknownWordPenalty::Lookup(const Manager &mgr,
                                InputPathsBase &inputPaths) const
{
  BOOST_FOREACH(InputPathBase *pathBase, inputPaths) {
    InputPath *path = static_cast<InputPath*>(pathBase);

    if (SatisfyBackoff(mgr, *path)) {
      const SubPhrase<Moses2::Word> &phrase = path->subPhrase;

      TargetPhrases *tps = Lookup(mgr, mgr.GetPool(), *path);
      path->AddTargetPhrases(*this, tps);
    }
  }

}

TargetPhrases *UnknownWordPenalty::Lookup(const Manager &mgr, MemPool &pool,
    InputPath &inputPath) const
{
  const System &system = mgr.system;
  TargetPhrases *tps = NULL;

  // any other pt translate this?
  size_t numPt = mgr.system.mappings.size();
  const TargetPhrases **allTPS =
    static_cast<InputPath&>(inputPath).targetPhrases;
  for (size_t i = 0; i < numPt; ++i) {
    const TargetPhrases *otherTps = allTPS[i];

    if (otherTps && otherTps->GetSize()) {
      return tps;
    }
  }

  const SubPhrase<Moses2::Word> &source = inputPath.subPhrase;
  const Moses2::Word &sourceWord = source[0];
  const Factor *factor = sourceWord[0];

  tps = new (pool.Allocate<TargetPhrases>()) TargetPhrases(pool, 1);

  size_t numWords = m_drop ? 0 : 1;

  TargetPhraseImpl *target =
    new (pool.Allocate<TargetPhraseImpl>()) TargetPhraseImpl(pool, *this,
        system, numWords);

  if (!m_drop) {
    Moses2::Word &word = (*target)[0];

    if (m_prefix.empty() && m_suffix.empty()) {
      word[0] = factor;
    } else {
      stringstream strm;
      if (!m_prefix.empty()) {
        strm << m_prefix;
      }
      strm << factor->GetString();
      if (!m_suffix.empty()) {
        strm << m_suffix;
      }

      FactorCollection &fc = system.GetVocab();
      const Factor *targetFactor = fc.AddFactor(strm.str(), system, false);
      word[0] = targetFactor;
    }
  }

  Scores &scores = target->GetScores();
  scores.PlusEquals(mgr.system, *this, -100);

  MemPool &memPool = mgr.GetPool();
  system.featureFunctions.EvaluateInIsolation(memPool, system, source, *target);

  tps->AddTargetPhrase(*target);
  system.featureFunctions.EvaluateAfterTablePruning(memPool, *tps, source);

  return tps;
}

void UnknownWordPenalty::EvaluateInIsolation(const System &system,
    const Phrase<Moses2::Word> &source, const TargetPhraseImpl &targetPhrase, Scores &scores,
    SCORE &estimatedScore) const
{

}

// SCFG ///////////////////////////////////////////////////////////////////////////////////////////
void UnknownWordPenalty::InitActiveChart(
  MemPool &pool,
  const SCFG::Manager &mgr,
  SCFG::InputPath &path) const
{
}

void UnknownWordPenalty::Lookup(MemPool &pool,
                                const SCFG::Manager &mgr,
                                size_t maxChartSpan,
                                const SCFG::Stacks &stacks,
                                SCFG::InputPath &path) const
{
  const System &system = mgr.system;

  size_t numWords = path.range.GetNumWordsCovered();
  if (numWords > 1) {
    // only create 1 word phrases
    return;
  }

  if (path.GetNumRules()) {
    // only create rules if no other rules
    return;
  }

  // don't do 1st if 1st word
  if (path.range.GetStartPos() == 0) {
    return;
  }

  // don't do 1st if last word
  const SCFG::Sentence &sentence = static_cast<const SCFG::Sentence&>(mgr.GetInput());
  if (path.range.GetStartPos() + 1 == sentence.GetSize()) {
    return;
  }

  // terminal
  const SCFG::Word &lastWord = path.subPhrase.Back();
  //cerr << "UnknownWordPenalty lastWord=" << lastWord << endl;

  const Factor *factor = lastWord[0];
  SCFG::TargetPhraseImpl *tp = new (pool.Allocate<SCFG::TargetPhraseImpl>()) SCFG::TargetPhraseImpl(pool, *this, system, 1);
  SCFG::Word &word = (*tp)[0];
  word.CreateFromString(system.GetVocab(), system, factor->GetString().as_string());

  tp->lhs.CreateFromString(system.GetVocab(), system, "[X]");

  size_t endPos = path.range.GetEndPos();
  const SCFG::InputPath &subPhrasePath = *mgr.GetInputPaths().GetMatrix().GetValue(endPos, 1);

  SCFG::ActiveChartEntry *chartEntry = new (pool.Allocate<SCFG::ActiveChartEntry>()) SCFG::ActiveChartEntry(pool);
  chartEntry->AddSymbolBindElement(subPhrasePath.range, lastWord, NULL, *this);
  path.AddActiveChartEntry(GetPtInd(), chartEntry);

  Scores &scores = tp->GetScores();
  scores.PlusEquals(mgr.system, *this, -100);

  MemPool &memPool = mgr.GetPool();
  const SubPhrase<SCFG::Word> &source = path.subPhrase;
  system.featureFunctions.EvaluateInIsolation(memPool, system, source, *tp);

  SCFG::TargetPhrases *tps = new (pool.Allocate<SCFG::TargetPhrases>()) SCFG::TargetPhrases(pool);
  tps->AddTargetPhrase(*tp);

  path.AddTargetPhrasesToPath(pool, mgr.system, *this, *tps, chartEntry->GetSymbolBind());
}

void UnknownWordPenalty::LookupUnary(MemPool &pool,
                                     const SCFG::Manager &mgr,
                                     const SCFG::Stacks &stacks,
                                     SCFG::InputPath &path) const
{
}

void UnknownWordPenalty::LookupNT(
  MemPool &pool,
  const SCFG::Manager &mgr,
  const Moses2::Range &subPhraseRange,
  const SCFG::InputPath &prevPath,
  const SCFG::Stacks &stacks,
  SCFG::InputPath &outPath) const
{
  UTIL_THROW2("Not implemented");
}

void UnknownWordPenalty::LookupGivenWord(
  MemPool &pool,
  const SCFG::Manager &mgr,
  const SCFG::InputPath &prevPath,
  const SCFG::Word &wordSought,
  const Moses2::Hypotheses *hypos,
  const Moses2::Range &subPhraseRange,
  SCFG::InputPath &outPath) const
{
  UTIL_THROW2("Not implemented");
}

void UnknownWordPenalty::LookupGivenNode(
  MemPool &pool,
  const SCFG::Manager &mgr,
  const SCFG::ActiveChartEntry &prevEntry,
  const SCFG::Word &wordSought,
  const Moses2::Hypotheses *hypos,
  const Moses2::Range &subPhraseRange,
  SCFG::InputPath &outPath) const
{
  UTIL_THROW2("Not implemented");
}

}


text:
#pragma once

#include <futurehead/lib/numbers.hpp>
#include <futurehead/node/distributed_work.hpp>

#include <boost/optional/optional.hpp>

#include <atomic>
#include <functional>
#include <mutex>
#include <unordered_map>
#include <vector>

namespace futurehead
{
class node;
class distributed_work;
class root;

class distributed_work_factory final
{
public:
	distributed_work_factory (futurehead::node &);
	~distributed_work_factory ();
	bool make (futurehead::work_version const, futurehead::root const &, std::vector<std::pair<std::string, uint16_t>> const &, uint64_t, std::function<void(boost::optional<uint64_t>)> const &, boost::optional<futurehead::account> const & = boost::none);
	bool make (std::chrono::seconds const &, futurehead::work_request const &);
	void cancel (futurehead::root const &, bool const local_stop = false);
	void cleanup_finished ();
	void stop ();

	futurehead::node & node;
	std::unordered_map<futurehead::root, std::vector<std::weak_ptr<futurehead::distributed_work>>> items;
	std::mutex mutex;
	std::atomic<bool> stopped{ false };
};

class container_info_component;
std::unique_ptr<container_info_component> collect_container_info (distributed_work_factory & distributed_work, const std::string & name);
}

ext: hpp

max_stars_repo_name: futureheadgroup/futurehead-node

max_issues_repo_name: FutureHeadCoin/futurehead-node

max_forks_repo_name: FutureHeadCoin/futurehead-node


text:
/******************************************************************************
 * Copyright (c) 2016-2017 Sergey Alexandrov
 *
 * Permission is hereby granted, free of charge, to any person obtaining a copy
 * of this software and associated documentation files (the "Software"), to
 * deal in the Software without restriction, including without limitation the
 * rights to use, copy, modify, merge, publish, distribute, sublicense, and/or
 * sell copies of the Software, and to permit persons to whom the Software is
 * furnished to do so, subject to the following conditions:
 *
 * The above copyright notice and this permission notice shall be included in
 * all copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
 * SOFTWARE.
 ******************************************************************************/

#include <iostream>

#include <boost/assert.hpp>

#include <opencv2/imgproc/imgproc.hpp>

#include "dataset_collection.h"

DatasetCollection::DatasetCollection(grabbers::Grabber::Ptr grabber, const Parameters& params)
: grabber_(grabber)
, params_(params)
, dataset_(new Dataset)
, mean_(false, params.num_average_frames)
, mean_mask_(false, params.num_average_frames)
, morph_(cv::getStructuringElement(cv::MORPH_ELLIPSE, cv::Size(params_.bloom_radius * 2, params_.bloom_radius * 2))) {
  BOOST_ASSERT(params_.exposure_min <= params_.exposure_max);
  BOOST_ASSERT(params_.exposure_factor > 1.0);
  exposure_ = params_.exposure_min;
  skip_frames_ = params_.exposure_control_lag;
  images_to_accumulate_ = params_.num_images;
  std::cout << "Starting data collection" << std::endl;
  std::cout << "Exposure range: " << params_.exposure_min << " → " << params_.exposure_max << " with factor "
            << params_.exposure_factor << std::endl;
  std::cout << "Exposure: " << exposure_ << std::flush;
}

bool DatasetCollection::addFrame(const cv::Mat& frame) {
  if (skip_frames_-- > 0)
    return false;

  auto averaging_done = mean_.add(frame);
  mean_mask_.add(computeSaturationMask(frame));
  if (!averaging_done)
    return false;

  auto mask = mean_mask_.getMean();  // everything below 255 was saturated in at least one frame
  cv::threshold(mask, mask, 254, 255, cv::THRESH_BINARY_INV);
  auto mean = mean_.getMean().clone();
  mean.reshape(1, 1).setTo(0, mask.reshape(1, 1));  // reshape to single-channel, otherwise masking will not work
  dataset_->insert(exposure_, mean);

  if (--images_to_accumulate_ > 0)
    return false;

  exposure_ += static_cast<int>(std::ceil(exposure_ * (params_.exposure_factor - 1.0)));
  skip_frames_ = params_.exposure_control_lag;
  images_to_accumulate_ = params_.num_images;
  grabber_->setExposure(exposure_);
  std::cout << " " << exposure_ << std::flush;

  if (exposure_ > params_.exposure_max) {
    std::cout << std::endl;
    return true;
  }
  return false;
}

Dataset::Ptr DatasetCollection::getDataset() const {
  return dataset_;
}

cv::Mat DatasetCollection::computeSaturationMask(const cv::Mat& image) {
  static std::vector<cv::Mat> mask_channels;
  cv::Mat mask;
  // Set overexposed (per channel) pixels to 0, everything else to 255
  cv::threshold(image, mask, params_.valid_intensity_max, 255, cv::THRESH_BINARY_INV);
  cv::split(mask, mask_channels);
  // Pixels that are overexposed in all channels are set to 0
  cv::Mat bloom_mask = mask_channels[0];
  for (size_t i = 1; i < mask_channels.size(); ++i)
    bloom_mask |= mask_channels[i];
  cv::erode(bloom_mask, bloom_mask, morph_);
  for (auto& mask_channel : mask_channels)
    mask_channel &= bloom_mask;
  cv::merge(mask_channels, mask);
  return mask;
}

max_stars_repo_name: taketwo/radical

max_issues_repo_name: taketwo/radical

max_forks_repo_name: taketwo/radical


text:
#include <memory>

#include <Eigen/Core>

#include <map-sparsification/heuristic/cost-functions/min-keypoints-per-keyframe-cost.h>
#include <map-sparsification/heuristic/heuristic-sampling.h>
#include <map-sparsification/heuristic/scoring/descriptor-variance-scoring.h>
#include <map-sparsification/heuristic/scoring/observation-count-scoring.h>
#include <maplab-common/test/testing-entrypoint.h>
#include <maplab-common/test/testing-predicates.h>

#include <vi-map/pose-graph.h>
#include <vi-map/test/vi-map-generator.h>
#include <vi-map/vi-map.h>

class MapSparsification : public testing::Test {
 protected:
  typedef map_sparsification::sampling::LandmarkSamplingWithCostFunctions
      Sampler;

  virtual void SetUp() {
    generator_map_.reset(new vi_map::VIMap);
    constexpr int kSeed = 42;
    generator_.reset(new vi_map::VIMapGenerator(*generator_map_, kSeed));

    is_map_data_initialized_ = false;

    initializeMapData();
    addMissionAndVertices();
    buildMapSummarizer();
  }

  const vi_map::LandmarkId& generateMapToTestObservationCount();
  const vi_map::LandmarkId& generateMapToTestKeyframeConstraints();
  void sample(vi_map::LandmarkIdSet* summary_store_landmark_ids);

  void expectRemovedLandmark(
      const vi_map::LandmarkIdSet& summary_store_landmark_ids,
      const vi_map::LandmarkId& deleted_landmark) const;
  void expectPreservedLandmark(
      const vi_map::LandmarkIdSet& summary_store_landmark_ids,
      const vi_map::LandmarkId& preserved_landmark) const;

  inline int getNumDesiredLandmarks() const {
    return kNumDesiredNumLandmarks;
  }

 private:
  void initializeMapData();
  void addMissionAndVertices();
  void buildMapSummarizer();

  std::unique_ptr<vi_map::VIMap> generator_map_;
  std::unique_ptr<vi_map::VIMapGenerator> generator_;
  Sampler sampler_;

  static constexpr int kNumVertices = 5;
  static constexpr int kNumLandmarks = 5;
  static constexpr int kNumMissions = 1;
  static constexpr int kNumDesiredNumLandmarks = 4;

  vi_map::MissionId mission_id_;
  pose_graph::VertexId vertex_ids_[kNumVertices];
  vi_map::LandmarkId landmark_ids_[kNumLandmarks];
  pose::Transformation T_G_M_;
  pose::Transformation T_G_I_[kNumVertices];
  Eigen::Vector3d p_G_fi_[kNumLandmarks];

  bool is_map_data_initialized_;

 public:
  EIGEN_MAKE_ALIGNED_OPERATOR_NEW
};

void MapSparsification::initializeMapData() {
  ASSERT_FALSE(is_map_data_initialized_);

  T_G_M_.setIdentity();

  for (unsigned int i = 0; i < kNumVertices; ++i) {
    T_G_I_[i].setIdentity();
  }

  for (unsigned int i = 0; i < kNumLandmarks; ++i) {
    p_G_fi_[i] = Eigen::Vector3d(1, 1, 1);
  }
  is_map_data_initialized_ = true;
}

void MapSparsification::addMissionAndVertices() {
  ASSERT_TRUE(is_map_data_initialized_);

  mission_id_ = generator_->createMission(T_G_M_);

  for (unsigned int i = 0; i < kNumVertices; ++i) {
    vertex_ids_[i] = generator_->createVertex(mission_id_, T_G_I_[i]);
  }
}

// This method generates a map where one of the landmarks has fewer
// observations than all the others. ID of this landmark is returned.
const vi_map::LandmarkId&
MapSparsification::generateMapToTestObservationCount() {
  pose_graph::VertexIdList all_vertices;
  all_vertices.assign(vertex_ids_ + 1, vertex_ids_ + kNumVertices);
  for (unsigned int i = 1; i < kNumLandmarks; ++i) {
    landmark_ids_[i] =
        generator_->createLandmark(p_G_fi_[i], vertex_ids_[0], all_vertices);
  }

  pose_graph::VertexIdList empty_vertex_list;
  landmark_ids_[0] =
      generator_->createLandmark(p_G_fi_[0], vertex_ids_[0], empty_vertex_list);
  generator_->generateMap();
  return landmark_ids_[0];
}

// This method generates a map where one of the keyframes is observed by
// smaller number of landmarks than the rest. The observation count of all
// landmarks is identical. The method returns the landmark ID that should
// be preserved because of keypoint per keyframe threshold violation.
const vi_map::LandmarkId&
MapSparsification::generateMapToTestKeyframeConstraints() {
  const pose_graph::VertexId additional_vertex =
      generator_->createVertex(mission_id_, T_G_I_[0]);

  pose_graph::VertexIdList vertices_minus_first_and_last;
  vertices_minus_first_and_last.assign(
      vertex_ids_ + 1, vertex_ids_ + kNumVertices - 1);
  for (unsigned int i = 1; i < kNumLandmarks; ++i) {
    landmark_ids_[i] = generator_->createLandmark(
        p_G_fi_[i], vertex_ids_[0], vertices_minus_first_and_last);
  }

  pose_graph::VertexIdList vertices_minus_first_plus_additional;
  vertices_minus_first_plus_additional.assign(
      vertex_ids_ + 1, vertex_ids_ + kNumVertices);
  vertices_minus_first_plus_additional.push_back(additional_vertex);

  // Additional link s.t. all landmarks have idential number of observers.
  landmark_ids_[0] = generator_->createLandmark(
      p_G_fi_[0], vertex_ids_[0], vertices_minus_first_plus_additional);

  generator_->generateMap();
  return landmark_ids_[0];
}

void MapSparsification::buildMapSummarizer() {
  using map_sparsification::cost_functions::IsRequiredToConstrainKeyframesCost;
  using map_sparsification::scoring::ObservationCountScoringFunction;
  using map_sparsification::scoring::DescriptorVarianceScoring;

  const double kDescriptorDevThreshold = 30.0;
  const int kMinKeyframesPerKeypoint = 5;

  DescriptorVarianceScoring::Ptr descriptor_dev_score(
      new DescriptorVarianceScoring(kDescriptorDevThreshold));
  IsRequiredToConstrainKeyframesCost::Ptr keyframe_keypoint_cost(
      new IsRequiredToConstrainKeyframesCost(kMinKeyframesPerKeypoint));
  ObservationCountScoringFunction::Ptr obs_count_score(
      new ObservationCountScoringFunction);

  const double kDescriptorVarianceWeight = 0.2;
  const double kObsCountWeight = 1.0;
  const double kKeyframeConstraintWeight = 1.0;
  descriptor_dev_score->setWeight(kDescriptorVarianceWeight);
  obs_count_score->setWeight(kObsCountWeight);
  keyframe_keypoint_cost->setWeight(kKeyframeConstraintWeight);

  // Squared loss.
  std::function<double(double)> keyframe_constraint_loss =  // NOLINT
      [](double x) {
        const double kLinearFactor = 5.0;
        return kLinearFactor * x * x;
      };  // NOLINT
  keyframe_keypoint_cost->setLossFunction(keyframe_constraint_loss);

  sampler_.registerScoringFunction(obs_count_score);
  sampler_.registerScoringFunction(descriptor_dev_score);
  sampler_.registerCostFunction(keyframe_keypoint_cost);
}

void MapSparsification::sample(
    vi_map::LandmarkIdSet* summary_store_landmark_ids) {
  CHECK_NOTNULL(summary_store_landmark_ids);
  sampler_.sample(
      *generator_map_, kNumDesiredNumLandmarks, summary_store_landmark_ids);
}

void MapSparsification::expectRemovedLandmark(
    const vi_map::LandmarkIdSet& summary_landmark_ids,
    const vi_map::LandmarkId& deleted_landmark) const {
  EXPECT_EQ(0u, summary_landmark_ids.count(deleted_landmark));
  for (unsigned int i = 0; i < kNumLandmarks; ++i) {
    if (landmark_ids_[i] != deleted_landmark) {
      EXPECT_EQ(1u, summary_landmark_ids.count(landmark_ids_[i]));
    }
  }
}

void MapSparsification::expectPreservedLandmark(
    const vi_map::LandmarkIdSet& summary_landmark_ids,
    const vi_map::LandmarkId& preserved_landmark) const {
  // Expect that preserved_landmark is indeed preserved.
  EXPECT_EQ(1u, summary_landmark_ids.count(preserved_landmark));
  int num_preserved_landmarks = 0;
  for (unsigned int i = 0; i < kNumLandmarks; ++i) {
    if (summary_landmark_ids.count(landmark_ids_[i]) > 0u) {
      ++num_preserved_landmarks;
    }
  }
  // Other landmarks could be deleted, but the total number has to match
  // the desired number.
  EXPECT_EQ(getNumDesiredLandmarks(), num_preserved_landmarks);
}

TEST_F(MapSparsification, ObservationCountSparsificationTest) {
  const vi_map::LandmarkId& landmark_to_be_deleted =
      generateMapToTestObservationCount();

  vi_map::LandmarkIdSet summary_landmark_list;
  sample(&summary_landmark_list);

  expectRemovedLandmark(summary_landmark_list, landmark_to_be_deleted);
  EXPECT_EQ(getNumDesiredLandmarks(), summary_landmark_list.size());
}

TEST_F(MapSparsification, KeyframeKeypointConstraintSparsificationTest) {
  const vi_map::LandmarkId& landmark_to_be_preserved =
      generateMapToTestKeyframeConstraints();

  vi_map::LandmarkIdSet summary_landmark_list;
  sample(&summary_landmark_list);

  expectPreservedLandmark(summary_landmark_list, landmark_to_be_preserved);
}

MAPLAB_UNITTEST_ENTRYPOINT

max_stars_repo_name: AdronTech/maplab

max_issues_repo_name: AdronTech/maplab

max_forks_repo_name: AdronTech/maplab