/************************************************************************
 * This file introduces a class to model a Routing Resource Graph (RRGraph or RRG) 
 * which is widely used by placers, routers, analyzers etc.
 *
 * Overview
 * ========
 * RRGraph aims to describe in a general way how routing resources are connected
 * in a FPGA fabric.
 * It includes device-level information for routing resources, 
 * such as the physical location of nodes, 
 * routing segment information of each routing resource 
 * switch information of each routing resource.
 * 
 * A Routing Resource Graph (RRGraph or RRG) is a directed graph (has many cycles),
 * which consists of a number of nodes and edges.
 *
 * Node
 * ----
 * Each node represents a routing resource, which could be 
 * 1. a routing track in X-direction or Y-direction (CHANX or CHANY) 
 * 2. an input or an output of a logic block (IPIN or OPIN) 
 * 3. a virtual source or sink node (SOURCE or SINK), which are starting/ending points of routing trees.
 *
 * Edge
 * ----
 * Each edge represents a switch between routing resources, which could be
 * 1. a multiplexer
 * 2. a tri-state buffer
 * 3. a pass gate
 * 4. a non-configurable (can not be turned off) buffer
 * 5. a short (metal connection that can not be turned off
 *
 * Note: Multiplexers are the most common type
 *
 * The switch information are categorized in the rr_switch_inf of RRGraph class.
 * rr_switch_inf is created to minimize memory footprint of RRGraph classs
 * While the RRG could contain millions (even much larger) of edges, there are only
 * a limited number of types of switches.
 * Hence, we use a flyweight pattern to store switch-related information that differs
 * only for types of switches (switch type, drive strength, R, C, etc.).
 * Each edge stores the ids of the switch that implements it so this additional information
 * can be easily looked up.
 *
 * Note: All the switch-related information, such as R, C, should be placed in rr_switch_inf
 * but NOT directly in the edge-related data of RRGraph. 
 * If you wish to create a new data structure to represent switches between routing resources,
 * please follow the flyweight pattern by linking your switch ids to edges only!
 *
 * Guidlines on using the RRGraph data structure 
 * =============================================
 *
 * For those want to access data from RRGraph
 * ------------------------------------------
 * Some examples for most frequent data query:
 * 
 *     // Strongly suggest to use a read-only rr_graph object
 *     const RRGraph& rr_graph;
 *
 *     // Access type of a node with a given node id
 *     // Get the unique node id that you may get 
 *     // from other data structures or functions 
 *     RRNodeId node_id;                                    
 *     t_rr_type node_type = rr_graph.node_type(node_id);
 *
 *     // Access all the fan-out edges from a given node  
 *     for (const RREdgeId& out_edge_id : rr_graph.node_out_edges(node_id)) {
 *       // Do something with out_edge
 *     }
 *     // If you only want to learn the number of fan-out edges
 *     size_t num_out_edges = rr_graph.node_fan_out(node_id);
 *
 *     // Access all the switches connected to a given node  
 *     for (const RREdgeId& in_edge_id : rr_graph.node_in_edges(node_id)) {
 *       RRSwitchId edge_switch_id = rr_graph.edge_switch(in_edge_id);
 *       // Do something with the switch
 *     }
 *
 * Please refer to the detailed comments on each public accessors
 *
 * For those want to build/modify a RRGraph
 * -----------------------------------------
 * Do NOT add a builder to this data structure!
 * Builders should be kept as free functions that use the public mutators
 * We suggest developers to create builders in separated C/C++ source files
 * outside the rr_graph header and source files
 *
 * After build/modify a RRGraph, please do run a fundamental check, a public accessor.
 * to ensure that your RRGraph does not include invalid nodes/edges/switches/segements 
 * as well as connections.
 * The validate() function gurantees the consistency between internal data structures, 
 * such as the id cross-reference between nodes and edges etc.,
 * so failing it indicates a fatal bug!
 * This is a must-do check! 
 *
 * Example: 
 *    RRGraph rr_graph;
 *    ... // Building RRGraph
 *    rr_graph.validate(); 
 *
 * Optionally, we strongly recommend developers to run an advance check in check_rr_graph()  
 * This guarantees legal and routable RRGraph for VPR routers.
 *
 * This checks for connectivity or other information in the RRGraph that is unexpected 
 * or unusual in an FPGA, and likely indicates a problem in your graph generation. 
 * However, if you are intentionally creating an RRGraph with this unusual, 
 * buts still technically legal, behaviour, you can write your own check_rr_graph() with weaker assumptions. 
 *
 * Note: Do NOT modify the coordinate system for nodes, they are designed for downstream drawers and routers
 *
 * For those want to extend RRGraph data structure
 * --------------------------------------------------------------------------
 * Please avoid modifying any existing public/private accessors/mutators
 * in order to keep a stable RRGraph object in the framework
 * Developers may add more internal data to RRGraph as well as associate accessors/mutators
 * Please update and comment on the added features properly to keep this data structure friendly to be extended.
 *
 * Try to keep your extension within only graph-related internal data to RRGraph.
 * In other words, extension is necessary when the new node/edge attributes are needed.
 * RRGraph should NOT include other data which are shared by other data structures outside.
 * The rr-graph is the single largest data structure in VPR,
 * so avoid adding unnecessary information per node or per edge to it, as it will impact memory footprint.
 * Instead, using indices to point to the outside data source instead of embedding to RRGraph
 * For example: 
 *   For any placement/routing cost related information, try to extend t_rr_indexed_data, but not RRGraph
 *   For any placement/routing results, try to extend PlaceContext and RoutingContext, but not RRGraph
 * 
 * For those want to develop placers or routers
 * --------------------------------------------------------------------------
 * The RRGraph is designed to be a read-only database/graph, once created.
 * Placement and routing should NOT change any attributes of RRGraph.
 * Any placement and routing results should be stored in other data structures, such as PlaceContext and RoutingContext. 
 *
 * Tracing Cross-Reference 
 * =======================
 * RRGraph is designed to a self-contained data structure as much as possible.
 * It includes the switch information (rr_switch) and segment_information (rr_segment)
 * which are necessary to build-up any external data structures.
 *
 * Internal cross-reference
 * ------------------------
 *
 *  +--------+                  +--------+
 *  |        |  node_in_edges   |        |
 *  |        |  node_out_edges  |        |
 *  |  Node  |----------------->|  Edge  |--+
 *  |        |<-----------------|        |  |
 *  |        |  edge_src_node   |        |  |
 *  +--------+  edge_sink_node  +--------+  |edge_switch
 *      |                                   |
 *      | node_segment                      |
 *      v                                   v
 *  +------------+                     +----------+
 *  |            |                     |          |
 *  |            |                     |          |
 *  |  Segments  |                     |  Switch  |
 *  |            |                     |          |
 *  |            |                     |          |
 *  +------------+                     +----------+
 *
 *
 * External cross-reference
 * ------------------------
 * The only cross-reference to outside data structures is the cost_index
 * corresponding to the data structure t_rr_index_data
 * Details can be found in the definition of t_rr_index_data
 * This allows rapid look up by the router of additional information it needs for this node, using a flyweight pattern.
 *
 * +---------+  cost_index   +------------------------------+
 * | RRGraph |-------------->| cost_index_data[cost_index] | 
 * +---------+               +------------------------------+
 *
 * Note: if you wish to use a customized routing-cost data structure, 
 * please use the flyweigth pattern as we do for t_rr_index_data!
 *
 * Access to a node/edge/switch/segment, please use the StrongId created
 * ---------------------------------------------------------------------
 *    For node, use RRNodeId
 *    For edge, use RREdgeId
 *    For switch, use RRSwitchId
 *    For segment, use RRSegmentId
 *
 *    These are the unique identifier for each data type.
 *    To check if your id is valid or not, use the INVALID() function of StrongId class.
 *    Example:
 *       if (node_id == RRNodeId::INVALID()) {
 *       }  
 *
 ***********************************************************************/
