Debian Codegraph @

gcc/testsuite/gm2/examples/map/pass/Find.mod

raw
1 (* Copyright (C) 2005, 2006, 2007, 2008, 2009, 2010
2 Free Software Foundation, Inc. *)
3 (* This file is part of GNU Modula-2.
4
5 GNU Modula-2 is free software; you can redistribute it and/or modify it under
6 the terms of the GNU General Public License as published by the Free
7 Software Foundation; either version 3, or (at your option) any later
8 version.
9
10 GNU Modula-2 is distributed in the hope that it will be useful, but WITHOUT ANY
11 WARRANTY; without even the implied warranty of MERCHANTABILITY or
12 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
13 for more details.
14
15 You should have received a copy of the GNU General Public License along
16 with gm2; see the file COPYING. If not, write to the Free Software
17 Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. *)
18 IMPLEMENTATION MODULE Find ;
19
20
21 FROM NumberIO IMPORT WriteCard ;
22 FROM StrIO IMPORT WriteString, WriteLn ;
23
24
25 CONST
26 MaxX = 10 ;
27 MaxY = 20 ;
28 Infinity = 10000 ;
29 Wall = Infinity ;
30 Door = Infinity-1 ;
31
32 VAR
33 MapDist: ARRAY [0..MaxX], [0..MaxY] OF CARDINAL ;
34 Xoffset,
35 Yoffset: CARDINAL ;
36
37 (*
38 FindOptimumRoute - finds the optimum route between two points,
39 x1, y1, x2, y2. The directions are returned
40 in a string, Commands. A boolean is returned
41 if any commands were entered.
42 *)
43
44 PROCEDURE FindOptimumRoute (x1, y1, x2, y2: INTEGER;
45 VAR Commands: ARRAY OF CHAR) : BOOLEAN ;
46 BEGIN
47 IF IsOptimumRoutePossible(x1, y1, x2, y2)
48 THEN
49 InitMapDist(x1, y1, x2, y2) ;
50 RETURN( CalculateOptimumRoute(x1, y1, x2, y2, Commands) )
51 ELSE
52 RETURN( FALSE )
53 END
54 END FindOptimumRoute ;
55
56
57 (*
58 IsOptimumRoutePossible - returns true if we can use the optimum
59 route procedure to work out how to get
60 to position, x2, y2 from x1, y1.
61 *)
62
63 PROCEDURE IsOptimumRoutePossible (x1, y1, x2, y2: INTEGER) : BOOLEAN ;
64 BEGIN
65 RETURN( (Abs(x1, x2) <= MaxX) AND (Abs(y1, y2) <= MaxY) )
66 END IsOptimumRoutePossible ;
67
68
69 (*
70 Min - returns the minimum of two cardinals.
71 *)
72
73 PROCEDURE Min (a, b: CARDINAL) : CARDINAL ;
74 BEGIN
75 IF a>b
76 THEN
77 RETURN( b )
78 ELSE
79 RETURN( a )
80 END
81 END Min ;
82
83
84 (*
85 Abs - returns the absolute difference between two INTEGERs.
86 *)
87
88 PROCEDURE Abs (a, b: INTEGER) : INTEGER ;
89 BEGIN
90 IF a>b
91 THEN
92 RETURN( a-b )
93 ELSE
94 RETURN( b-a )
95 END
96 END Abs ;
97
98
99 (*
100 CalculateOptimumRoute - calculates the optimum route between
101 two points and putting the route into
102 the string Commands. TRUE is returned
103 if any commands are placed into Commands.
104 *)
105
106 PROCEDURE CalculateOptimumRoute (x1, y1, x2, y2: INTEGER;
107 VAR Commands: ARRAY OF CHAR) : BOOLEAN ;
108 VAR
109 Distance: CARDINAL ;
110 BEGIN
111 Distance := ScanBackwards(x1, y1, x2, y2, 0) ;
112 RETURN( FALSE )
113 END CalculateOptimumRoute ;
114
115
116 (*
117 ScanBackwards - fills in the DistMap with the distance values
118 from x2, y2 to x1, y1.
119 *)
120
121 PROCEDURE ScanBackwards (x1, y1, x2, y2: INTEGER;
122 Distance: CARDINAL) : CARDINAL ;
123 VAR
124 ShortDist: CARDINAL ;
125 BEGIN
126 IF ((MapDist[x2, y2]=0) OR (Distance < MapDist[x2, y2]))
127 THEN
128 ShortDist := Infinity ;
129 MapDist[x2, y2] := Distance ;
130 ShortDist := MoveVector(x1, y1, x2, y2, 0, 1, Distance) ;
131 ShortDist := MoveVector(x1, y1, x2, y2, 1, 0, Distance) ;
132 ShortDist := MoveVector(x1, y1, x2, y2, 0, -1, Distance) ;
133 ShortDist := MoveVector(x1, y1, x2, y2, -1, 0, Distance) ;
134 RETURN( ShortDist )
135 ELSE
136 RETURN( MapDist[x2, y2]+Distance )
137 END
138 END ScanBackwards ;
139
140
141 (*
142 MoveVector - returns a CARDINAL value indicating the distance between
143 x2, y2 and x1, y1. It moves one step from x2, y2 along
144 vector xv, yv. If this vector hits upon a door then
145 we increment the vector - we dont increment the
146 distance as one goes through a door using 1 unit
147 of distance (actually covering 2 units of space).
148 *)
149
150 PROCEDURE MoveVector (x1, y1, x2, y2: INTEGER ;
151 xv, yv : INTEGER ;
152 Distance: CARDINAL) : CARDINAL ;
153 VAR
154 ShortDist: CARDINAL ;
155 BEGIN
156 IF IsDoor(x2+xv, y2+yv)
157 THEN
158 xv := 2*xv ;
159 yv := 2*yv
160 END ;
161 INC(Distance) ;
162 y2 := y2+yv ;
163 x2 := x2+xv ;
164 IF CheckSquare(x2, y2)
165 THEN
166 ShortDist := ScanBackwards(x1, y1, x2, y2, Distance)
167 ELSE
168 ShortDist := Infinity
169 END ;
170 RETURN( ShortDist )
171 END MoveVector ;
172
173
174 (*
175 CheckSquare - checks to see whether square, x, y, is free.
176 If this square is free then true is returned.
177 *)
178
179 PROCEDURE CheckSquare (x, y: INTEGER) : BOOLEAN ;
180 BEGIN
181 IF InRange(x, y) AND (MapDist[x, y] # Wall)
182 THEN
183 RETURN( TRUE )
184 END ;
185 RETURN( FALSE )
186 END CheckSquare ;
187
188
189 (*
190 IsDoor - returns true if point, x, y, is legal and is
191 on a door.
192 *)
193
194 PROCEDURE IsDoor (x, y: INTEGER) : BOOLEAN ;
195 BEGIN
196 RETURN( InRange(x, y) AND (MapDist[x, y] = Door) )
197 END IsDoor ;
198
199
200 (*
201 InRange - returns a boolean result determining whether, x, y,
202 is a legal index for the MapDist array.
203 *)
204
205 PROCEDURE InRange (x, y: INTEGER) : BOOLEAN ;
206 BEGIN
207 RETURN( (x <= MaxX) AND (y <= MaxY) AND
208 (x >= 0) AND (y >= 0) )
209 END InRange ;
210
211
212 (*
213 InitMapDist - initializes the MapDist matrix.
214 *)
215
216 PROCEDURE InitMapDist (x1, y1, x2, y2: INTEGER) ;
217 VAR
218 i, j: CARDINAL ;
219 BEGIN
220 FOR i := 0 TO MaxX DO
221 FOR j := 0 TO MaxY DO
222 MapDist[i, j] := 0 (* Empty *)
223 END
224 END ;
225 (*
226 Work out the Xoffset and Yoffset. We require that
227 our x1, y1 and x2, y2 are as central as possible.
228 *)
229 Xoffset := (MaxX DIV 2) - (Abs(x1, x2) DIV 2) ;
230 Yoffset := (MaxY DIV 2) - (Abs(y1, y2) DIV 2) ;
231 OverlayAdvMap
232 END InitMapDist ;
233
234
235 PROCEDURE OverlayAdvMap ;
236 VAR
237 r, w, d: CARDINAL ;
238 BEGIN
239 END OverlayAdvMap ;
240
241
242 (*
243 DisplayMap - display the contents of the DistMap.
244 *)
245
246 PROCEDURE DisplayMap ;
247 VAR
248 x, y: CARDINAL ;
249 BEGIN
250 WriteString('------------------------------------------------------') ;
251 WriteLn ;
252 FOR y := 0 TO MaxY DO
253 FOR x := 0 TO MaxX DO
254 IF MapDist[x, y] = Wall
255 THEN
256 WriteString('######')
257 ELSIF MapDist[x, y] = Door
258 THEN
259 WriteString(' ')
260 ELSE
261 WriteCard(MapDist[x, y], 3) ; WriteString(' ')
262 END
263 END ;
264 WriteLn
265 END
266 END DisplayMap ;
267
268
269 (*
270 TestDistance - tests to see whether the ScanBackwards procedure
271 works.
272 *)
273
274 PROCEDURE TestDistance ;
275 VAR
276 MyDist: CARDINAL ;
277 x, y : CARDINAL ;
278 BEGIN
279 InitMapDist(0, 0, MaxX, MaxY) ;
280 FOR y := 0 TO MaxY DO
281 MapDist[4, y] := Wall
282 END ;
283 MapDist[4, 3] := Door ;
284
285 FOR y := 0 TO MaxY DO
286 MapDist[7, y] := Wall
287 END ;
288 MapDist[7, 7] := Door ;
289
290 FOR x := 0 TO MaxX DO
291 MapDist[x, 2] := Wall
292 END ;
293 MapDist[2, 2] := Door ;
294 DisplayMap ;
295 WriteString('Creating distance map between points 0,0 and MaxX, MaxY') ;
296 WriteLn ;
297 MyDist := ScanBackwards(0, 0, MaxX, MaxY, 1) ;
298
299 WriteString('Distance is') ;
300
301 WriteCard(MapDist[0,0], 6) ;
302 WriteLn ;
303 DisplayMap
304 END TestDistance ;
305
306
307 BEGIN
308 TestDistance
309 END Find.