/*----------------------------------------------------------------*\
	   CS130 Assignment #3 ( 1999 )

		DJIKTRA.CPP - Implementation of Djiktra's Algo

		with a built in Visual GRAPH Studio !!

|
|    An Object Oriented Approach to Implementation Of Djiktra
|
\*----------------------------------------------------------------*/


#include <fstream.h>
#include <conio.h>
#include <stdlib.h>
#include <string.h>
#include <dos.h>
#include <graphics.h>
#include <math.h>


void ftoa(float number,char *string);


#define MOUSE_INT							0x33
const float INF=32767;   // Infinity for vertices

class mouse
	{
	public:

	int Reset(int& buttons)
		{
		union REGS inregs, outregs;
		inregs.x.ax = 0x00;
		int86(MOUSE_INT, &inregs, &outregs);
		buttons = outregs.x.bx;
		return(outregs.x.ax);
		}

	int Show()
		{
		union REGS inregs, outregs;
		inregs.x.ax = 0x01;
		int86(MOUSE_INT, &inregs, &outregs);
		return(1);
		}

	int Hide()
		{
		union REGS inregs, outregs;
		inregs.x.ax = 0x02;
		int86(MOUSE_INT, &inregs, &outregs);
		return(1);
		}

	int Status(int& x, int& y, int& buttons)
		{
		union REGS inregs, outregs;
		inregs.x.ax = 0x03;
		int86(MOUSE_INT, &inregs, &outregs);
		x			= outregs.x.cx;
		y			= outregs.x.dx;
		buttons = outregs.x.bx;
		return(1);
		}

		void Clip(int x1,int y1,int x2,int y2)
		{
			union REGS inregs,outregs;

			inregs.x.ax=0x7;
			inregs.x.cx=x1;
			inregs.x.dx=x2;
			int86(MOUSE_INT,&inregs,&outregs);

			inregs.x.ax=0x8;
			inregs.x.cx=y1;
			inregs.x.dx=y2;
			int86(MOUSE_INT,&inregs,&outregs);
		}

		void RemoveClipping()
		{
			Clip(0,0,640,480);  //______Only for VGA_____
		}


	};


class Data
{
private:
	int vertex;
	float distance;
public:
	void Set_vertex(int v)
	{
		vertex=v;
	}
	int Return_vertex()
	{
		return vertex;
	}

	void Set_distance(float d)
	{
		distance=d;
	}
	float Return_distance()
	{
		return distance;
	}

};


//__________Nodes for the heap structure_______________
class Node
{
private:
	Data data;
public:

	void Set_priority(float p)
	{
		data.Set_distance(p);
	}
	float Return_priority()
	{
		return data.Return_distance();
	}

	void Set_data(Data d)
	{
		data=d;
	}
	Data Return_data()
	{
		return data;
	}


};

class Heap
{
private:
	Node* heap;
	int last;		 //____last stores current last element position_________
	int size;
	int* node_locations; //_____stores positions of nodes in the heap______

public:
	//____________Constructors____________
	Heap(int siz)
	{
		heap=new Node[siz];
		node_locations=new int[siz];
		int i;
		for(i=0;i<siz;i++)
		{
			node_locations[i]=-1;
		}

		last=-1;
		size=siz;
	}

	~Heap()
	{
		Destroy();
	}

	void Destroy()
	{
		delete[] heap;
		heap=NULL;
		delete[] node_locations;
		node_locations=NULL;
	}

	//___________Interface Functions_________
	int Insert_Element(Data d);
	Data DeleteMinimum();
	int Update_Element(Data d);
	Data Return_data(int vertexno)
	{
		int pos=node_locations[vertexno-1];
		if(pos>=0)
		{
			return heap[pos].Return_data();
		}
		else
		{
			Data d;
			d.Set_vertex(-1);
			return d;
		}
	}


	void ClearHeap()
	{
		last=-1;
	};
	int IsEmpty()
	{
		if (last<0)
			return -1;
		else
			return 0;
	}

	void Print()
	{
		int i;
		for(i=0;i<=last;i++)
		{
			cout << endl << heap[i].Return_data().Return_vertex();
			cout << "    " << heap[i].Return_data().Return_distance();
		}
		for(i=0;i<=last;i++)
		{
			cout << endl << node_locations[i];
		}
	}


private:
	//_________Implementation Functions______________
	void SwapNodes(Node& a,Node& b)
	{
		Node t;
		t=a;
		a=b;
		b=t;
	}
	void SwapNodeLocations(int a,int b)
	{
		int t;
		t=node_locations[a];
		node_locations[a]=node_locations[b];
		node_locations[b]=t;
	}

	int Parent(int c)
	{
		if(c==0)
			return 0;
		else
			return int((c+1)/2  -  1);
	}