#ifndef RR_GRAPH_OBJ_H
#define RR_GRAPH_OBJ_H

/*
 * Notes in include header files in a head file 
 * Only include the neccessary header files 
 * that is required by the data types in the function/class declarations!
 */
/* Header files should be included in a sequence */
/* Standard header files required go first */
#include <limits>
#include <vector>

/* EXTERNAL library header files go second*/
#include "vtr_vector.h"
#include "vtr_range.h"
#include "vtr_geometry.h"
#include "arch_types.h"

/* VPR header files go third */
#include "vpr_types.h"
#include "rr_graph_fwd.h"

class RRGraph {
  public: /* Types */
    /* Iterators used to create iterator-based loop for nodes/edges/switches/segments */
    typedef vtr::vector<RRNodeId, RRNodeId>::const_iterator node_iterator;
    typedef vtr::vector<RREdgeId, RREdgeId>::const_iterator edge_iterator;
    typedef vtr::vector<RRSwitchId, RRSwitchId>::const_iterator switch_iterator;
    typedef vtr::vector<RRSegmentId, RRSegmentId>::const_iterator segment_iterator;

    /* Ranges used to create range-based loop for nodes/edges/switches/segments */
    typedef vtr::Range<node_iterator> node_range;
    typedef vtr::Range<edge_iterator> edge_range;
    typedef vtr::Range<switch_iterator> switch_range;
    typedef vtr::Range<segment_iterator> segment_range;

