#include <iostream>
#include <vector>
#include <algorithm>
#include "readDatFile.h"
#include <ctime>
#define INF 9999

Graph g;
std::vector<int> FS, NS, NNS,Level;
bool *Visited;
//int *Level;
int cur_level;

//initialize level of all vertices as INF = 9999
struct Initialize{
        void operator()(int src){
                        Level[ src] = INF;
        }
};

//explore neighbours and push in next set
struct findNeighbour{
	void operator()(int frontier){
		int start = g.psrc[ frontier];
		int end = g.psrc[ frontier] + g.noutgoing[ frontier];
		while( start != end ){
			int dst = g.edgessrcdst[ start];
			NS.push_back( dst);
			start++;
		}
	}
};

//update level of newly explored vertices
struct updateLevel{
	void operator()(int vertex){
		if(Level[ vertex] == INF){
                        //Visited[ vertex] = true;
			Level[ vertex] = cur_level+1;
			NNS.push_back( vertex);
		}
	}
};

int main(int argc, char *argv[]){
       // bool *Visited;
       // int *Level;
        int start = clock();
        //read the graph
	g.readGraph(argv[1]);
        //int end = clock();
	std::vector<int> srcVec(g.srcsrc, g.srcsrc+g.nnodes);
        Level = srcVec;
	//initalize
	for_each( srcVec.begin(), srcVec.end(), Initialize());
	cur_level = 0;
	Level[ srcVec[ 1]] = cur_level;
	FS.push_back( srcVec[ 1]);


	//repeat until FS is empty
	while( !FS.empty()){
//                std::cout<<FS.size()<<"\n";
		for_each( FS.begin(), FS.end(), findNeighbour());   
	//	std::cout<<NS.size()<<"\n";
		for_each( NS.begin(), NS.end(), updateLevel());
		//update level by 1
		cur_level++;
		//clear current frontier set
		FS.clear();
		//make newly expolred vertex as frontier set for next iteration
		FS = NNS;
		//clear Next sets
		NS.clear();
		NNS.clear();
               // std::cout<<cur_level<<"\n";
	}
std::cout<<"Max Level: "<<cur_level-1<<"\n";
         int end = clock();
         double total_time = (double) (end-start)/CLOCKS_PER_SEC;
         std::cout<<"Total Time: "<<total_time<<"\n";
int i=0;
/*for( std::vector<int>::iterator it = Level.begin(); it!=Level.end(); it++)
{
   if( *it != INF)
           i++;
}
std::cout<<"Total visted vertex: "<<i<<"\n";*/
return 0;
}
