#ifndef TGRAPH_H
#define TGRAPH_H
#include "tnode.h"
#include<cmath>
#include<cassert>
#include<fstream>
#include<iostream>
#include<vector>
#include<map>
using namespace std;
const int DIRECTION_UP=0;
const int DIRECTION_RIGHT=1;
const int DIRECTION_DOWN=2;
const int DIRECTION_LEFT=3;

class Transistor {
    public:
        int nodes[2];
        int state;
        int type;
        int strength;
        int circuit_id;
        Transistor(){}
        Transistor(int node1, int node2, int _type, int _circuitid) {
            nodes[0]=node1;
            nodes[1]=node2;
            type=_type;
            if(type==-1) state=1;
            strength=STRENGTH_Y;
            circuit_id=_circuitid;
        }
        int tstate(int nodestate) {
        	if(type==-1) return 1;
            if(type==TRANSISTOR_N) {
                return nodestate;
            }
            else {
                if(nodestate==1) return 0;
                else if(nodestate==0) return 1;
                return -1;
            }
            
        }

};


class TGraph {
    public:
        vector<vector<int> > circuit;
        vector<TNode> nodes;
        map<int,Transistor> transistors;
        vector<int> input_name;
        int inputgroups;
        vector<int> output_name;
        int outputgroups;

        int circuit_width, circuit_height;
        int number_of_ptransistors, number_of_ntransistors;
        int number_of_outputs, number_of_inputs;
        int number_of_vdds, number_of_vccs;
        ifstream fin;
        TGraph() {}
        void read_input(char* file) {
            fin.open(file);
            // reading attributes
            fin>>circuit_height>>circuit_width;
            fin>>number_of_outputs>>number_of_inputs;
            fin>>number_of_vdds>>number_of_vccs;
            fin>>number_of_ptransistors>>number_of_ntransistors;

            //initializing circuit grid
            circuit.resize(circuit_height);
            for(int i=0;i<circuit_height;i++) circuit[i].resize(circuit_width);

            //reading circuit grid
            for(int i=0;i<circuit_height;i++) {
                for(int j=0;j<circuit_width;j++) {
                    fin >> circuit[i][j];
                }
            }
        }
        int get_node_type(int type) {
            if(type==0) return NODE_TYPE_EMPTY;
            if(type<15) return NODE_TYPE_JUNCTION;
            int prev=15;
            if(type>=prev && type < prev + number_of_outputs) return NODE_TYPE_OUTPUT;
            prev += number_of_outputs;
            if( type >= prev && type < prev + number_of_inputs) return NODE_TYPE_INPUT;
            prev += number_of_inputs;
            if( type >= prev && type < prev + number_of_vdds) return NODE_TYPE_VDD;
            prev += number_of_vdds;
            if( type >= prev && type < prev + number_of_vccs) return NODE_TYPE_VCC;
            prev += number_of_vccs;
            if( type >= prev && type < prev + number_of_ptransistors) return NODE_TYPE_TRANSISTOR_P;
            prev += number_of_ptransistors;
            if( type >= prev && type < prev + number_of_ntransistors) return NODE_TYPE_TRANSISTOR_N;
            cout<<"error\n";
            assert(false);
            return NODE_TYPE_UNKNOWN;
        }


        bool has_edge_to(int i, int j, int direction) {
            int type=circuit[i][j];
            if(type==13) return true;
            int node_type=get_node_type(type);
            if(node_type==NODE_TYPE_TRANSISTOR_P||node_type==NODE_TYPE_TRANSISTOR_N) { 
                if(direction==DIRECTION_DOWN || direction==DIRECTION_UP) return true;
                else return false; 
            }
            if(node_type==NODE_TYPE_OUTPUT||node_type==NODE_TYPE_INPUT||node_type==NODE_TYPE_VDD||node_type==NODE_TYPE_VCC) {

                if(i==0 && direction==DIRECTION_DOWN) return true;
                if(i==circuit_height-1 && direction==DIRECTION_UP) return true;
                if(j==0 && direction==DIRECTION_RIGHT) return true;
                if(j==circuit_width-1 && direction==DIRECTION_LEFT) return true;

                return false;
            }
            if(direction==DIRECTION_UP) {
                if(type == 4 || type == 6 || type == 7 || type == 9 || type == 11 || type == 12 || type == 14) return true;
            } else if(direction==DIRECTION_RIGHT) {
                if(type == 3  || type == 7 || type == 8 || type == 9 || type == 10 || type == 12) return true;

            } else if(direction== DIRECTION_DOWN) {
                if( type == 4 || type == 5 || type == 8 || type == 10 || type == 11 || type == 12 || type == 14) return true;
            } else if(direction == DIRECTION_LEFT) {
                if(type==3 || type == 5 || type == 6 || type == 9 || type == 10 || type == 11) return true;
            }
            return false;
        }



