/*
								+--------------------------------+
								|                                |
								|*** Simple search algorithms ***|
								|                                |
								|  Copyright © -tHE SWINe- 2009  |
								|                                |
								|            Search.h            |
								|                                |
								+--------------------------------+
*/

#pragma once
#ifndef __SIMPLE_SEARCH_ALGORITHMS_INCLUDED
#define __SIMPLE_SEARCH_ALGORITHMS_INCLUDED

/**
 *	@file Search.h
 *	@brief simple search algorithms (BFS, DFS)
 *	@date 2009
 *	@author -tHE SWINe-
 *
 *	Here is a small use case:
 *	@code
 *	class CSearchTest {
 *	public:
 *		typedef std::pair<int, int> TState; // x and y in the maze
 *	
 *		struct TPath { // this is only needed if a path needs to be recovered, otherwise TState will do
 *			std::vector<TState> seq; // sequence of state (alternately the moves cound be stored)
 *
 *			inline operator TState() const // this is required by CDepthFirstSearch, CBreadthFirstSearch
 *			{
 *				return seq.back();
 *			}
 *		};
 *	
 *		template <template <class> class CSearchType>
 *		struct TNextSteps { // this is needed to propose next steps from a specific state
 *			int n;
 *			const char *p_maze;
 *	
 *			TNextSteps(int _n, const char *_p_maze) // needs to know the maze (for collision checking)
 *				:n(_n), p_maze(_p_maze)
 *			{}
 *	
 *			void operator ()(const TPath &p, typename
 *				CSearchType<TState>::CAdjacentCallback<TPath> cb) const // propose next steps from p
 *			{
 *				TState s = (TState)p; // get the last state
 *				for(int i = 0; i < 4; ++ i) { // try all four directions
 *					TState ns(s.first + ((1 == i) ^ -!i), s.second + i % 3 - !!i);
 *					if(p_maze[ns.first + n * ns.second] == '*')
 *						continue; // would hit a wall
 *					TPath np = p;
 *					np.seq.push_back(ns); // make a path with the next step
 *					cb(np); // pass to explore the following steps
 *				}
 *			}
 *		};
 *	
 *		struct TIsGoal { // this is needed to accept the state as a goal
 *			int n;
 *			const char *p_maze;
 *	
 *			TIsGoal(int _n, const char *_p_maze) // needs to know the maze (goal is marked there)
 *				:n(_n), p_maze(_p_maze)
 *			{}
 *	
 *			bool operator ()(TState s) const // return true if s is the goal state
 *			{
 *				return p_maze[s.first + n * s.second] == 'G'; // we reached a goal
 *			}
 *		};
 *	
 *		CSearchTest() // runs some tests
 *		{
 *			char p_maze[] = // not constant string, so we can modify
 *				"**********\n"
 *				"*        *\n"
 *				"* * **** *\n"
 *				"* *    * *\n"
 *				"* **** * *\n"
 *				"* * G  * *\n"
 *				"* * ****S*\n"
 *				"* *    * *\n"
 *				"* **** * *\n"
 *				"*        *\n"
 *				"**********\n";
 *			const int n = 11; // newlines also counted
 *			int n_start = int(strchr(p_maze, 'S') - p_maze);
 *			printf("%s", p_maze);
 *	
 *			TPath path;
 *			path.seq.push_back(TState(n_start % n, n_start / n));
 *			// prepare a path with just the starting point in it
 *
 *			path = CDepthFirstSearch<TState>::t_Find(path,
 *				TNextSteps<CDepthFirstSearch>(n, p_maze), TIsGoal(n, p_maze), n * n).first;
 *			// perform the search (DFS is sometimes fast but not optimal)
 *
 *			for(size_t i = 1, ss = path.seq.size() - 1; i < ss; ++ i)
 *				p_maze[path.seq[i].first + n * path.seq[i].second] = '.'; // leave breadcrumbs
 *			printf("DFS found path of length %d\n", path.seq.size());
 *			printf("%s", p_maze);
 *			// print the solution
 *	
 *			std::replace(p_maze, p_maze + strlen(p_maze), '.', ' '); // delete breadcrumbs
 *			path.seq.erase(path.seq.begin() + 1, path.seq.end()); // delete steps except the first one
 *	
 *			path = CBreadthFirstSearch<TState>::t_Find(path,
 *				TNextSteps<CBreadthFirstSearch>(n, p_maze), TIsGoal(n, p_maze)).first;
 *			// perform the search (BFS guaranteed to be optimal)
 *
 *			for(size_t i = 1, ss = path.seq.size() - 1; i < ss; ++ i)
 *				p_maze[path.seq[i].first + n * path.seq[i].second] = '.'; // leave breadcrumbs
 *			printf("BFS found path of length %d\n", path.seq.size());
 *			printf("%s", p_maze);
 *	
 *			size_t n_path_length_bound = path.seq.size();
 *			std::replace(p_maze, p_maze + strlen(p_maze), '.', ' '); // delete breadcrumbs
 *			path.seq.erase(path.seq.begin() + 1, path.seq.end()); // delete steps except the first one
 *	
 *			path = CDepthFirstSearch<TState>::t_Find(path, TNextSteps<CDepthFirstSearch>(n, p_maze),
 *				TIsGoal(n, p_maze), n_path_length_bound).first;
 *			// depth-limited DFS is guaranteed to find the solution if it exists at the given bound
 *
 *			for(size_t i = 1, ss = path.seq.size() - 1; i < ss; ++ i)
 *				p_maze[path.seq[i].first + n * path.seq[i].second] = '.'; // leave breadcrumbs
 *			printf("depth-limited DFS also found path of length %d\n", path.seq.size());
 *			printf("%s", p_maze);
 *		}
 *	} run_test;
 *	@endcode
 */

