/*
 * Given a group of atom blocks and a partially-packed complex block, find placement for group of atom blocks in complex block
 * To use, keep "cluster_placement_stats" data structure throughout packing
 * cluster_placement_stats undergoes these major states:
 * Initialization - performed once at beginning of packing
 * Reset          - reset state in between packing of clusters
 * In flight      - Speculatively place
 * Finalized      - Commit or revert placements
 * Freed          - performed once at end of packing
 *
 * Author: Jason Luu
 * March 12, 2012
 */

#include <cstdio>
#include <cstring>

#include "vtr_assert.h"
#include "vtr_memory.h"

#include "read_xml_arch_file.h"
#include "vpr_types.h"
#include "globals.h"
#include "atom_netlist.h"
#include "vpr_utils.h"
#include "hash.h"
#include "cluster_placement.h"

/****************************************/
/*Local Function Declaration			*/
/****************************************/
static void load_cluster_placement_stats_for_pb_graph_node(t_cluster_placement_stats* cluster_placement_stats,
                                                           t_pb_graph_node* pb_graph_node);
static void requeue_primitive(t_cluster_placement_stats* cluster_placement_stats,
                              t_cluster_placement_primitive* cluster_placement_primitive);
static void update_primitive_cost_or_status(const t_pb_graph_node* pb_graph_node,
                                            const float incremental_cost,
                                            const bool valid);
static float try_place_molecule(const t_pack_molecule* molecule,
                                t_pb_graph_node* root,
                                t_pb_graph_node** primitives_list);
static bool expand_forced_pack_molecule_placement(const t_pack_molecule* molecule,
                                                  const t_pack_pattern_block* pack_pattern_block,
                                                  t_pb_graph_node** primitives_list,
                                                  float* cost);
static t_pb_graph_pin* expand_pack_molecule_pin_edge(const int pattern_id,
                                                     const t_pb_graph_pin* cur_pin,
                                                     const bool forward);
static void flush_intermediate_queues(t_cluster_placement_stats* cluster_placement_stats);

/****************************************/
/*Function Definitions					*/
/****************************************/

/**
 * [0..num_pb_types-1] array of cluster placement stats, one for each device_ctx.block_types
 */
t_cluster_placement_stats* alloc_and_load_cluster_placement_stats() {
    t_cluster_placement_stats* cluster_placement_stats_list;

    auto& device_ctx = g_vpr_ctx.device();

    cluster_placement_stats_list = (t_cluster_placement_stats*)vtr::calloc(device_ctx.logical_block_types.size(),
                                                                           sizeof(t_cluster_placement_stats));
    for (const auto& type : device_ctx.logical_block_types) {
        if (device_ctx.EMPTY_TYPE != physical_tile_type(&type)) {
            cluster_placement_stats_list[type.index].valid_primitives = (t_cluster_placement_primitive**)vtr::calloc(
                get_max_primitives_in_pb_type(type.pb_type) + 1,
                sizeof(t_cluster_placement_primitive*)); /* too much memory allocated but shouldn't be a problem */

            cluster_placement_stats_list[type.index].curr_molecule = nullptr;
            load_cluster_placement_stats_for_pb_graph_node(&cluster_placement_stats_list[type.index],
                                                           type.pb_graph_head);
        }
    }
    return cluster_placement_stats_list;
}

/**
 * get next list of primitives for list of atom blocks
 *
 * primitives is the list of ptrs to primitives that matches with the list of atom block, assumes memory is preallocated
 *   - if this is a new block, requeue tried primitives and return a in-flight primitive list to try
 *   - if this is an old block, put root primitive to tried queue, requeue rest of primitives. try another set of primitives
 *
 * return true if can find next primitive, false otherwise
 *
 * cluster_placement_stats - ptr to the current cluster_placement_stats of open complex block
 * molecule - molecule to pack into open complex block
 * primitives_list - a list of primitives indexed to match atom_block_ids of molecule.
 *                   Expects an allocated array of primitives ptrs as inputs.
 *                   This function loads the array with the lowest cost primitives that implement molecule
 */
