
#include "tgraph.h"
#include<cmath>
#include<fstream>
#include<iostream>
#include<vector>
#include<queue>
#include<map>
using namespace std;

int steplimit=1000;
TGraph g;
queue<int> E;
queue<int> C;

void init() {
    for(int i=0;i<g.nodes.size();i++) g.nodes[i].newstate=-1;
    for(int i=0;i<g.nodes.size();i++) g.nodes[i].done=true;
    map<int,Transistor>::iterator p;
    for(p=g.transistors.begin();p!=g.transistors.end();p++) {
    	if(p->second.type!=-1) p->second.state=-1;
    	else p->second.state=1;

    }
}

void perturb(int node) {
    TNode& n = g.nodes[node];
    if(n.strength!=STRENGTH_INF && n.done) {
        n.done=false;
        E.push(node);
    }
}


void find_vicinity(vector<int>& V, int node) {

    TNode& n = g.nodes[node];
    n.found=true;
    V.push_back(n.graph_id);
    for(int i=0;i<n.edges.size();i++) {
    	
        TNode& other = g.nodes[n.edges[i].dest];
        if(other.strength<STRENGTH_INF) {
            if(!other.found) find_vicinity(V,other.graph_id);
        }
    }


}


int up(int a, int b) {
    if(b==1||b==-1) return a;
    return 0;
}
int down(int a, int b) {
    if(b==0||b==-1) return a;
    else return 0;
}
int tilde(int a, int b) {
    if(a>=b) return a;
    return 0;
}

int compute_b(int node, bool u) {
    TNode& n = g.nodes[node];
    int b=up(n.strength,n.state);
    for(int j=0;j<n.edges.size();j++) {
        TNode& other = g.nodes[n.edges[j].dest];
        if(other.strength!=STRENGTH_INF) continue;
        Transistor& t = g.transistors[n.edges[j].transistor];
        if(t.state==0) continue;
        if(u) b=max(b,up(t.strength,other.state));
        else b=max(b,down(t.strength,other.state));

    }

    
    return b;

}

void solve_q(vector<int>& V) {
    vector<queue<int> > L(4);
    for(int i=0;i<V.size();i++) {
        TNode& n = g.nodes[V[i]];
        n.done=false;
        n.q=n.strength;
        for(int j=0;j<n.edges.size();j++) {
            TNode& other = g.nodes[n.edges[j].dest];
            if(other.strength!=STRENGTH_INF) continue;
            Transistor& t = g.transistors[n.edges[j].transistor];
            if(t.state==1) {
                n.q = max(n.q,t.strength);

            }
        }
        
        L[n.q].push(n.graph_id);
    }
    int qval;
    for(int i=STRENGTH_Y;i>0;i--) {
        while(!L[i].empty()) {
            int node=L[i].front();
            L[i].pop();
            TNode& n = g.nodes[node];
            if(!n.done) {
                n.done=true;
                for(int j=0;j<n.edges.size();j++) {
                    TNode& other = g.nodes[n.edges[j].dest];

                    if(other.strength==STRENGTH_INF) continue;
                    Transistor& t = g.transistors[n.edges[j].transistor];
                    if(t.state!=1) continue;
                    qval=min(n.q,t.strength);
                    if(t.state==1 && qval > other.q) {
                        other.q=qval;
                        L[qval].push(other.graph_id);
                    }

                }
            }
        }
    }
}



void solve_u(vector<int>& V) {
    vector<queue<int> > L(4);
    for(int i=0;i<V.size();i++) {
        TNode& n = g.nodes[V[i]];
        n.done=false;
        n.u=tilde(compute_b(n.graph_id,true),n.q);
        L[n.u].push(n.graph_id);

    }
    int uval,aux;
    for(int i=STRENGTH_Y;i>0;i--) {
        while(!L[i].empty()) {
            int node=L[i].front();
            L[i].pop();
            TNode& n = g.nodes[node];
            if(!n.done) {
                n.done=true;
                for(int j=0;j<n.edges.size();j++) {
                    TNode& other = g.nodes[n.edges[j].dest];
                    if(other.strength==STRENGTH_INF) continue;
                    Transistor& t = g.transistors[n.edges[j].transistor];
                    if(t.state==0) continue;
                    aux=min(n.u,t.strength);
                    uval=tilde(aux,other.q);
                    if(other.u < uval) {
                        other.u=uval;
                        L[uval].push(other.graph_id);
                    }

                }
            }
        }
    }
}
void solve_d(vector<int>& V) {
    vector<queue<int> > L(4);
    for(int i=0;i<V.size();i++) {
        TNode& n = g.nodes[V[i]];
        n.done=false;
        n.d=tilde(compute_b(n.graph_id,false),n.q);
        L[n.d].push(n.graph_id);
    }
    int dval,aux;
    for(int i=STRENGTH_Y;i>0;i--) {
        while(!L[i].empty()) {
            int node=L[i].front();
            L[i].pop();
            TNode& n = g.nodes[node];
            if(!n.done) {
                n.done=true;
                for(int j=0;j<n.edges.size();j++) {
                    TNode& other = g.nodes[n.edges[j].dest];
                    if(other.strength==STRENGTH_INF) continue;
                    Transistor& t = g.transistors[n.edges[j].transistor];
                    if(t.state==0) continue;
                    aux=min(n.d,t.strength);
                    dval=tilde(aux,other.q);
                    if(other.d < dval) {
                        other.d=dval;
                        L[dval].push(other.graph_id);
                    }

                }
            }
        }
    }

}






