/*
 * Name: Owen Sullivan
 * Date Submitted: 12/5/2022
 * Lab Section: 006
 * Assignment Name: Lab 10: Using Breadth-First Search to Solve Puzzles
*/

#include <iostream>
#include <vector>
#include <map>
#include <queue>
using namespace std;

// Reflects what each node represents...
// First value units of water in A, second units of water in B
typedef pair<int, int> state;

// Each string in edge_label must be one of the following:
const string actions[] = {"Fill A",
                          "Fill B",
                          "Empty A",
                          "Empty B",
                          "Pour A->B",
                          "Pour B->A"};

// GENERIC -- these shouldn't need to be changed...
map<state, bool> visited;         // have we queued up this state for visitation?
map<state, state> pred;           // predecessor state we came from
map<state, int> dist;             // distance (# of hops) from source node
map<state, vector<state>> nbrs;   // vector of neighboring states

map<pair<state, state>, string> edge_label;

// GENERIC (breadth-first search, outward from source_node)
void search(state source_node)
{
  queue<state> to_visit;
  to_visit.push(source_node);
  visited[source_node] = true;
  dist[source_node] = 0;
  
  while (!to_visit.empty()) {
    state curnode = to_visit.front();
    to_visit.pop();
    for (state n : nbrs[curnode])
      if (!visited[n]) {
	pred[n] = curnode;
	dist[n] = 1 + dist[curnode];
	visited[n] = true;
	to_visit.push(n);
      }
  }
}

// GENERIC
void print_path(state s, state t)
{
  if (s != t) {
    print_path(s, pred[t]);
    cout << edge_label[make_pair(pred[t], t)] << ": " << "[" << t.first << "," << t.second << "]\n";
  } else {
    cout << "Initial state: " << "[" << s.first << "," << s.second << "]\n";
  }
}

// Function to get the correct sizes for a pour operation
state pour(const bool &jarA, const int &jarAsize, const int &jarBsize) {

  // If the destination jar is jar A (max size of 3)
  if (jarA) {

    // If the sum of jar sizes would be greater than 3
    if (jarAsize + jarBsize >= 3) {

      // If pouring 3 from jar B would result in a jar B size greater than 0
      if (jarBsize - 3 > 0) {

        return make_pair(3, (jarBsize - 3));

        // If pouring 3 from jar B would result in a jar B size less than or 
        // equal to 0
      } else {

        return make_pair(3, 0);

      }

      // If the sum of jar sizes would not be greater than 3
    } else {

      // If pouring 3 from jar B would result in a jar B size greater than 0
      if (jarBsize - 3 > 0) {

        return make_pair((jarAsize + jarBsize), (jarBsize - 3));

        // If pouring 3 from jar B would result in a jar B size less than or 
        // equal to 0
      } else {

        return make_pair((jarAsize + jarBsize), 0);

      }

    }

    // If the destination jar is jar B (max size of 4)
  } else {

    // If the sum of jar sizes would be greater than 4
    if (jarAsize + jarBsize >= 4) {

      // If pouring 4 from jar A would result in a jar A size greater than 0
      if (jarAsize - 4 > 0) {

        return make_pair((jarAsize - 4), 4);

        // If pouring 4 from jar A would result in a jar A size less than or 
        // equal to 0
      } else {

        return make_pair(0, 4);

      }

      // If the sum of jar sizes would not be greater than 4
    } else {

      // If pouring 4 from jar A would result in a jar A size greater than 0
      if (jarAsize - 4 > 0) {

        return make_pair((jarAsize - 4), (jarAsize + jarBsize));

        // If pouring 4 from jar A would result in a jar A size less than or 
        // equal to 0
      } else {

        return make_pair(0, (jarAsize + jarBsize));

      }

    }

  }

}

void build_graph(void) {
  
  // Store the maximum size for each jar
  int jarA = 3;
  int jarB = 4;
  
  // Create state for current state, will initialize to (0, 0)
  state currentState;
  // Create state for last possible state, initialized with maximum sizes
  state lastState(jarA, jarB);

  // Loop until the last possible state has been reached
  while (currentState != lastState) {

    // Create a state for the "Fill A" operation where jar A has its maximum 
    // size
    state fillA(jarA, currentState.second);
    // If the new jar isn't equal to the current state, add it to the 
    // neighbors map and add the "Fill A" action to the edge labels map
    if (fillA != currentState) {

      nbrs[currentState].push_back(fillA);

      edge_label[make_pair(currentState, fillA)] = actions[0];

    }

    // Create a state for the "Fill B" operation where jar B has its maximum 
    // size
    state fillB(currentState.first, jarB);
    // If the new jar isn't equal to the current state, add it to the 
    // neighbors map and add the "Fill B" action to the edge labels map
    if (fillB != currentState) {

      nbrs[currentState].push_back(fillB);

      edge_label[make_pair(currentState, fillB)] = actions[1];

    }

    // Create a state for the "Empty A" operation where jar A has a size of 0
    state emptyA(0, currentState.second);
    // If the new jar isn't equal to the current state, add it to the 
    // neighbors map and add the "Empty A" action to the edge labels map
    if (emptyA != currentState) {

      nbrs[currentState].push_back(emptyA);

      edge_label[make_pair(currentState, emptyA)] = actions[2];

    }

    // Create a state for the "Empty B" operation where jar B has a size of 0
    state emptyB(currentState.first, 0);
    // If the new jar isn't equal to the current state, add it to the 
    // neighbors map and add the "Empty B" action to the edge labels map
    if (emptyB != currentState) {

      nbrs[currentState].push_back(emptyB);

      edge_label[make_pair(currentState, emptyB)] = actions[3];

    }

    // Create a state for the "Pour A into B" operation where jar B has a size 
    // equal to the sum of A's size and B's size (or jar B's maximum size, if 
    // the sum would be greater than or equal)
    state pourAintoB(pour(false, currentState.first, currentState.second));
    // If the new jar isn't equal to the current state, add it to the 
    // neighbors map and add the "Pour A into B" action to the edge labels map
    if (pourAintoB != currentState) {

      nbrs[currentState].push_back(pourAintoB);

      edge_label[make_pair(currentState, pourAintoB)] = actions[4];

    }

    // Create a state for the "Pour B into A" operation where jar A has a size 
    // equal to the sum of A's size and B's size (or jar A's maximum size, if 
    // the sum would be greater than or equal)
    state pourBintoA(pour(true, currentState.first, currentState.second));
    // If the new jar isn't equal to the current state, add it to the 
    // neighbors map and add the "Pour B into A" action to the edge labels map
    if (pourBintoA != currentState) {

      nbrs[currentState].push_back(pourBintoA);

      edge_label[make_pair(currentState, pourBintoA)] = actions[5];

    }

    // If we've reached jar B's maximum size, increment jar A's size and set 
    // jar B's size to 0
    if (currentState.second == jarB) {

      currentState.first++;

      currentState.second = 0;

      // If we haven't reached jar B's maximum size, increment jar B's size
    } else {

      currentState.second++;

    }

  }

}

// int main(void)
// {
//   build_graph();

//   state start = make_pair(0,0);
  
//   for (int i=0; i<5; i++)
//     nbrs[make_pair(i,5-i)].push_back(make_pair(-1,-1));
//   search (start);
//   if (visited[make_pair(-1,-1)]) 
//     print_path (start, pred[make_pair(-1,-1)]);
//   else
//     cout << "No path!\n";
  
//   return 0;
// }