#include "NewFix.h"
#include "CallStack.h"
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <utility>

/**
 *	@brief breadth-first search algorithm
 *	@tparam CState is state representation, must have copy and comparison operators
 *
 *	Use as follows:
 *	@code
 *	void Test()
 *	{
 *		int n = 5;
 *		size_t P[] = {2, 3, 1, 4, 0};
 *		// a permutation
 *	
 *		std::vector<size_t> perm(P, P + n);
 *		size_t count_BFS = CBreadthFirstSearch<TPerm>::n_Find(perm, Enumerate_NextPermutations, b_IsIdentity);
 *		// find the number of swaps changing the given permutation to an identity permutation
 *	
 *		printf("reachable in %d steps\n", count_BFS);
 *		// print the number of swaps
 *	
 *		TPermSeq path;
 *		path.final.insert(path.final.end(), P, P + n);
 *		path = CBreadthFirstSearch<TPerm>::t_Find(path, Enumerate_NextPermutations2, b_IsIdentity).first;
 *		// recover the sequence of the swaps as well
 *	
 *		for(size_t i = 0; i < path.swap_list.size(); ++ i) {
 *			for(int j = 0; j < n; ++ j)
 *				printf("%d ", P[j]);
 *			printf("| swap %d <-> %d\n", path.swap_list[i].first, path.swap_list[i].second);
 *			std::swap(P[path.swap_list[i].first], P[path.swap_list[i].second]);
 *		}
 *		for(int j = 0; j < n; ++ j)
 *			printf("%d ", P[j]);
 *		printf("\n");
 *		// print the list of the moves
 *	}
 *	@endcode
 *
 *	This outputs:
 *	@code
 *	reachable in 4 steps
 *	2 3 1 4 0 | swap 0 <-> 1
 *	3 2 1 4 0 | swap 0 <-> 3
 *	4 2 1 3 0 | swap 0 <-> 4
 *	0 2 1 3 4 | swap 1 <-> 2
 *	0 1 2 3 4
 *	@endcode
 *
 *	Assuming the following helper functions are provided:
 *	@code
 *	typedef std::vector<size_t> TPerm; // permutation type
 *	
 *	struct TPermSeq { // permutation sequence, a path
 *		std::vector<std::pair<size_t, size_t> > swap_list;
 *		TPerm final;
 *	
 *		inline operator TPerm() const
 *		{
 *			return final;
 *		}
 *	};
 *	
 *	inline bool b_IsIdentity(const TPerm &P) // identifies goal
 *	{
 *		for(size_t i = 0, n = P.size(); i < n; ++ i) {
 *			if(P[i] != i)
 *				return false;
 *		}
 *		return true;
 *	}
 *	
 *	inline void Enumerate_NextPermutations(const TPerm &P,
 *		CBreadthFirstSearch<TPerm>::CAdjacentCallback<> cb)
 *	{
 *		size_t n = P.size();
 *		for(size_t i = 0; i < n; ++ i) {
 *			for(size_t j = i + 1; j < n; ++ j) { // order of swap does not matter
 *				TPerm next(P);
 *				std::swap(next[i], next[j]);
 *				// modify P to get the next state
 *	
 *				cb(next);
 *				// enqueue the next state to be explored
 *			}
 *		}
 *	}
 *
 *	inline void Enumerate_NextPermutations2(const TPermSeq &P,
 *		CBreadthFirstSearch<TPerm>::CAdjacentCallback<TPermSeq> cb)
 *	{
 *		size_t n = P.final.size();
 *		for(size_t i = 0; i < n; ++ i) {
 *			for(size_t j = i + 1; j < n; ++ j) { // order of swap does not matter
 *				TPermSeq next = P; // make a copy
 *				std::swap(next.final[i], next.final[j]);
 *				next.swap_list.push_back(std::make_pair(i, j)); // remember how we did it
 *				// modify P to get the next state
 *	
 *				cb(next);
 *				// enqueue the next state to be explored
 *			}
 *		}
 *	}
 *	@endcode
 */
