lib/a_star: replace some class parameters with virtual types

Signed-off-by: Alexis Laferrière <alexis.laf@xymus.net>

diff --git a/lib/a_star.nit b/lib/a_star.nit
index 9faa262..98a905f 100644 (file)
--- a/lib/a_star.nit
+++ b/lib/a_star.nit
@@ -63,16 +63,16 @@ class Node
        type N: Node
 
        # parent graph
-       var graph: Graph[N, Link[N]]
+       var graph: Graph[N, Link]
 
-       init(graph: Graph[N, Link[N]])
+       init(graph: Graph[N, Link])
        do
                self.graph = graph
                graph.add_node(self)
        end
 
        # adjacent nodes
-       var links: Set[Link[N]] = new HashSet[Link[N]]
+       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
@@ -93,7 +93,7 @@ class Node
        protected fun cost_to(other: N): Int do return 1
 
        # Main functionnality, returns path from `self` to `dest`
-       fun path_to(dest: Node, max_cost: Int, context: PathContext[N, Link[N]]): nullable Path[N]
+       fun path_to(dest: Node, max_cost: Int, context: PathContext): nullable Path[N]
        do
                var cost: Int = 0
 
@@ -222,8 +222,9 @@ class Node
        end
 end
 
-class Link[N:Node]
-       type L: Link[N]
+class Link
+       type N: Node
+       type L: Link
 
        var graph: Graph[N, L]
 
@@ -241,13 +242,10 @@ class Link[N:Node]
 end
 
 # General graph
-class Graph[N:Node, L:Link[N]]
+class Graph[N: Node, L: Link]
        var nodes: Set[N] = new HashSet[N]
        var links: Set[L] = new HashSet[L]
 
-       #var max_link_cost: Int = 0
-       #var max_heuristic_cost: Int = 0
-
        fun add_node(node: N): N
        do
                nodes.add(node)
@@ -259,8 +257,6 @@ class Graph[N:Node, L:Link[N]]
        do
                links.add(link)
 
-               #if link.cost > max_link_cost then max_link_cost = link.cost
-
                link.from.links.add(link)
 
                return link
@@ -296,22 +292,26 @@ class Path[N]
 end
 
 # Context related to an evocation of pathfinding
-class PathContext[N: Node, L: Link[N]]
+class PathContext
+       type N: Node
+       type L: Link
+
        var graph: Graph[N, L]
 
        # Worst cost of all the link's costs
        fun worst_cost: Int is abstract
 
        # Get cost of a link
-       fun cost(link: Link[N]): Int is abstract
+       fun cost(link: Link): Int is abstract
 
        # Is that link blocked?
-       fun is_blocked(link: Link[N]): Bool is abstract
+       fun is_blocked(link: Link): Bool is abstract
 
        # Heuristic
        fun heuristic_cost(a, b: Node): Int is abstract
-end
 
+       fun worst_heuristic_cost: Int is abstract
+end
 
 #
 ### Additionnal classes, may be useful
@@ -319,26 +319,29 @@ end
 
 # Simple context with constant cost on each links
 # Warning: A* is not optimize for such a case
-class ConstantPathContext[N: Node, L: Link[N]]
-       super PathContext[N, L]
+class ConstantPathContext
+       super PathContext
 
        redef fun worst_cost do return 1
        redef fun cost(l) do return 1
        redef fun is_blocked(l) do return false
-       redef fun heuristic_cost(a, b) do return 1 # TODO
+       redef fun heuristic_cost(a, b) do return 0
+       redef fun worst_heuristic_cost do return 0
 end
 
-class WeightedPathContext[N: Node, L: WeigthedLink[N]]
-       super PathContext[N,L]
+class WeightedPathContext
+       super PathContext
+
+       redef type L: WeightedLink
 
-       init(graph: Graph[N,L])
+       init(graph: Graph[N, L])
        do
                super
 
                var worst_cost = 0
                for l in graph.links do
                        var cost = l.weight
-                       if cost > worst_cost then worst_cost = cost
+                       if cost >= worst_cost then worst_cost = cost + 1
                end
                self.worst_cost = worst_cost
        end
@@ -350,15 +353,16 @@ class WeightedPathContext[N: Node, L: WeigthedLink[N]]
                return l.weight
        end
        redef fun is_blocked(l) do return false
-       redef fun heuristic_cost(a, b) do return 10 # TODO
+       redef fun heuristic_cost(a, b) do return 0
+       redef fun worst_heuristic_cost do return 0
 end
 
-class WeigthedLink[N: Node]
-       super Link[N]
+class WeightedLink
+       super Link
 
        var weight: Int
 