        void convert_to_nodes() {


            vector<vector<int> > node_id(circuit_height);
            for(int i=0;i<circuit_height;i++) {
                node_id[i].resize(circuit_width);
                for(int j=0;j<circuit_width;j++) {
                    node_id[i][j]=-1;
                }
            }



            // Connect all nodes (except transistor gates and circuit cell type 14 in horizontal direction) if they are connected in the circuits
            for(int i=0;i<circuit_height;i++) {
                for(int j=0;j<circuit_width;j++) {
                    int type=circuit[i][j];

                    if(type==0) continue;
                    node_id[i][j]=nodes.size();
                    TNode node(nodes.size(),type,get_node_type(type));
                    nodes.push_back(node);
                    // connect with the node to up
                    if(has_edge_to(i,j,DIRECTION_UP)) {
                        if(i>0 && node_id[i-1][j]!=-1 && has_edge_to(i-1,j,DIRECTION_DOWN)) {

                        	if(nodes[node_id[i-1][j]].strength != STRENGTH_INF || nodes[node_id[i][j]].strength != STRENGTH_INF) {
                            nodes[node_id[i-1][j]].add(nodes[node_id[i][j]].graph_id,-1,-1);
                            nodes[node_id[i][j]].add(nodes[node_id[i-1][j]].graph_id,-1,-1);
                            }
                        }
                    }
                    // connect with the node to left
                    if(has_edge_to(i,j,DIRECTION_LEFT)) {
                        int left=j-1;

                        // skip all the bridge cells(type 14)
                        while(left>=0 && circuit[i][left]==14) {
                            left--;

                        }
                        if(left<0) continue;


                        if(j>0 && node_id[i][left]!=-1 && has_edge_to(i,left,DIRECTION_RIGHT)) {
                            nodes[node_id[i][left]].add(nodes[node_id[i][j]].graph_id,-1,-1);
                            nodes[node_id[i][j]].add(nodes[node_id[i][left]].graph_id,-1,-1);
                            //cout<<"zNODES "<<node_id[i][j]<<","<<node_id[i][left]<<endl;
                        }                

                    }
                }

            }

            // Transistor gates are connected to the node at the left of them
            for(int i=0;i<circuit_height;i++) {
                for(int j=0;j<circuit_width;j++) {
                    int type=circuit[i][j];
                    if(get_node_type(type)==NODE_TYPE_TRANSISTOR_P||get_node_type(type)==NODE_TYPE_TRANSISTOR_N) {
                        int left=j-1;

                        // skip cell-type 14
                        while(left>=0 && circuit[i][left]==14) {
                            left--;

                        }
                        if(left<0) continue;

                        
                        if(j>0 && node_id[i][left]!=-1 && has_edge_to(i,left,DIRECTION_RIGHT)) {
                            nodes[node_id[i][left]].add_gate(nodes[node_id[i][j]].graph_id);
                            nodes[node_id[i][j]].add_gate(nodes[node_id[i][left]].graph_id);
                        }                

                    }
                }
            }
            // Two adjacent transistors are separated with a junction node

            for(int i=0;i<nodes.size();i++) {
                TNode& n=nodes[i];
                if(n.type==NODE_TYPE_TRANSISTOR_P || n.type == NODE_TYPE_TRANSISTOR_N) {

                    for(int j=0;j<n.edges.size();j++) {
                        TNode& dest=nodes[n.edges[j].dest];

                        if(dest.type==NODE_TYPE_TRANSISTOR_P || dest.type==NODE_TYPE_TRANSISTOR_N) {

                            TNode junction(nodes.size(),-1,NODE_TYPE_JUNCTION);

                            n.remove_edge(dest.graph_id);
                            dest.remove_edge(n.graph_id);
                            n.add(junction.graph_id,-1,-1);
                            dest.add(junction.graph_id,-1,-1);
                            junction.add(n.graph_id,-1,-1);
                            junction.add(dest.graph_id,-1,-1);
                            nodes.push_back(junction);
                        }
                    }
                }
            }
        
        }


        