bool get_next_primitive_list(t_cluster_placement_stats* cluster_placement_stats,
                             const t_pack_molecule* molecule,
                             t_pb_graph_node** primitives_list) {
    t_cluster_placement_primitive *cur, *next, *best, *before_best, *prev;
    int i;
    float cost, lowest_cost;
    best = nullptr;
    before_best = nullptr;

    if (cluster_placement_stats->curr_molecule != molecule) {
        /* New block, requeue tried primitives and in-flight primitives */
        flush_intermediate_queues(cluster_placement_stats);

        cluster_placement_stats->curr_molecule = molecule;
    } else {
        /* Hack! Same failed molecule may re-enter if upper stream functions suck,
         * I'm going to make the molecule selector more intelligent.
         * TODO: Remove later
         */
        if (cluster_placement_stats->in_flight != nullptr) {
            /* Hack end */

            /* old block, put root primitive currently inflight to tried queue	*/
            cur = cluster_placement_stats->in_flight;
            next = cur->next_primitive;
            cur->next_primitive = cluster_placement_stats->tried;
            cluster_placement_stats->tried = cur;
            /* should have only one block in flight at any point in time */
            VTR_ASSERT(next == nullptr);
            cluster_placement_stats->in_flight = nullptr;
        }
    }

    /* find next set of blocks
     * 1. Remove invalid blocks to invalid queue
     * 2. Find lowest cost array of primitives that implements blocks
     * 3. When found, move current blocks to in-flight, return lowest cost array of primitives
     * 4. Return NULL if not found
     */
    lowest_cost = HUGE_POSITIVE_FLOAT;
    for (i = 0; i < cluster_placement_stats->num_pb_types; i++) {
        if (cluster_placement_stats->valid_primitives[i]->next_primitive == nullptr) {
            continue; /* no more primitives of this type available */
        }
        if (primitive_type_feasible(molecule->atom_block_ids[molecule->root],
                                    cluster_placement_stats->valid_primitives[i]->next_primitive->pb_graph_node->pb_type)) {
            prev = cluster_placement_stats->valid_primitives[i];
            cur = cluster_placement_stats->valid_primitives[i]->next_primitive;
            while (cur) {
                /* remove invalid nodes lazily when encountered */
                while (cur && cur->valid == false) {
                    prev->next_primitive = cur->next_primitive;
                    cur->next_primitive = cluster_placement_stats->invalid;
                    cluster_placement_stats->invalid = cur;
                    cur = prev->next_primitive;
                }
                if (cur == nullptr) {
                    break;
                }
                /* try place molecule at root location cur */
                cost = try_place_molecule(molecule, cur->pb_graph_node, primitives_list);
                // if the cost is lower than the best, or is equal to the best but this
                // primitive is more available in the cluster mark it as the best primitive
                if (cost < lowest_cost || (best && cost == lowest_cost && cur->pb_graph_node->total_primitive_count > best->pb_graph_node->total_primitive_count)) {
                    lowest_cost = cost;
                    best = cur;
                    before_best = prev;
                }
                prev = cur;
                cur = cur->next_primitive;
            }
        }
    }
    if (best == nullptr) {
        /* failed to find a placement */
        for (i = 0; i < molecule->num_blocks; i++) {
            primitives_list[i] = nullptr;
        }
    } else {
        /* populate primitive list with best */
        cost = try_place_molecule(molecule, best->pb_graph_node, primitives_list);
        VTR_ASSERT(cost == lowest_cost);

        /* take out best node and put it in flight */
        cluster_placement_stats->in_flight = best;
        before_best->next_primitive = best->next_primitive;
        best->next_primitive = nullptr;
    }

    if (best == nullptr) {
        return false;
    }
    return true;
}

/**
 * Resets one cluster placement stats by clearing incremental costs and returning all primitives to valid queue
 */