	int LeftChild(int p)
	{
		return 2*p+1;
	}

	int RightChild(int p)
	{
		return (2*p+2);
	}


};


int Heap::Insert_Element(Data d)
{

	if(last==size-1)
		return -1;
	else
	{
		last++;
		heap[last].Set_data(d);
		node_locations[d.Return_vertex()-1]=last;
	}

	int i=last;
	//_______Swap up till we get heap property_________
	while( heap[Parent(i)].Return_priority() >
				heap[i].Return_priority() )
	{

		SwapNodes(heap[Parent(i)],heap[i]);

		SwapNodeLocations(heap[Parent(i)].Return_data().Return_vertex()-1,
				heap[i].Return_data().Return_vertex()-1);

		i=Parent(i);
	}
	return 0;


}

int Heap::Update_Element(Data d)
{
//	cout << endl << "Update " << d.Return_vertex() << " "  << d.Return_distance();
//	getch();

	if(node_locations[d.Return_vertex()-1]==-1)
	{
		return -1;
	}
	else
	{
		heap[node_locations[d.Return_vertex()-1]].Set_data(d);
	}

	int i=node_locations[d.Return_vertex()-1];
	//_______Swap up till we get heap property_________
	while( heap[Parent(i)].Return_priority() >
				heap[i].Return_priority() )
	{

		SwapNodes(heap[Parent(i)],heap[i]);

		SwapNodeLocations(heap[Parent(i)].Return_data().Return_vertex()-1,
				heap[i].Return_data().Return_vertex()-1);

		i=Parent(i);
	}
	return 0;


}

Data Heap::DeleteMinimum()
{
	if(last<0)
	{
		cout << "Error : No Element Left !";
		return *(new Data);
	}

	//_________Store minimum priority element__________
	Data rt=heap[0].Return_data();
	node_locations[rt.Return_vertex()-1]=-1; //___Indicate not in Heap_____

	//_________Assign last element to first__________
	heap[0]=heap[last];
	node_locations[heap[last].Return_data().Return_vertex()-1]=0;
	last--;

	int i=0;
	//__________Keep on swapping downwards with lower priority child till
	//__________penultimate level of tree________________________
	while( i<=Parent(last) && last>0)
	{
		int j;

		if( ( heap[LeftChild(i)].Return_priority() <
				heap[RightChild(i)].Return_priority() ) || LeftChild(i)==last)
		{
			j=LeftChild(i);
		}
		else
			j=RightChild(i);

		if(heap[i].Return_priority() > heap[j].Return_priority() )
		{
			SwapNodes(heap[i],heap[j]);
			SwapNodeLocations(heap[i].Return_data().Return_vertex()-1,
				heap[j].Return_data().Return_vertex()-1);

		}

		i=j;
	}

	return rt;
}


class LinkList
{
public:
	int vertex;
	float distance;
	LinkList* next;

public:
	//_______Constructor______
	LinkList(int v,float d,LinkList* n)
	{
		vertex=v;
		distance=d;
		next=n;

	}

	//_______Interface functions__________
	LinkList*  Insert_Element(int v,float d)  //_______Adds in sorted order________
	{
		if(v>vertex)
		{
			if(next!=NULL)
			{
				next=next->Insert_Element(v,d);
			}
			else
			{
				next=new LinkList(v,d,NULL);
			}
			return this;
		}
		else
			return new LinkList(v,d,this);

	}

	//________Useful for traversals____________
	LinkList* Return_next()
	{
		return next;
	}

	int Return_vertex()
	{
		return vertex;
	}

	float Return_distance()
	{
		return distance;

	}

};

//___________Stores the graph__________
class GraphMap
{
private:
	LinkList** array;
	int size;
	int noofedges;

public:
	//_______Constructors__________
	GraphMap(int no_of_vertex) //______Please specify size_______
	{
		array=new LinkList*[no_of_vertex];
		size=no_of_vertex;
		//______Initialize to Null______
		for(int i=0;i<no_of_vertex;i++)
		{
			array[i]=NULL;
		}

		noofedges=0;
	}

	void Destroy()
	{
		LinkList* travel;
		for(int i=0;i<size;i++)
		{
			travel=array[i];
			while(travel!=NULL)
			{
				LinkList* t=travel->Return_next();
				if(travel) delete travel;
				travel=t;
			}
			array[i]=NULL;
		}
		delete array;
		array=NULL;
	}

	void Clear()
	{
		LinkList* travel;
		for(int i=0;i<size;i++)
		{
			travel=array[i];
			while(travel!=NULL)
			{
				LinkList* t=travel->Return_next();
				if(travel) delete travel;
				travel=t;
			}
			array[i]=NULL;
		}

		noofedges=0;
	}


