/*****************************************************************
*                                                                *
*                         Projektarbeit                          *
*                                                                *
*   "Implementierung und Darstellung ebener Fraktale mit LEDA"   *
*                                                                *
*                                                                *
*                   (c) 1998 Sascha Broich                       *
*                                                                *
*                                                                *
*      Programmteil für die Klasse der Endlichen Automaten       *
*                                                                *
*****************************************************************/

#include <LEDA/array.h>
#include <LEDA/basic.h>
#include <LEDA/string.h>
#include <LEDA/panel.h>
#include <LEDA/point.h>
#include <LEDA/random_source.h>
#include <LEDA/graph.h>
#include <LEDA/basic_graph_alg.h>
#include <LEDA/window.h>
#include <LEDA/ps_file.h>
#include <LEDA/graphwin.h>
#include <stdio.h>
#include <math.h>

using namespace leda;

class EA
{
private:
	GRAPH<int,string> ZeigG;
	GRAPH<int,int> ArbG;
	static	string ea_text;
	int Rek;
	
public:
	static char* pix;
	static int Basis;
	static double size;
	bool graph_edit(GRAPH<int,string>& ZeigG);
	bool proof(GRAPH<int,string>& ZeigG);
	static void graph_copy(GRAPH<int,string>& ZeigG,GRAPH<int,int>& ArbG);
	void det_draw(GRAPH<int,int>& ArbG,window& w,int Basis,int Rek,int i,node z,double x, double y);
	void det_draw(GRAPH<int,int>& ArbG,ps_file& w,int Basis,int Rek,int i,node z,double x, double y);
	void draw(GRAPH<int,int>& ArbG, int Basis);
	point punkt(double x,double y);
	static void PAINT(window* win);
	static void Basis_Eingabe(GraphWin& gw);
	static void Non_Det(GraphWin& gw);
	static void new_edge(GraphWin& grw,edge e);
	static void new_node(GraphWin& grw,node v);
	void menue();
	EA();
	~EA();
};

string EA::ea_text="Endlicher Automat";
char* EA::pix;
int EA::Basis=2;
double EA::size=900.0;

inline point EA::punkt(double x,double y) 
{
	point p(x,y);
	return(p);
}

EA::~EA(){}

EA::EA(){}

void EA::menue()
{
	while (graph_edit(ZeigG))
	{
		graph_copy(ZeigG,ArbG);
		draw(ArbG,Basis);

	}
}



// int graph_copy: 0,falls alles okay
//                 1, falls falsche Kantenbeschriftung usw.
void EA::graph_copy(GRAPH<int,string>& ZeigG,GRAPH<int,int>& ArbG)
{
	int n,i,j,a;
	string s,t;
	edge e;
	node v,w;
	n=0;
	forall_nodes(v,ZeigG) if(n<ZeigG.inf(v)) n=ZeigG.inf(v);

	array<node> z_list(0,n);

	ArbG.clear();

	for(i=0;i<=n;i++)
	{
		z_list[i]=ArbG.new_node(i);
	}
	forall_edges(e,ZeigG)
	{
		v=z_list[ZeigG.inf(ZeigG.source(e))];
		w=z_list[ZeigG.inf(ZeigG.target(e))];
		s=ZeigG.inf(e)+",";
		printf("\n%2d->%2d:",ZeigG[v],ZeigG[w]);
		i=0;j=0;
		while (j>-1)
		{
			j=s.pos(",",i);
			if (j>i)
			{
				a=atoi(s(i,j-1));
				printf("%2d,",a);
				ArbG.new_edge(v,w,a);
				i=j+1;
			}
			else
			  i++;
		}
	}
}