template <class CState>
class CBreadthFirstSearch {
public:
	/**
	 *	@brief adjacent state callback
	 *
	 *	@tparam CPath is state string representation (a path); may be equal to CState
	 *	@tparam CPayload is state payload (default size_t - the depth of the state in the search tree)
	 */
	template <class CPath = CState, class CPayload = size_t>
	class CAdjacentCallback {
	protected:
		std::queue<std::pair<CPath, CPayload> > &m_r_opened; /**< @brief reference to the queue of states to be explored */
		std::set<CState> &m_r_closed; /**< @brief reference to the set of closed states */
		CPayload m_t_next_payload; /**< @brief generated states payload */

	public:
		/**
		 *	@brief default constructor
		 *
		 *	@param[in] r_opened is reference to the queue of states to be explored
		 *	@param[in] r_closed is reference to the set of closed states
		 *	@param[in] t_next_payload is payload to be packed with the generated next states
		 */
		CAdjacentCallback(std::queue<std::pair<CPath, CPayload> > &r_opened,
			std::set<CState> &r_closed, CPayload t_next_payload)
			:m_r_opened(r_opened), m_r_closed(r_closed), m_t_next_payload(t_next_payload)
		{}

		/**
		 *	@brief function operator; adds a next state or path to be explored
		 *	@param[in] r_next is next state or path to be explored
		 *	@note This function throws std::bad_alloc.
		 */
		inline void operator ()(const CPath &r_next) // throw(std::bad_alloc)
		{
			if(m_r_closed.find(r_next) != m_r_closed.end())
				return;
			// ...

			m_r_closed.insert((CState)r_next); // cast to state (the final state)
			m_r_opened.push(std::make_pair(r_next, m_t_next_payload));
			// try the permutation and see if we already visited it
		}
	};

public:
	/**
	 *	@brief finds if there is a BFS solution and returns path to it
	 *
	 *	@tparam CPath is path representation, must implement conversion to state
	 *		which returns the final state in that path (may equal CState)
	 *	@tparam CAdjacentEnum is adjacent state enumerator function object
	 *		with function operator that takes CPath and CAdjacentCallback<CPath>
	 *		as parameters, emits new possible CPath instances to the callback
	 *	@tparam CAccept is accept object that takes pair of CState and size_t
	 *		as parameters (the size_t is depth of the item) and returns true
	 *		if it represents a valid solution
	 *
	 *	@param[in] starting_state is path, containing just the state to start with
	 *	@param[in] enumerate is function object that enumerates the next steps
	 *	@param[in] accept is function object that accepts solution
	 *	@param[in] n_max_depth is maximum search depth bound (0 is infinite depth)
	 *
	 *	@return Returns pair of the shortest path and depth at which the solution
	 *		was found, or pair of the initial state and -1 if no solution was found.
	 *
	 *	@note This function throws std::bad_alloc.
	 */
	template <class CPath, class CAdjacentEnum, class CAccept>
	static std::pair<CPath, size_t> t_Find(CPath starting_state, CAdjacentEnum enumerate,
		CAccept accept, size_t n_max_depth = 0) // throw(std::bad_alloc)
	{
		std::set<CState> closed;
		closed.insert((CState)starting_state);
		// don't come back to the first one

		std::queue<std::pair<CPath, size_t> > opened;
		opened.push(std::make_pair(starting_state, size_t(0)));
		while(!opened.empty()) {
			std::pair<CPath, size_t> cur = opened.front();
			opened.pop();
			// get the next state from the queue

			if(accept((const CPath&)cur.first))
				return cur; // path and depth where it was found
			if(n_max_depth && cur.second == n_max_depth)
				continue; // can't recurse from here
			// see if we can accept as solution or recurse

			enumerate(cur.first, CAdjacentCallback<CPath>(opened, closed, cur.second + 1));
			// generate adjacent states
		}

		return std::make_pair(starting_state, size_t(-1));
		// no solution found
	}

