# Abstract search problem over immutable states (`S`) and actions (`A`).
#
# This class serves to model problems of planing and path-finding.
# A state, `S`, is a point in the search problem and fully models a given state of the world.
# An action, `A`, is an available mean of transition between two states.
#
# This abstract class is generic made to work with any kind of states and actions.
# Therefore, specific subclasses must be developed to implement the required services:
#
# * `initial_state`
# * `actions`
# * `apply_action`
# * `is_goal`
#
# Note that the implemented methods should not temper with the parameters since it is expected
# that they remain unmodified.
#
#
# # Basic search
#
# These tree method are enough to trigger a basic search.
#
# The methods `breadth_first` and `depth_first` return pre-configured solvers for, respectively,
# a breadth-first search, a depth-first search.
#
#
# # Advanced search
#
# The `cost` method can be implemented to represent the cost of a single transition.
# By default, the cost is 1.
#
# The `heuristic` method can be implemented to represent a lower-bound estimation of the remaining
# cost to reach a goal state.
# By default, the heuristic is 0.
#
# If one of these (or both) methods are implemented, the `astar` method will return a pre-configured
# solver for a A* search.
#
# More configuration and optimization on the search can to be done in the `SearchSolver` class.
interface SearchProblem[S: Object, A]
	# The starting state for the problem
	fun initial_state: S is abstract

	# The available applicable actions for a given state.
	# While there is a potential large number of distinct states and actions, there should be only
	# a small number of possible action from a specific state (a small, or at least finite, branching factor).
	fun actions(state: S): nullable SequenceRead[A] is abstract

	# The new state when applying a given action
	#
	# The returned state can be:
	# * a completely new state,
	# * an existing state,
	# * a new state but equals to an existing state
	#   in this case, ensure that the `==` and `hash` method
	#   are correctly implemented.
	#
	# Remember, this method should not modify its parameters.
	#
	# REQUIRE: `actions(state).has(action)`
	fun apply_action(state:S, action:A): S is abstract

	# Is the state a goal state?
	# Once a goal state is found, the solver is automatically stopped.
	# A problem can have 0, one or more goals if it makes sense
	# but solver must be used accordingly.
	# Default: no goals
	fun is_goal(state:S): Bool do return false

	# The cost for `action` from `old_state` to `new_state`
	# REQUIRE: `apply_action(old_state, action) == new_state`
	# Default: `1`.
	# Note that having a 0 or negative value can make some search
	# algorithms fail, or not terminate.
	fun cost(state:S, action:A, state2: S): Float do return 1.0

	# An heuristic of the estimated `cost` going from `state` to a goal state.
	#
	# Is is expected that the heuristic is *admissible*, it means its is an
	# optimistic estimation and never an over-estimate, thus is cannot be
	# higher than the lowest possible remaining cost.
	# See `SearchSolver::do_revisit` for details.
	#
	# Default: `0`.
	fun heuristic(state: S): Float do return 0.0

	# return a new breadth-first solver
	fun breadth_first: SearchSolver[S, A]
	do
		var todo = (new Array[SearchNode[S, A]]).as_fifo
		var sol = new SearchSolver[S, A](self, todo)
		return sol
	end

	# return a new depth-first solver
	fun depth_first: SearchSolver[S, A]
	do
		var todo = (new List[SearchNode[S, A]]).as_lifo
		var sol = new SearchSolver[S, A](self, todo)
		return sol
	end

	# return a new best-first solver
	#
	# notes:
	# * if `heuristic` is not defined, this is basically a Dijkstra search.
	# * if `cost` in not defined either, this is basically a breadth-first search.
	fun astar: SearchSolver[S, A]
	do
		var cpt = new NodeComparator[S, A]
		var todo = new MinHeap[SearchNode[S, A]](cpt)
		var sol = new SearchSolver[S, A](self, todo)
		return sol
	end

	# Create the initial node in the search-tree.
	# Used internally by the solvers but made public for those who want to replay a plan.
	fun initial_node: SearchNode[S, A]
	do
		var res = new SearchNode[S,A](self, initial_state, null, null, 0.0, 0)
		res.compute_heuristic
		return res
	end

	# Negligible quantity for float comparisons
	# Because of float imprecision, two really near float values should be considered equals.
	# However, the specific epsilon value could be specific to the problem.
	#
	# The epsilon value is used for cost comparisons.
	#
	# Default: 1E-9
	fun epsilon: Float do return 0.000000001

	# Run and evaluate solvers with multiple configuration.
	# This method can be used to evaluate which configuration to choose by default for a given problem.
	#
	# `steps` is the maximum number of steps a giver configuration can run.
	fun run_configs(steps: Int)
	do
		var c = 0
		loop
			if astar.run_config(steps, c, "A*") then break
			c += 1
		end
	end

	# Various Map implementations of memory.
	# In order to try more configurations with `run_config`, this method
	# is called to provide alternative implementation.
	#
	# For instance, a subclass can redefine this method and extends the result with an additional `RBTreeMap`.
	# Note: because the true nature of the sates `S` is left to the user, some
	# specific Map implementation could be more efficient than a HashMop.
	#
	# Default: A `HashMap`
	fun make_memory: Array[Map[S, SearchNode[S, A]]]
	do
		var res = new Array[Map[S, SearchNode[S, A]]]
		res.add new HashMap[S, SearchNode[S, A]]
		return res
	end
end