/*
 * INSTRUCTOR-GIVEN TEMPLATE
 * COSC 140: Lab 9B - Shape Shifter!
 *
 * Description:
 *     A simple introduction to recursion. Brute force through all possible
 *     combinations of a puzzle until a valid solution is found. If none are
 *     discovered, print nothing. If a solution does exist, print out the
 *     pieces and the positions where they would solve the puzzle.
 *
 * Author:
 *     Your Name
 */

//C++
#include <iostream>
#include <string>
#include <vector>
#include <deque>
#include <map>
#include <algorithm>
#include <sstream>

//C
#include <stdio.h>
#include <stdlib.h>

using namespace std;

// ----------------------------------------------------------------------------
// Class/Struct Function Prototypes                                        {{{1
// ----------------------------------------------------------------------------

/*
 * Class for ShapeShifter. Has a grid of the initial setup that you will try to
 * put pieces into. Also has a struct called "shape" that stores a shape's
 * grid, width, and height.
 */

typedef unsigned int uint;

class ShapeShifter {
	struct shape {
		//Constructors
		shape();
		shape(const string&);
		
		//Variables
		vector< vector<bool> > grid;
		uint width, height;
		string text;
	};
		
	public:
		//Constructors
		ShapeShifter();
		ShapeShifter(const vector<string>&);
		
		//Dealing with shapes
		void add_shape(const string&);
		bool apply_shape(uint, uint, uint);
		
		//Solving functions
		bool all_one();
		bool find_solution(uint = 0);
		void print_solution();
		
	private:
		//All shapes to be inserted into the grid
		vector<shape> shapes;
		
		//Game Grid
		vector< vector<bool> > grid;
		
		//(x, y) points for each shape when the solution is found.
		deque< pair<uint, uint> > solution;
		
		//Game grid size
		uint width, height;
};

// ----------------------------------------------------------------------------
// Class/Struct Function Declarations                                      {{{1
// ----------------------------------------------------------------------------

/* Shape Sub-Struct */

/*
 * ShapeShifter::shape constructor (Default)                               {{{2
 *
 * Leave this blank.
 */

ShapeShifter::shape::shape() {
	/* Leave Empty */
}

/*
 * ShapeShifter::shape constructor (construct via string)                  {{{2
 *
 * Takes a string via "line" and makes a grid out of it.
 */

ShapeShifter::shape::shape(const string& line) {
	/*
	 * - Split the string by space (probably via istringstream).
	 *   Put each row into a temporary vector<string>.
	 *
	 * - Go through each char in each row and set "grid" up.
	 *
	 * - Set width and height
	 *
	 * - Store the original string ("line") in "text".
	 */
}

/* ShapeShifter Class */

/*
 * ShapeShifter constructor (Default)                                      {{{2
 *
 * Leave this blank.
 */

ShapeShifter::ShapeShifter() {
	/* Leave Empty */
}

/*
 * ShapeShifter constructor (construct via vector of strings)              {{{2
 *
 * Takes strings read into a vector "rows" and defines the initial grid of the
 * ShapeShifter object with it (stored as a 2D vector of bools in "grid").
 */

ShapeShifter::ShapeShifter(const vector<string>& rows) {

}

/*
 * add_shape                                                               {{{2
 *
 * Creates a single shape based on a string in "line" and puts it into the
 * "shapes" vector.
 */

void ShapeShifter::add_shape(const string& line) {

}

/*
 * apply_shape                                                             {{{2
 *
 * Inserts a shape into the game grid. The shape is in "shapes" at index
 * "shape_id" and it is inserted at the top-left corner, but shifted by
 * "x" and "y". If the shape shifted by "x" and "y" goes out of the game board,
 * make sure nothing happens. This function may be used twice to "undo" a shape
 * apply.
 *
 * (ex. Assume the given grid "100 101 000" and shape "111".
 *
 *    apply_shape at (x: 0, y: 0)      apply_shape at (x: 0, y: 1)
 *      100   111   011                  100         100
 *      101 +     = 101                  101 + 111 = 010
 *      000         000                  000         000
 */

bool ShapeShifter::apply_shape(uint shape_id, uint x, uint y) {
	/*
	 * - Check if the shape can fit in the grid when shifted by "x" and "y".
	 * - Invert all parts of the grid where the shape would be red at.
	 */

	return false;
}

/*
 * all_one                                                                 {{{2
 *
 * Checks if all cells in the grid are "1". Returns TRUE if so. Otherwise, it
 * returns FALSE.
 */

bool ShapeShifter::all_one() {
	return false;
}

/*
 * find_solution                                                           {{{2
 *
 * Recursively traverse and try to find a solution. If called with no argument,
 * it'll start at the very first shape in the "shapes" vector and go through
 * each of them trying to apply in every possible position until a solution is
 * found. Returns TRUE upon a solution being found, and FALSE otherwise.
 */

bool ShapeShifter::find_solution(uint shape_id) {
	/*
	 * The recursive function.
	 *
	 * - With "shape_id", go through every possible position and try to insert
	 *   shape[shape_id] in.
	 *
	 * - If inserted and it isn't the last shape, call:
	 *     find_solution(shape_id + 1)
	 *
	 * - If inserted and it is the last shape, call "all_one". If true then
	 *   return true. Have the other calls to the function also handle this
	 *   return.
	 *
	 * - If you looped through all possible positions and it didn't work, undo
	 *   all changes done to the class involving this shape and return false.
	 */

	return false;
}

/*
 * print_solution                                                          {{{2
 *
 * Goes through the "solution" deque and prints out the coordinates of each
 * shape, along with the original string used to make up the shape.
 */

void ShapeShifter::print_solution() {

}

// ----------------------------------------------------------------------------
// Main Function                                                           {{{1
// ----------------------------------------------------------------------------

int main(int argc, char** argv) {
	/*
	 * - Create a vector of strings holding all argv after argv[0]
	 *
	 * - Create your ShapeShifter object.
	 *
	 * - Create all shapes.
	 *
	 * - Find a solution.
	 *
	 * - Print the result.
	 */

	return 0;
}