netlist.h

#pragma once
/**
 * @file
 * @brief This file defines the Netlist class, which stores the connectivity information
 * of the components in a netlist. It is the base class for AtomNetlist and ClusteredNetlist.
 *
 * Overview
 * ========
 * The netlist logically consists of several different components: Blocks, Ports, Pins and Nets
 * Each component in the netlist has a unique template identifier (BlockId, PortId, PinId, NetId)
 * used to retrieve information about it. In this implementation these ID's are unique throughout the
 * netlist (i.e. every port in the netlist has a unique ID, even if the ports share a common type).
 *
 * Block
 * -----
 * A Block is the primitive netlist element (a node in the netlist hyper-graph).
 * Blocks have various attributes (a name, a type etc.) and are associated with sets of
 * input/output/clock ports.
 *
 * Block related information can be retrieved using the block_*() member functions.
 *
 * Pins
 * ----
 * Pins define single-bit connections between a block and a net.
 *
 * Pin related information can be retrieved using the pin_*() member functions.
 *
 * Nets
 * ----
 * Nets represent the connections between blocks (the edges of the netlist hyper-graph).
 * Each net has a single driver pin, and a set of sink pins.
 *
 * Net related information can be retrieved using the net_*() member functions.
 *
 * Ports
 * -----
 * A Port is a (potentially multi-bit) group of pins.
 *
 * For example, the two operands and output of an N-bit adder would logically be grouped as three ports.
 * Ports have a specified bit-width which defines how many pins form the port.
 *
 * Port related information can be retrieved using the port_*() member functions.
 *
 *
 * Usage
 * =====
 *
 * The following provides usage examples for common use-cases.
 *
 * Walking the netlist
 * -------------------
 * To iterate over the whole netlist use the blocks() and/or nets() member functions:
 *
 *      Netlist netlist;
 *
 *      //... initialize the netlist
 *
 *      //Iterate over all the blocks
 *      for(BlockId blk_id : netlist.blocks()) {
 *          //Do something with each block
 *      }
 *
 *
 *      //Iterate over all the nets
 *      for(NetId net_id : netlist.nets()) {
 *          //Do something with each net
 *      }
 *
 * To retrieve information about a netlist component call one of the associated member functions:
 *
 *      //Print out each block's name
 *      for(BlockId blk_id : netlist.blocks()) {
 *
 *          //Get the block name
 *          const std::string& block_name = netlist.block_name(blk_id);
 *
 *          //Print it
 *          printf("Block: %s\n", block_name.c_str());
 *      }
 *
 * Note that the member functions are associated with the type of component (e.g. block_name() yields
 * the name of a block, net_name() yields the name of a net).
 *
 * Tracing cross-references
 * ------------------------
 * It is common to need to trace the netlist connectivity. The Netlist allows this to be done
 * efficiently by maintaining cross-references between the various netlist components.
 *
 * The following diagram shows the main methods and relationships between netlist components:
 * ```
 *              +---------+      pin_block()
 *              |         |<--------------------------+
 *              |  Block  |                           |
 *              |         |-----------------------+   |
 *              +---------+      block_pins()     |   |
 *                 |   ^                          v   |
 *                 |   |                       +---------+  net_pins()  +---------+
 *                 |   |                       |         |<-------------|         |
 *   block_ports() |   | port_block()          |   Pin   |              |   Net   |
 *                 |   |                       |         |------------->|         |
 *                 |   |                       +---------+  pin_net()   +---------+
 *                 v   |                          ^   |
 *              +---------+      port_pins()      |   |
 *              |         |-----------------------+   |
 *              |  Port   |                           |
 *              |         |<--------------------------+
 *              +---------+      pin_port()
 * ```
 * <!-- NOTE: Markdown ``` are used to display the code properly in the documentation -->
 *
 * Note that methods which are plurals (e.g. net_pins()) return multiple components.
 *
 * As an example consider the case where we wish to find all the blocks associated with a particular net:
 *
 *      NetId net_id;
 *
 *      //... Initialize net_id with the net of interest
 *
 *      //Iterate through each pin on the net to get the associated port
 *      for(PinId pin_id : netlist.net_pins(net_id)) {
 *
 *          //Get the port associated with the pin
 *          PortId port_id = netlist.pin_port(pin_id);
 *
 *          //Get the block associated with the port
 *          BlockId blk_id = netlist.port_block(port_id);
 *
 *          //Print out the block name
 *          const std::string& block_name = netlist.block_name(blk_id);
 *          printf("Associated block: %s\n", block_name.c_str());
 *      }
 *
 * Netlist also defines some convenience functions for common operations to avoid tracking the intermediate IDs
 * if they are not needed. The following produces the same result as above:
 *
 *      NetId net_id;
 *
 *      //... Initialize net_id with the net of interest
 *
 *      //Iterate through each pin on the net to get the associated port
 *      for(PinId pin_id : netlist.net_pins(net_id)) {
 *
 *          //Get the block associated with the pin (bypassing the port)
 *          BlockId blk_id = netlist.pin_block(pin_id);
 *
 *          //Print out the block name
 *          const std::string& block_name = netlist.block_name(blk_id);
 *          printf("Associated block: %s\n", block_name.c_str());
 *      }
 *
 *
 * As another example, consider the inverse problem of identifying the nets connected as inputs to a particular block:
 *
 *      BlkId blk_id;
 *
 *      //... Initialize blk_id with the block of interest
 *
 *      //Iterate through the ports
 *      for(PortId port_id : netlist.block_input_ports(blk_id)) {
 *
 *          //Iterate through the pins
 *          for(PinId pin_id : netlist.port_pins(port_id)) {
 *              //Retrieve the net
 *              NetId net_id = netlist.pin_net(pin_id);
 *
 *              //Get its name
 *              const std::string& net_name = netlist.net_name(net_id);
 *              printf("Associated net: %s\n", net_name.c_str());
 *          }
 *      }
 *
 * Here we used the block_input_ports() method which returned an iterable range of all the input ports
 * associated with blk_id. We then used the port_pins() method to get iterable ranges of all the pins
 * associated with each port, from which we can find the associated net.
 *
 * Often port information is not relevant so this can be further simplified by iterating over a block's pins
 * directly (e.g. by calling one of the block_*_pins() functions):
 *
 *      BlkId blk_id;
 *
 *      //... Initialize blk_id with the block of interest
 *
 *      //Iterate over the blocks ports directly
 *      for(PinId pin_id : netlist.block_input_pins(blk_id)) {
 *
 *          //Retrieve the net
 *          NetId net_id = netlist.pin_net(pin_id);
 *
 *          //Get its name
 *          const std::string& net_name = netlist.net_name(net_id);
 *          printf("Associated net: %s\n", net_name.c_str());
 *      }
 *
 * Note the use of range-based-for loops in the above examples; it could also have written (more verbosely)
 * using a conventional for loop and explicit iterators as follows:
 *
 *      BlkId blk_id;
 *
 *      //... Initialize blk_id with the block of interest
 *
 *      //Iterate over the blocks ports directly
 *      auto pins = netlist.block_input_pins(blk_id);
 *      for(auto pin_iter = pins.begin(); pin_iter != pins.end(); ++pin_iter) {
 *
 *          //Retrieve the net
 *          NetId net_id = netlist.pin_net(*pin_iter);
 *
 *          //Get its name
 *          const std::string& net_name = netlist.net_name(net_id);
 *          printf("Associated net: %s\n", net_name.c_str());
 *      }
 *
 *
 * Creating the netlist
 * --------------------
 * The netlist can be created by using the create_*() member functions to create individual Blocks/Ports/Pins/Nets.
 *
 * For instance to create the following netlist (where each block is the same type, and has an input port 'A'
 * and output port 'B'):
 *
 *      -----------        net1         -----------
 *      | block_1 |-------------------->| block_2 |
 *      -----------          |          -----------
 *                           |
 *                           |          -----------
 *                           ---------->| block_3 |
 *                                      -----------
 * We could do the following:
 *
 *      const t_model* blk_model = .... //Initialize the block model appropriately
 *
 *      Netlist netlist("my_netlist"); //Initialize the netlist with name 'my_netlist'
 *
 *      //Create the first block
 *      BlockId blk1 = netlist.create_block("block_1", blk_model);
 *
 *      //Create the first block's output port
 *      //  Note that the input/output/clock type of the port is determined
 *      //  automatically from the block model
 *      PortId blk1_out = netlist.create_port(blk1, "B");
 *
 *      //Create the net
 *      NetId net1 = netlist.create_net("net1");
 *
 *      //Associate the net with blk1
 *      netlist.create_pin(blk1_out, 0, net1, PinType::DRIVER);
 *
 *      //Create block 2 and hook it up to net1
 *      BlockId blk2 = netlist.create_block("block_2", blk_model);
 *      PortId blk2_in = netlist.create_port(blk2, "A");
 *      netlist.create_pin(blk2_in, 0, net1, PinType::SINK);
 *
 *      //Create block 3 and hook it up to net1
 *      BlockId blk3 = netlist.create_block("block_3", blk_model);
 *      PortId blk3_in = netlist.create_port(blk3, "A");
 *      netlist.create_pin(blk3_in, 0, net1, PinType::SINK);
 *
 * Modifying the netlist
 * ---------------------
 * The netlist can also be modified by using the remove_*() member functions. If we wanted to remove
 * block_3 from the netlist creation example above we could do the following:
 *
 *      //Mark blk3 and any references to it invalid
 *      netlist.remove_block(blk3);
 *
 *      //Compress the netlist to actually remove the data associated with blk3
 *      // NOTE: This will invalidate all client held IDs (e.g. blk1, blk1_out, net1, blk2, blk2_in)
 *      netlist.compress();
 *
 * The resulting netlist connectivity now looks like:
 *
 *      -----------        net1         -----------
 *      | block_1 |-------------------->| block_2 |
 *      -----------                     -----------
 *
 * Note that until compress() is called any 'removed' elements will have invalid IDs (e.g. BlockId::INVALID()).
 * As a result after calling remove_block() (which invalidates blk3) we *then* called compress() to remove the
 * invalid IDs.
 *
 * Also note that compress() is relatively slow. As a result avoid calling compress() after every call to
 * a remove_*() function, and instead batch up calls to remove_*() and call compress() only after a set of
 * modifications have been applied.
 *
 * Verifying the netlist
 * ---------------------
 * Particularly after construction and/or modification it is a good idea to check that the netlist is in
 * a valid and consistent state. This can be done with the verify() member function:
 *
 *      netlist.verify()
 *
 * If the netlist is not valid verify() will throw an exception, otherwise it returns true.
 *
 * Invariants
 * ==========
 * The Netlist maintains stronger invariants if the netlist is in compressed form.
 *
 * Netlist is compressed ('not dirty')
 * -----------------------------------
 * If the netlist is compressed (i.e. !is_dirty(), meaning there have been NO calls to remove_*() since the last call to
 * compress()) the following invariant will hold:
 *      - Any range returned will contain only valid IDs
 *
 * In practise this means the following conditions hold:
 *      - Blocks will not contain empty ports/pins (e.g. ports with no pin/net connections)
 *      - Ports will not contain pins with no associated net
 *      - Nets will not contain invalid sink pins
 *
 * This means that no error checking for invalid IDs is needed if simply iterating through netlist (see below for
 * some exceptions).
 *
 * NOTE: you may still encounter invalid IDs in the following cases:
 *      - net_driver() will return an invalid ID if the net is undriven
 *      - port_pin()/port_net() will return an invalid ID if the bit index corresponds to an unconnected pin
 *
 * Netlist is NOT compressed ('dirty')
 * -----------------------------------
 * If the netlist is not compressed (i.e. is_dirty(), meaning there have been calls to remove_*() with no subsequent
 * calls to compress()) then the invariant above does not hold.
 *
 * Any range may return invalid IDs. In practise this means,
 *      - Blocks may contain invalid ports/pins
 *      - Ports may contain invalid pins
 *      - Pins may not have a valid associated net
 *      - Nets may contain invalid sink pins
 *
 * Implementation Details
 * ======================
 * The netlist is stored in Struct-of-Arrays format rather than the more conventional Array-of-Structs.
 * This improves cache locality by keeping component attributes of the same type in contiguous memory.
 * This prevents unneeded member data from being pulled into the cache (since most code accesses only a few
 * attributes at a time this tends to be more efficient).
 *
 * Clients of this class pass nearly-opaque IDs (BlockId, PortId, PinId, NetId, StringId) to retrieve
 * information. The ID is internally converted to an index to retrieve the required value from it's associated storage.
 *
 * By using nearly-opaque IDs we can change the underlying data layout as need to optimize performance/memory, without
 * disrupting client code.
 *
 * Strings
 * -------
 * To minimize memory usage, we store each unique string only once in the netlist and give it a unique ID (StringId).
 * Any references to this string then make use of the StringId.
 *
 * In particular this prevents the (potentially large) strings from begin duplicated multiple times in various look-ups,
 * instead the more space efficient StringId is duplicated.
 *
 * Note that StringId is an internal implementation detail and should not be exposed as part of the public interface.
 * Any public functions should take and return std::string's instead.
 *
 * Block pins/Block ports data layout
 * ----------------------------------
 * The pins/ports for each block are stored in a similar manner, for brevity we describe only pins here.
 *
 * The pins for each block (i.e. PinId's) are stored in a single vector for each block (the block_pins_ member).
 * This allows us to iterate over all pins (i.e. block_pins()), or specific subsets of pins (e.g. only inputs with
 * block_input_pins()).
 *
 * To accomplish this all pins of the same group (input/output/clock) are located next to each other. An example is
 * shown below, where the block has n input pins, m output pins and k clock pins.
 *
 * ```
 *  -------------------------------------------------------------------------------------------------------------------
 *  | ipin_1 | ipin_2 | ... | ipin_n | opin_1 | opin_2 | ... | opin_m | clock_pin_1 | clock_pin_2 | ... | clock_pin_k |
 *  -------------------------------------------------------------------------------------------------------------------
 *  ^                                ^                                ^                                               ^
 *  |                                |                                |                                               |
 * begin                         opin_begin                    clock_pin_begin                                       end
 * ```
 *
 * Provided we know the internal dividing points (i.e. opin_begin and clock_pin_begin) we can easily build the various
 * ranges of interest:
 *
 *      all pins   : [begin, end)
 *      input pins : [begin, opin_begin)
 *      output pins: [opin_begin, clock_pin_begin)
 *      clock pins : [clock_pin_begin, end)
 *
 * Since any reallocation would invalidate any iterators to these internal dividers, we separately store the number
 * of input/output/clock pins per block (i.e. in block_num_input_pins_, block_num_output_pins_ and
 * block_num_clock_pins_). The internal dividers can then be easily calculated (e.g. see block_output_pins()), even
 * if new pins are inserted (provided the counts are updated).
 *
 * Adding data to the netlist
 * --------------------------
 * The Netlist should contain only information directly related to the netlist state (i.e. netlist connectivity).
 * Various mappings to/from elements (e.g. what CLB contains an atom block), and algorithmic state (e.g. if a net
 * is routed) do NOT constitute netlist state and should NOT be stored here.
 *
 * Such implementation state should be stored in other data structures (which may reference the Netlist's IDs).
 *
 * The netlist state should be immutable (i.e. read-only) for most of the CAD flow.
 *
 * Interactions with other netlists
 * --------------------------------
 * Currently, the AtomNetlist and ClusteredNetlist are both derived from Netlist. The AtomNetlist has primitive
 * specific details (t_model, TruthTable), and handles all operations with the atoms. The ClusteredNetlist
 * contains information on the CLB (Clustered Logic Block) level, which includes the physical description of the
 * blocks (t_logical_block_type), as well as the internal hierarchy and wiring (t_pb/t_pb_route).
 *
 * The calling-conventions of the functions in the AtomNetlist and ClusteredNetlist is as follows:
 *
 *    Functions where the derived class (Atom/Clustered) calls the base class (Netlist)
 *       create_*()
 *
 *    Functions where the base class calls the derived class (Non-Virtual Interface idiom as described
 *    https://en.wikibooks.org/wiki/More_C%2B%2B_Idioms/Non-Virtual_Interface)
 *       remove_*()
 *       clean_*()
 *       validate_*_sizes()
 *       shrink_to_fit()
 *    The derived functions based off of the virtual functions have suffix *_impl()
 *
 */