  public: /* Accessors */
    /* Aggregates: create range-based loops for nodes/edges/switches/segments
     * To iterate over the nodes/edges/switches/segments in a RRGraph, 
     *    using a range-based loop is suggested.
     *  -----------------------------------------------------------------
     *    Example: iterate over all the nodes
     *      // Strongly suggest to use a read-only rr_graph object
     *      const RRGraph& rr_graph;
     *      for (const RRNodeId& node : rr_graph.nodes()) {
     *        // Do something with each node
     *      }
     *
     *      for (const RREdgeId& edge : rr_graph.edges()) {
     *        // Do something with each edge
     *      }
     *
     *      for (const RRSwitchId& switch : rr_graph.switches()) {
     *        // Do something with each switch
     *      }
     *
     *      for (const RRSegmentId& segment : rr_graph.segments()) {
     *        // Do something with each segment
     *      }
     */
    node_range nodes() const;
    edge_range edges() const;
    switch_range switches() const;
    segment_range segments() const;

    /* Node-level attributes */
    size_t node_index(const RRNodeId& node) const; /* TODO: deprecate this accessor as outside functions should use RRNodeId */

    /* get the type of a RRGraph node : types of each node, can be channel wires (CHANX or CHANY) or 
     *                                  logic block pins(OPIN or IPIN) or virtual nodes (SOURCE or SINK)
     *                                  see t_rr_type definition for more details
     */
    t_rr_type node_type(const RRNodeId& node) const;

    /* Get coordinate of a node. (xlow, xhigh, ylow, yhigh):
     *   For OPIN/IPIN/SOURCE/SINK, xlow = xhigh and ylow = yhigh
     *   This is still the case when a logic block has a height > 1
     *   For CHANX/CHANY, (xlow, ylow) and (xhigh, yhigh) represent
     *   where the routing segment starts and ends.
     *   Note that our convention alway keeps
     *   xlow <= xhigh and ylow <= yhigh
     *   Therefore, (xlow, ylow) is a starting point for a CHANX/CHANY in INC_DIRECTION
     *   (xhigh, yhigh) is a starting point for a CHANX/CHANY in DEC_DIRECTION
     *
     *   Note: there is only a single drive point for each routing segment (track)
     *   in the context of uni-directional wires
     *                           
     *   Example :
     *   CHANX in INC_DIRECTION  
     *   (xlow, ylow)                (xhigh, yhigh)
     *        |                           |
     *       \|/                         \|/
     *        ---------------------------->
     *
     *   CHANX in DEC_DIRECTION  
     *   (xlow, ylow)                (xhigh, yhigh)
     *        |                           |
     *       \|/                         \|/
     *        <----------------------------
     *
     *   CHANY in INC_DIRECTION
     *       
     *      /|\ <-------(xhigh, yhigh)
     *       |
     *       |  <-------(xlow, ylow)
     *
     *   CHANY in DEC_DIRECTION
     *       
     *       |  <-------(xhigh, yhigh)
     *       |
     *      \|/ <-------(xlow, ylow)
     */
    short node_xlow(const RRNodeId& node) const;
    short node_ylow(const RRNodeId& node) const;
    short node_xhigh(const RRNodeId& node) const;
    short node_yhigh(const RRNodeId& node) const;

    /* Get the length of a routing track. 
     * Note that it is ONLY meaningful for CHANX and CHANY, which represents the number of logic blocks that a routing track spans
     * For nodes that are OPIN/IPIN/SOURCE/SINK, the length is supposed to be always 0
     */
    short node_length(const RRNodeId& node) const;

    /* A short-cut function to get coordinates of a node,
     * where xmin of vtr::Rect = xlow, 
     *       ymin of vtr::Rect = ylow,
     *       xmax of vtr::Rect = xhigh, 
     *       ymax of vtr::Rect = yhigh. 
     */
    vtr::Rect<short> node_bounding_box(const RRNodeId& node) const;

