#include <iostream>
#include <string>
#include <fstream>
#include <iomanip>
using namespace std;

#include "linkset.h"
#include "tvector.h"
#include "point.h"
#include "randgen.h"
#include "prompt.h"
#include "boggleboard.h"

/**
 * find all words on a boggle board
 *
 * The class BoggleFinder finds a word on a BoggleBoard if
 * the word can be found. To find all words, call
 * BoggleFinder::OnBoard once for each word in a dictionary
 *
 * BoggleFinder uses backtracking and a per-letter set of
 * board locations at which letters occur, see the code
 * for details
 *
 * author: Owen Astrachan
 * date: 1/12/00 methods lowercased
 *       4/99 developed for A Computer Science Tapestry
 */



// use Location to store pairs of board coordinates
// in sets, so overload == since current set using == only,
// not <.

struct Location
{
    int x;
    int y;
    Location(int tx, int ty)
	: x(tx), y(ty)
    { }
    Location()
	: x(0), y(0)
    { }
};

bool operator == (const Location& p, const Location& q)
{
    return p.x == q.x && p.y == q.y;
}
bool operator != (const Location& p, const Location & q)
{
    return ! (p == q);
}

ostream& operator << (ostream& out, const Location& loc)
{
    out << "(" << loc.x << ", " << loc.y << ")";
    return out;
}

class BoggleFinder
{
  public:
    BoggleFinder(const BoggleBoard& b);
    
    bool onBoard(const string& s, tvector<Location>& locations);
    
  private:
    
    typedef LinkSet<Location>         LocationSet;
    typedef LinkSetIterator<Location> LocationSetIterator;

    BoggleBoard          myBoard;
    tvector<LocationSet> myLetterLocs;
    LocationSet          myVisited;
    
    bool isAdjacent(const Location& p, const Location& q)   const;
    bool onBoardAt(const string& s, const Location& p, tvector<Location>& locs);
    
};

BoggleFinder::BoggleFinder(const BoggleBoard& b)
 : myBoard(b),
   myLetterLocs(26)
// post: private state initialized    
{
    int j,k;
    int size = myBoard.size();
    
    for(j=0; j < size; j++)
    {
	for(k=0; k < size; k++)
        { 
            myLetterLocs['z'-myBoard.charAt(j,k)].insert(Location(j,k));
	}
    }
}

bool BoggleFinder::isAdjacent(const Location& p, const Location& q) const
// post: returns true if p adjacent to q, false otherwise    
{
    cout << "isAdjacent not implemented" << endl;
    return false;
}

bool BoggleFinder::onBoardAt(const string& s, const Location& loc,
			     tvector<Location>& locvec)
// post: returns true if string s can be found in myBoard, starting at
//       location loc according to rules of the game, false if s isn't found
//       If true returned, locations of characters in s on myBoard are 
//       returned in parameter locvec, in order of characters in s
{
    if (s.length() == 0) return true;
    
    LocationSet ps = myLetterLocs['z' - s[0]];   // locations of first char
    LocationSetIterator psi(ps);                 // iterate over each location

    for(psi.Init(); psi.HasMore(); psi.Next())
    {
	Location nextLoc = psi.Current();
        if (isAdjacent(loc,nextLoc) && ! myVisited.contains(nextLoc))
        {
	    myVisited.insert(nextLoc);
            locvec.push_back(nextLoc);
            if (onBoardAt(s.substr(1,s.length()-1),nextLoc,locvec))
            {
		return true;
            }
            locvec.pop_back();
            myVisited.erase(nextLoc);
        }
    }
    return false;
}

bool BoggleFinder::onBoard(const string& s,
			   tvector<Location>& locations)
// post: returns true if s found on board, false otherwise
//       if s found then position of each character in s stored in
//       locations in same order as characters in s
    
{
    cout << "onBoard not implemented" << endl;
    return false;
}

void Print(const tvector<Location>& v)
// pre: v contains v.size() entries
// post: v printed, all entries on one line    
{
    int k;
    for(k=0; k < v.size(); k++)
    {
	cout << v[k] << " ";
    }
    cout << endl;
}

int main()
{
    int size = PromptRange("boggle size ",3,8);
    BoggleBoard board(size);
    
    BoggleFinder bogfinder(board);    
    string word;
    tvector<Location> locs;
    string filename = PromptString("words ");
    ifstream input(filename.c_str());

    board.print(cout);
    while (input >> word)
    {
	if (bogfinder.onBoard(word,locs))
        {
	    cout << word << "\t"; Print(locs);
        }
        else
        {
	    // cout << "not found" << endl;
        }
    }
    board.print(cout);
    
    return 0;
}