#include <fstream>                 // for class ifstream
#include <cctype>                  // for function isalpha
#include <queue>
using namespace std;
#include "ladder.h"

const unsigned int Ladder::WORD_SIZE = 5;


//////////////////////////////////////////////////////////////
// Internal node used for keeping track of words in ladder
// In addition to word, keeps track of
//   boolean as to whether or not this word has been "visited"
//     (i.e., placed on the queue)
//   pointer to ancestor word that caused this one to be
//     placed on queue (i.e., previous word in ladder)
//
struct LadderNode
{
  public:
    LadderNode (const string & newWord);

    bool IsEqual (const LadderNode & rhs) const;
    bool IsOneApart (const LadderNode & rhs) const;
    bool IsVisited () const;
    void Print (ostream & output) const;

    void Visit ();
    void DeriveFrom (LadderNode * ancestor);
    void Clear ();

  private:
    string myWord;
    bool myVisited;
    LadderNode * myAncestor;

};


// LadderNode member functions
LadderNode::LadderNode (const string & newWord)
  : myWord(newWord),
    myVisited(false),
    myAncestor(NULL)
{}

bool LadderNode::IsEqual (const LadderNode & rhs) const
// post: returns true if words within nodes are equal
{
    return myWord == rhs.myWord;
}

bool LadderNode::IsOneApart (const LadderNode & rhs) const
// post: returns true if and only if differ from rhs by exactly
//       one letter
{
    int diff = 0;

    unsigned int k;
    for (k = 0; k < myWord.length(); k++)
    {
        if (myWord[k] != rhs.myWord[k])
        {
           diff++;
           if (diff > 1) return false;
        }
    }

    return (diff == 1);
}

bool LadderNode::IsVisited () const
{
    return myVisited;
}

void LadderNode::Print (ostream & output) const
{
    output << myWord;
}

void LadderNode::Visit ()
{
    myVisited = true;
}

void LadderNode::DeriveFrom (LadderNode * ancestor)
{
    myAncestor = ancestor;
}

void LadderNode::Clear ()
{
    myVisited = false;
    myAncestor = NULL;
}


// overloaded operators for LadderNode
bool operator== (const LadderNode & lhs, const LadderNode & rhs)
{
    return lhs.IsEqual(rhs);
}

bool operator!= (const LadderNode & lhs, const LadderNode & rhs)
{
    return !(lhs == rhs);
}

ostream & operator<< (ostream & output, const LadderNode & l)
{
    l.Print(output);
    return output;
}



//////////////////////////////////////////////////////////////
// Ladder member functions
//
Ladder::Ladder (istream & input)
{
    Load(input);
}


Ladder::~Ladder ()
{
    int k;
    for (k = 0; k < myWords.size(); k++)
    {
        delete myWords[k];
    }
}


bool Ladder::Find (const string & from,
		   const string & to)
// post: finds a ladder from from to to
{
    Clear();

    cout << "Find not implemented" << endl;

    return false;
}


void Ladder::Print (ostream & output)
// post: prints the ladder on output
{
    output << "Print not implemented." << endl;
}


void Ladder::Load (istream & input)
// pre:  input is open for reading
// post: words are read from input stream and placed into vector myWords
{
    string word;
    while (getline(input, word))   // read each line
    {
        if (isalpha(word[0]))      // some words marked as unusable
        {
	    // only consider 5 letter words 
            myWords.push_back(new LadderNode(word.substr(0, WORD_SIZE)));
        }
    }
}


void Ladder::Clear ()
// post: marks all "words" as not visited
{
    int k;
    for (k = 0; k < myWords.size(); k++)
    {
        myWords[k]->Clear();
    }
}