void vicinity_response(int node) {
    vector<int> V;
    find_vicinity(V,node);
    
    solve_q(V);
    for(int i=0;i<V.size();i++) {
        //cout<<V[i]<<".q = "<<g.nodes[V[i]].q<<endl;
    }
    solve_u(V);
    for(int i=0;i<V.size();i++) {
       // cout<<V[i]<<".u = "<<g.nodes[V[i]].u<<endl;
    }
    solve_d(V);
    for(int i=0;i<V.size();i++) {
     //   cout<<V[i]<<".d = "<<g.nodes[V[i]].d<<endl;
    }
    
    for(int i=0;i<V.size();i++) {
        TNode& n = g.nodes[V[i]];
        n.found=false;
        n.newstate=n.nstate();
        if(n.state != n.newstate) C.push(n.graph_id);
    }
    for(int i=0;i<V.size();i++) {
        TNode& n=g.nodes[V[i]];
    }
 //   cout<<"--\n";
}




void step() {
	//cout<<"List of nodes to be edited:\n";
    while(!E.empty()) {
        int node=E.front();
        //cout<<node<<endl;
        E.pop();
        if(!g.nodes[node].done) {
            vicinity_response(node);
        }
        
    }
    //cout<<"-----\n";
    while(!C.empty()) {
        int node=C.front();
        C.pop();
        TNode& n = g.nodes[node];
        
        if(n.type<1) continue;
        n.state=n.newstate;
        for(int j=0;j<n.gate_edges.size();j++) {
            int gate=n.gate_edges[j];
            Transistor& t = g.transistors[gate];
            
            if(t.state!=t.tstate(n.state)) {
                t.state=t.tstate(n.state);
                perturb(t.nodes[0]);
                perturb(t.nodes[1]);
            }
        } 
    }
}


void phase() {
    // Initialize


    for(int i=0;i<g.nodes.size();i++) {
        TNode& n = g.nodes[i];
        if(n.type<1) continue;
        if(n.strength!=STRENGTH_INF)  n.state=n.newstate;
        for(int j=0;j<g.nodes[i].gate_edges.size();j++) {
            int gate=g.nodes[i].gate_edges[j];
            Transistor& t = g.transistors[gate];
            if(t.tstate(n.state) != t.state) {
                t.state=t.tstate(n.state);
                perturb(t.nodes[0]);
                perturb(t.nodes[1]);
            }
        }
        if(n.strength==STRENGTH_INF) {
            for(int j=0;j<g.nodes[i].gate_edges.size();j++) {
                int gate=g.nodes[i].gate_edges[j];
                Transistor& t = g.transistors[gate];
                if(t.state==1||t.state==-1) {
                    if(g.nodes[t.nodes[1]].strength != STRENGTH_INF) perturb(t.nodes[1]);
                }
            }
        } else perturb(i);
    }
    // Repeat step until the circuit stabilizes
    int stepcount=0;
    while(!E.empty() && stepcount < steplimit) {
        step();
        stepcount++;
    }
    

}



void run(vector<int>& inputs) {
    for(int i=0;i<g.nodes.size();i++) {
        for(int j=0;j<inputs.size();j++) {
            if(g.input_name[i]==j) {
            	g.nodes[i].state=inputs[j];       
            }
        }
    }
    init();
    phase();
    for(int i=0;i<g.nodes.size();i++) {
        TNode& n=g.nodes[i];
        if(n.type==NODE_TYPE_OUTPUT) cout<<n.circuit_id<<": "<<n.state<<endl;
    }
}

void run() {
    init();
    phase();
}







int main(int argc, char* argv[]) {
    if(argc==1) g.load_graph((char*)"input");
    else g.load_graph(argv[1]);
//    g.print_graph();
    
    vector<int> inputs(g.inputgroups);
    for(int i=0;i<(1<<g.inputgroups);i++) {
        for(int j=0;j<g.inputgroups;j++) inputs[j]=(i>>j)&1;
        cout<<"Input: ";
        for(int j=0;j<g.inputgroups;j++) cout<<inputs[j];
        cout<<endl;
        run(inputs);
        cout<<"---\n";
    //break;
    }


}