    /* Get node starting and ending points in routing channels. 
     * See details in the figures for node_xlow(), node_ylow(), node_xhigh() and node_yhigh()
     * For routing tracks in INC_DIRECTION:
     * node_start_coordinate() returns (xlow, ylow) as the starting point 
     * node_end_coordinate() returns (xhigh, yhigh) as the ending point 
     *
     * For routing tracks in DEC_DIRECTION:
     * node_start_coordinate() returns (xhigh, yhigh) as the starting point 
     * node_end_coordinate() returns (xlow, ylow) as the ending point 
     *
     * For routing tracks in BI_DIRECTION:
     * node_start_coordinate() returns (xlow, ylow) as the starting point 
     * node_end_coordinate() returns (xhigh, yhigh) as the ending point 
     *
     * Applicable to routing track nodes only!!! 
     * This function will requires the types of node to be either CHANX or CHANY
     */
    vtr::Point<short> node_start_coordinate(const RRNodeId& node) const;
    vtr::Point<short> node_end_coordinate(const RRNodeId& node) const;

    /* Get the capacity of a node. 
     * Literally, how many nets can be mapped to the node. 
     * Typically, each node has a capacity of 1 but special nodes (SOURCE and SINK) will have a 
     * large number due to logic equivalent pins
     * See Vaughn Betz's book for more details
     */
    short node_capacity(const RRNodeId& node) const;

    /* Get the number of edges that drives a given node
     * Note that each edge is typically driven by a node
     * (true in VPR RRG that is currently supported, may not be true in customized RRG)
     * This can also represent the number of drive nodes 
     * An example where fan-in of a node C is 2
     *      
     *                edge A
     *        node A -------->+
     *                        |
     *                        |-->node C 
     *                 edgeB  |
     *        node B -------->+
     *  
     */
    short node_fan_in(const RRNodeId& node) const;

    /* Get the number of edges that are driven a given node
     * Note that each edge typically drives by a node 
     * (true in VPR RRG that is currently supported, may not be true in customized RRG)
     * This can also represent the number of fan-out nodes 
     * An example where fan-out of a node A is 2
     *      
     *                  edge A
     *        node A -+--------> node B
     *                |
     *                |     
     *                | edgeB  
     *                +--------> node C
     *  
     */
    short node_fan_out(const RRNodeId& node) const;

    /* Get the ptc_num of a node
     * The ptc (pin, track, or class) number is an integer 
     * that allows you to differentiate between wires, pins or sources/sinks with overlapping x,y coordinates or extent. 
     * This is useful for drawing rr-graphs nicely. 
     * For example, all the CHANX rr_nodes that have the same y coordinate and x-coordinates 
     * that overlap will have different ptc numbers, by convention starting at 0. 
     * This allows them to be drawn without overlapping, as the ptc num can be used as a track identifier. 
     * The main routing code does not care about ptc num.
     *
     * The ptc_num carries different meanings for different node types
     * (true in VPR RRG that is currently supported, may not be true in customized RRG)
     * CHANX or CHANY: the track id in routing channels
     * OPIN or IPIN: the index of pins in the logic block data structure
     * SOURCE and SINK: the class id of a pin (indicating logic equivalence of pins) in the logic block data structure
     *  
     * To ease the access to ptc_num for different types of nodes:
     * node_pin_num() is designed for logic blocks, which are IPIN and OPIN nodes
     * node_track_num() is designed for routing tracks, which are CHANX and CHANY nodes
     * node_class_num() is designed for routing source and sinks, which are SOURCE and SINK nodes
     *
     * Due to a useful identifier, ptc_num is used in building fast look-up 
     */
    short node_ptc_num(const RRNodeId& node) const;
    short node_pin_num(const RRNodeId& node) const;
    short node_track_num(const RRNodeId& node) const;
    short node_class_num(const RRNodeId& node) const;

    /* Get the index of cost data in the list of cost_indexed_data data structure
     * It contains the routing cost for different nodes in the RRGraph
     * when used in evaluate different routing paths
     * See cross-reference section in this header file for more details
     */
    short node_cost_index(const RRNodeId& node) const;

    /* Get the directionality of a node
     * see node coordinate for details 
     * only matters the routing track nodes (CHANX and CHANY) 
     */
    e_direction node_direction(const RRNodeId& node) const;

    /* Get the side where the node physically locates on a logic block. 
     * Mainly applicable to IPIN and OPIN nodes, which locates on the perimeter of logic block 
     * The side should be consistent to <pinlocation> definition in architecture XML
     *
     *             TOP
     *        +-----------+
     *        |           |
     *  LEFT  |   Logic   | RIGHT
     *        |   Block   |
     *        |           |
     *        +-----------+
     *            BOTTOM
     *
     */
    e_side node_side(const RRNodeId& node) const;

    /* Get resistance of a node, used to built RC tree for timing analysis */
    float node_R(const RRNodeId& node) const;

