# A node in the search-tree visited by a `SearchSolver`.
# In search-trees, nodes are labeled with states (`S`), and edges by actions (`A`).
#
# The root node is labeled by the initial state of the problem.
#
# This class is exposed to allow queries on the solution provided by the solver.
class SearchNode[S: Object, A]
	# A flag that indicate that `self` is virtually removed from the todo-list.
	# `self` was added to the todo-list but that a better node for the
	# same state was found latter.
	private var drop = false

	# The associated problem
	var problem: SearchProblem[S, A]

	# The state associated to `self`.
	# The state labels the node `self`.
	var state: S

	# Is `self` a root node of the search-tree?
	# ensure: `result` == `parent == null` and `result`== `action == null`
	fun is_root: Bool do return parent == null

	# The previous node in the search-tree (if not root).
	var parent: nullable SearchNode[S, A]

	# The action used to go from `parent` to `self` (if not root)
	# The action labels the edge from `parent` to `self`.
	var action: nullable A

	# The past cost (g) from the root node to `self`.
	var cost: Float

	# The heuristic from self to the goal (according to `problem.heuristic(state)`
	# It is the future cost (h)
	var heuristic: Float is noinit

	# The sum of `cost` and `heuristic`
	# It is the f function.
	var score: Float is noinit

	# Update `heuristic` and `score` according to `problem`.
	private fun compute_heuristic
	do
		var h = problem.heuristic(state)
		heuristic = h
		score = cost + h
	end

	# The depth of `self` in the search tree
	# It is the number of parents to the root node.
	var depth: Int

	# The number of steps needed by the solver to process `self`
	# It is just a useless generation number, but could be used to evaluate
	# the behavior of search algorithms.
	var steps: Int = 0

	# The rank of creation of nodes by the solver.
	# It is just a useless generation number, but could be used to evaluate
	# the behavior of search algorithms.
	var id: Int = 0

	# The number of (potential) revisits of `node`.
	# This information can be used to debug search algorithms.
	# And to detect when heuristics are not admissible.
	#
	# See `SearchSolver::revisits` and `SearchSolver::do_revisit`
	# for details.
	var revisits: Int = 0

	# Create a new child node for the next state, according to `problem`.
	# Used internally by the solvers but made public for those who want to replay a plan.
	#
	# ensure `result.parent == self`
	# ensure `result.action == action`
	fun apply_action(action: A): SearchNode[S, A]
	do
		var new_state = problem.apply_action(state, action)
		var new_cost = problem.cost(state, action, new_state)
		var new_node = new SearchNode[S, A](problem, new_state, self, action, cost + new_cost, depth+1)
		new_node.compute_heuristic
		return new_node
	end

	# Build the sequence of nodes from the initial node to `self`
	#
	# ensure `result.first.is_root and result.last == self`
	fun path: Sequence[SearchNode[S, A]]
	do
		var res = new List[SearchNode[S, A]]
		res.add(self)
		var node = parent
		while node != null do
			res.unshift(node)
			node = node.parent
		end
		return res
	end

	# Build a sequence of actions from the initial state to `self`
	# See `path` for a more detailed plan.
	fun plan: Sequence[A]
	do
		var res = new List[A]
		var node: nullable SearchNode[S, A] = self
		while node != null do
			var a = node.action
			if a != null then res.unshift(a)
			node = node.parent
		end
		return res
	end

	# Just print a detailed path on the screen
	fun dump
	do
		print "result:{state}"
		for n in path do
			var a = n.action
			if a != null then print "    + {a}"
			print "  {n.steps}: {n.state} ({n.cost}$)"
		end
	end

	redef fun to_s do return "#{steps}/{id} d={depth} f={cost+heuristic} g={cost} h={heuristic}: {state}"
	#redef fun to_s do return "#{steps} f={(cost+heuristic).to_i} g={cost.to_i} h={heuristic.to_i}"
end