        void merge_junctions() {
            // find all connected non-transistor nodes and merge them
            for(int i=0;i<nodes.size();i++) {
                TNode& n = nodes[i];
                if(n.type != NODE_TYPE_TRANSISTOR_P && n.type != NODE_TYPE_TRANSISTOR_N && n.strength != STRENGTH_INF) {
                    bool rerun=false;
                    for(int j=0;j<n.edges.size();j++) {
                        TNode& other = nodes[n.edges[j].dest];
                        if(other.type == NODE_TYPE_JUNCTION) {
                            n.remove_edge(other.graph_id);
                            other.remove_edge(n.graph_id);
                            j--;
                            other.type = NODE_TYPE_EMPTY;
                            for(int k=0;k<other.edges.size();k++) {
                                nodes[other.edges[k].dest].remove_edge(other.graph_id);
                                if(!n.has_edge(other.edges[k].dest)) {
                                    nodes[other.edges[k].dest].add(n.graph_id,-1,-1);
                                    n.add(other.edges[k].dest,-1,-1);
                                }
                            }
                            for(int k=0;k<other.gate_edges.size();k++) {
                                nodes[other.gate_edges[k]].remove_gate_edge(other.graph_id);
                                if(!n.has_gate_edge(other.gate_edges[k])) {
                                    nodes[other.gate_edges[k]].add_gate(n.graph_id);
                                    n.add_gate(other.gate_edges[k]);
                                    
                                }
                            }
                        }
                    }
                }
            }
        }


        void convert_transistors_to_edges() {
            for(int i=0;i<nodes.size();i++) {
                TNode& n = nodes[i];
                if((nodes[i].type == NODE_TYPE_TRANSISTOR_N || nodes[i].type == NODE_TYPE_TRANSISTOR_P)) {

                    if(n.edges.size() == 2) {
                        Edge& c = n.edges[0];
                        Edge& d = n.edges[1];
                        TNode& a = nodes[c.dest];
                        TNode& b = nodes[d.dest];
                        int type=TRANSISTOR_N;
                        if(n.type == NODE_TYPE_TRANSISTOR_P) type=TRANSISTOR_P;

                        a.remove_edge(n.graph_id);
                        b.remove_edge(n.graph_id);
                        
                        int gate=-1;
                        if(n.gate_edges.size()>0) gate=n.gate_edges[0];
                        else type=-2;
                        a.add(d.dest,type,gate,n.graph_id);
                        b.add(c.dest,type,gate,n.graph_id);
                        
                        if(nodes[c.dest].type==NODE_TYPE_INPUT) {
                            Transistor t(c.dest,d.dest,type,n.circuit_id);
                            transistors[n.graph_id]=t;
                        } else {
                            Transistor t(d.dest,c.dest,type,n.circuit_id);
                            transistors[n.graph_id]=t;

                        }
                        //Transistor(c.dest,d.dest,type);

                        n.type = NODE_TYPE_EMPTY;
                    } else if(n.edges.size()==1) {
                    	n.type=NODE_TYPE_EMPTY;
                        
                        for(int j=0;j<nodes.size();j++) {
                        if(nodes[j].has_edge(n.graph_id)) nodes[j].remove_edge(n.graph_id);
                            if(nodes[j].has_gate_edge(n.graph_id)) nodes[j].remove_gate_edge(n.graph_id);
                        if(n.has_gate_edge(j))n.remove_gate_edge(j);
                        }

                    } else {
                        n.type=NODE_TYPE_EMPTY;
                        for(int j=0;j<nodes.size();j++) {
                            if(nodes[j].has_edge(n.graph_id)) nodes[j].remove_edge(n.graph_id);
                            if(nodes[j].has_gate_edge(n.graph_id)) nodes[j].remove_gate_edge(n.graph_id);
                            if(n.has_gate_edge(j))n.remove_gate_edge(j);
                        }
                    }
                }
            }
            transistors[-1]=Transistor(-1,-1,-1,-1);
        }