void reset_cluster_placement_stats(t_cluster_placement_stats* cluster_placement_stats) {
    t_cluster_placement_primitive *cur, *next;
    int i;

    /* Requeue primitives */
    flush_intermediate_queues(cluster_placement_stats);
    cur = cluster_placement_stats->invalid;
    while (cur != nullptr) {
        next = cur->next_primitive;
        requeue_primitive(cluster_placement_stats, cur);
        cur = next;
    }
    cur = cluster_placement_stats->invalid = nullptr;
    /* reset flags and cost */
    for (i = 0; i < cluster_placement_stats->num_pb_types; i++) {
        VTR_ASSERT(cluster_placement_stats->valid_primitives[i] != nullptr
                   && cluster_placement_stats->valid_primitives[i]->next_primitive != nullptr);
        cur = cluster_placement_stats->valid_primitives[i]->next_primitive;
        while (cur != nullptr) {
            cur->incremental_cost = 0;
            cur->valid = true;
            cur = cur->next_primitive;
        }
    }
    cluster_placement_stats->curr_molecule = nullptr;
    cluster_placement_stats->has_long_chain = false;
}

/**
 * Free linked lists found in cluster_placement_stats_list
 */
void free_cluster_placement_stats(t_cluster_placement_stats* cluster_placement_stats_list) {
    t_cluster_placement_primitive *cur, *next;
    auto& device_ctx = g_vpr_ctx.device();

    for (const auto& type : device_ctx.logical_block_types) {
        int index = type.index;
        cur = cluster_placement_stats_list[index].tried;
        while (cur != nullptr) {
            next = cur->next_primitive;
            free(cur);
            cur = next;
        }
        cur = cluster_placement_stats_list[index].in_flight;
        while (cur != nullptr) {
            next = cur->next_primitive;
            free(cur);
            cur = next;
        }
        cur = cluster_placement_stats_list[index].invalid;
        while (cur != nullptr) {
            next = cur->next_primitive;
            free(cur);
            cur = next;
        }
        for (int j = 0; j < cluster_placement_stats_list[index].num_pb_types; j++) {
            cur = cluster_placement_stats_list[index].valid_primitives[j]->next_primitive;
            while (cur != nullptr) {
                next = cur->next_primitive;
                free(cur);
                cur = next;
            }
            free(cluster_placement_stats_list[index].valid_primitives[j]);
        }
        free(cluster_placement_stats_list[index].valid_primitives);
    }
    free(cluster_placement_stats_list);
}

/**
 * Put primitive back on queue of valid primitives
 *  Note that valid status is not changed because if the primitive is not valid, it will get properly collected later
 */
static void requeue_primitive(t_cluster_placement_stats* cluster_placement_stats,
                              t_cluster_placement_primitive* cluster_placement_primitive) {
    int i;
    int null_index;
    bool success;
    null_index = OPEN;

    success = false;
    for (i = 0; i < cluster_placement_stats->num_pb_types; i++) {
        if (cluster_placement_stats->valid_primitives[i]->next_primitive == nullptr) {
            null_index = i;
            continue;
        }
        if (cluster_placement_primitive->pb_graph_node->pb_type
            == cluster_placement_stats->valid_primitives[i]->next_primitive->pb_graph_node->pb_type) {
            success = true;
            cluster_placement_primitive->next_primitive = cluster_placement_stats->valid_primitives[i]->next_primitive;
            cluster_placement_stats->valid_primitives[i]->next_primitive = cluster_placement_primitive;
        }
    }
    if (success == false) {
        VTR_ASSERT(null_index != OPEN);
        cluster_placement_primitive->next_primitive = cluster_placement_stats->valid_primitives[null_index]->next_primitive;
        cluster_placement_stats->valid_primitives[null_index]->next_primitive = cluster_placement_primitive;
    }
}

/**
 * Add any primitives found in pb_graph_nodes to cluster_placement_stats
 * Adds backward link from pb_graph_node to cluster_placement_primitive
 */