	void Insert_Element(int startv,int endv,float distance)
	{
		if(array[startv-1]==NULL)
		{
			array[startv-1]=new LinkList(endv,distance,NULL);
		}
		else
		{
			array[startv-1]=array[startv-1]->Insert_Element(endv,distance);
		}
		noofedges++;
	}

	int Return_noofedges()
	{
		return noofedges;
	}

	void Set_noofedges(int e)
	{
		noofedges=e;
	}

	LinkList* Return_LinkListPointer(int v)
	{
		return array[v-1];
	}

	int EdgeIsPresent(int sv,int ev,float d)
	{
		LinkList* travel;
		travel=Return_LinkListPointer(sv);
		while(travel!=NULL)
		{
			if(travel->Return_vertex()==ev && travel->Return_distance()==d)
			{
				return 1;
			}
			travel=travel->Return_next();
		}
		return 0;
	}

	int EdgeIsPresent(int sv,int ev)
	{
		LinkList* travel;
		travel=Return_LinkListPointer(sv);
		while(travel!=NULL)
		{
			if(travel->Return_vertex()==ev)
				return 1;
			travel=travel->Return_next();
		}
		return 0;
	}

	void Print()
	{
	LinkList* travel;
	for(int i=0;i<size;i++)
	{
		travel=Return_LinkListPointer(i+1);

		cout << endl << (i+1) << " -  ";
		while(travel!=NULL)
		{
			cout << travel->Return_vertex() << "," << travel->Return_distance() << "-";
			travel=travel->Return_next();
		}

	}
	}


};


class Diktra
{
private:
	Heap* heap;
	LinkList* s;
	GraphMap* g;
	int source_vertex;
	int no_of_vertices;
	int  error;

public:
	Diktra(char* filename)
	{

		source_vertex=1;
		heap=NULL;
		s=NULL;
		g=NULL;


		error=0;
		error=FillGraph(filename);// ________Init Graphmap_______

//		g->Print();
//		getch();

		InitHeap(); //_____All all vertices with distance infinity______

		s=NULL;
		//_______Update source in heap________

	}

	~Diktra()
	{
			Destroy();
	}

	void Destroy()
	{
		if(heap) heap->Destroy();
		delete heap;
		heap=NULL;

		if(g) g->Destroy();
		delete g;
		g=NULL;
	}


	//_________Interface_________
	void Run();

	LinkList* Return_s()
	{
		return s;
	}
	GraphMap* Return_g()
	{
		return g;
	}
	void Set_source_vertex(int sv)
	{
		source_vertex=sv;
		Data d;
		d.Set_vertex(sv);
		d.Set_distance(0);
		heap->Update_Element(d);
	}

	int Return_no_of_vertices()
	{
		return no_of_vertices;
	}

	int Return_error()
	{
		return error;
	}





private:
	int FillGraph(char* fname);
	void InitHeap();

};

void Diktra::Run()
{
		Data source,d;
		LinkList* travel;


		while(!heap->IsEmpty())
		{
			source=heap->DeleteMinimum(); //_______Get Least Element______

//			cout << endl << "Min : " << source.Return_vertex() << "   " << source.Return_distance();
//			getch();

			//______Add it in set 's'___________
			if(s==NULL)
			{
				s=new LinkList(source.Return_vertex(),source.Return_distance(),NULL);
			}
			else
			{
				s=s->Insert_Element(source.Return_vertex(),source.Return_distance());
			}


			travel=g->Return_LinkListPointer(source.Return_vertex());

			//________Now Update all distances_________
			while(travel!=NULL)
			{
//				cout << endl << "Travelling  : " << travel->Return_vertex();
//				getch();

				d=heap->Return_data(travel->Return_vertex());

 //				cout << endl << "Data returned : " << d.Return_vertex() << " " << d.Return_distance();
 //				getch();

				if(d.Return_vertex()>0)
				{
				float newd=source.Return_distance()+travel->Return_distance();

				if(newd<d.Return_distance() && newd>=0)
				{
					d.Set_distance(newd);
					heap->Update_Element(d);
				}
				}
				travel=travel->Return_next();
			}
		}
}


void Diktra::InitHeap()
{
	Data d;
	int i;

	for(i=1;i<=no_of_vertices;i++)
	{
		d.Set_vertex(i);
		d.Set_distance(INF);
		heap->Insert_Element(d);
	}
}