	/**
	 *	@brief finds if there is a BFS solution
	 *
	 *	@tparam CPath is path representation, must implement conversion to state
	 *		which returns the final state in that path (may equal CState)
	 *	@tparam CAdjacentEnum is adjacent state enumerator function object
	 *		with function operator that takes CPath and CAdjacentCallback<CPath>
	 *		as parameters, emits new possible CPath instances to the callback
	 *	@tparam CAccept is accept object that takes pair of CState and size_t
	 *		as parameters (the size_t is depth of the item) and returns true
	 *		if it represents a valid solution
	 *
	 *	@param[in] starting_state is path, containing just the state to start with
	 *	@param[in] enumerate is function object that enumerates the next steps
	 *	@param[in] accept is function object that accepts solution
	 *	@param[in] n_max_depth is maximum search depth bound (0 is infinite depth)
	 *
	 *	@return Returns depth at which the solution was found, or -1 if no solution was found.
	 *
	 *	@note This function throws std::bad_alloc.
	 */
	template <class CPath, class CAdjacentEnum, class CAccept>
	static inline size_t n_Find(CPath starting_state, CAdjacentEnum enumerate,
		CAccept accept, size_t n_max_depth = 0) // throw(std::bad_alloc)
	{
		return t_Find(starting_state, enumerate, accept, n_max_depth).second; // return just depth
		// note that this probably involves extra copy of the path // todo - can we avoid that without duplicating the code?
	}
};

/**
 *	@brief depth-first search algorithm
 *	@tparam CState is state representation, must have copy and comparison operators
 *	@note See CBreadthFirstSearch for example of how to use this.
 */
template <class CState>
class CDepthFirstSearch {
public:
	/**
	 *	@brief adjacent state callback
	 *
	 *	@tparam CPath is state string representation (a path); may be equal to CState
	 *	@tparam CPayload is state payload (default size_t - the depth of the state in the search tree)
	 */
	template <class CPath = CState, class CPayload = size_t>
	class CAdjacentCallback {
	protected:
		std::stack<std::pair<CPath, CPayload> > &m_r_opened; /**< @brief reference to the stack of states to be explored */
		CPayload m_t_next_payload; /**< @brief generated states payload */

	public:
		/**
		 *	@brief default constructor
		 *
		 *	@param[in] r_opened is reference to the stack of states to be explored
		 *	@param[in] t_next_payload is payload to be packed with the generated next states
		 */
		CAdjacentCallback(std::stack<std::pair<CPath, CPayload> > &r_opened,
			CPayload t_next_payload)
			:m_r_opened(r_opened), m_t_next_payload(t_next_payload)
		{}