static void load_cluster_placement_stats_for_pb_graph_node(t_cluster_placement_stats* cluster_placement_stats,
                                                           t_pb_graph_node* pb_graph_node) {
    int i, j, k;
    t_cluster_placement_primitive* placement_primitive;
    const t_pb_type* pb_type = pb_graph_node->pb_type;
    bool success;
    if (pb_type->modes == nullptr) {
        placement_primitive = (t_cluster_placement_primitive*)vtr::calloc(1,
                                                                          sizeof(t_cluster_placement_primitive));
        placement_primitive->pb_graph_node = pb_graph_node;
        placement_primitive->valid = true;
        pb_graph_node->cluster_placement_primitive = placement_primitive;
        placement_primitive->base_cost = compute_primitive_base_cost(pb_graph_node);
        success = false;
        i = 0;
        while (success == false) {
            if (cluster_placement_stats->valid_primitives[i] == nullptr
                || cluster_placement_stats->valid_primitives[i]->next_primitive->pb_graph_node->pb_type
                       == pb_graph_node->pb_type) {
                if (cluster_placement_stats->valid_primitives[i] == nullptr) {
                    cluster_placement_stats->valid_primitives[i] = (t_cluster_placement_primitive*)vtr::calloc(1,
                                                                                                               sizeof(t_cluster_placement_primitive)); /* head of linked list is empty, makes it easier to remove nodes later */
                    cluster_placement_stats->num_pb_types++;
                }
                success = true;
                placement_primitive->next_primitive = cluster_placement_stats->valid_primitives[i]->next_primitive;
                cluster_placement_stats->valid_primitives[i]->next_primitive = placement_primitive;
            }
            i++;
        }
    } else {
        for (i = 0; i < pb_type->num_modes; i++) {
            for (j = 0; j < pb_type->modes[i].num_pb_type_children; j++) {
                for (k = 0; k < pb_type->modes[i].pb_type_children[j].num_pb;
                     k++) {
                    load_cluster_placement_stats_for_pb_graph_node(cluster_placement_stats,
                                                                   &pb_graph_node->child_pb_graph_nodes[i][j][k]);
                }
            }
        }
    }
}

/**
 * Commit primitive, invalidate primitives blocked by mode assignment and update costs for primitives in same cluster as current
 * Costing is done to try to pack blocks closer to existing primitives
 *  actual value based on closest common ancestor to committed placement, the farther the ancestor, the less reduction in cost there is
 * Side effects: All cluster_placement_primitives may be invalidated/costed in this algorithm
 *               Al intermediate queues are requeued
 */
void commit_primitive(t_cluster_placement_stats* cluster_placement_stats,
                      const t_pb_graph_node* primitive) {
    t_pb_graph_node *pb_graph_node, *skip;
    float incr_cost;
    int i, j, k;
    int valid_mode;
    t_cluster_placement_primitive* cur;

    /* Clear out intermediate queues */
    flush_intermediate_queues(cluster_placement_stats);

    /* commit primitive as used, invalidate it */
    cur = primitive->cluster_placement_primitive;
    VTR_ASSERT(cur->valid == true);

    cur->valid = false;
    incr_cost = -0.01; /* cost of using a node drops as its neighbours are used, this drop should be small compared to scarcity values */

    pb_graph_node = cur->pb_graph_node;
    /* walk up pb_graph_node and update primitives of children */
    while (!pb_graph_node->is_root()) {
        skip = pb_graph_node; /* do not traverse stuff that's already traversed */
        valid_mode = pb_graph_node->pb_type->parent_mode->index;
        pb_graph_node = pb_graph_node->parent_pb_graph_node;
        for (i = 0; i < pb_graph_node->pb_type->num_modes; i++) {
            for (j = 0; j < pb_graph_node->pb_type->modes[i].num_pb_type_children; j++) {
                for (k = 0; k < pb_graph_node->pb_type->modes[i].pb_type_children[j].num_pb; k++) {
                    if (&pb_graph_node->child_pb_graph_nodes[i][j][k] != skip) {
                        update_primitive_cost_or_status(&pb_graph_node->child_pb_graph_nodes[i][j][k],
                                                        incr_cost, (bool)(i == valid_mode));
                    }
                }
            }
        }
        incr_cost /= 10; /* blocks whose ancestor is further away in tree should be affected less than blocks closer in tree */
    }
}

/**
 * Set mode of cluster
 */
void set_mode_cluster_placement_stats(const t_pb_graph_node* pb_graph_node, int mode) {
    int i, j, k;
    for (i = 0; i < pb_graph_node->pb_type->num_modes; i++) {
        if (i != mode) {
            for (j = 0; j < pb_graph_node->pb_type->modes[i].num_pb_type_children; j++) {
                for (k = 0; k < pb_graph_node->pb_type->modes[i].pb_type_children[j].num_pb; k++) {
                    update_primitive_cost_or_status(&pb_graph_node->child_pb_graph_nodes[i][j][k], 0, false);
                }
            }
        }
    }
}