void EA::draw(GRAPH<int,int>& ArbG,int Basis)
{
	panel iter("Iterationstiefe");
	iter.int_item("Iterationen",Rek,0,20);
	iter.real_item("Fenstergroesse",size);
	int ok=iter.button("OK");
	int no=iter.button("Abbrechen");
	iter.display();
	int choice=-1;
	while (choice!=no)
	{
		choice=iter.read();
		if (choice==ok)
		{
			iter.close();
			float t0,t1,t2,t3;
			window w((int)size,(int)size,ea_text);
			w.set_redraw(EA::PAINT);
			w.set_flush(true);
			w.init(-0.05,1.05,-0.05);
			w.display();

			t0=used_time();
		
			det_draw(ArbG,w,Basis,Rek,0,ArbG.first_node(),0.0,0.0);
			pix=w.get_window_pixrect();

			t1=used_time();

			printf("\nZeit: %.2f Sekunden.",t1-t0);
			panel wp("Fertig");
			int w_ok=wp.button("Fertig");
			int w_save=wp.button("Speichern");
			wp.display();
			int w_r=-1;
			while (w_r!=w_ok)
			{
				w_r=wp.read();
				if (w_r==w_save)
				{
					wp.close();
					string name;
					panel w2ps("Speichern");
					w2ps.string_item("Dateiname",name);
					int ps_ok=w2ps.button("Speichern");
					int ps_no=w2ps.button("Abbrechen");
					int ps_ch=-1;
					w2ps.display();
					while ((ps_ch!=ps_ok)&&(ps_ch!=ps_no))
					{
						ps_ch=w2ps.read();
						if (ps_ch==ps_ok) 
						{
							panel ps_wait("Bitte warten");
							ps_wait.button("Bitte warten");
							ps_wait.display();
							ps_file ps(name);
							ps.init(0.0,1.0,0.0);
							det_draw(ArbG,ps,Basis,Rek,0,ArbG.first_node(),0.0,0.0);
							ps_wait.close();
						}
					}
					w2ps.close();
					wp.display();
				}
			}
			wp.close();
			w.close();
			iter.display();
		}
	}
	iter.close();
}

void EA::det_draw(GRAPH<int,int>& ArbG,window& w,int Basis, int Rek,int i,node z,double x, double y)
{
	double m;

	m=exp((-i)*log(Basis));

	if (i==Rek)
	{
		x/=Basis;
		y/=Basis;
		w.draw_filled_rectangle(x,y,x+m,y+m,black);
	}
	else
	{
		int j,a,b;
		edge e;

		forall_out_edges(e,z)
		{
			j=ArbG.inf(e);
			a=j/10;
			b=j%10;
			det_draw(ArbG,w,Basis,Rek,i+1,ArbG.target(e),x+(a*m),y+(b*m));
		}
	}
}

void EA::det_draw(GRAPH<int,int>& ArbG,ps_file& w,int Basis, int Rek,int i,node z,double x, double y)
{
	double m;

	m=exp((-i)*log(Basis));

	if (i==Rek)
	{
		x/=Basis;
		y/=Basis;
		w.draw_box(x,y,x+m,y+m,black);
	}
	else
	{
		int j,a,b;
		edge e;

		forall_out_edges(e,z)
		{
			j=ArbG.inf(e);
			a=j/10;
			b=j%10;
			det_draw(ArbG,w,Basis,Rek,i+1,ArbG.target(e),x+(a*m),y+(b*m));
		}
	}
}

bool EA::graph_edit(GRAPH<int,string>& ZeigG)
{
	GraphWin gw(ZeigG,"Eingabe des Automaten");
//	gw.auto_create_target=false;
	gw.set_directed(true);
	gw.set_edge_shape(poly_edge,true);
	gw.set_edge_style(solid_edge,true);
	gw.set_edge_thickness(1.0,true);
	gw.set_edge_width((int)1.0,true);
	gw.set_edge_label_type(data_label,true);
	gw.set_node_label_type(data_label,true);

	gw.set_new_node_handler(EA::new_node);
	gw.set_new_edge_handler(EA::new_edge);
	
	gw_add_simple_call(gw,EA::Non_Det,"Nichtdeterminismen",0);
	gw_add_simple_call(gw,EA::Basis_Eingabe,"Basis",0);
	gw.enable_calls();	

	int ret=1;
	bool z_null=false;
	while((!z_null)&&ret)
	{
		ret=gw.open();
		node v;
		z_null=proof(ZeigG);
	}
	return(ret);
}