-       init(graph: Graph[N,L], from, to: N, weight: Int)
+       init(graph: Graph[N, L], from, to: N, weight: Int)
        do
                super
 

diff --git a/tests/test_a_star.nit b/tests/test_a_star.nit
index d6ac1ee..4d04c09 100644 (file)
--- a/tests/test_a_star.nit
+++ b/tests/test_a_star.nit
@@ -13,7 +13,7 @@ class NamedNode
 
        var name: String
 
-       init(graph: Graph[N, Link[N]], name: String)
+       init(graph: Graph[N, Link], name: String)
        do
                self.name = name
                super
@@ -39,7 +39,7 @@ end
 # c - d - e
 fun case_simple
 do
-       var graph = new Graph[NamedNode,Link[NamedNode]]
+       var graph = new Graph[NamedNode, Link]
 
        var na = new NamedNode(graph, "a")
        var nb = new NamedNode(graph, "b")
@@ -47,13 +47,13 @@ do
        var nd = new NamedNode(graph, "d")
        var ne = new NamedNode(graph, "e")
 
-       var lab = new Link[NamedNode](graph, na, nb)
-       var lac = new Link[NamedNode](graph, na, nc)
-       var lbd = new Link[NamedNode](graph, nb, nd)
-       var lcd = new Link[NamedNode](graph, nc, nd)
-       var lde = new Link[NamedNode](graph, nd, ne)
+       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[NamedNode, Link[NamedNode]](graph)
+       var context = new ConstantPathContext(graph)
 
        var path = na.path_to(ne, 100, context)
        print_path(path)
@@ -65,7 +65,7 @@ end
 # c - d    e
 fun case_failed
 do
-       var graph = new Graph[NamedNode,Link[NamedNode]]
+       var graph = new Graph[NamedNode,Link]
 
        var na = new NamedNode(graph, "a")
        var nb = new NamedNode(graph, "b")
@@ -73,24 +73,26 @@ do
        var nd = new NamedNode(graph, "d")
        var ne = new NamedNode(graph, "e")
 
-       var lab = new Link[NamedNode](graph, na, nb)
-       var lac = new Link[NamedNode](graph, na, nc)
-       var lbd = new Link[NamedNode](graph, nb, nd)
-       var lcd = new Link[NamedNode](graph, nc, nd)
+       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[NamedNode, Link[NamedNode]](graph)
+       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
+#     a -2- b
+#    /     /
+#   3     1
+#  /     /
+# c -3- d -8- e
 fun case_weighted
 do
-       var graph = new Graph[NamedNode,WeigthedLink[NamedNode]]
+       var graph = new Graph[NamedNode,WeightedLink]
 
        var na = new NamedNode(graph, "a")
        var nb = new NamedNode(graph, "b")
@@ -98,25 +100,27 @@ do
        var nd = new NamedNode(graph, "d")
        var ne = new NamedNode(graph, "e")
 
-       var lab = new WeigthedLink[NamedNode](graph, na, nb, 2)
-       var lac = new WeigthedLink[NamedNode](graph, na, nc, 3)
-       var lbd = new WeigthedLink[NamedNode](graph, nb, nd, 1)
-       var lcd = new WeigthedLink[NamedNode](graph, nc, nd, 3)
-       var lde = new WeigthedLink[NamedNode](graph, nd, ne, 8)
+       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[NamedNode, WeigthedLink[NamedNode]](graph)
+       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
+#     a -2- b
+#    /     /
+#   3     1
+#  /     /
+# c -3- d -8- e
 fun case_weighted_too_long
 do
-       var graph = new Graph[NamedNode,WeigthedLink[NamedNode]]
+       var graph = new Graph[NamedNode,WeightedLink]
 
        var na = new NamedNode(graph, "a")
        var nb = new NamedNode(graph, "b")
@@ -124,13 +128,13 @@ do
        var nd = new NamedNode(graph, "d")
        var ne = new NamedNode(graph, "e")
 
-       var lab = new WeigthedLink[NamedNode](graph, na, nb, 2)
-       var lac = new WeigthedLink[NamedNode](graph, na, nc, 3)
-       var lbd = new WeigthedLink[NamedNode](graph, nb, nd, 1)
-       var lcd = new WeigthedLink[NamedNode](graph, nc, nd, 3)
-       var lde = new WeigthedLink[NamedNode](graph, nd, ne, 8)
+       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[NamedNode, WeigthedLink[NamedNode]](graph)
+       var context = new WeightedPathContext(graph)
 
        var path = na.path_to(ne, 5, context)
        print_path(path)