int Diktra::FillGraph(char* fname)
{
	ifstream infile;
	infile.open(fname);
	if(infile==0)
	{
		return -1;
	}



	int i,j,l;
	int noofvertex;
	int edgeno;

	infile >> noofvertex;
	if(source_vertex>noofvertex) return (-2);
	no_of_vertices=noofvertex;

	infile >> edgeno;

	//______init heap and graphmap_______
	heap=new Heap(noofvertex);
	g=new GraphMap(noofvertex);


	int sv,ev;
	float distance;
	for(i=1;i<=edgeno;i++)
	{
		infile >> sv >> ev >> distance;
		sv++; ev++;
		if(distance>INF) distance=INF; //________constrain distances > INF
		if(distance<0) distance=0;
		g->Insert_Element(sv,ev,distance);
	}


	infile.close();

	return 0;
}


const int MAXSIZE=100;

class Program
{

private:

int coord[MAXSIZE][2];
char vertexisthere[MAXSIZE];
GraphMap *g;
int vertexno;
void *imagebuffer;
mouse pointer;

public:
	Program()
	{
		g=new GraphMap(MAXSIZE);
		vertexno=0;
		imagebuffer=NULL;

		for(int i=0;i<MAXSIZE;i++) vertexisthere[i]=0;
	}

	void Destroy()
	{
		g->Destroy(); //__________Destroy GraphMap___________
		delete g;
		g=NULL;
	}

	void Go();

	int Occupied(int x,int y);
	int Return_vertexno(int x,int y);
	void Program::cleartextxy(int x,int y,char* s);
	void WriteGraphToFile();
	void Program::Save();
	void Program::Restore() ;
	void Program::Bar(int,int,int,int) ;
	void Program::DrawEdge(int sx,int sy,int ox,int oy,float distance);
	void Program::DrawVertex(int ,int,int);
	void Program::Clear();
	void Program::Render();
	void Program::SaveGraph();
	void Program::LoadGraph();



};

void main()
{
int choice=0;
LinkList* result=NULL;

//_____________Start Console____________

while(choice!=4)
{
textbackground(0);
clrscr();

gotoxy(1,1);
textbackground(RED);
for(int i=1;i<=80;i++)
{
	gotoxy(i,1);
	cputs(" ");
}

gotoxy(32,1);
cputs("Djiktra's Algorithm");

gotoxy(36,3); cputs("Main Menu");

textbackground(0);
gotoxy(20,5); cputs("1. Compute Shortest path from a Graph File");
gotoxy(20,6); cputs("2. See shortest distance for a vertex");
gotoxy(20,7); cputs("3. Enter Visual Graph Studio");
gotoxy(20,8); cputs("4. Exit");

textbackground(RED);
for( i=1;i<=80;i++)
{
	gotoxy(i,11);
	cputs("-");
}



char buffer[10];
gotoxy(1,13); cputs("Enter choice : ");

cin.getline(buffer,9);

choice=atoi(buffer);


if(choice==1)
{
	char filename[80];
	int sv;

	gotoxy(1,15);
	cputs("Enter File Name : ");
	cin.getline(filename,79);


	Diktra d(filename);
	int e=d.Return_error();

	if(e==-1)
	{
		cout << endl << "Error: File not Found !";
		getch();
	}
	if(e==-2)
	{
		cout << endl << "Error : Invalid Source Vertex";
		getch();
	}


	if(e==0)
	{
	cout << endl << "No. of vertices : 0 to " << (d.Return_no_of_vertices()-1);


	do
	{
		cout << endl << "Enter Source Vertex : ";
		cin.getline(buffer,10);
		sv=atoi(buffer);
		sv++;
	}
	while(sv>d.Return_no_of_vertices() || sv<1);




	d.Set_source_vertex(sv);

	d.Run();
	result=d.Return_s();

//	getch();
	}


}

if(choice==2)
{
	cout << endl << "Enter Vertex No. to see ( -1 to see all ) :";
	char b[12];
	int a;

	cin.getline(b,10);
	a=atoi(b);

	a++; //__Change

	LinkList* travel=result;
	while(travel!=NULL)
	{
		int v=travel->Return_vertex();
		float d=travel->Return_distance();

		if(d==INF) strcpy(b,"Infinity");
		else ftoa(d,b);

		if(v==a)
		{
			cout << endl << "The shortest distance for vertex " << (a-1) << " is " << b;
		}

		else if(a==0)
		{
			cout << endl << "Vertex : " << (v-1) << "   Shortest Distance : " << b;
		}


		travel=travel->Return_next();
	}


	cout << endl << "Press any key...";
	getch();

}


	if(choice==3)  //_________Start Graph Studio__________
	{
		Program prg;
		prg.Go();
	}
}
}

//___________Make 3d buttons easily ( also detects for mouse clicks )_________
class Button
{
private:
	int x1,y1,x2,y2;
	int key;
	char title[20];
	int up;
public:

	void SetButton(int x,int y,char* s,int k)
	{
		strcpy(title,s);
		x1=x;
		y1=y;
		key=k;
		x2=x1+textwidth(title)+5;
		y2=y1+textheight(title)+5;

		Draw();
		up=1;

	}