        void print_graph() {
            string words[]={"unknown","empty","junction","tp","tn","input","output","vdd","vcc"};
            cout<<"graph g {\n";
            for(int i=0;i<nodes.size();i++) {
                if(nodes[i].type != NODE_TYPE_EMPTY) {
                    if(nodes[i].edges.size()==0) cout<<words[nodes[i].type+1]<<"_"<<nodes[i].graph_id<<"_"<<max(0,nodes[i].circuit_id)<<"_;\n";
                    for(int j=0;j<nodes[i].edges.size();j++) {
                        if(nodes[i].graph_id>nodes[i].edges[j].dest) continue;
                        cout<<words[nodes[i].type+1]<<"_"<<nodes[i].graph_id<<"_"<<max(0,nodes[i].circuit_id)<<"_ -- ";
                        int ind = nodes[i].edges[j].dest;
                        cout<<words[nodes[ind].type+1]<<"_"<<nodes[ind].graph_id<<"_"<<max(0,nodes[ind].circuit_id)<<"_"<<" [label=\"";
                        if(nodes[i].edges[j].type!=-1) {
                            if(nodes[i].edges[j].type==0) cout<<"P";
                            else cout<<"N";
                            cout<<"_"<<nodes[i].edges[j].gate;
                            cout<<"_"<<nodes[i].edges[j].transistor;
                        } else cout<<"a";
                        cout<<"\"];\n";

                    }
                }
            }
            cout<<"}\n";
            //for(int i=0;i<transistors.size();i++) cout<<transistors[i].gate<<endl;
        }
        void read_inputgroups() {
            // reading outputgroups
            output_name.resize(circuit_height*circuit_width);
            fin>>outputgroups;
            for(int i=0;i<output_name.size();i++) output_name[i]=-1;
            for(int i=0;i<outputgroups;i++) {
                int j;
                fin>>j;
                for(int k=0;k<j;k++) {
                    int n;
                    fin>>n;
                    for(int l=0;l<nodes.size();l++) {
                        if(nodes[l].type!=NODE_TYPE_EMPTY && nodes[l].circuit_id==n) {
                            output_name[l]=i;
                        }
                    }
                }
            }
            for(int i=0;i<nodes.size();i++) {
                for(int j=i+1;j<nodes.size();j++) {
                    if(output_name[i]!=-1&&output_name[i]==output_name[j]) {
                        if(!nodes[i].has_edge(j)) {
                            nodes[i].add(j,-1,-1);
                            nodes[j].add(i,-1,-1);
                        }
                    }
                }
            }

            input_name.resize(circuit_height*circuit_width);
            fin>>inputgroups;
            for(int i=0;i<input_name.size();i++) input_name[i]=-1;
            for(int i=0;i<inputgroups;i++) {
                int j;
                fin>>j;
                for(int k=0;k<j;k++) {
                    int n;
                    fin>>n;
                    for(int l=0;l<nodes.size();l++) {
                        if(nodes[l].type!=NODE_TYPE_EMPTY && nodes[l].circuit_id==n) {
                            input_name[l]=i;
                        }
                    }
                }
            }
        }

        void load_graph(char* filename) {
            string words[]={"unknown","empty","junction","tp","tn","input","output","vdd","vcc"};
            read_input(filename);
            convert_to_nodes();   
            merge_junctions();
 //           for(int i=0;i<nodes[60].edges.size();i++) cout<<nodes[60].edges[i].dest<<" "<<words[nodes[nodes[60].edges[i].dest].type]<<endl;
            convert_transistors_to_edges();
            read_inputgroups();


            //           cout<<"-1: "<<transistors[-1].type<<", "<<transistors[-1].state<<endl;
        }
};
#endif