/**
 * For sibling primitives of pb_graph node, decrease cost
 * For modes invalidated by pb_graph_node, invalidate primitive
 * int distance is the distance of current pb_graph_node from original
 */
static void update_primitive_cost_or_status(const t_pb_graph_node* pb_graph_node,
                                            const float incremental_cost,
                                            const bool valid) {
    int i, j, k;
    t_cluster_placement_primitive* placement_primitive;
    if (pb_graph_node->is_primitive()) {
        /* is primitive */
        placement_primitive = (t_cluster_placement_primitive*)pb_graph_node->cluster_placement_primitive;
        if (valid) {
            placement_primitive->incremental_cost += incremental_cost;
        } else {
            placement_primitive->valid = false;
        }
    } else {
        for (i = 0; i < pb_graph_node->pb_type->num_modes; i++) {
            for (j = 0; j < pb_graph_node->pb_type->modes[i].num_pb_type_children; j++) {
                for (k = 0; k < pb_graph_node->pb_type->modes[i].pb_type_children[j].num_pb; k++) {
                    update_primitive_cost_or_status(&pb_graph_node->child_pb_graph_nodes[i][j][k],
                                                    incremental_cost, valid);
                }
            }
        }
    }
}

/**
 * Try place molecule at root location, populate primitives list with locations of placement if successful
 */
static float try_place_molecule(const t_pack_molecule* molecule,
                                t_pb_graph_node* root,
                                t_pb_graph_node** primitives_list) {
    int list_size, i;
    float cost = HUGE_POSITIVE_FLOAT;
    list_size = get_array_size_of_molecule(molecule);

    if (primitive_type_feasible(molecule->atom_block_ids[molecule->root],
                                root->pb_type)) {
        if (root->cluster_placement_primitive->valid == true) {
            for (i = 0; i < list_size; i++) {
                primitives_list[i] = nullptr;
            }
            cost = root->cluster_placement_primitive->base_cost
                   + root->cluster_placement_primitive->incremental_cost;
            primitives_list[molecule->root] = root;
            if (molecule->type == MOLECULE_FORCED_PACK) {
                if (!expand_forced_pack_molecule_placement(molecule,
                                                           molecule->pack_pattern->root_block, primitives_list,
                                                           &cost)) {
                    return HUGE_POSITIVE_FLOAT;
                }
            }
            for (i = 0; i < list_size; i++) {
                VTR_ASSERT((primitives_list[i] == nullptr) == (!molecule->atom_block_ids[i]));
                for (int j = 0; j < list_size; j++) {
                    if (i != j) {
                        if (primitives_list[i] != nullptr && primitives_list[i] == primitives_list[j]) {
                            return HUGE_POSITIVE_FLOAT;
                        }
                    }
                }
            }
        }
    }
    return cost;
}

/**
 * Expand molecule at pb_graph_node
 * Assumes molecule and pack pattern connections have fan-out 1
 */
