/* 
 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 <queue>
using namespace std;

#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"
#include "pack_molecules.h"

/****************************************/
/*Local Datastrcture Declaration		*/
/****************************************/
struct MoleculePlaceInfo {
    bool legal = false;
    std::map<MoleculeBlockId,t_pb_graph_node*> block_locations;
    std::set<t_pb_graph_node*> used_pb_nodes;
    float cost = HUGE_POSITIVE_FLOAT;
};

/****************************************/
/*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 PackMolecules& molecules,
        const PackMoleculeId molecule_id,
        const MoleculeStats& molecule_stats,
		t_pb_graph_node *root,
        vtr::vector<MoleculeBlockId,t_pb_graph_node*>&  primitives_list);

static MoleculePlaceInfo try_place_molecule_recurr(const PackMolecule& molecule,
                                                   const MoleculeBlockId molecule_block, 
                                                   MoleculePlaceInfo partial_placement,
                                                   t_pb_graph_node* pb_node,
                                                   int depth=0);

static t_pb_graph_node* try_place_molecule_block(const PackMolecule& molecule, const MoleculeBlockId molecule_blk,
                                                 const MoleculePlaceInfo& partial_placement,
                                                 t_pb_graph_node* pb_node);

static bool molecule_block_upstream_connections_feasible(const PackMolecule& molecule, const MoleculeBlockId molecule_blk, 
                                                  const MoleculePlaceInfo& partial_placement, t_pb_graph_node* pb_node);

static bool cluster_routing_path_feasible(const t_pb_graph_pin* driver, const t_pb_graph_pin* sink);

static bool expand_forced_pack_molecule_placement(
		const t_pack_molecule *molecule,
		const t_pack_pattern_block *pack_pattern_block,
        vtr::vector<MoleculeBlockId,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);

static bool is_force_pack_molecule(const MoleculeStats& molecule_stats, const PackMoleculeId molecule_id);

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

/**
 * [0..num_pb_types-1] array of cluster placement stats, one for each device_ctx.block_types 
 */
std::vector<t_cluster_placement_stats> alloc_and_load_cluster_placement_stats() {
    auto& device_ctx = g_vpr_ctx.device();

    std::vector<t_cluster_placement_stats> cluster_placement_stats(device_ctx.num_block_types);

	for (int i = 0; i < device_ctx.num_block_types; i++) {
		if (device_ctx.EMPTY_TYPE != &device_ctx.block_types[i]) {
			cluster_placement_stats[i].valid_primitives = (t_cluster_placement_primitive **) vtr::calloc(
					get_max_primitives_in_pb_type(device_ctx.block_types[i].pb_type) + 1,
                    sizeof(t_cluster_placement_primitive*)); /* too much memory allocated but shouldn't be a problem */
			load_cluster_placement_stats_for_pb_graph_node(
					cluster_placement_stats[i],
					device_ctx.block_types[i].pb_graph_head);
		}
	}
	return cluster_placement_stats;
}