#include <ranges>
#include <string>
#include <vector>
#include <unordered_map>
#include "vtr_range.h"
#include "vtr_vector_map.h"

#include "netlist_fwd.h"

//Forward declaration for private methods
template<typename BlockId, typename PortId, typename PinId, typename NetId>
class NetlistIdRemapper {
  public:
    BlockId new_block_id(BlockId old_blk) const;
    PortId new_port_id(PortId old_port) const;
    PinId new_pin_id(PinId old_pin) const;
    NetId new_net_id(NetId old_net) const;

  private:
    friend Netlist<BlockId, PortId, PinId, NetId>;

    vtr::vector_map<BlockId, BlockId> block_id_map_;
    vtr::vector_map<PortId, PortId> port_id_map_;
    vtr::vector_map<PinId, PinId> pin_id_map_;
    vtr::vector_map<NetId, NetId> net_id_map_;
};

template<typename BlockId = ParentBlockId, typename PortId = ParentPortId, typename PinId = ParentPinId, typename NetId = ParentNetId>
class Netlist {
  public: //Public Types
    typedef typename vtr::vector_map<BlockId, BlockId>::const_iterator block_iterator;
    typedef typename std::unordered_map<std::string, std::string>::const_iterator attr_iterator;
    typedef typename std::unordered_map<std::string, std::string>::const_iterator param_iterator;
    typedef typename vtr::vector_map<NetId, NetId>::const_iterator net_iterator;
    typedef typename vtr::vector_map<PinId, PinId>::const_iterator pin_iterator;
    typedef typename vtr::vector_map<PortId, PortId>::const_iterator port_iterator;