static bool expand_forced_pack_molecule_placement(const t_pack_molecule* molecule,
                                                  const t_pack_pattern_block* pack_pattern_block,
                                                  t_pb_graph_node** primitives_list,
                                                  float* cost) {
    t_pb_graph_node* pb_graph_node = primitives_list[pack_pattern_block->block_id];
    t_pb_graph_node* next_primitive;
    t_pack_pattern_connections* cur;
    t_pb_graph_pin *cur_pin, *next_pin;
    t_pack_pattern_block* next_block;

    cur = pack_pattern_block->connections;
    while (cur) {
        if (cur->from_block == pack_pattern_block) {
            next_block = cur->to_block;
        } else {
            next_block = cur->from_block;
        }
        if (primitives_list[next_block->block_id] == nullptr && molecule->atom_block_ids[next_block->block_id]) {
            /* first time visiting location */

            /* find next primitive based on pattern connections, expand next primitive if not visited */
            if (cur->from_block == pack_pattern_block) {
                /* forward expand to find next block */
                int from_pin, from_port;
                from_pin = cur->from_pin->pin_number;
                from_port = cur->from_pin->port->port_index_by_type;
                cur_pin = &pb_graph_node->output_pins[from_port][from_pin];
                next_pin = expand_pack_molecule_pin_edge(pack_pattern_block->pattern_index, cur_pin, true);
            } else {
                /* backward expand to find next block */
                VTR_ASSERT(cur->to_block == pack_pattern_block);
                int to_pin, to_port;
                to_pin = cur->to_pin->pin_number;
                to_port = cur->to_pin->port->port_index_by_type;

                if (cur->from_pin->port->is_clock) {
                    cur_pin = &pb_graph_node->clock_pins[to_port][to_pin];
                } else {
                    cur_pin = &pb_graph_node->input_pins[to_port][to_pin];
                }
                next_pin = expand_pack_molecule_pin_edge(pack_pattern_block->pattern_index, cur_pin, false);
            }
            /* found next primitive */
            if (next_pin != nullptr) {
                next_primitive = next_pin->parent_node;
                /* Check for legality of placement, if legal, expand from legal placement, if not, return false */
                if (molecule->atom_block_ids[next_block->block_id] && primitives_list[next_block->block_id] == nullptr) {
                    if (next_primitive->cluster_placement_primitive->valid == true && primitive_type_feasible(molecule->atom_block_ids[next_block->block_id], next_primitive->pb_type)) {
                        primitives_list[next_block->block_id] = next_primitive;
                        *cost += next_primitive->cluster_placement_primitive->base_cost + next_primitive->cluster_placement_primitive->incremental_cost;
                        if (!expand_forced_pack_molecule_placement(molecule, next_block, primitives_list, cost)) {
                            return false;
                        }
                    } else {
                        return false;
                    }
                }
            } else {
                return false;
            }
        }
        cur = cur->next;
    }

    return true;
}

/**
 * Find next primitive pb_graph_pin
 */
static t_pb_graph_pin* expand_pack_molecule_pin_edge(const int pattern_id,
                                                     const t_pb_graph_pin* cur_pin,
                                                     const bool forward) {
    int i, j, k;
    t_pb_graph_pin *temp_pin, *dest_pin;
    temp_pin = nullptr;
    dest_pin = nullptr;
    if (forward) {
        for (i = 0; i < cur_pin->num_output_edges; i++) {
            /* one fanout assumption */
            if (cur_pin->output_edges[i]->infer_pattern) {
                for (k = 0; k < cur_pin->output_edges[i]->num_output_pins;
                     k++) {
                    if (cur_pin->output_edges[i]->output_pins[k]->parent_node->pb_type->num_modes
                        == 0) {
                        temp_pin = cur_pin->output_edges[i]->output_pins[k];
                    } else {
                        temp_pin = expand_pack_molecule_pin_edge(pattern_id,
                                                                 cur_pin->output_edges[i]->output_pins[k],
                                                                 forward);
                    }
                }
                if (temp_pin != nullptr) {
                    VTR_ASSERT(dest_pin == nullptr || dest_pin == temp_pin);
                    dest_pin = temp_pin;
                }
            } else {
                for (j = 0; j < cur_pin->output_edges[i]->num_pack_patterns;
                     j++) {
                    if (cur_pin->output_edges[i]->pack_pattern_indices[j]
                        == pattern_id) {
                        for (k = 0;
                             k < cur_pin->output_edges[i]->num_output_pins;
                             k++) {
                            if (cur_pin->output_edges[i]->output_pins[k]->parent_node->pb_type->num_modes
                                == 0) {
                                temp_pin = cur_pin->output_edges[i]->output_pins[k];
                            } else {
                                temp_pin = expand_pack_molecule_pin_edge(pattern_id,
                                                                         cur_pin->output_edges[i]->output_pins[k],
                                                                         forward);
                            }
                        }
                        if (temp_pin != nullptr) {
                            VTR_ASSERT(dest_pin == nullptr || dest_pin == temp_pin);
                            dest_pin = temp_pin;
                        }
                    }
                }
            }
        }
    } else {
        for (i = 0; i < cur_pin->num_input_edges; i++) {
            /* one fanout assumption */
            if (cur_pin->input_edges[i]->infer_pattern) {
                for (k = 0; k < cur_pin->input_edges[i]->num_input_pins; k++) {
                    if (cur_pin->input_edges[i]->input_pins[k]->parent_node->pb_type->num_modes
                        == 0) {
                        temp_pin = cur_pin->input_edges[i]->input_pins[k];
                    } else {
                        temp_pin = expand_pack_molecule_pin_edge(pattern_id,
                                                                 cur_pin->input_edges[i]->input_pins[k],
                                                                 forward);
                    }
                }
                if (temp_pin != nullptr) {
                    VTR_ASSERT(dest_pin == nullptr || dest_pin == temp_pin);
                    dest_pin = temp_pin;
                }
            } else {
                for (j = 0; j < cur_pin->input_edges[i]->num_pack_patterns;
                     j++) {
                    if (cur_pin->input_edges[i]->pack_pattern_indices[j]
                        == pattern_id) {
                        for (k = 0; k < cur_pin->input_edges[i]->num_input_pins;
                             k++) {
                            if (cur_pin->input_edges[i]->input_pins[k]->parent_node->pb_type->num_modes
                                == 0) {
                                temp_pin = cur_pin->input_edges[i]->input_pins[k];
                            } else {
                                temp_pin = expand_pack_molecule_pin_edge(pattern_id,
                                                                         cur_pin->input_edges[i]->input_pins[k],
                                                                         forward);
                            }
                        }
                        if (temp_pin != nullptr) {
                            VTR_ASSERT(dest_pin == nullptr || dest_pin == temp_pin);
                            dest_pin = temp_pin;
                        }
                    }
                }
            }
        }
    }
    return dest_pin;
}