/**
 * 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
 *   - 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 PackMolecules& molecules,
		const PackMoleculeId molecule_id,
        const MoleculeStats& molecule_stats,
        vtr::vector<MoleculeBlockId,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_id) {
		/* New block, requeue tried primitives and in-flight primitives */
		flush_intermediate_queues(cluster_placement_stats);

		cluster_placement_stats.curr_molecule = molecule_id;
	} 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 */
		}
        t_pb_type* pb_type = cluster_placement_stats.valid_primitives[i]->next_primitive->pb_graph_node->pb_type;
        vtr::printf("Checking if molecule '%s' is feasible rooted at primitive '%s'\n", molecules.pack_molecules[molecule_id].name().c_str(), pb_type->name);
        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(
                    molecules,
                    molecule_id,
                    molecule_stats,
                    cur->pb_graph_node,
                    primitives_list);
            if (cost < lowest_cost) {
                lowest_cost = cost;
                best = cur;
                before_best = prev;
            }
            prev = cur;
            cur = cur->next_primitive;
        }
	}
	if (best == nullptr) {
		/* failed to find a placement */
        primitives_list.assign(primitives_list.size(), nullptr);
	} else {
		/* populate primitive list with best */
		cost = try_place_molecule(
                molecules,
                molecule_id,
                molecule_stats,
                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 = PackMoleculeId::INVALID();
}

/** 
 * Free linked lists found in cluster_placement_stats_list 
 */
void free_cluster_placement_stats(std::vector<t_cluster_placement_stats>& cluster_placement_stats_list) {
	t_cluster_placement_primitive *cur, *next;
	int i, j;
    auto& device_ctx = g_vpr_ctx.device();

	for (i = 0; i < device_ctx.num_block_types; i++) {
		cur = cluster_placement_stats_list[i].tried;
		while (cur != nullptr) {
			next = cur->next_primitive;
			free(cur);
			cur = next;
		}
		cur = cluster_placement_stats_list[i].in_flight;
		while (cur != nullptr) {
			next = cur->next_primitive;
			free(cur);
			cur = next;
		}
		cur = cluster_placement_stats_list[i].invalid;
		while (cur != nullptr) {
			next = cur->next_primitive;
			free(cur);
			cur = next;
		}
		for (j = 0; j < cluster_placement_stats_list[i].num_pb_types; j++) {
			cur =
					cluster_placement_stats_list[i].valid_primitives[j]->next_primitive;
			while (cur != nullptr) {
				next = cur->next_primitive;
				free(cur);
				cur = next;
			}
			free(cluster_placement_stats_list[i].valid_primitives[j]);
		}
		free(cluster_placement_stats_list[i].valid_primitives);
	}
}

/**
 * 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
 *               All 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->parent_pb_graph_node != nullptr) {
		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->pb_type->num_modes == 0) {
		/* 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 PackMolecules& molecules,
        const PackMoleculeId molecule_id,
        const MoleculeStats& /*molecule_stats*/,
		t_pb_graph_node *root,
        vtr::vector<MoleculeBlockId,t_pb_graph_node*>&  primitives_list) {

    const PackMolecule& molecule = molecules.pack_molecules[molecule_id];

    MoleculePlaceInfo empty_placement;
    empty_placement.legal = true;
    empty_placement.cost = 0.;

    vtr::printf(" Try place molecule at root %s\n", describe_pb_graph_node_hierarchy(root).c_str());

    MoleculePlaceInfo molecule_placement = try_place_molecule_recurr(molecule,
                                                                     molecule.root_block(),
                                                                     empty_placement,
                                                                     root,
                                                                     1);

    vtr::printf("    Proposed molecule placement: (cost %f)\n", molecule_placement.cost);
    if (molecule_placement.legal) {
        primitives_list.assign(molecule.blocks().size(), nullptr);

        for (auto molecule_blk : molecule.blocks()) {
            if (molecule_placement.block_locations.count(molecule_blk)) {
                t_pb_graph_node* loc = molecule_placement.block_locations[molecule_blk];    
                VTR_ASSERT(loc);

                primitives_list[molecule_blk] = loc;

                vtr::printf("      %zu: %s\n", size_t(molecule_blk), describe_pb_graph_node_hierarchy(primitives_list[molecule_blk]).c_str());
            } else {
                vtr::printf("      %zu: N/A\n", size_t(molecule_blk));
            }
        }
    } else {
        VTR_ASSERT(!molecule_placement.legal);
        VTR_ASSERT(molecule_placement.cost == HUGE_POSITIVE_FLOAT);
        vtr::printf("      NONE\n");
    }

    return molecule_placement.cost;
}

