# General graph node
class Node
	super Serializable

	# Type of the others nodes in the `graph`
	type N: Node

	# parent graph
	var graph: Graph[N, Link]

	init
	do
		graph.add_node(self)
	end

	# adjacent nodes
	var links: Set[Link] = new HashSet[Link]

	# used to check if node has been searched in one pathfinding
	private var last_pathfinding_evocation: Int = 0

	# cost up to in current evocation
	# lifetime limited to evocation of `path_to`
	private var best_cost_up_to: Int = 0

	# source node
	# lifetime limited to evocation of `path_to`
	private var best_source: nullable N = null

	# is in frontier or buckets
	# lifetime limited to evocation of `path_to`
	private var open: Bool = false

	# Main functionality, returns path from `self` to `dest`
	fun path_to(dest: N, max_cost: Int, context: PathContext): nullable AStarPath[N]
	do
		return path_to_alts(dest, max_cost, context, null)
	end

	# Find a path to a possible `destination` or a node accepted by `alt_targets`
	fun path_to_alts(destination: nullable N, max_cost: Int, context: PathContext,
		alt_targets: nullable TargetCondition[N]): nullable AStarPath[N]
	do
		var cost = 0

		var nbr_buckets = context.worst_cost + context.worst_heuristic_cost + 1
		var buckets = new Array[List[N]].with_capacity(nbr_buckets)

		for i in [0 .. nbr_buckets[ do
			buckets.add(new List[N])
		end

		graph.pathfinding_current_evocation += 1

		# open source node
		buckets[0].add(self)
		open = true
		self.last_pathfinding_evocation = graph.pathfinding_current_evocation
		self.best_cost_up_to = 0

		loop
			var frontier_node: nullable N = null

			var bucket_searched = 0

			# find next valid node in frontier/buckets
			loop
				var current_bucket = buckets[cost % nbr_buckets]

				if current_bucket.is_empty then # move to next bucket
					cost += 1
					if cost > max_cost then return null
					bucket_searched += 1

					if bucket_searched > nbr_buckets then break
				else # found a node
					frontier_node = current_bucket.pop

					if frontier_node.open then break
				end
			end

			# no path possible
			if frontier_node == null then
				return null

			# at destination
			else if frontier_node == destination or
			     (alt_targets != null and alt_targets.accept(frontier_node)) then

				var path = new AStarPath[N](cost)

				while frontier_node != self do
					path.nodes.unshift(frontier_node)
					frontier_node = frontier_node.best_source
					assert frontier_node != null
				end

				return path

			# adds all next nodes to frontier/buckets
			else
				frontier_node.open = false

				for link in frontier_node.links do
					var peek_node = link.to
					if not context.is_blocked(link) and
					 (peek_node.last_pathfinding_evocation != graph.pathfinding_current_evocation or
					   (peek_node.open and
					     peek_node.best_cost_up_to > cost + context.cost(link)))
					then
						peek_node.open = true
						peek_node.last_pathfinding_evocation = graph.pathfinding_current_evocation
						peek_node.best_cost_up_to = cost + context.cost(link)
						peek_node.best_source = frontier_node

						var est_cost
						if destination != null then
							est_cost = peek_node.best_cost_up_to + context.heuristic_cost(peek_node, destination)
						else if alt_targets != null then
							est_cost = peek_node.best_cost_up_to + alt_targets.heuristic_cost(peek_node, link)
						else est_cost = 0

						var at_bucket = buckets[est_cost % nbr_buckets]
						at_bucket.add(peek_node)
					end
				end
			end
		end
	end

	# Find the closest node accepted by `cond` under `max_cost`
	fun find_closest(max_cost: Int, context: PathContext, cond: nullable TargetCondition[N]): nullable N
	do
		var path = path_to_alts(null, max_cost, context, cond)
		if path == null then return null
		return path.nodes.last
	end

	# We customize the serialization process to avoid problems with recursive
	# serialization engines. These engines, such as `JsonSerializer`,
	# are at danger to serialize the graph as a very deep tree.
	# With a large graph it can cause a stack overflow.
	#
	# Instead, we serialize the nodes first and then the links.
	redef fun core_serialize_to(serializer)
	do
		serializer.serialize_attribute("graph", graph)
	end

	redef init from_deserializer(deserializer)
	do
		deserializer.notify_of_creation self

		var graph = deserializer.deserialize_attribute("graph", (new GetName[Graph[N, Link]]).to_s)
		if not graph isa Graph[N, Link] then graph = new Graph[N, Link]
		self.graph = graph
	end
end