    typedef typename vtr::Range<block_iterator> block_range;
    typedef typename vtr::Range<attr_iterator> attr_range;
    typedef typename vtr::Range<param_iterator> param_range;
    typedef typename vtr::Range<net_iterator> net_range;
    typedef typename vtr::Range<pin_iterator> pin_range;
    typedef typename vtr::Range<port_iterator> port_range;

    typedef NetlistIdRemapper<BlockId, PortId, PinId, NetId> IdRemapper;

  public:
    Netlist(std::string name = "", std::string id = "");
    virtual ~Netlist();

  public: //Public Accessors
    /*
     * Netlist
     */
    ///@brief Retrieve the name of the netlist
    const std::string& netlist_name() const;

    /**
     * @brief Retrieve the unique identifier for this netlist
     *        This is typically a secure digest of the input file.
     */
    const std::string& netlist_id() const;

    /*
     * Utility
     */

    ///@brief Sanity check for internal consistency (throws an exception on failure)
    bool verify() const;

    ///@brief Returns true if the netlist has invalid entries due to modifications (e.g. from remove_*() calls)
    bool is_dirty() const;

    /**
     * @brief  Returns true if the netlist has *no* invalid entries due to modifications (e.g. from remove_*() calls)
     * @note   This is a convenience method which is the logical inverse of is_dirty()
     */
    bool is_compressed() const;

