////////////////////////////////////////////////////////////////////
// The Jewel Game                                                 //
// by Nick Cash                                                   //
//                                                                //
// Fall 2007                                                      //
// 810:161 - Artificial Intelligence                              //
//                                                                //
// search.cpp - Contains the search functions                     //
////////////////////////////////////////////////////////////////////

// standard includes
#include <cstdlib>
#include <queue>
#include <stack>
#include <map>
#include <list>
#include <iostream>

// custom includes
#include "game.h"

// setup the namespace so we dont have "std::" everywhere
using namespace std;

// our global variable so we know which search to use
// 0 = Iterative Deepening
// 1 = DepthLimited
// 2 = Breadth
short search_function = 0;

// Initialize counters for root nodes
unsigned int nodes_expanded = 0;
unsigned int nodes_stored = 0;

///////// Search Functions /////////
string BreadthSearch( cGameBoard* board )
{
  queue<cGameBoard*> q; // our queue to hold nodes
  std::map<cGameBoard*, cGameBoard*> parent_tree; // keep track of our parents in a map (red/black tree)
  cGameBoard* gb = NULL;
  string solution = "";

  // put our root node in the parent tree and the queue
  parent_tree[board] = NULL;
  q.push(board);

  // examine the queue
  while ( q.empty() == false )
  {
    // grab front runner
    gb = q.front();
    q.pop();

    // check for winning game boards
    if (gb->CheckWin())
     break;

    // do a depth check
    if ( gb->GetDepth() > 18 )
     return "Aborted: Depth > 18";

    // Generate successors
    std::list<cGameBoard*> branches;
    GenerateBranches(*gb, branches, true);

    // Go through the list and add each new node to the queue, and record its parent
    for (std::list<cGameBoard*>::const_iterator j = branches.begin(); j != branches.end(); ++j)
    {
      cGameBoard* v = *j;

      if (parent_tree.count(v) == 0)
      {
        // If v is unvisited.
        parent_tree[v] = gb;
        q.push(v);
      }
    } // end for
  } // end while

  // Print the final board
  cout << "\n\nFinal Board\n-----------\n";
  gb->Print();
  cout << endl << endl;

  // generate our solution
  while ( gb != NULL )
  {
    int x = gb->GetSpell(); // record our spell

    // check for root, where we terminate
    if ( x == 0 )
     break;
    else // otherwise, add the spell to our solution string
    {
      char c[2];
      sprintf( c, "%d", x);

      solution += c;
    }

    // move up the tree by one
    gb = parent_tree[gb];
  }

  return solution;
}

// Recursive function implementing depth limited search
cGameBoard* DLS( cGameBoard * board, string& solution, const int depth )
{
  std::stack<cGameBoard*> stack;

  // make sure we have a board
  if ( !board )
   return NULL;

  // check for the win
  if ( board->CheckWin() == true )
   return board;
  else
  {
    cGameBoard* ret = NULL; // our return pointer if we found a solution

    // Generate successors
    std::list<cGameBoard*> branches;
    GenerateBranches(*board, branches, false);

    // add to the stack
    for (std::list<cGameBoard*>::const_iterator j = branches.begin(); j != branches.end(); ++j)
        stack.push(*j);

    // evaluate the stack
    while ( !stack.empty() )
    {
      // grab the top of the stack
      cGameBoard* child = stack.top();
      stack.pop();

      if ( child->GetDepth() < depth  )
       if ( (ret = DLS( child, solution, depth )) != NULL )
       {
        char c[2];
        sprintf( c, "%d", child->GetSpell());
        solution += c;

        return ret;
       }
       
       // ran DLS on this child w/ no winning solution, so we delete it to save space
       delete child;
    }

    // if we havent returned yet
    return NULL;
  }
}


// Depth first only, limited to whatever MAX_DEPTH is (18)
std::string DepthLimitedSearch( cGameBoard* board )
{
  string solution = "";

  // run the algorithm
  board = DLS(board, solution, MAX_DEPTH);

  // Chop off extraneous spells
  for ( int i = solution.length(); i > 0; i-- )
  {
     if ( (solution[i] == solution[i-1]) && (solution[i] == solution[i-2]))
     {
       solution.erase(i-2,3);
       i = solution.length();
     }
  }

  // Print the final board
  cout << "\n\nFinal Board\n-----------\n";
  board->Print();
  cout << endl << endl;

  return solution;
}

// IDS: DLS + Breadth = great :)
std::string IterativeDeepeningSearch( cGameBoard* board )
{
  string solution = "";
  cGameBoard* ptr = NULL;

  // increase our depth each time
  for ( int depth = 1; depth < 18; depth++ )
   if ( (ptr = DLS(board, solution, depth)) != NULL )
    break;

  // Print the final board
  cout << "\n\nFinal Board\n-----------\n";
  ptr->Print();
  cout << endl << endl;

  return solution;
}