	void Draw()
	{

	up=1;
	setfillstyle(1,EGA_LIGHTGRAY);
	bar(x1,y1,x2,y2);

	setfillstyle(1,EGA_WHITE);
	bar(x1-1,y1-1,x2+1,y1-1);
	bar(x1-1,y1-1,x1-1,y2+1);

	setfillstyle(1,EGA_DARKGRAY);
	bar(x1,y2+1,x2+1,y2+1);
	bar(x2+1,y1,x2+1,y2+1);

	setfillstyle(1,EGA_BLACK);
	bar(x1-1,y2+2,x2+2,y2+2);
	bar(x2+2,y1-1,x2+2,y2+2);


		setwritemode(0);
		setcolor(0);
		settextstyle(DEFAULT_FONT,HORIZ_DIR,0);
		outtextxy(x1+2,y1+2,title);
		setwritemode(0);

	}

	void Press()
	{
	up=0;
	setfillstyle(1,EGA_LIGHTGRAY);
	bar(x1,y1,x2,y2);

	setfillstyle(1,EGA_BLACK);
	bar(x1-1,y1-1,x2+1,y1-1);
	bar(x1-1,y1-1,x1-1,y2+1);


	setfillstyle(1,EGA_DARKGRAY);
	bar(x1,y1,x2,y1);
	bar(x1,y1,x1,y2);


	setfillstyle(1,EGA_WHITE);
	bar(x1-1,y2+2,x2+2,y2+2);
	bar(x2+2,y1-1,x2+2,y2+2);

	setfillstyle(1,EGA_LIGHTGRAY);
	bar(x1,y2+1,x2+1,y2+1);
	bar(x2+1,y1,x2+1,y2+1);


		setwritemode(0);
		setcolor(0);
		settextstyle(DEFAULT_FONT,HORIZ_DIR,0);
		outtextxy(x1+2,y1+2,title);
		setwritemode(0);

	}

	int IsPressed()
	{
		return (up-1);
	}

	//__________Interface________
	int IsInside(int x,int y)
	{
		if(x>=x1 && x<=x2 && y>=y1 && y<=y2)
		{
			return key;
		}
		else return 0;
	}

};



