// 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 bfsTreePrint(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 bfs with the word 'about'
	apvector<int> distances; 
	apvector<int> parent ;
        word = "about" ;
	myGraph.bfs(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 bfs tree..." << endl ;
	  cout << "------------" << endl ;
	  bfsTreePrint(myGraph, indie, 0, parent) ;
        }//if

	int max_distance = distances[0] ;
	for(int i = 0 ; i < distances.length() ; i++)
	  if(distances[i] > max_distance)
            max_distance = distances[i] ;

	apvector<int> max_indexes ;
	for(int p = 0 ; p < distances.length() ; p++)
          if(max_distance == distances[p])
            max_indexes.push_back(p) ;

        string extra = "farthest word is " ;
	if(max_indexes.size() > 1) extra = "furthest words ... " ;

	for(int b = 0 ; b < max_indexes.size() ; b++){
          cout << "\n" << extra << "'" << myGraph.getItem(max_indexes[b]) << "'" 
               << " (" << distances[max_indexes[b]] << " hops away)" << endl ;

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

          cout << "\npath from 'about' to '" << myGraph.getItem(max_indexes[b]) << "'" << endl ;
	  cout << "about -> " ;
	  while(!path.empty()){
            cout << myGraph.getItem(path.top()) ;
            path.pop() ;
            if(!path.empty()) cout << " -> " ;
          }//while
	  cout << endl ;
 	}//for more maximums

	return 0;
}// end of main

void bfsTreePrint(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)
      bfsTreePrint(myGraph, j, level + 1, parent) ;
}//end of bfsTree

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