module test_a_star

import a_star

#redef class Object
#	redef fun debug_a_star do return true
#end

# Simple node with a name
class NamedNode
	super Node

	redef type N: NamedNode

	var name: String

	init(graph: Graph[N, Link], name: String)
	do
		self.name = name
		super
	end

	redef fun to_s do return "node:{name}"
end

# Node with a name and position
class PositionedNamedNode
	super NamedNode

	redef type N: PositionedNamedNode

	var x: Int
	var y: Int

	init(graph: Graph[N, Link], name: String, x, y: Int)
	do
		super

		self.x = x
		self.y = y
	end

	redef fun to_s do return "{super}-at-({x},{y})"

	fun dist_with(o: PositionedNamedNode): Int
	do
		var dx = o.x - x
		var dy = o.y - y
		var d2 = dx*dx + dy*dy
		return d2.sqrt
	end
end

# Link for nodes with a position
class PositionedLink
	super Link

	redef type N: PositionedNamedNode
end

# Context for a graph with positions
class PositionPathContext
	super PathContext

	redef type N: PositionedNamedNode
	redef type L: PositionedLink

	init(graph: Graph[N,L])
	do
		super

		for l in graph.links do
			var this_cost = cost(l)
			if this_cost > worst_cost then worst_cost = this_cost
		end
	end

	redef var worst_cost = 0

	redef fun cost(link) do return link.from.dist_with(link.to)

	redef fun is_blocked(link) do return false

	redef fun heuristic_cost(a, b)
	do
		var cost = a.dist_with(b)
		if cost > 100 then return 100
		return cost
	end

	redef fun worst_heuristic_cost do return 100
end

fun print_path(path: nullable AStarPath[NamedNode]) do if path == null then
	print "null path"
else
	var names = new Array[String]
	while not path.at_end_of_path do
		var step = path.step
		names.add(step.name)
	end
	print names.join(", ")
end

# Graph
#   a - b
#  /   /
# c - d - e
fun case_simple
do
	var graph = new Graph[NamedNode, Link]

	var na = new NamedNode(graph, "a")
	var nb = new NamedNode(graph, "b")
	var nc = new NamedNode(graph, "c")
	var nd = new NamedNode(graph, "d")
	var ne = new NamedNode(graph, "e")

	var lab = new Link(graph, na, nb)
	var lac = new Link(graph, na, nc)
	var lbd = new Link(graph, nb, nd)
	var lcd = new Link(graph, nc, nd)
	var lde = new Link(graph, nd, ne)

	var context = new ConstantPathContext(graph)

	var path = na.path_to(ne, 100, context)
	print_path(path)
end

# Graph
#   a - b
#  /   /
# c - d    e
fun case_failed
do
	var graph = new Graph[NamedNode,Link]

	var na = new NamedNode(graph, "a")
	var nb = new NamedNode(graph, "b")
	var nc = new NamedNode(graph, "c")
	var nd = new NamedNode(graph, "d")
	var ne = new NamedNode(graph, "e")

	var lab = new Link(graph, na, nb)
	var lac = new Link(graph, na, nc)
	var lbd = new Link(graph, nb, nd)
	var lcd = new Link(graph, nc, nd)

	var context = new ConstantPathContext(graph)

	var path = na.path_to(ne, 100, context)
	print_path(path)
end

# Weighted graph
#     a -2- b
#    /     /
#   3     1
#  /     /
# c -3- d -8- e
fun case_weighted
do
	var graph = new Graph[NamedNode,WeightedLink]

	var na = new NamedNode(graph, "a")
	var nb = new NamedNode(graph, "b")
	var nc = new NamedNode(graph, "c")
	var nd = new NamedNode(graph, "d")
	var ne = new NamedNode(graph, "e")

	var lab = new WeightedLink(graph, na, nb, 2)
	var lac = new WeightedLink(graph, na, nc, 3)
	var lbd = new WeightedLink(graph, nb, nd, 1)
	var lcd = new WeightedLink(graph, nc, nd, 3)
	var lde = new WeightedLink(graph, nd, ne, 8)

	var context = new WeightedPathContext(graph)

	var path = na.path_to(ne, 100, context)
	print_path(path)
end