void Program::Go()
{

Button buttons[10];

int grDriver=DETECT,grMode;
initgraph(&grDriver,&grMode,"d:\\tc\\bgi");


//__________Initialize screen________
Render();

//__________Make Buttons____
Bar(505,90,639,280);
buttons[0].SetButton(515,100,"Write to file",1);
buttons[1].SetButton(515,125,"Exit",2);
buttons[2].SetButton(515,150,"Save Graph",3);
buttons[3].SetButton(515,175,"Load Graph",4);
buttons[4].SetButton(515,200,"Clear Graph",5);
buttons[5].SetButton(515,225,"Toggle ZOOM",6);
buttons[6].SetButton(515,250,"Z-Factor++",7);

int noofbuttons;
int x=0,y=0,bs=0;
int leftispressed=0,rightispressed=0;
int dragging=0;

pointer.Show();

setwritemode(1);
	int ox,oy;
	int sx,sy;


int i,j,zc,i1,j1,zox=0,zoy=0;
int zfactor=2;

const int ZX=505;
const int ZY=300;

int zoomon=0;

while(1)   //___________Message Loop_____________
{

	pointer.Status(x,y,bs);

	//________Zoomer
	if(zoomon && (zox!=x || zoy!=y))
	{

		setcolor(15);
		setwritemode(0);
		rectangle(ZX,ZY,ZX+20*zfactor+1,ZY+20*zfactor+1);

		pointer.Hide();
		for(i=-9;i<=9;i++)
		for(j=-9;j<=9;j++)
		{
			zc=getpixel(x+i,y+j);
			i1=ZX+1+(i+9)*zfactor;
			j1=ZY+1+(j+9)*zfactor;
			setfillstyle(SOLID_FILL,zc);
			bar(i1,j1,i1+zfactor,j1+zfactor);
		}
		zox=x;zoy=y;

	pointer.Show();
	}




	if(dragging)  //________Line Dragger________________
	{
		if(ox!=(x/10)*10 || oy!=(y/10)*10) //____if cursor was moved______
		{
		pointer.Hide();
		setwritemode(1);
		setcolor(15);
		line(sx,sy,ox,oy); //______Erase old line_________
		line(sx,sy,(x/10)*10,(y/10)*10);
		setwritemode(0);
		pointer.Show();
		ox=(x/10)*10;oy=(y/10)*10;

		float distance=sqrt(abs((sx-ox)/10*(sx-ox)/10+(sy-oy)/10*(sy-oy)/10));

		char b[10];
		ftoa(distance,b);

		settextstyle(SMALL_FONT,HORIZ_DIR,5);

		cleartextxy(590,45,"12345");
		outtextxy(590,45,b);
		}
	}


	if((bs & 1) && leftispressed==0) //________Left Button Clicked_________
	{
		leftispressed=1;

		//________Make a vertex__________
		if(vertexno<MAXSIZE && !Occupied(x,y) && !dragging && x<500)
		{
		int i=x/10;
		int j=y/10;

		DrawVertex(i,j,vertexno+1);

		//_______Set data_____________
		vertexisthere[vertexno]=1;
		coord[vertexno][0]=i;
		coord[vertexno][1]=j;
		vertexno++;
		}

		else if(Occupied(x,y))  //______User Wants to Make Edge____
		{
			if(!dragging) //______Start Making Edge_________
			{
				dragging=1;
				sx=(x/10)*10;
				sy=(y/10)*10;
				ox=sx;oy=sy;
				pointer.Hide();
				setwritemode(1);
				moveto(sx,sy);
				line(sx,sy,ox,oy);
				pointer.Show();
				pointer.Clip(0,0,500,479);

			}

			else
			{   //___________________End Making Edge__________


				dragging=0;

				int sv,ev;
				float distance;
				sv=Return_vertexno(sx,sy);
				ev=Return_vertexno(ox,oy);


				sx/=10;sy/=10;
				ox/=10;oy/=10;
				distance=(float)sqrt(double(abs((sx-ox)*(sx-ox)+(sy-oy)*(sy-oy))));


				pointer.Hide();
				setwritemode(0);
				Save();
				settextstyle(DEFAULT_FONT,HORIZ_DIR,0);
				setcolor(EGA_BLACK);
				outtextxy(170,110,"Enter Edge Length : ");
				float d;

				do
				{
					gotoxy(170/8+1,9);
					char b[10];
					cin.getline(b,9);
					d=atof(b);
				} while( d >= INF || d<0);

				if(d>0) distance=d;

				Restore();
				pointer.Show();




				DrawEdge(sx*10,sy*10,ox*10,oy*10,distance);
				pointer.RemoveClipping();

				if(!g->EdgeIsPresent(sv,ev,distance))
				{
					g->Insert_Element(sv,ev,distance);
				}
				else
				{
					pointer.Hide();
					setwritemode(0);
					Save();
					settextstyle(DEFAULT_FONT,HORIZ_DIR,0);
					setcolor(EGA_BLACK);

					outtextxy(170,110,"Edge already Present");
					outtextxy(170,125,"Press any key...");
					settextstyle(DEFAULT_FONT,VERT_DIR,0);

					getch();
					Restore();
					pointer.Show();

				}
				settextstyle(SMALL_FONT,HORIZ_DIR,5);
				cleartextxy(590,45,"12345");


			}
		}


		//_________Check for buttons pressed____________
		int bkey;
		for(int i=0;i<7;i++)
		{
			bkey=buttons[i].IsInside(x,y);
			if(bkey)
			{
				pointer.Hide();
				buttons[i].Press();
				pointer.Show();
				break;
			}
		}


	}
	else if(!(bs &1 )) //_______Left button Released)_______________
	{
		if(leftispressed)
		{
		//_________Check for buttons pressed____________
			int bkey;
			for(int i=0;i<7;i++)
			{
				if(buttons[i].IsPressed())
				{
					pointer.Hide();
					buttons[i].Draw();
					pointer.Show();
				}
				bkey=buttons[i].IsInside(x,y);
				if(bkey)
				{
					break;
				}
			}

			if(bkey==2)  //_________Exit pressed__________
			{
				closegraph();
				return;
			}

			if(bkey==1)   //____________Write pressed__________
			{
				WriteGraphToFile();
			}

			if(bkey==3) //_____Save graph_____
			{
				SaveGraph();
			}

			if(bkey==4)  //_________Load graph___
			{
				LoadGraph();
				Render();
			}

			if(bkey==5)  //________Clear Graph______
			{
				Clear();
				Render();
			}

			if(bkey==6)  //________Toggle Zoom______
			{
				if(zoomon)
				{
					 zoomon=0;
					 pointer.Hide();
					 setfillstyle(SOLID_FILL,0);
					 bar(ZX,ZY,ZX+20*zfactor+1,ZY+20*zfactor+1);
					 pointer.Show();
				}

				else zoomon=1;
			}

			if(bkey==7)      //_________Z-factor++
			{
					 pointer.Hide();
					 setfillstyle(SOLID_FILL,0);
					 bar(ZX,ZY,ZX+20*zfactor+1,ZY+20*zfactor+1);
					 pointer.Show();

					 zfactor+=1;
					 if(zfactor==7) zfactor=2;
					 zox=0;zoy=0;
			}


		}
				leftispressed=0; //_____Released

	}


	if((bs & 2) && rightispressed==0) //Right button clicked
	{
		rightispressed=1;
		if(dragging)
		{
			dragging=0;
			setwritemode(1);
			setcolor(15);
			pointer.Hide();
			line(sx,sy,(x/10)*10,(y/10)*10);

			settextstyle(SMALL_FONT,HORIZ_DIR,5);
			cleartextxy(590,45,"12345");

			pointer.Show();
			pointer.RemoveClipping();


		}
	}
	else if(!(bs & 2))
		rightispressed=0;
}

}


