Harmonize spelling

[factor.git] / extra / path-finding / path-finding-tests.factor

diff --git a/extra/path-finding/path-finding-tests.factor b/extra/path-finding/path-finding-tests.factor
index 11a047cb89684cb0c2430a12d7246266213acc56..e5466d0326aa25c9c4fa055aed0894334b85783c 100644 (file)
--- a/extra/path-finding/path-finding-tests.factor
+++ b/extra/path-finding/path-finding-tests.factor
@@ -28,9 +28,9 @@ TUPLE: maze < astar ;
   6  X X X X   X   X e X
   7  X g   X           X
   8  X X X X X X X X X X"
-        "\n" split ] nth nth CHAR: X = not ;
+        split-lines ] nth nth CHAR: X = not ;
 
-M: maze neighbours
+M: maze neighbors
     drop
     first2
     { [ 1 + 2array ] [ 1 - 2array ] [ [ 1 + ] dip 2array ] [ [ 1 - ] dip 2array ] } 2cleave
@@ -41,14 +41,14 @@ M: maze heuristic
     drop v- [ abs ] [ + ] map-reduce ;
 
 M: maze cost
-    drop 2dup [ first ] bi@ = [ [ second ] bi@ > 1 5 ? ] [ 2drop 2 ] if ;
+    drop 2dup [ first ] same? [ [ second ] bi@ > 1 5 ? ] [ 2drop 2 ] if ;
 
 : test1 ( to -- path considered )
     { 1 1 } swap maze new [ find-path ] [ considered ] bi ;
 >>
 
 ! Existing path from s to f
-[
+{
     {
         { 1 1 }
         { 2 1 }
@@ -66,15 +66,15 @@ M: maze cost
         { 8 7 }
         { 8 6 }
     }
-] [
+} [
     { 8 6 } test1 drop
 ] unit-test
 
 ! Check that only the right positions have been considered in the s to f path
-[ 7 ] [ { 7 1 } test1 nip length ] unit-test
+{ 7 } [ { 7 1 } test1 nip length ] unit-test
 
 ! Non-existing path from s to g -- all positions must have been considered
-[ f 26 ] [ { 1 7 } test1 length ] unit-test
+{ f 26 } [ { 1 7 } test1 length ] unit-test
 
 ! Look for a path between A and C. The best path is A --> D --> C. C will be placed
 ! in the open set early because B will be examined first. This checks that the evaluation
@@ -99,7 +99,7 @@ M: maze cost
 
 MEMO: routes ( -- hash ) $[ { "ABD" "BC" "C" "DCE" "ECF" } [ unclip swap 2array ] map >hashtable ] ;
 
-: n ( pos -- neighbours )
+: n ( pos -- neighbors )
     routes at ;
 
 : c ( from to -- cost )
@@ -110,13 +110,40 @@ MEMO: routes ( -- hash ) $[ { "ABD" "BC" "C" "DCE" "ECF" } [ unclip swap 2array
 >>
 
 ! Check path from A to C -- all nodes but F must have been examined
-[ "ADC" "ABCDE" ] [ "AC" test2 [ >string ] dip ] unit-test
+{ "ADC" "ABCDE" } [ "AC" test2 [ >string ] dip ] unit-test
 
 ! No path from D to B -- all nodes reachable from D must have been examined
-[ f "CDEF" ] [ "DB" test2 ] unit-test
+{ f "CDEF" } [ "DB" test2 ] unit-test
 
 ! Find a path using BFS. There are no path from F to A, and the path from D to
 ! C does not include any other node.
 
-[ f ] [ "FA" first2 routes <bfs> find-path ] unit-test
-[ "DC" ] [ "DC" first2 routes <bfs> find-path >string ] unit-test
+{ f } [ "FA" first2 routes <bfs> find-path ] unit-test
+{ "DC" } [ "DC" first2 routes <bfs> find-path >string ] unit-test
+
+<<
+
+! Build the costs as expected by the dijkstra word.
+
+MEMO: costs ( -- costs )
+    routes keys [ dup dup n [ dup [ c ] dip swap 2array ] with { } map-as >hashtable 2array ] map >hashtable ;
+
+: test3 ( fromto -- path considered )
+    first2 costs <dijkstra> [ find-path ] [ considered natural-sort >string ] bi ;
+
+>>
+
+! Check path from A to C -- all nodes but F must have been examined
+{ "ADC" "ABCDE" } [ "AC" test3 [ >string ] dip ] unit-test
+
+! No path from D to B -- all nodes reachable from D must have been examined
+{ f "CDEF" } [ "DB" test3 ] unit-test
+
+{ { 1 3 } } [
+    1 3 H{
+        { 1 H{ { 2 0 } { 3 0 } } }
+        { 2 H{ { 3 0 } { 1 0 } { 4 0 } } }
+        { 3 H{ { 4 0 } } }
+        { 4 H{ } }
+    } <dijkstra> find-path
+] unit-test