#include <iostream> // For cout
#include <vector>   // For Vector
#include <string>   // for string
#include <fstream>  // for file reading
#include <algorithm>// for binary_search fun
#include <sstream>  // for string streams

using namespace std;

// Enumerators
enum ALPHABET {a, b, c, d, e, f, g, h, i, j, k, l, m,
               n, o, p, q, r, s, t, u, v, w, x, y, z};

// Global Variable Declarations
vector<string> _Dictionary;
char           _AlphabetList[26] = {'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm',
                                    'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z'};
int            _MaxSize = 0;
vector<int>    _MaxVector;

// Node Structure
struct node
{
  int word;
  node* next;
  node* last;

  node(int a_word)
  {
    word = a_word;
  }
};

// Function Declarations
bool dictionary_create();
bool word_exists(vector<string>::iterator a_begin, vector<string>::iterator a_end, string a_word)
                { return binary_search(a_begin, a_end, a_word); };
void depth_search(int a_start, int a_stop);
int index_of_alphabet(char a_char);
int index_of_Dictionary(string a_word);

class Stack
{
public:
  // Constructor and destructor's
  Stack(node* a_top, node* a_target);
  ~Stack();

  // Member Functions
  void DepthFirstSearch(int a_start, int a_stop);
  void node_parse(node* a_node);
  void stack_addNode(node* a_node)  { nodeStack.push_back(a_node); wordStack.push_back(a_node->word); };
  void stack_eraseTop();

  vector<node*> nodeStack;
  vector<int>   wordStack;
private:
  node* root;
  node* target;

};

Stack::Stack(node* a_root, node* a_target)
{
  root = a_root;
  target = a_target;
  nodeStack.push_back(root);
  wordStack.push_back(root->word);
}

Stack::~Stack()
{
  delete root;
  delete target;
}

void Stack::DepthFirstSearch(int a_start, int a_stop)
{
  node_parse(root);
 // system("pause");
}

void Stack::node_parse(node* a_node)
{
  for(int curChar = 0; curChar < 4; curChar = curChar + 1)
    for(int curLetter = index_of_alphabet(_Dictionary[root->word][0]) + 1; curLetter != 26; curLetter = curLetter + 1)
    {
      string newWord = _Dictionary[a_node->word];
      newWord[curChar] = _AlphabetList[curLetter];

      // Get rid of invalid or already existing words in chain, or if it's itself

      if(!word_exists(_Dictionary.begin(), _Dictionary.end(), newWord)) /// TODO: Replace needless functions with std::find(iterator, iterator, value);
        continue;
      if(find(wordStack.begin(), wordStack.end(), index_of_Dictionary(newWord)) != wordStack.end()) // if found
        continue;
      if(newWord == _Dictionary[a_node->word])
        continue;

      // check for completion

      if(newWord == _Dictionary[target->word])
      {
        cout << "Solution found for " << _Dictionary[root->word] << " to " << _Dictionary[target->word] << " Size = " << wordStack.size() + 1 << endl;
        if(wordStack.size() + 1 > _MaxSize)
        {
          _MaxSize = wordStack.size() + 1;
          _MaxVector.clear();
          for(int i = 0; i < wordStack.size(); i++)
            _MaxVector.push_back(wordStack[i]);
          _MaxVector.push_back(index_of_Dictionary(newWord));
        }
      }
      nodeStack.push_back(new node(index_of_Dictionary(newWord)));
      wordStack.push_back(index_of_Dictionary(newWord));
      node_parse(nodeStack[nodeStack.size() - 1]);
    }
}

void Stack::stack_eraseTop()
{
  vector<node*>::iterator it = nodeStack.end();
  delete *it;
 // nodeStack.erase(it);
}

int main()
{
  if(!dictionary_create()) // create dictionary file, if it fails, exit
  {
    cout << "File not good" << endl;
    return 0;
  }

  // iterate through the dictionary, and for every two pairs of words, run the algorithm.
  for(int i = 0; i < _Dictionary.size(); i++)
    for(int x = 0; x < _Dictionary.size(); x++)
      if(i != x)
      {
        depth_search(i, x);
      }
  cout << "Program finished" << endl;
  cout << "Max size = " << _MaxSize << endl;

  ofstream outputFile;
  outputFile.open("data.txt", ios::trunc);
  outputFile << "Max size = " << _MaxSize << endl;

  for(int i = 0; i < _MaxVector.size(); i++)
    outputFile << _Dictionary[_MaxVector[i]] << endl;
}

void depth_search(int a_start, int a_stop)
{
  node* myNode = new node(a_start);

  node* targetNode = new node(a_stop);

  Stack* DepthFirst = new Stack(myNode, targetNode);
  DepthFirst->DepthFirstSearch(a_start, a_stop);

  delete DepthFirst;
}

bool dictionary_create()
{
  ifstream dictionaryFile;
  dictionaryFile.open("dictionary.txt", ifstream::in); // Create and open file

  if(!dictionaryFile.good()) // return false (thus closing the program) if problem
    return false;
  cout << "Opened file." << endl;

  string tempWord;
  while(dictionaryFile.good()) // while not end of file, add current line to dictionary
  {
    getline(dictionaryFile, tempWord);
    _Dictionary.push_back(tempWord);
  }
  cout << "Read all dictionary words from file." << endl;

  dictionaryFile.close();
  cout << "Closed file." << endl;

  return true;
}

int index_of_alphabet(char a_char)
{
    int i = 0;
    while(_AlphabetList[i] != a_char)
      i++;
    return i;
}

int index_of_Dictionary(string a_word)
{
  find(_Dictionary.begin(), _Dictionary.end(), a_word)
  vector<string>::iterator it = _Dictionary.begin();
  int i = 0;

  while(*it != a_word)
  {
    it++;
    i++;
  }
  return i;
}