    ///@brief Returns whether the net is ignored i.e. not routed
    bool net_is_ignored(const NetId id) const;

    ///@brief Returns whether the net is global
    bool net_is_global(const NetId id) const;

    ///@brief Item counts and container info (for debugging)
    void print_stats() const;

    /*
     * Blocks
     */

    ///@brief Returns the name of the specified block
    const std::string& block_name(const BlockId blk_id) const;

    ///@brief Returns true if the block is purely combinational (i.e. no input clocks and not a primary input
    bool block_is_combinational(const BlockId blk_id) const;

    ///@brief Returns a range of all attributes associated with the specified block
    attr_range block_attrs(const BlockId blk_id) const;

    ///@brief Returns a range of all parameters associated with the specified block
    param_range block_params(const BlockId blk_id) const;

    ///@brief Returns a range of all pins associated with the specified block
    pin_range block_pins(const BlockId blk_id) const;

    ///@brief Returns a range of all input pins associated with the specified block
    pin_range block_input_pins(const BlockId blk_id) const;

    /**
     * @brief Returns a range of all output pins associated with the specified block
     *
     * @note  This is typically only data pins, but some blocks (e.g. PLLs) can produce outputs
     *        which are clocks.
     */
    pin_range block_output_pins(const BlockId blk_id) const;

    ///@brief Returns a range of all clock pins associated with the specified block
    pin_range block_clock_pins(const BlockId blk_id) const;

    ///@brief Returns a range of all ports associated with the specified block
    port_range block_ports(const BlockId blk_id) const;

    ///@brief Returns a range consisting of the input ports associated with the specified block
    port_range block_input_ports(const BlockId blk_id) const;

    /**
     * @brief Returns a range consisting of the output ports associated with the specified block
     *
     * @note  This is typically only data ports, but some blocks (e.g. PLLs) can produce outputs
     *        which are clocks.
     */
    port_range block_output_ports(const BlockId blk_id) const;

    ///@brief Returns a range consisting of the input clock ports associated with the specified block
    port_range block_clock_ports(const BlockId blk_id) const;

    /**
     * @brief Removes a block from the netlist. This will also remove the associated ports and pins.
     *
     *   @param blk_id   The block to be removed
     */
    void remove_block(const BlockId blk_id);

    /*
     * Ports
     */

    ///@brief Returns the name of the specified port
    const std::string& port_name(const PortId port_id) const;

    ///@brief Returns the block associated with the specified port
    BlockId port_block(const PortId port_id) const;

    ///@brief Returns the set of valid pins associated with the port
    pin_range port_pins(const PortId port_id) const;

    /**
     * @brief Returns the pin (potentially invalid) associated with the specified port and port bit index
     *
     *   @param port_id   The ID of the associated port
     *   @param port_bit  The bit index of the pin in the port
     *
     * @note This function is a synonym for find_pin()
     */
    PinId port_pin(const PortId port_id, const BitIndex port_bit) const;