    /* Get capacitance of a node, used to built RC tree for timing analysis */
    float node_C(const RRNodeId& node) const;

    /* Get segment id of a node, containing the information of the routing
     * segment that the node represents. See more details in the data structure t_segment_inf
     */
    RRSegmentId node_segment(const RRNodeId& node) const;

    /* Get the number of non-configurable incoming edges to a node */
    short node_num_configurable_in_edges(const RRNodeId& node) const;

    /* Get the number of non-configurable outgoing edges from a node */
    short node_num_non_configurable_in_edges(const RRNodeId& node) const;

    /* Get the number of configurable output edges of a node */
    short node_num_configurable_out_edges(const RRNodeId& node) const;

    /* Get the number of non-configurable output edges of a node */
    short node_num_non_configurable_out_edges(const RRNodeId& node) const;

    /* Get the range (list) of edges related to a given node */
    edge_range node_configurable_in_edges(const RRNodeId& node) const;
    edge_range node_non_configurable_in_edges(const RRNodeId& node) const;
    edge_range node_configurable_out_edges(const RRNodeId& node) const;
    edge_range node_non_configurable_out_edges(const RRNodeId& node) const;

    /* Get a list of edge ids, which are incoming edges to a node */
    edge_range node_in_edges(const RRNodeId& node) const;

    /* Get a list of edge ids, which are outgoing edges from a node */
    edge_range node_out_edges(const RRNodeId& node) const;

    /* Edge-related attributes 
     * An example to explain the terminology used in RRGraph
     *          edgeA
     *  nodeA --------> nodeB
     *        | edgeB
     *        +-------> nodeC
     *
     *  +----------+----------------+----------------+
     *  |  Edge Id |  edge_src_node | edge_sink_node |
     *  +----------+----------------+----------------+
     *  |   edgeA  |     nodeA      |      nodeB     |
     *  +----------+----------------+----------------+
     *  |   edgeB  |     nodeA      |      nodeC     |
     *  +----------+----------------+----------------+
     *
     */
    size_t edge_index(const RREdgeId& edge) const; /* TODO: deprecate this accessor as outside functions should use RREdgeId */
    /* Get the source node which drives a edge */
    RRNodeId edge_src_node(const RREdgeId& edge) const;
    /* Get the sink node which a edge ends to */
    RRNodeId edge_sink_node(const RREdgeId& edge) const;
    /* Get the switch id which a edge represents
     * using switch id, timing and other information can be found
     * for any node-to-node connection
     */
    RRSwitchId edge_switch(const RREdgeId& edge) const;
    /* Judge if a edge is configurable or not. 
     * A configurable edge is controlled by a programmable memory bit
     * while a non-configurable edge is typically a hard-wired connection
     */
    bool edge_is_configurable(const RREdgeId& edge) const;
    bool edge_is_non_configurable(const RREdgeId& edge) const;

    /* Switch Info */
    size_t switch_index(const RRSwitchId& switch_id) const; /* TODO: deprecate this accessor as outside functions should use RRSwitchId */
    /* Get the switch info of a switch used in this RRGraph */
    const t_rr_switch_inf& get_switch(const RRSwitchId& switch_id) const;

    /* Segment Info */
    size_t segment_index(const RRSegmentId& segment_id) const; /* TODO: deprecate this accessor as outside functions should use RRSegmentId */
    /* Get the segment info of a routing segment used in this RRGraph */
    const t_segment_inf& get_segment(const RRSegmentId& segment_id) const;

    /* Utilities */
    /* Find the edges connecting two nodes */
    std::vector<RREdgeId> find_edges(const RRNodeId& src_node, const RRNodeId& sink_node) const;
    /* Find a node with given features from internal fast look-up */
    RRNodeId find_node(const short& x, const short& y, const t_rr_type& type, const int& ptc, const e_side& side = NUM_SIDES) const;
    /* Find the number of routing tracks in a routing channel with a given coordinate */
    short chan_num_tracks(const short& x, const short& y, const t_rr_type& type) const;

    /* This flag is raised when the RRgraph contains invalid nodes/edges etc. 
     * Invalid nodes/edges exist when users remove nodes/edges from RRGraph
     * RRGraph object will not immediately remove the nodes and edges but
     * will mark them with invalid ids.
     * Afterwards the is_dirty flag is raised as an indicator, to tell users
     * that a clean-up process (invoked by compress() function)is required.
     * After executing compress(), the is_dirty will be reset to false
     *
     * Example:
     *   RRGraph rr_graph;
     *   RRNodeId node_id; // Node id to be removed
     *   rr_graph.remove_node(node_id); 
     *   // RRGraph is now dirty (rr_graph.is_dirty() == true)
     *   ...
     *   // During this period, when you perform data query,
     *   // You may encounter invalid nodes and edges
     *   // It may happen that 
     *   // 1. their ids are invalid 
     *   // 2. the cross-reference between nodes and edge, i.e.,
     *   //    node_in_edges(), node_out_edges() 
     *   // 3. invalid node returned from find_node(), which use fast look-up
     *   ... 
     *   rr_graph.compress(); 
     *   // RRGraph is now clean (rr_graph.is_dirty() == false)
     */
    bool is_dirty() const;