static MoleculePlaceInfo try_place_molecule_recurr(const PackMolecule& molecule, const MoleculeBlockId molecule_block, 
                                      MoleculePlaceInfo partial_placement,
                                      t_pb_graph_node* pb_node,
                                      int depth) {

    MoleculePlaceInfo placement = partial_placement;

    if (molecule.block_type(molecule_block) == PackMolecule::BlockType::EXTERNAL) {
        //Recurse down to internal blocks

        //For every molecule block subtree fanning out from the current external molecule block
        vtr::printf("%sPlacing sub-tree rooted at external molecule block %zu\n", vtr::indent(depth).c_str(), size_t(molecule_block));
        for (auto molecule_driver_pin_id : molecule.block_output_pins(molecule_block)) {
            auto molecule_edge_id = molecule.pin_edge(molecule_driver_pin_id);

            for (auto molecule_sink_pin_id : molecule.edge_sinks(molecule_edge_id)) {
                MoleculeBlockId molecule_subtree_block = molecule.pin_block(molecule_sink_pin_id);

                //See if the subtree is valid at the current pb_node
                MoleculePlaceInfo subtree_placement = try_place_molecule_recurr(molecule, molecule_subtree_block, placement, pb_node, depth+1);
                if (subtree_placement.legal) {
                    placement = subtree_placement;
                } else {
                    VTR_ASSERT(!subtree_placement.legal);
                    //No legal location found for the next molecule block subtree,
                    //so the entire molecule is illegal
                    return MoleculePlaceInfo();
                }
            }
        }
    } else {
        VTR_ASSERT(molecule.block_type(molecule_block) == PackMolecule::BlockType::INTERNAL);

        AtomBlockId atom_blk = molecule.block_atom(molecule_block);

        vtr::printf("%sTrying to place internal molecule block %zu (%s) in %s\n", vtr::indent(depth).c_str(), size_t(molecule_block),
                g_vpr_ctx.atom().nlist.block_model(atom_blk)->name,
                describe_pb_graph_node_hierarchy(pb_node).c_str());

        //Find a valid placement location for the atom associated with this block in the molecule
        t_pb_graph_node* atom_loc = try_place_molecule_block(molecule, molecule_block, placement, pb_node);

        if (atom_loc) {
            //Recursively try to place the sub-tree rooted at the current molecule block

            VTR_ASSERT(atom_loc->is_primitive());

            placement.legal = true;
            placement.block_locations.emplace(molecule_block,atom_loc);
            placement.used_pb_nodes.insert(atom_loc);

            vtr::printf("%sFound legal placement location of molecule block %zu in %s\n", vtr::indent(depth).c_str(), size_t(molecule_block), describe_pb_graph_node_hierarchy(atom_loc).c_str());
            vtr::printf("%sPlacing sub-tree rooted at internal molecule block %zu\n", vtr::indent(depth).c_str(), size_t(molecule_block));
            for (auto molecule_driver_pin_id : molecule.block_output_pins(molecule_block)) {
                auto molecule_edge_id = molecule.pin_edge(molecule_driver_pin_id);

                for (auto molecule_sink_pin_id : molecule.edge_sinks(molecule_edge_id)) {
                    MoleculeBlockId molecule_subtree_block = molecule.pin_block(molecule_sink_pin_id);

                    //Try placing the molecule sub-tree within the same parent as the current atom,
                    //if it isn't valid, retry placing into the grand-parent pb node (this is done
                    //repeatedly up to the root).
                    //
                    //This ensures that atoms prefer to stay in the same parent pb_node if possible
                    t_pb_graph_node* subtree_pb_node = atom_loc->parent_pb_graph_node;
                    MoleculePlaceInfo subtree_placement;
                    while (!subtree_placement.legal && subtree_pb_node != nullptr) {
                        subtree_placement = try_place_molecule_recurr(molecule, molecule_subtree_block, placement, subtree_pb_node, depth+1);
                        subtree_pb_node = subtree_pb_node->parent_pb_graph_node; //Next parent
                    }

                    if (subtree_placement.legal) {
                        placement = subtree_placement;
                    } else {
                        //No valid placement possible for this subtree.
                        //This implies the molecule placement at the current atom location is illegal.
                        return MoleculePlaceInfo();
                    }
                }
            }
        } else {
            //No valid internal block location
            placement = MoleculePlaceInfo(); //Invalid
        }
    }
    return placement;
}