int Program::Occupied(int x,int y)
{
	if (Return_vertexno(x,y)>0)
		return 1;
	else return 0;

}

int Program::Return_vertexno(int x,int y)
{
int i,j;

i=x/10;
j=y/10;

int m;
for(m=0;m<MAXSIZE;m++)
{
	if(coord[m][0]==i && coord[m][1]==j)
		return m+1;
}

return 0;

}

void Program::cleartextxy(int x,int y,char* s)
{
int i,j;
i=textwidth(s);
j=textheight(s);
setfillstyle(SOLID_FILL,0);
bar(x,y,x+i+1,y+j+1);
setfillstyle(SOLID_FILL,15);
}


void Program::WriteGraphToFile()
{
	pointer.Hide();

	Save();
	settextstyle(DEFAULT_FONT,HORIZ_DIR,0);
	setwritemode(0);
	outtextxy(160,110,"Enter filename to write to : ");

	gotoxy(160/8+1,9);

	char filename[80];
	cin.getline(filename,79);
	ofstream outfile;
	outfile.open(filename);

int i=0;

LinkList* travel;

//______Write GraphMap Info________
outfile << vertexno << endl;
outfile << g->Return_noofedges() << endl;

for(i=1;i<=MAXSIZE;i++)
{
	travel=g->Return_LinkListPointer(i);
	while(travel!=NULL)
	{

		outfile << (i-1) << " " << (travel->Return_vertex()-1) << " " << travel->Return_distance() << endl;
		travel=travel->Return_next();

	}
}

Restore();
pointer.Show();
outfile.close();
}

void Program::SaveGraph()
{
	pointer.Hide();

	Save();
	settextstyle(DEFAULT_FONT,HORIZ_DIR,0);
	setwritemode(0);
	outtextxy(160,110,"Enter filename to save: ");

	gotoxy(160/8+1,9);

	char filename[80];
	cin.getline(filename,79);
	ofstream outfile;
	outfile.open(filename);

int i=0;

LinkList* travel;

//______Write GraphMap Info________
outfile << vertexno << endl;
outfile << g->Return_noofedges() << endl;

for(i=1;i<=MAXSIZE;i++)
{
	travel=g->Return_LinkListPointer(i);
	while(travel!=NULL)
	{

		outfile << (i-1) << " " << (travel->Return_vertex()-1) << " " << travel->Return_distance() << endl;
		travel=travel->Return_next();

	}
}


//________Write coord info
for(i=0;i<MAXSIZE;i++)
{
	outfile << coord[i][0] << "  " << coord[i][1] << endl;
}

//______Write vertexisthere array__________
for(i=0;i<MAXSIZE;i++)
{
	outfile << vertexisthere[i] << endl;
}

Restore();
pointer.Show();

outfile.close();
}


void Program::LoadGraph()
{
	pointer.Hide();

	Save();
	settextstyle(DEFAULT_FONT,HORIZ_DIR,0);
	setwritemode(0);
	outtextxy(160,110,"Enter filename to load: ");

	gotoxy(160/8+1,9);

	char filename[80];
	cin.getline(filename,79);
	ifstream infile;
	infile.open(filename);

	if(infile==0)
	{
		Restore();
		pointer.Show();
		return;
	}


	g->Clear();

int i=0;
int edgenos;

//______Load GraphMap Info________
infile >> vertexno;
infile >> edgenos;

int sv,ev;
float distance;
for(i=1;i<=edgenos;i++)
{
		infile >> sv >> ev >> distance;
		sv++; ev++;
		if(distance>INF) distance=INF;
		if(distance<0) distance=0;
		g->Insert_Element(sv,ev,distance);
}

//________Read coord info
for(i=0;i<MAXSIZE;i++)
{
	infile >> coord[i][0] >> coord[i][1];
}

//______Read vertexisthere array__________
for(i=0;i<MAXSIZE;i++)
{
	infile >> vertexisthere[i];

//	cout << int(vertexisthere[i]);
//	getch();

}


infile.close();

Restore();
pointer.Show();

}