  public:                                        /* Echos */
    void print_node(const RRNodeId& node) const; /* Print the detailed information of a node */

  public: /* Public Validators */
    /* Check data structure for internal consistency
     * This function will 
     * 1. re-build fast look-up for nodes
     * 2. check all the edges and nodes are connected
     *    Literally, no invalid ids in fan-in/fan-out of edges/nodes
     * 3. check that all the nodes representing routing tracks have valid id linked to its segment-related data structure
     * 4. check that all the edges have valid id linked to its switch-related data structure 
     *
     * Any valid and non-dirty RRGraph should pass this check
     * It is highly recommended to run this function after building any RRGraph object
     */
    bool validate() const;

    /* Validate is the node id does exist in the RRGraph */
    bool valid_node_id(const RRNodeId& node) const;

    /* Validate is the edge id does exist in the RRGraph */
    bool valid_edge_id(const RREdgeId& edge) const;

  public: /* Mutators */
    /* Reserve the lists of nodes, edges, switches etc. to be memory efficient. 
     * This function is mainly used to reserve memory space inside RRGraph,
     * when adding a large number of nodes/edge/switches/segments,
     * in order to avoid memory fragements
     * For example: 
     *    RRGraph rr_graph;
     *    // Add 1000 CHANX nodes to the RRGraph object
     *    rr_graph.reserve_nodes(1000);
     *    for (size_t i = 0; i < 1000; ++i) {
     *      rr_graph.create_node(CHANX);
     *    }
     */
    void reserve_nodes(const int& num_nodes);
    void reserve_edges(const int& num_edges);
    void reserve_switches(const int& num_switches);
    void reserve_segments(const int& num_segments);

    /* Add new elements (node, edge, switch, etc.) to RRGraph */
    /* Add a node to the RRGraph with a deposited type 
     * Detailed node-level information should be added using the set_node_* functions
     * For example: 
     *   RRNodeId node = create_node();
     *   set_node_xlow(node, 0);
     */
    RRNodeId create_node(const t_rr_type& type);
    /* Add a edge to the RRGraph, by providing the source and sink node 
     * This function will automatically create a node and
     * configure the nodes and edges in connection   
     */
    RREdgeId create_edge(const RRNodeId& source, const RRNodeId& sink, const RRSwitchId& switch_id);
    RRSwitchId create_switch(const t_rr_switch_inf& switch_info);
    RRSegmentId create_segment(const t_segment_inf& segment_info);

    /* Remove elements from RRGraph
     * This function just turn the nodes and edges to an invalid id without deletion
     * This will cause the RRGraph to be marked as dirty (is_dirty(): false => true)
     * To thoroughly remove the edges and nodes as well as clear the dirty flag,
     * use compress() after the remove functions
     * Example: 
     *   RRGraph rr_graph;
     *   rr_graph.remove_node()
     *   .. // remove more nodes 
     *   rr_graph.remove_edge()
     *   .. // remove more nodes 
     *   // rr_graph.is_dirty() == true
     *   // If you want to access any node or edge
     *   // Check codes for ids should be intensively used
     *   // Such as, 
     *   // for (const RREdgeId& in_edge : rr_graph.node_in_edges()) {
     *   //   if (RREdgeId::INVALID() != in_edge) {
     *   //     ...
     *   //   }
     *   // }
     *   rr_graph.compress()
     *   // rr_graph.is_dirty() == false
     */
    void remove_node(const RRNodeId& node);
    void remove_edge(const RREdgeId& edge);

    /* Set node-level information */
    void set_node_xlow(const RRNodeId& node, const short& xlow);
    void set_node_ylow(const RRNodeId& node, const short& ylow);
    void set_node_xhigh(const RRNodeId& node, const short& xhigh);
    void set_node_yhigh(const RRNodeId& node, const short& yhigh);