    /**
     * @brief Returns the net (potentially invalid) associated with the specified port and port bit index
     *
     *   @param port_id   The ID of the associated port
     *   @param port_bit  The bit index of the pin in the port
     */
    NetId port_net(const PortId port_id, const BitIndex port_bit) const;

    ///@brief Returns the width (number of bits) in the specified port
    BitIndex port_width(const PortId port_id) const;

    ///@brief Returns the type of the specified port
    PortType port_type(const PortId port_id) const;

    /** @brief Removes a port from the netlist.
     *
     * The port's pins are also marked invalid and removed from any associated nets
     *   @param port_id   The ID of the port to be removed
     */
    void remove_port(const PortId port_id);

    /*
     * Pins
     */

    ///@brief Returns the constructed name (derived from block and port) for the specified pin
    std::string pin_name(const PinId pin_id) const;

    ///@brief Returns the type of the specified pin
    PinType pin_type(const PinId pin_id) const;

    ///@brief Returns the net associated with the specified pin
    NetId pin_net(const PinId pin_id) const;

    ///@brief Returns the index of the specified pin within it's connected net
    int pin_net_index(const PinId pin_id) const;

    ///@brief Returns the port associated with the specified pin
    PortId pin_port(const PinId pin_id) const;

    ///@brief Returns the port bit index associated with the specified pin
    BitIndex pin_port_bit(const PinId pin_id) const;

    ///@brief Returns the block associated with the specified pin
    BlockId pin_block(const PinId pin_id) const;

    ///@brief Returns the port type associated with the specified pin
    PortType pin_port_type(const PinId pin_id) const;

    ///@brief Returns true if the pin is a constant (i.e. its value never changes)
    bool pin_is_constant(const PinId pin_id) const;

    /**
     * @brief Removes a pin from the netlist.
     *
     * The pin is marked invalid, and removed from any associated nets
     *   @param pin_id   The pin_id of the pin to be removed
     */
    void remove_pin(const PinId pin_id);

    /*
     * Nets
     */

    ///@brief Returns the name of the specified net
    const std::string& net_name(const NetId net_id) const;

    /**
     * @brief Returns a range consisting of all the pins in the net (driver and sinks)
     *
     * The first element in the range is the driver (and may be invalid)
     * The remaining elements (potentially none) are the sinks
     */
    pin_range net_pins(const NetId net_id) const;

    ///@brief Returns the net_pin_index'th pin of the specified net
    PinId net_pin(const NetId net_id, int net_pin_index) const;

    ///@brief Returns the block associated with the net_pin_index'th pin of the specified net
    BlockId net_pin_block(const NetId net_id, int net_pin_index) const;

    ///@brief Returns the (potentially invalid) net driver pin
    PinId net_driver(const NetId net_id) const;

    ///@brief Returns the (potentially invalid) net driver block
    BlockId net_driver_block(const NetId net_id) const;

    ///@brief Returns a (potentially empty) range consisting of net's sink pins
    pin_range net_sinks(const NetId net_id) const;

    ///@brief Returns true if the net is driven by a constant pin (i.e. its value never changes)
    bool net_is_constant(const NetId net_id) const;

    /**
     * @brief Removes a net from the netlist.
     *
     * This will mark the net's pins as having no associated.
     *   @param net_id   The net to be removed
     */
    void remove_net(const NetId net_id);

    /**
     * @brief Removes a connection between a net and pin.
     *
     * The pin is removed from the net and the pin
     * will be marked as having no associated net
     *   @param net_id   The net from which the pin is to be removed
     *   @param pin_id   The pin to be removed from the net
     */
    void remove_net_pin(const NetId net_id, const PinId pin_id);

    /*
     * Aggregates
     */

    ///@brief Returns a range consisting of all blocks in the netlist
    block_range blocks() const;

    ///@brief Returns a range consisting of all ports in the netlist
    port_range ports() const;

    ///@brief Returns a range consisting of all nets in the netlist
    net_range nets() const;

    ///@brief Returns a view over the nets that are not ignored.
    auto non_ignored_nets() const {
        return nets() | std::views::filter([this](NetId net_id) { return !net_is_ignored(net_id); });
    }

    ///@brief Returns a range consisting of all pins in the netlist
    pin_range pins() const;

    /*
     * ID Checks
     *
     * Validates that the specified ID is valid in the current netlist state
     */
    bool valid_block_id(BlockId block_id) const;
    bool valid_port_id(PortId port_id) const;
    bool valid_port_bit(PortId port_id, BitIndex port_bit) const;
    bool valid_pin_id(PinId pin_id) const;
    bool valid_net_id(NetId net_id) const;

    /*
     * Lookups
     */

    /**
     * @brief Returns the BlockId of the specified block or BlockId::INVALID() if not found
     *
     *   @param name   The name of the block
     */
    BlockId find_block(const std::string& name) const;

    /**
     * @brief Finds a block where the block's name contains the
     *        provided input name as a substring. 
     *        The intended use is to find the block id of a 
     *        hard block without knowing its name in the netlist. Instead
     *        the block's module name in the HDL design can be used as it will
     *        be a substring within its full name in the netlist.
     * 
     *        For example, suppose a RAM block was named in the netlist as
     *        "top|alu|test_ram|out". The user instantiated the ram module
     *        in the HDL design as "test_ram". So instead of going through 
     *        the netlist and finding the ram block's full name, this
     *        function can be used by just providing the module name "test_ram"
     *        and using this substring to match the blocks name in the netlist
     *        and retrieving its block id. If no blocks matched to input pattern
     *        then an invalid block id is returned.
     * 
     *        This function runs in linear time (O(N)) as it goes over all the 
     *        cluster blocks in the netlist. Additionally, if there are multiple
     *        blocks that contain the provided input as a substring, then the
     *        first block found is returned.
     * 
     *        NOTE: This function tries to find blocks by checking for 
     *              substrings.
     *              The clustered netlist class defines another version of this
     *              function that find blocks by checking for a pattern match,
     *              meaning that the input is a pattern string and the pattern
     *              is looked for in each block name.
     * 
     * @param name_substring A substring of a block name for which an ID needs  
     *             to be found.
     * @return A cluster block id representing a unique cluster block that 
     *         matched to the input string pattern.
     *        
     */
    BlockId find_block_by_name_fragment(const std::string& name_substring) const;