void Program::Save()
{
unsigned int l=imagesize(150,100,490,200);

imagebuffer=(void *)new char[l];
getimage(150,100,490,200,imagebuffer);
Bar(150,100,490,200);
}

void Program::Restore()
{
putimage(150,100,imagebuffer,0);
delete[] imagebuffer;
imagebuffer=NULL;
}

void Program::Bar(int x1,int y1,int x2,int y2)
{
	x1+=1;
	y1+=1;
	x2-=2;
	y2-=2;
	setfillstyle(1,EGA_LIGHTGRAY);
	bar(x1,y1,x2,y2);

	setfillstyle(1,EGA_WHITE);
	bar(x1-1,y1-1,x2+1,y1-1);
	bar(x1-1,y1-1,x1-1,y2+1);

	setfillstyle(1,EGA_DARKGRAY);
	bar(x1,y2+1,x2+1,y2+1);
	bar(x2+1,y1,x2+1,y2+1);

	setfillstyle(1,EGA_BLACK);
	bar(x1-1,y2+2,x2+2,y2+2);
	bar(x2+2,y1-1,x2+2,y2+2);


}

void Program::Clear()
{

	g->Clear();
	vertexno=0;

}


void Program::Render()
{


setfillstyle(SOLID_FILL,0);
bar(0,0,500,479);
setfillstyle(SOLID_FILL,15);

//_________Make Grid Lines____________
setcolor(EGA_DARKGRAY);
setlinestyle(1,3,1);

int i,j;
for(i=10;i<500;i+=10)
{
	line(i,0,i,479);
}
for(j=10;j<480;j+=10)
{
	line(0,j,500,j);
}

setlinestyle(0,3,1);
setcolor(7);
rectangle(0,0,500,479);
setcolor(15);

Bar(505,5,630,40);
settextstyle(DEFAULT_FONT,HORIZ_DIR,0);
outtextxy(510,15,"G - Studio");


//____________Draw Vertices_____________
for(i=0;i<vertexno;i++)
{
//	cout << int(vertexisthere[i]);
//	getch();
	if(vertexisthere[i]) DrawVertex(coord[i][0],coord[i][1],i+1);
}


//_____________Draw Edges_______________
LinkList* travel;
for(i=1;i<=MAXSIZE;i++)
{
	travel=g->Return_LinkListPointer(i);

	while(travel!=NULL)
	{
		int ev=travel->Return_vertex();
		float d=travel->Return_distance();
		DrawEdge(coord[i-1][0]*10,coord[i-1][1]*10,coord[ev-1][0]*10,
					coord[ev-1][1]*10,d);
		travel=travel->Return_next();

	}
}

}

void Program::DrawVertex(int i,int j,int vertexno)
{
		pointer.Hide();
		setcolor(RED);
		setfillstyle(SOLID_FILL,EGA_BLUE);
		pieslice(i*10,j*10,0,360,6);

		char b[5];
		itoa(vertexno,b,10);
		settextstyle(SMALL_FONT,HORIZ_DIR,3);
		setwritemode(0);
		setcolor(WHITE);
		outtextxy(i*10-textwidth(b)/2,j*10-textheight(b)/2,b);
		setwritemode(1);
		pointer.Show();

}

void Program::DrawEdge(int sx,int sy,int ox,int oy,float distance)
{
				//________Make line
				pointer.Hide();
				setwritemode(0);
				setcolor(EGA_LIGHTGRAY);
				line(sx,sy,ox,oy);

				//__________Create Arrow__________
				int mx,my;
				mx=abs((sx+ox)/2);
				my=abs((sy+oy)/2);

				mx=abs((sx+mx)/2);
				my=abs((sy+my)/2);

				setwritemode(0);

				setcolor(EGA_RED);
				setfillstyle(SOLID_FILL,EGA_RED);
				pieslice(mx,my,0,360,2);


				//________Write edge length_________
				char b[10];
				ftoa(distance,b);
				//______Show Distance____
				setcolor(EGA_WHITE);
				settextstyle(SMALL_FONT,HORIZ_DIR,2);
				outtextxy(mx,my,b);

				pointer.Show();
}

void ftoa(float d,char *s)
{

int dec,sign;

strcpy(s,fcvt(d,5,&dec,&sign));

char answer[10];



if(dec>=0)
{
	strncpy(answer,s,dec);
	answer[dec]=0;
	strcat(answer,".");
	strncat(answer,&s[dec],2);
	strcpy(s,answer);

}
else
{
	strcpy(answer,".");
	for(int i=0;i<abs(dec);i++)
	{
		strcat(answer,"0");
	}
	strcat(answer,s);

	strncpy(s,answer,5);
	s[5]=0;
}
}