void EA::Non_Det(GraphWin& gw)
{
	GRAPH<int,int> ArbG;
	graph& G=gw.get_graph();
	int i,j;
	string s;
	node v,z0;
	node_array<node> copy(G);
	edge e,f;
	list<node> non_det;
	list<node> terminal;
	list<node> non_reach;

	forall_nodes(v,G)
	{
		if(G.outdeg(v)==0) terminal.append(v);
		copy[v]=ArbG.new_node(atoi(gw.get_data(v)));
	}

	forall_edges(e,G)
	{
		s=gw.get_data(e)+",";
		i=0;j=0;
		while (j>-1)
		{
			j=s.pos(",",i);
			if (j>i)
			{
				ArbG.new_edge(copy[G.source(e)],copy[G.target(e)],atoi(s(i,j-1)));
				i=j+1;
			}
		}
	}

	node_array<node> rcopy(ArbG);
	forall_nodes(v,G) rcopy[copy[v]]=v;

	forall_nodes(v,ArbG)
	{
		if(ArbG.inf(v)==0) z0=v;
		forall_out_edges(e,v)
		{
			forall_out_edges(f,v)
			{
				if((e!=f)&&(ArbG.inf(e)==ArbG.inf(f))) 
				{
					non_det.append(rcopy[v]);	
				}
			}
		}
	}
	node_array<bool> reached(ArbG);
	forall_nodes(v,ArbG) reached[v]=false;
	list<node> reached_nodes;
	reached_nodes=DFS(ArbG,z0,reached);
	forall_nodes(v,ArbG) if(!reached[v]) non_reach.append(rcopy[v]);

	gw.set_color(G.all_nodes(),yellow);
	gw.set_color(non_reach,black);
	gw.set_color(non_det,red);
	gw.set_color(terminal,blue);
	//	gw.del_messages();
	s="";
	if(!non_det.empty()) s=s+"Rot=nichtdeterministisch ";
	if(!terminal.empty())s=s+"Blau=keine Out-Kanten ";
	if(!non_reach.empty()) s=s+"Schwarz=nicht erreichbare Knoten";
	gw.message(s);
	gw.update_graph();
}

void EA::Basis_Eingabe(GraphWin& gw)
{
  //	gw.del_messages();
	panel P("Eingabe der Basis");
	P.int_item("Basis",EA::Basis,2,9,1);
	int Pok=P.button("OK");
	P.display();
	while (P.read()!=Pok);

	graph& G=gw.get_graph();
	int i,j,a;
	string s;
	edge e;
	list<edge> FehlerListe;

	forall_edges(e,G)
	{
		s=gw.get_data(e)+",";
		i=0;j=0;
		while (j>-1)
		{
			j=s.pos(",",i);
			if (j>i)
			{
				a=atoi(s(i,j-1));
				if((a/10)>=EA::Basis) FehlerListe.append(e);
				if((a%10)>=EA::Basis) FehlerListe.append(e);
				i=j+1;
			}
		}
	}

	gw.set_color(G.all_edges(),black);
	gw.set_color(FehlerListe,red);
	gw.set_label_color(G.all_edges(),black);
	gw.set_label_color(FehlerListe,red);
	if(!FehlerListe.empty())
		gw.message("Zu kleine Basis");
}

void EA::PAINT(window* win){win->put_pixrect(EA::pix);}

void EA::new_edge(GraphWin& grw,edge e)
{
	string s;
	point x=grw.get_target_anchor(e);
	panel p;
	p.string_item("Funktionen:",s);
	int ok=p.button("OK");
	int p1 = (int) x.xcoord();
	int p2 = (int) x.ycoord();
	p.display(p1, p2, grw.get_window());
	while(p.read()!=ok);
	p.close();
	grw.set_data(e,s);
	grw.update_graph();
}

void EA::new_node(GraphWin& grw,node v)
{
	string index="";
	string number="0123456789";
	int i=grw.get_index(v);
	while(i>-1)
	{
		index=number(i%10,i%10).cstring()+index;
		i/=10;
		if(i==0)i--;
	}
	grw.set_data(v,index);
	grw.update_graph();
}

bool EA::proof(GRAPH<int,string>& ZeigG)
{
	bool t=false,t1;
	string s,c="0123456789,";
	int i,j;
	edge e;
	node v;
	forall_nodes(v,ZeigG) t=t||(ZeigG.inf(v)==0);
	if(t)
	forall_edges(e,ZeigG)
	{
		if(t)
		{
			s=ZeigG.inf(e);
			for(i=0;i<s.length();i++)
			{
				t1=false;
				for(j=0;j<11;j++) t1=t1||(c(j,j)==s(i,i));
				t=t&&t1;		
			}
		}
	}
	return(t);
}