    /**
     * @brief Returns the PortId of the specified port if it exists or PortId::INVALID() if not
     *
     * @note  This method is typically less efficient than searching by a t_model_port
     *        With the overloaded AtomNetlist method
     *   @param blk_id   The ID of the block who's ports will be checked
     *   @param name     The name of the port to look for
     */
    PortId find_port(const BlockId blk_id, const std::string& name) const;

    /**
     * @brief Returns the NetId of the specified net or NetId::INVALID() if not found
     *   @param name   The name of the net
     */
    NetId find_net(const std::string& name) const;

    /**
     * @brief Returns the PinId of the specified pin or PinId::INVALID() if not found
     *
     *   @param port_id   The ID of the associated port
     *   @param port_bit  The bit index of the pin in the port
     */
    PinId find_pin(const PortId port_id, BitIndex port_bit) const;

    /**
     * @brief Returns the PinId of the specified pin or PinId::INVALID() if not found
     *
     * @note  This method is SLOW, O(num_pins) -- avoid if possible
     *   @param name   The name of the pin
     */
    PinId find_pin(const std::string name) const;

  public: //Public Mutators
    /**
     * @brief Add the specified pin to the specified net as pin_type.
     *
     * Automatically removes any previous net connection for this pin.
     *   @param pin        The pin to add
     *   @param pin_type   The type of the pin (i.e. driver or sink)
     *   @param net        The net to add the pin to
     */
    void set_pin_net(const PinId pin, PinType pin_type, const NetId net);

    /**
     * @brief Mark a pin as being a constant generator.
     *
     * There are some cases where a pin can not be identified as a is constant until after
     * the full netlist has been built; so we expose a way to mark existing pins as constants.
     *   @param pin_id   The pin to be marked
     *   @param value    The boolean value to set the pin_is_constant attribute
     */
    void set_pin_is_constant(const PinId pin_id, const bool value);

    /**
     * @brief Re-name a block
     *
     *   @param blk_id   : The block to be renamed
     *   @param new_name : The new name for the specified block
     */
    void set_block_name(const BlockId blk_id, const std::string new_name);

    /**
     * @brief Set a block attribute
     *
     *   @param blk_id   The block to which the attribute is attached
     *   @param name     The name of the attribute to set
     *   @param value    The new value for the specified attribute on the specified block
     */
    void set_block_attr(const BlockId blk_id, const std::string& name, const std::string& value);

    /**
     * @brief Set a block parameter
     *
     *   @param blk_id   The block to which the parameter is attached
     *   @param name     The name of the parameter to set
     *   @param value    The new value for the specified parameter on the specified block
     */
    void set_block_param(const BlockId blk_id, const std::string& name, const std::string& value);

    /**
     * @brief Sets the flag in net_ignored_ = state
     *
     *   @param net_id   The Net Id
     *   @param state   true(false): net should(shouldn't) be ignored
     */
    void set_net_is_ignored(NetId net_id, bool state);

    ///@brief Sets the flag in net_is_global_ = state
    void set_net_is_global(NetId net_id, bool state);

    /**
     * @brief Merges sink_net into driver_net
     *
     * After merging driver_net will contain all the sinks of sink_net
     *   @param driver_net   The net which includes the driver pin
     *   @param sink_net     The target net to be merged into driver_net (must have no driver pin)
     */
    void merge_nets(const NetId driver_net, const NetId sink_net);

    /*
     * Note: all remove_*() will mark the associated items as invalid, but the items
     * will not be removed until compress() is called.
     */

    /**
     * @brief Wrapper for remove_unused() & compress()
     *
     * This function should be used in the case where a netlist is fully modified
     */
    IdRemapper remove_and_compress();

    /**
     * @brief This should be called after completing a series of netlist modifications
     *        (e.g. removing blocks/ports/pins/nets).
     *
     * Marks netlist components which have become redundant due to other removals
     * (e.g. ports with only invalid pins) as invalid so they will be destroyed during
     * compress()
     */
    void remove_unused();

    /**
     * @brief Compresses the netlist, removing any invalid and/or unreferenced
     *        blocks/ports/pins/nets.
     *
     * @note this invalidates all existing IDs!
     */
    IdRemapper compress();

  protected: //Protected Mutators
    /**
     * @brief Create or return an existing block in the netlist
     *
     *   @param name   The unique name of the block
     */
    BlockId create_block(const std::string name);

    /**
     * @brief Create or return an existing port in the netlist
     *
     *   @param blk_id   The block the port is associated with
     *   @param name     The name of the port (must match the name of a port in the block's model)
     *   @param width    The width (number of bits) of the port
     *   @param type     The type of the port (INPUT, OUTPUT, CLOCK)
     */
    PortId create_port(const BlockId blk_id, const std::string name, BitIndex width, PortType type);