static void flush_intermediate_queues(t_cluster_placement_stats* cluster_placement_stats) {
    t_cluster_placement_primitive *cur, *next;
    cur = cluster_placement_stats->tried;
    while (cur != nullptr) {
        next = cur->next_primitive;
        requeue_primitive(cluster_placement_stats, cur);
        cur = next;
    }
    cluster_placement_stats->tried = nullptr;

    cur = cluster_placement_stats->in_flight;
    if (cur != nullptr) {
        next = cur->next_primitive;
        requeue_primitive(cluster_placement_stats, cur);
        /* should have at most one block in flight at any point in time */
        VTR_ASSERT(next == nullptr);
    }
    cluster_placement_stats->in_flight = nullptr;
}

/* Determine max index + 1 of molecule */
int get_array_size_of_molecule(const t_pack_molecule* molecule) {
    if (molecule->type == MOLECULE_FORCED_PACK) {
        return molecule->pack_pattern->num_blocks;
    } else {
        return molecule->num_blocks;
    }
}

/* Given atom block, determines if a free primitive exists for it */
bool exists_free_primitive_for_atom_block(t_cluster_placement_stats* cluster_placement_stats,
                                          const AtomBlockId blk_id) {
    int i;
    t_cluster_placement_primitive *cur, *prev;

    /* might have a primitive in flight that's still valid */
    if (cluster_placement_stats->in_flight) {
        if (primitive_type_feasible(blk_id,
                                    cluster_placement_stats->in_flight->pb_graph_node->pb_type)) {
            return true;
        }
    }

    /* Look through list of available primitives to see if any valid */
    for (i = 0; i < cluster_placement_stats->num_pb_types; i++) {
        if (cluster_placement_stats->valid_primitives[i]->next_primitive == nullptr) {
            continue; /* no more primitives of this type available */
        }
        if (primitive_type_feasible(blk_id,
                                    cluster_placement_stats->valid_primitives[i]->next_primitive->pb_graph_node->pb_type)) {
            prev = cluster_placement_stats->valid_primitives[i];
            cur = cluster_placement_stats->valid_primitives[i]->next_primitive;
            while (cur) {
                /* remove invalid nodes lazily when encountered */
                while (cur && cur->valid == false) {
                    prev->next_primitive = cur->next_primitive;
                    cur->next_primitive = cluster_placement_stats->invalid;
                    cluster_placement_stats->invalid = cur;
                    cur = prev->next_primitive;
                }
                if (cur == nullptr) {
                    break;
                }
                return true;
            }
        }
    }

    return false;
}

void reset_tried_but_unused_cluster_placements(t_cluster_placement_stats* cluster_placement_stats) {
    flush_intermediate_queues(cluster_placement_stats);
}