    /* This is a short-cut function, set xlow/xhigh/ylow/yhigh for a node
     * Please respect the following to configure the bb object:
     * bb.xmin = xlow, bb.ymin = ylow; bb.xmax = xhigh, bb.ymax = yhigh;
     */
    void set_node_bounding_box(const RRNodeId& node, const vtr::Rect<short>& bb);

    void set_node_capacity(const RRNodeId& node, const short& capacity);

    /* A generic function to set the ptc_num for a node */
    void set_node_ptc_num(const RRNodeId& node, const short& ptc);

    /* Only applicable to IPIN and OPIN, set the ptc_num for a node, which is the pin id in a logic block,
     * See definition in t_type_descriptor data structure   
     */
    void set_node_pin_num(const RRNodeId& node, const short& pin_id);

    /* Only applicable to CHANX and CHANY, set the ptc_num for a node, which is the track id in a routing channel,
     * Routing channel is a group of routing tracks, each of which has a unique index
     * An example 
     *       Routing Channel 
     *    +------------------+
     *    |                  |
     * ---|----------------->|----> track_id: 0
     *    |                  |
     *   ...   More tracks  ...
     *    |                  |
     * ---|----------------->|----> track_id: 1
     *    |                  |
     *    +------------------+
     */
    void set_node_track_num(const RRNodeId& node, const short& track_id);

    /* Only applicable to SOURCE and SINK, set the ptc_num for a node, which is the class number in a logic block,
     * See definition in t_type_descriptor data structure   
     */
    void set_node_class_num(const RRNodeId& node, const short& class_id);

    /* Set the routing cost index for node, see node_cost_index() for details */
    /* TODO: the cost index should be changed to a StrongId!!! */
    void set_node_cost_index(const RRNodeId& node, const short& cost_index);

    /* Set the directionality for a node, only applicable to CHANX and CHANY */
    void set_node_direction(const RRNodeId& node, const e_direction& direction);

    /* Set the side for a node, only applicable to OPIN and IPIN */
    void set_node_side(const RRNodeId& node, const e_side& side);

    /* Set the RC information for a node */
    void set_node_R(const RRNodeId& node, const float& R);
    void set_node_C(const RRNodeId& node, const float& C);

    /* Set the routing segment linked to a node, only applicable to CHANX and CHANY */
    void set_node_segment(const RRNodeId& node, const RRSegmentId& segment_index);

    /* Edge partitioning is performed for efficiency, 
     * so we can store configurable and non-configurable edge lists for a node in one vector, 
     * and efficiently iterate over all edges, or only the configurable or non-configurable subsets.
     * This function will re-organize the incoming and outgoing edges of each node, 
     * i.e., node_in_edges() and node_out_edges():
     * 1. configurable edges (1st part of the vectors) 
     * 2. non-configurable edges (2nd part of the vectors) 
     */
    void partition_edges();

    /* Graph-level Clean-up, remove invalid nodes/edges etc.
     * This will clear the dirty flag (query by is_dirty()) of RRGraph object, if it was set 
     */
    void compress();

    /* top-level function to free, should be called when to delete a RRGraph */
    void clear();

  private: /* Internal Mutators to perform edge partitioning */
    /* classify the input edges of each node to be configurable (1st part) and non-configurable (2nd part) */
    void partition_node_in_edges(const RRNodeId& node);

    /* classify the output edges of each node to be configurable (1st part) and non-configurable (2nd part) */
    void partition_node_out_edges(const RRNodeId& node);

    /* classify the input edges of each node to be configurable (1st part) and non-configurable (2nd part) */
    void partition_in_edges();

    /* classify the output edges of each node to be configurable (1st part) and non-configurable (2nd part) */
    void partition_out_edges();

  private: /* Internal free functions */
    void clear_nodes();
    void clear_edges();
    void clear_switches();
    void clear_segments();

  private: /* Graph Compression related */
    void build_id_maps(vtr::vector<RRNodeId, RRNodeId>& node_id_map,
                       vtr::vector<RREdgeId, RREdgeId>& edge_id_map);
    void clean_nodes(const vtr::vector<RRNodeId, RRNodeId>& node_id_map);
    void clean_edges(const vtr::vector<RREdgeId, RREdgeId>& edge_id_map);
    void rebuild_node_refs(const vtr::vector<RREdgeId, RREdgeId>& edge_id_map);

    void set_dirty();
    void clear_dirty();

  private: /* Internal validators and builders */
    /* Fast look-up builders and validators */
    void build_fast_node_lookup() const;
    void invalidate_fast_node_lookup() const;
    bool valid_fast_node_lookup() const;
    void initialize_fast_node_lookup() const;