    /**
     * @brief Create or return an existing pin in the netlist
     *
     *   @param port_id    The port this pin is associated with
     *   @param port_bit   The bit index of the pin in the port
     *   @param net_id     The net the pin drives/sinks
     *   @param pin_type   The type of the pin (driver/sink)
     *   @param is_const   Indicates whether the pin holds a constant value (e. g. vcc/gnd)
     */
    PinId create_pin(const PortId port_id, BitIndex port_bit, const NetId net_id, const PinType pin_type, bool is_const = false);

    /**
     * @brief Create an empty, or return an existing net in the netlist
     *
     *   @param name   The unique name of the net
     */
    NetId create_net(const std::string name); //An empty or existing net

    /**
     * @brief Create a completely specified net from specified driver and sinks
     *
     *   @param name     The name of the net (Note: must not already exist)
     *   @param driver   The net's driver pin
     *   @param sinks    The net's sink pins
     */
    NetId add_net(const std::string name, PinId driver, std::vector<PinId> sinks);

  protected: //Protected Base Types
    ///@brief A unique identifier for a string in the netlist
    typedef vtr::StrongId<struct string_id_tag> StringId;

  protected: //Protected Base Members
    /*
     * Lookups
     */

    /**
     * @brief Returns the StringId of the specified string if it exists or StringId::INVALID() if not
     *
     *   @param str   The string to look for
     */
    StringId find_string(const std::string& str) const;

    /**
     * @brief Returns the BlockId of the specified block if it exists or BlockId::INVALID() if not
     *
     *   @param name_id : The block name to look for
     */
    BlockId find_block(const StringId name_id) const;

    /**
     * @brief Returns the NetId of the specified port if it exists or NetId::INVALID() if not
     *
     *   @param name_id   The string ID of the net name to look for
     */
    NetId find_net(const StringId name_id) const;

    /*
     * Mutators
     */

    /**
     * @brief Create or return the ID of the specified string
     *
     *   @param str   The string whose ID is requested
     */
    StringId create_string(const std::string& str);

    /**
     * @brief Updates net cross-references for the specified pin
     *
     * @return Returns the pin's index within the net
     */
    int associate_pin_with_net(const PinId pin_id, const PinType type, const NetId net_id);

    ///@brief Updates port cross-references for the specified pin
    void associate_pin_with_port(const PinId pin_id, const PortId port_id);

    ///@brief Updates block cross-references for the specified pin
    void associate_pin_with_block(const PinId pin_id, const PortType type, const BlockId blk_id);

    ///@brief Updates block cross-references for the specified port
    void associate_port_with_block(const PortId port_id, const PortType type, const BlockId blk_id);

    /*
     * Netlist compression/optimization
     */

    /**
     * @brief Builds the new mappings from old to new IDs.
     *
     * The various IdMap's should be initialized with invalid mappings
     * for all current ID's before being called.
     */
    IdRemapper build_id_maps();

    ///@brief Removes invalid and reorders blocks
    void clean_blocks(const vtr::vector_map<BlockId, BlockId>& block_id_map);

    ///@brief Removes invalid and reorders ports
    void clean_ports(const vtr::vector_map<PortId, PortId>& port_id_map);

    ///@brief Removes invalid and reorders pins
    void clean_pins(const vtr::vector_map<PinId, PinId>& pin_id_map);

    ///@brief Removes invalid and reorders nets
    void clean_nets(const vtr::vector_map<NetId, NetId>& net_id_map);

    ///@brief Re-builds fast look-ups
    void rebuild_lookups();

    ///@brief Re-builds cross-references held by blocks
    void rebuild_block_refs(const vtr::vector_map<PinId, PinId>& pin_id_map,
                            const vtr::vector_map<PortId, PortId>& port_id_map);

    ///@brief Re-builds cross-references held by ports
    void rebuild_port_refs(const vtr::vector_map<BlockId, BlockId>& block_id_map,
                           const vtr::vector_map<PinId, PinId>& pin_id_map);

    ///@brief Re-builds cross-references held by pins
    void rebuild_pin_refs(const vtr::vector_map<PortId, PortId>& port_id_map,
                          const vtr::vector_map<NetId, NetId>& net_id_map);

    ///@brief Re-builds cross-references held by nets
    void rebuild_net_refs(const vtr::vector_map<PinId, PinId>& pin_id_map);

    void shrink_to_fit();

    /*
     * Sanity Checks
     */

    //Verify the internal data structure sizes match
    bool verify_sizes() const;
    bool validate_block_sizes() const;
    bool validate_port_sizes() const;
    bool validate_pin_sizes() const;
    bool validate_net_sizes() const;
    bool validate_string_sizes() const;

    //Verify that internal data structure cross-references are consistent
    bool verify_refs() const; //All cross-references
    bool validate_block_port_refs() const;
    bool validate_block_pin_refs() const;
    bool validate_port_pin_refs() const;
    bool validate_net_pin_refs() const;
    bool validate_string_refs() const;

    ///@brief Verify that block invariants hold (i.e. logical consistency)
    bool verify_block_invariants() const;

    ///@brief Verify that fast-lookups are consistent with internal data structures
    bool verify_lookups() const;

    ///@brief Validates that the specified ID is valid in the current netlist state
    bool valid_string_id(StringId string_id) const;

  protected: //Protected virtual functions implemented in derived classes
    //The functions follow the Non-Virtual Interface (NVI) idiom, and
    //are called from this class in their respective non-impl() functions.
    virtual void shrink_to_fit_impl() {}

    virtual bool validate_block_sizes_impl(size_t /*num_blocks*/) const { return true; }
    virtual bool validate_port_sizes_impl(size_t /*num_ports*/) const { return true; }
    virtual bool validate_pin_sizes_impl(size_t /*num_pins*/) const { return true; }
    virtual bool validate_net_sizes_impl(size_t /*num_nets*/) const { return true; }

