# A node in the backtrack-zipper visited by a `BacktrackSolver`.
#
# The solver visits the virtual search tree with a zipper.
#
# A node is the zipper (this class) is associated to:
# * a state of the problem (indirectly),
# * the actions not yet explored from the state (see `totry`)
# * the action that yields to the state (see `action`), used to backtrack.
# * and the parent node in the zipper (see `parent`).
#
# There is no direct link between a node and a state; it is unneeded
# since the same state is used, and mutated, during the whole execution of the solver.
#
# This class is exposed to allow queries on the solution provided by the solver.
class BacktrackNode[A]
	# The previous node in the backtrack-zipper
	var parent: nullable BacktrackNode[A]

	# The last action executed
	var action: nullable A

	# The remaining actions to try from this node
	var totry: nullable Array[A] = null

	# The depth of `self` in the search-tree.
	var depth: Int

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

	# Build a sequence of nodes from the initial node to `self`
	# ensure `result.first.parent == null and result.last == self`
	fun path: Sequence[BacktrackNode[A]]
	do
		var res = new List[BacktrackNode[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 BacktrackNode[A] = self
		while node != null do
			var a = node.action
			if a != null then res.unshift(a)
			node = node.parent
		end
		return res
	end

	redef fun to_s do
		var res = "#{steps} d={depth}"
		var tt = totry
		if tt != null then res += " tt={tt.join(" ")}"
		return res
	end
end