# Weighted graph
#     a -2- b
#    /     /
#   3     1
#  /     /
# c -3- d -8- e
fun case_weighted_too_long
do
	var graph = new Graph[NamedNode,WeightedLink]

	var na = new NamedNode(graph, "a")
	var nb = new NamedNode(graph, "b")
	var nc = new NamedNode(graph, "c")
	var nd = new NamedNode(graph, "d")
	var ne = new NamedNode(graph, "e")

	var lab = new WeightedLink(graph, na, nb, 2)
	var lac = new WeightedLink(graph, na, nc, 3)
	var lbd = new WeightedLink(graph, nb, nd, 1)
	var lcd = new WeightedLink(graph, nc, nd, 3)
	var lde = new WeightedLink(graph, nd, ne, 8)

	var context = new WeightedPathContext(graph)

	var path = na.path_to(ne, 5, context)
	print_path(path)
end

# "Big" weighted graph
#
#     a -2- b -1- f -1- g
#    /     /       \   /
#   3     1        4  1
#  /     /         \ /
# c -3- d -8- e -2- h -2- i -3- j
#
fun case_weighted_big
do
	var graph = new Graph[NamedNode,WeightedLink]

	var na = new NamedNode(graph, "a")
	var nb = new NamedNode(graph, "b")
	var nc = new NamedNode(graph, "c")
	var nd = new NamedNode(graph, "d")
	var ne = new NamedNode(graph, "e")
	var nf = new NamedNode(graph, "f")
	var ng = new NamedNode(graph, "g")
	var nh = new NamedNode(graph, "h")
	var ni = new NamedNode(graph, "i")
	var nj = new NamedNode(graph, "j")

	var lab = new WeightedLink(graph, na, nb, 2)
	var lac = new WeightedLink(graph, na, nc, 3)
	var lbd = new WeightedLink(graph, nb, nd, 1)
	var lcd = new WeightedLink(graph, nc, nd, 3)
	var lde = new WeightedLink(graph, nd, ne, 8)
	var lbf = new WeightedLink(graph, nb, nf, 1)
	var lfg = new WeightedLink(graph, nf, ng, 1)
	var leh = new WeightedLink(graph, ne, nh, 2)
	var lhi = new WeightedLink(graph, nh, ni, 2)
	var lij = new WeightedLink(graph, ni, nj, 3)
	var lfh = new WeightedLink(graph, nf, nh, 4)
	var lgh = new WeightedLink(graph, ng, nh, 1)

	var context = new WeightedPathContext(graph)

	var path = na.path_to(nj, 100, context)
	print_path(path)
end

# Double-edge graph with coordinates on nodes
#
# a--b--d--e
#  \       |
#   c------f
#
fun cases_with_positions_and_heuristic
do
	var graph = new Graph[PositionedNamedNode,PositionedLink]

	var na = new PositionedNamedNode(graph, "a", 0, 0)
	var nb = new PositionedNamedNode(graph, "b", 2, 0)
	var nc = new PositionedNamedNode(graph, "c", 2, 2)
	var nd = new PositionedNamedNode(graph, "d", 5, 0)
	var ne = new PositionedNamedNode(graph, "e", 8, 0)
	var nf = new PositionedNamedNode(graph, "f", 8, 2)

	var lab = new PositionedLink(graph, na, nb)
	var lac = new PositionedLink(graph, na, nc)
	var lbd = new PositionedLink(graph, nb, nd)
	var lde = new PositionedLink(graph, nd, ne)
	var lef = new PositionedLink(graph, ne, nf)
	var lcf = new PositionedLink(graph, nc, nf)

	# inverted
	var lba = new PositionedLink(graph, nb, na)
	var lca = new PositionedLink(graph, nc, na)
	var ldb = new PositionedLink(graph, nd, nb)
	var led = new PositionedLink(graph, ne, nd)
	var lfe = new PositionedLink(graph, nf, ne)
	var lfc = new PositionedLink(graph, nf, nc)

	var context = new PositionPathContext(graph)

	print_path(na.path_to(nf, 100, context))
	print_path(nf.path_to(na, 100, context))
	print_path(nc.path_to(ne, 100, context))
	print_path(nd.path_to(nc, 100, context))
end

case_simple
case_failed
case_weighted
case_weighted_too_long
case_weighted_big
cases_with_positions_and_heuristic