		/**
		 *	@brief function operator; adds a next state or path to be explored
		 *	@param[in] r_next is next state or path to be explored
		 *	@note This function throws std::bad_alloc.
		 */
		inline void operator ()(const CPath &r_next) // throw(std::bad_alloc)
		{
			m_r_opened.push(std::make_pair(r_next, m_t_next_payload));
			// try the permutation and see if we already visited it
		}
	};

public:
	/**
	 *	@brief finds if there is a DFS solution and returns path to it
	 *
	 *	@tparam CPath is path representation, must implement conversion to state
	 *		which returns the final state in that path (may equal CState)
	 *	@tparam CAdjacentEnum is adjacent state enumerator function object
	 *		with function operator that takes CPath and CAdjacentCallback<CPath>
	 *		as parameters, emits new possible CPath instances to the callback
	 *	@tparam CAccept is accept object that takes pair of CState and size_t
	 *		as parameters (the size_t is depth of the item) and returns true
	 *		if it represents a valid solution
	 *
	 *	@param[in] starting_state is path, containing just the state to start with
	 *	@param[in] enumerate is function object that enumerates the next steps
	 *	@param[in] accept is function object that accepts solution
	 *	@param[in] n_max_depth is maximum search depth bound (0 is infinite depth)
	 *
	 *	@return Returns pair of the shortest path and depth at which the solution
	 *		was found, or pair of the initial state and -1 if no solution was found.
	 *
	 *	@note This function throws std::bad_alloc.
	 */
	template <class CPath, class CAdjacentEnum, class CAccept>
	static std::pair<CPath, size_t> t_Find(CPath starting_state, CAdjacentEnum enumerate,
		CAccept accept, size_t n_max_depth = 0) // throw(std::bad_alloc)
	{
		if(n_max_depth) {
			// depth-limited search is slightly more complicated

			std::map<CState, size_t> closed; // state and depth where it was closed
			std::stack<std::pair<CPath, size_t> > opened;
			opened.push(std::make_pair(starting_state, size_t(0)));
			while(!opened.empty()) {
				std::pair<CPath, size_t> cur = opened.top();
				opened.pop();
				// get the next state from the stack

				_ASSERTE(n_max_depth);
				if(/*n_max_depth &&*/ cur.second > n_max_depth)
					continue; // can't recurse from here
				std::map<CState, size_t>::const_iterator p_closed_it;
				if((p_closed_it = closed.find((CState)cur.first)) != closed.end() &&
				   (*p_closed_it).second <= cur.second)
					continue; // only reject if it was closed on higher depth
				closed[(CState)cur.first] = cur.second;
				// checking for closed is here in DFS

				if(accept((const CPath&)cur.first))
					return cur; // path and depth where it was found
				// see if we can accept as solution or recurse

				enumerate(cur.first, CAdjacentCallback<CPath>(opened, cur.second + 1));
				// generate adjacent states
			}
		} else {
			// depth unlimited search is simpler

			std::set<CState> closed; // only state
			std::stack<std::pair<CPath, size_t> > opened;
			opened.push(std::make_pair(starting_state, size_t(0)));
			while(!opened.empty()) {
				std::pair<CPath, size_t> cur = opened.top();
				opened.pop();
				// get the next state from the stack

				if(closed.find((CState)cur.first) != closed.end())
					continue; // depth unbound - always reject
				closed.insert((CState)cur.first);
				// checking for closed is here in DFS

				if(accept((const CPath&)cur.first))
					return cur; // path and depth where it was found
				// see if we can accept as solution or recurse

				enumerate(cur.first, CAdjacentCallback<CPath>(opened, cur.second + 1));
				// generate adjacent states
			}
		}

		return std::make_pair(starting_state, size_t(-1));
		// no solution found
	}

	/**
	 *	@brief finds if there is a DFS solution
	 *
	 *	@tparam CPath is path representation, must implement conversion to state
	 *		which returns the final state in that path (may equal CState)
	 *	@tparam CAdjacentEnum is adjacent state enumerator function object
	 *		with function operator that takes CPath and CAdjacentCallback<CPath>
	 *		as parameters, emits new possible CPath instances to the callback
	 *	@tparam CAccept is accept object that takes pair of CState and size_t
	 *		as parameters (the size_t is depth of the item) and returns true
	 *		if it represents a valid solution
	 *
	 *	@param[in] starting_state is path, containing just the state to start with
	 *	@param[in] enumerate is function object that enumerates the next steps
	 *	@param[in] accept is function object that accepts solution
	 *	@param[in] n_max_depth is maximum search depth bound (0 is infinite depth)
	 *
	 *	@return Returns depth at which the solution was found, or -1 if no solution was found.
	 *
	 *	@note This function throws std::bad_alloc.
	 */
	template <class CPath, class CAdjacentEnum, class CAccept>
	static inline size_t n_Find(CPath starting_state, CAdjacentEnum enumerate,
		CAccept accept, size_t n_max_depth = 0) // throw(std::bad_alloc)
	{
		return t_Find(starting_state, enumerate, accept, n_max_depth).second; // return just depth
		// note that this probably involves extra copy of the path // todo - can we avoid that without duplicating the code?
	}
};

#endif // !__SIMPLE_SEARCH_ALGORITHMS_INCLUDED