    /* Graph property Validation */
    bool validate_sizes() const;
    bool validate_node_sizes() const;
    bool validate_edge_sizes() const;
    bool validate_switch_sizes() const;
    bool validate_segment_sizes() const;

    bool validate_invariants() const;
    bool validate_unique_edges_invariant() const;

    bool validate_crossrefs() const;
    bool validate_node_edge_crossrefs() const;

    /* Node-level validators */
    bool validate_node_segment(const RRNodeId& node) const;
    bool validate_node_in_edges(const RRNodeId& node) const;
    bool validate_node_out_edges(const RRNodeId& node) const;
    bool validate_node_edges(const RRNodeId& node) const;

    /* Edge-level checking */
    bool validate_node_is_edge_src(const RRNodeId& node, const RREdgeId& edge) const;
    bool validate_node_is_edge_sink(const RRNodeId& node, const RREdgeId& edge) const;
    bool validate_edge_switch(const RREdgeId& edge) const;
    bool validate_edge_src_node(const RREdgeId& edge) const;
    bool validate_edge_sink_node(const RREdgeId& edge) const;

    /* List-level checking */
    bool validate_nodes_in_edges() const;
    bool validate_nodes_out_edges() const;
    bool validate_nodes_edges() const;
    bool validate_node_segments() const;
    bool validate_edge_switches() const;
    bool validate_edge_src_nodes() const;
    bool validate_edge_sink_nodes() const;

    /* Validate switch list */
    bool valid_switch_id(const RRSwitchId& switch_id) const;

    /* Validate segment list */
    bool valid_segment_id(const RRSegmentId& segment_id) const;

  private: /* Internal Data */
    /* Node related data */
    vtr::vector<RRNodeId, RRNodeId> node_ids_; /* Unique identifiers for the nodes */
    vtr::vector<RRNodeId, t_rr_type> node_types_;

    vtr::vector<RRNodeId, vtr::Rect<short>> node_bounding_boxes_;

    vtr::vector<RRNodeId, short> node_capacities_;
    vtr::vector<RRNodeId, short> node_ptc_nums_;
    vtr::vector<RRNodeId, short> node_cost_indices_;
    vtr::vector<RRNodeId, e_direction> node_directions_;
    vtr::vector<RRNodeId, e_side> node_sides_;
    vtr::vector<RRNodeId, float> node_Rs_;
    vtr::vector<RRNodeId, float> node_Cs_;
    vtr::vector<RRNodeId, RRSegmentId> node_segments_; /* Segment ids for each node */
    /* Record the dividing point between configurable and non-configurable edges for each node */
    vtr::vector<RRNodeId, size_t> node_num_non_configurable_in_edges_;
    vtr::vector<RRNodeId, size_t> node_num_non_configurable_out_edges_;

    vtr::vector<RRNodeId, std::vector<RREdgeId>> node_in_edges_;
    vtr::vector<RRNodeId, std::vector<RREdgeId>> node_out_edges_;

    /* Edge related data */
    vtr::vector<RREdgeId, RREdgeId> edge_ids_; /* unique identifiers for edges */
    vtr::vector<RREdgeId, RRNodeId> edge_src_nodes_;
    vtr::vector<RREdgeId, RRNodeId> edge_sink_nodes_;
    vtr::vector<RREdgeId, RRSwitchId> edge_switches_;

    /* Switch related data
     * Note that so far there has been no need to remove
     * switches, so no such facility exists
     */
    /* Unique identifiers for switches which are used in the RRGraph */
    vtr::vector<RRSwitchId, RRSwitchId> switch_ids_;
    /* Detailed information about the switches, which are used in the RRGraph */
    vtr::vector<RRSwitchId, t_rr_switch_inf> switches_;

    /* Segment relatex data 
     * Segment info should be corrected annotated for each rr_node
     * whose type is CHANX and CHANY
     */
    vtr::vector<RRSegmentId, RRSegmentId> segment_ids_; /* unique identifiers for routing segments which are used in the RRGraph */
    vtr::vector<RRSegmentId, t_segment_inf> segments_;  /* detailed information about the segments, which are used in the RRGraph */

    /* Misc. */
    /* A flag to indicate if the graph contains invalid elements (nodes/edges etc.) */
    bool dirty_ = false;

    /* Fast look-up to search a node by its type, coordinator and ptc_num 
     * Indexing of fast look-up: [0..xmax][0..ymax][0..NUM_TYPES-1][0..ptc_max][0..NUM_SIDES-1] 
     */
    typedef std::vector<std::vector<std::vector<std::vector<std::vector<RRNodeId>>>>> NodeLookup;
    mutable NodeLookup node_lookup_;
};

#endif