    virtual void clean_blocks_impl(const vtr::vector_map<BlockId, BlockId>& /*block_id_map*/) {}
    virtual void clean_ports_impl(const vtr::vector_map<PortId, PortId>& /*port_id_map*/) {}
    virtual void clean_pins_impl(const vtr::vector_map<PinId, PinId>& /*pin_id_map*/) {}
    virtual void clean_nets_impl(const vtr::vector_map<NetId, NetId>& /*net_id_map*/) {}

    virtual void remove_block_impl(const BlockId /*blk_id*/) {}
    virtual void remove_port_impl(const PortId /*port_id*/) {}
    virtual void remove_pin_impl(const PinId /*pin_id*/) {}
    virtual void remove_net_impl(const NetId /*net_id*/) {}

    virtual void rebuild_block_refs_impl(const vtr::vector_map<PinId, PinId>& /*pin_id_map*/, const vtr::vector_map<PortId, PortId>& /*port_id_map*/) {}
    virtual void rebuild_port_refs_impl(const vtr::vector_map<BlockId, BlockId>& /*block_id_map*/, const vtr::vector_map<PinId, PinId>& /*pin_id_map*/) {}
    virtual void rebuild_pin_refs_impl(const vtr::vector_map<PortId, PortId>& /*port_id_map*/, const vtr::vector_map<NetId, NetId>& /*net_id_map*/) {}
    virtual void rebuild_net_refs_impl(const vtr::vector_map<PinId, PinId>& /*pin_id_map*/) {}

  protected:
    constexpr static int INVALID_INDEX = -1;
    constexpr static int NET_DRIVER_INDEX = 0;

  private:                     //Data
    std::string netlist_name_; ///<Name of the top-level netlist
    std::string netlist_id_;   ///<Unique identifier for the netlist
    bool dirty_ = false;       ///<Indicates the netlist has invalid entries from remove_*() functions

    //Block data
    vtr::vector_map<BlockId, BlockId> block_ids_;    ///<Valid block ids
    vtr::vector_map<BlockId, StringId> block_names_; ///<Name of each block

    vtr::vector_map<BlockId, std::vector<PortId>> block_ports_; ///<Ports of each block
    vtr::vector_map<BlockId, unsigned> block_num_input_ports_;  ///<Input ports of each block
    vtr::vector_map<BlockId, unsigned> block_num_output_ports_; ///<Output ports of each block
    vtr::vector_map<BlockId, unsigned> block_num_clock_ports_;  ///<Clock ports of each block

    vtr::vector_map<BlockId, std::vector<PinId>> block_pins_;  ///<Pins of each block
    vtr::vector_map<BlockId, unsigned> block_num_input_pins_;  ///<Number of input pins on each block
    vtr::vector_map<BlockId, unsigned> block_num_output_pins_; ///<Number of output pins on each block
    vtr::vector_map<BlockId, unsigned> block_num_clock_pins_;  ///<Number of clock pins on each block

    vtr::vector_map<BlockId, std::unordered_map<std::string, std::string>> block_params_; ///<Parameters of each block
    vtr::vector_map<BlockId, std::unordered_map<std::string, std::string>> block_attrs_;  ///<Attributes of each block

    //Port data
    vtr::vector_map<PortId, PortId> port_ids_;              ///<Valid port ids
    vtr::vector_map<PortId, StringId> port_names_;          ///<Name of each port
    vtr::vector_map<PortId, BlockId> port_blocks_;          ///<Block associated with each port
    vtr::vector_map<PortId, std::vector<PinId>> port_pins_; ///<Pins associated with each port
    vtr::vector_map<PortId, BitIndex> port_widths_;         ///<Width (in bits) of each port
    vtr::vector_map<PortId, PortType> port_types_;          ///<Type of the port (INPUT, OUTPUT, CLOCK)

    //Pin data
    vtr::vector_map<PinId, PinId> pin_ids_;          ///<Valid pin ids
    vtr::vector_map<PinId, PortId> pin_ports_;       ///<Type of each pin
    vtr::vector_map<PinId, BitIndex> pin_port_bits_; ///<The pins bit position in the port
    vtr::vector_map<PinId, NetId> pin_nets_;         ///<Net associated with each pin
    vtr::vector_map<PinId, int> pin_net_indices_;    ///<Index of the specified pin within it's associated net
    vtr::vector_map<PinId, bool> pin_is_constant_;   ///<Indicates if the pin always keeps a constant value

    //Net data
    vtr::vector_map<NetId, NetId> net_ids_;               ///<Valid net ids
    vtr::vector_map<NetId, StringId> net_names_;          ///<Name of each net
    vtr::vector_map<NetId, std::vector<PinId>> net_pins_; ///<Pins associated with each net

    //String data
    // We store each unique string once, and reference it by an StringId
    // This avoids duplicating the strings in the fast look-ups (i.e. the look-ups
    // only store the Ids)
    vtr::vector_map<StringId, StringId> string_ids_; ///<Valid string ids
    vtr::vector_map<StringId, std::string> strings_; ///<Strings

  private: //Fast lookups
    vtr::vector_map<StringId, BlockId> block_name_to_block_id_;
    vtr::vector_map<StringId, NetId> net_name_to_net_id_;
    std::unordered_map<std::string, StringId> string_to_string_id_;
    vtr::vector_map<NetId, bool> net_is_ignored_; ///<Boolean mapping indicating if the net is ignored
    vtr::vector_map<NetId, bool> net_is_global_;  ///<Boolean mapping indicating if the net is global
};

#include "netlist.tpp"