static t_pb_graph_node* try_place_molecule_block(const PackMolecule& molecule, const MoleculeBlockId molecule_blk,
                                                 const MoleculePlaceInfo& partial_placement,
                                                 t_pb_graph_node* pb_node) {
    if (partial_placement.used_pb_nodes.count(pb_node)) {
        return nullptr; //Already in use
    }

    if (pb_node->is_primitive()) {
        if (pb_node->cluster_placement_primitive->valid
            && primitive_type_feasible(molecule.block_atom(molecule_blk), pb_node->pb_type)
            && molecule_block_upstream_connections_feasible(molecule, molecule_blk, partial_placement, pb_node)) {
            return pb_node; //Primitive match
        }

        return nullptr; //Primitive mismatch
    }

    //Not primitive, recursively search children
    //
    //TODO: Could speed-up by tracing pack pattern annotations in arch,
    //      instead of enumerating legal placements (?)
    VTR_ASSERT(!pb_node->is_primitive());

    for (int imode = 0; imode < pb_node->num_modes(); ++imode) {
        for (int ichild_type = 0; ichild_type < pb_node->num_pb_type_children(imode); ++ichild_type) {
            for (int ichild = 0; ichild < pb_node->num_pb_type_child_pb(imode, ichild_type); ++ichild) {
                t_pb_graph_node *child_pb_node = &pb_node->child_pb_graph_nodes[imode][ichild_type][ichild];
                t_pb_graph_node* legal_child = try_place_molecule_block(molecule, molecule_blk, partial_placement, child_pb_node); 
                if (legal_child) { //Legal within child sub-nodes
                    return legal_child;
                }
            }
        }
    }

    return nullptr; //No match within children
}

static bool molecule_block_upstream_connections_feasible(const PackMolecule& molecule, const MoleculeBlockId molecule_blk, 
                                                  const MoleculePlaceInfo& partial_placement, t_pb_graph_node* pb_node) {
    for (auto molecule_sink_pin : molecule.block_input_pins(molecule_blk)) {
        auto molecule_edge = molecule.pin_edge(molecule_sink_pin);
        auto molecule_driver_pin = molecule.edge_driver(molecule_edge);
        auto molecule_driver_blk = molecule.pin_block(molecule_driver_pin);

        const t_pb_graph_pin* sink_pin = find_corresponding_pb_graph_pin(pb_node, molecule.pin_atom(molecule_sink_pin));
        VTR_ASSERT(sink_pin);

        //Verify there is a path from src to sink
        const t_pb_graph_pin* driver_pin = nullptr;
        auto itr = partial_placement.block_locations.find(molecule_driver_blk);
        if (itr == partial_placement.block_locations.end()) {
            //External block connection

            //TODO: instead of skipping check, verify that 'correct' top-level pin can reach the corresponding sink
            continue;
        } else {
            VTR_ASSERT(itr != partial_placement.block_locations.end());
            t_pb_graph_node* driver_loc = itr->second;

            driver_pin = find_corresponding_pb_graph_pin(driver_loc, molecule.pin_atom(molecule_driver_pin));
        }
        VTR_ASSERT(driver_pin);

        if (!cluster_routing_path_feasible(driver_pin, sink_pin)) {
            return false; //Infeasible
        }
    }

    return true; //Feasible
}

static bool cluster_routing_path_feasible(const t_pb_graph_pin* driver, const t_pb_graph_pin* sink) {
    //Simple BFS (for now) from driver to sink
    std::queue<const t_pb_graph_pin*> q;
    q.push(driver);

    while (!q.empty()) {
        const t_pb_graph_pin* pin = q.front();
        q.pop();

        if (pin == sink) return true;

        //Expand neighbours
        for (int iedge = 0; iedge < pin->num_output_edges; ++iedge) {
            t_pb_graph_edge* edge = pin->output_edges[iedge];

            for (int ipin = 0; ipin < edge->num_output_pins; ++ipin) {
                t_pb_graph_pin* sink_pin = edge->output_pins[ipin];
                q.push(sink_pin);
            }
        }
    }

    return false; //No path
}

/**
 * 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);
}

static bool is_force_pack_molecule(const MoleculeStats& molecule_stats, const PackMoleculeId molecule_id) {
    return molecule_stats.num_blocks(molecule_id) > 1;
}