// problem2.cpp : Defines the entry point for the console application.
//
#include <fstream>
#include <iostream>
#include <string>
using namespace std;

#include "apvector.h"
#include "graph.h"

void dfsTreePrint(graph<string>, int, int, apvector<int>) ;

bool different_by_one(string str1, string str2)
{
	int numDifferent=0;
	if(str1.length()!=str2.length())
		return false;
	for(int count=0;count<str1.length();count++)
	{
		if(str1[count]!=str2[count])
			numDifferent++;
		if (numDifferent>1)
			return false;
	}
	if(numDifferent==0)
		return false;
	return true;
}

void usage(void) ;

int main(int argc, char * argv[])
{
	boolean verbose = false ;
	if(argc != 2)
	  usage() ;

	if(strcmp(argv[1], "-n") == 0)
	  verbose = false ;
	else if(strcmp(argv[1], "-v") == 0)
	  verbose = true ;
        else 
          usage() ;

	const int MAX_NEIGHBORS=30;
	ifstream in("words.dat",ios::in);
	graph<string> myGraph;
	string word;
	apvector<string> words(10000);
	int numWords=0;
	while(in>>word)
	{
		myGraph.addVertex(word);
		words[numWords]=word;
		numWords++;
		for(int count=0;count<myGraph.numVertices();count++)
		{
			if(different_by_one(word,words[count]))
			{
				myGraph.addEdge(word,words[count]);
			}
		}
	}
	in.close();
	
	// test dfs with the word 'smart'
	apvector<int> distances; 
	apvector<int> parent ;
        word = "smart" ;
	myGraph.dfs(word, distances, parent) ;

	if(verbose){
	  int indie ;
	  for(int k = 0 ; k < distances.length() ; k++)
            if(distances[k] == 0)
              if(parent[k] == -1){
                indie = k ;
                break ;
              }//if
	  cout << "the dfs tree..." << endl ;
	  cout << "------------" << endl ;
	  dfsTreePrint(myGraph, indie, 0, parent) ;
        }//if

	int brain_index = myGraph.getIndex("brain") ;
	
          cout << "\nbrain is " << distances[brain_index] << " hops away" << endl ;

          // get path from about to farthest word
          stack<int> path ;
          int cur_index = brain_index  ;
	  do{
            path.push(cur_index) ;
            cur_index = parent[cur_index] ;
          }while(parent[cur_index] != -1) ;

          cout << "\npath from 'smart' to 'brain'" << endl ;
	  cout << "smart -> " ;
	  while(!path.empty()){
            cout << myGraph.getItem(path.top()) ;
            path.pop() ;
            if(!path.empty()) cout << " -> " ;
          }//while
	  cout << endl ;

	return 0;
}// end of main

void dfsTreePrint(graph<string> myGraph, int index, int level, apvector<int> parent){
  for(int i = 0 ; i < level ; i++) cout << " " ;
  cout << level << " - " ;
  cout << myGraph.getItem(index) << endl ;
  for(int j = 0 ; j < parent.length() ; j++)
    if(parent[j] == index)
      dfsTreePrint(myGraph, j, level + 1, parent) ;
}//end of bfsTree

void usage(void){
  cerr << "Usage:\n\t./problem2 -n\n\t\t- for normal usage\n\n\tOR\n\n\t./problem2 -v\n\t\t- for verbose output" << endl ;
  exit(EXIT_FAILURE) ;
}//end of usage