1 /***********************************************************************
5 The following is a notice of limited availability of the code and
6 Government license and disclaimer which must be included in the
7 prologue of the code and in all source listings of the code.
10 (c) 1977 University of Chicago
12 Permission is hereby granted to use, reproduce, prepare
13 derivative works, and to redistribute to others at no charge. If
14 you distribute a copy or copies of the Software, or you modify a
15 copy or copies of the Software or any portion of it, thus forming
16 a work based on the Software and make and/or distribute copies of
17 such work, you must meet the following conditions:
19 a) If you make a copy of the Software (modified or verbatim)
20 it must include the copyright notice and Government
21 license and disclaimer.
23 b) You must cause the modified Software to carry prominent
24 notices stating that you changed specified portions of
27 This software was authored by:
29 Argonne National Laboratory
30 J. Michalakes: (630) 252-6646; email: michalak@mcs.anl.gov
31 Mathematics and Computer Science Division
32 Argonne National Laboratory, Argonne, IL 60439
34 ARGONNE NATIONAL LABORATORY (ANL), WITH FACILITIES IN THE STATES
35 OF ILLINOIS AND IDAHO, IS OWNED BY THE UNITED STATES GOVERNMENT,
36 AND OPERATED BY THE UNIVERSITY OF CHICAGO UNDER PROVISION OF A
37 CONTRACT WITH THE DEPARTMENT OF ENERGY.
39 GOVERNMENT LICENSE AND DISCLAIMER
41 This computer code material was prepared, in part, as an account
42 of work sponsored by an agency of the United States Government.
43 The Government is granted for itself and others acting on its
44 behalf a paid-up, nonexclusive, irrevocable worldwide license in
45 this data to reproduce, prepare derivative works, distribute
46 copies to the public, perform publicly and display publicly, and
47 to permit others to do so. NEITHER THE UNITED STATES GOVERNMENT
48 NOR ANY AGENCY THEREOF, NOR THE UNIVERSITY OF CHICAGO, NOR ANY OF
49 THEIR EMPLOYEES, MAKES ANY WARRANTY, EXPRESS OR IMPLIED, OR
50 ASSUMES ANY LEGAL LIABILITY OR RESPONSIBILITY FOR THE ACCURACY,
51 COMPLETENESS, OR USEFULNESS OF ANY INFORMATION, APPARATUS,
52 PRODUCT, OR PROCESS DISCLOSED, OR REPRESENTS THAT ITS USE WOULD
53 NOT INFRINGE PRIVATELY OWNED RIGHTS.
55 ***************************************************************************/
62 #define INDEX_2(A,B,NB) ( (B) + (A)*(NB) )
64 mark_line( wrk
, m
, n
, x1
, y1
, x2
, y2
)
66 int m
, n
, x1
, y1
, x2
, y2
;
71 double SLOPE
, X
, Y
, DX
, DY
, dY
, X1
, X2
, Y1
, Y2
;
82 for ( i
= y1
; i
<= y2
; i
++ )
83 wrk
[ INDEX_2( x1
, i
, m
)] = 1 ;
85 for ( i
= y2
; i
<= y1
; i
++ )
86 wrk
[ INDEX_2( x1
, i
, m
)] = 1 ;
98 for ( X
= x1
+.5 ; X
< x2
+.5 ; X
= X
+.5 )
102 for ( i
= Y
; i
<= (k
=Y
+dY
) ; i
++ ) /* k business converts to int */
103 wrk
[ INDEX_2( j
, i
, m
)] = 1 ;
105 for ( i
= Y
; i
>= (k
=Y
+dY
) ; i
-- )
106 wrk
[ INDEX_2( j
, i
, m
)] = 1 ;
109 wrk
[ INDEX_2( x2
, y2
, m
)] = 1 ;
114 for ( X
= x2
+.5 ; X
< x1
+.5 ; X
= X
+.5 )
118 for ( i
= Y
; i
<= (k
=Y
+dY
) ; i
++ ) /* k business converts to int */
119 wrk
[ INDEX_2( j
, i
, m
)] = 1 ;
121 for ( i
= Y
; i
>= (k
=Y
+dY
) ; i
-- )
122 wrk
[ INDEX_2( j
, i
, m
)] = 1 ;
125 wrk
[ INDEX_2( x1
, y1
, m
)] = 1 ;
129 fill_region( wrk
, m
, n
)
134 for ( y
= 0 ; y
< m
; y
++ )
136 flood( 0, y
, 0, 2, wrk
, m
, n
) ;
137 flood( n
-1, y
, 0, 2, wrk
, m
, n
) ;
139 for ( x
= 0 ; x
< n
; x
++ )
141 flood( x
, 0, 0, 2, wrk
, m
, n
) ;
142 flood( x
, m
-1, 0, 2, wrk
, m
, n
) ;
145 for ( y
= 0 ; y
< n
; y
++ )
147 for ( x
= 0 ; x
< m
; x
++ )
149 if ( wrk
[ INDEX_2(x
,y
,m
) ] == 0 )
150 wrk
[ INDEX_2(x
,y
,m
) ] = 1 ;
151 else if ( wrk
[ INDEX_2(x
,y
,m
) ] == 2 )
152 wrk
[ INDEX_2(x
,y
,m
) ] = 0 ;
157 decomp_region_1( wrk
, m
, n
, py
, px
)
158 int wrk
[], m
, n
, py
, px
;
161 int x
, y
, ncells
, nprocs
, n_p
, n_py
, n_px
, i
, pid
, p
;
163 wk
= (int*)malloc(m
*n
*sizeof(int)) ;
167 for ( x
= 0 ; x
< m
*n
; x
++ )
170 if ( wrk
[x
] != 0 ) ncells
++ ;
173 n_p
= ncells
/ nprocs
;
175 /* divide over py in m dimension first */
179 for ( y
= 0 ; y
< m
; y
++ )
181 for ( x
= 0 ; x
< n
; x
++ )
183 if ( wrk
[INDEX_2(x
,y
,m
)] != 0 ) /* only do cells in partition */
186 if ( i
% n_py
== 0 ) pid
++ ;
187 wk
[INDEX_2(x
,y
,m
)] = pid
;
192 /* now divide over px in n dimension */
194 for ( p
= 0 ; p
< py
; p
++ )
198 for ( x
= 0 ; x
< n
; x
++ )
200 for ( y
= 0 ; y
< m
; y
++ )
202 if ( wk
[INDEX_2(x
,y
,m
)] == p
)
205 if ( i
% n_px
== 0 ) pid
++ ;
206 if ( pid
> px
-1 ) pid
= px
-1 ;
207 wk
[INDEX_2(x
,y
,m
)] = pid
*10000 + p
;
213 for ( x
= 0 ; x
< n
; x
++ )
214 for ( y
= 0 ; y
< m
; y
++ )
216 if (( p
= wk
[ INDEX_2( x
, y
, m
) ] ) != -1 )
220 wrk
[INDEX_2( x
, y
, m
)] = n_py
*px
+ n_px
;
224 wrk
[INDEX_2( x
, y
, m
)] = wk
[INDEX_2( x
, y
, m
)] ;
231 decomp_region_2( wrk
, m
, n
, py
, px
)
232 int wrk
[], m
, n
, py
, px
;
235 int x
, y
, ncells
, nprocs
, n_p
, n_py
, n_px
, i
, pid
, p
;
238 printf("decomp_region_2( wrk, %d, %d, %d, %d )\n",m
, n
, py
, px
) ;
239 wk
= (int*)malloc(m
*n
*sizeof(int)) ;
243 for ( x
= 0 ; x
< m
*n
; x
++ )
246 if ( wrk
[x
] != 0 ) ncells
++ ;
249 n_p
= ncells
/ nprocs
;
251 dc2( 0, nprocs
, wk
, wrk
, m
, n
, py
, px
, n_p
) ;
253 for ( x
= 0 ; x
< n
; x
++ )
254 for ( y
= 0 ; y
< m
; y
++ )
256 if (( p
= wk
[ INDEX_2( x
, y
, m
) ] ) != -1 )
260 wrk
[INDEX_2( x
, y
, m
)] = n_py
*px
+ n_px
;
264 wrk
[INDEX_2( x
, y
, m
)] = wk
[INDEX_2( x
, y
, m
)] ;
271 dc2( p
, nprocs
, wk
, wrk
, m
, n
, py
, px
, n_p
)
272 int p
, nprocs
, wk
[], wrk
[], m
, n
, py
, px
, n_p
;
274 int x
, y
, i
, v
, flg
, reach
, oldi
;
276 if ( p
>= nprocs
) return ;
278 printf("dc2(%d, %d, wk, wk, %d, %d, %d, %d, %d)\n",p
, nprocs
,m
, n
, py
, px
, n_p
);
281 for ( x
= 0 ; x
< n
; x
++ )
284 for ( y
= 0 ; y
< m
&& flg
; y
++ )
286 if ( wrk
[INDEX_2(x
,y
,m
)] != 0 )
288 if ( wk
[INDEX_2(x
,y
,m
)] == -1 ) goto breakout
;
289 if ( wk
[INDEX_2(x
,y
,m
)] != -1 ) flg
= 0 ;
294 for ( y
= 0 ; y
< m
; y
++ )
297 for ( x
= n
-1 ; x
>= 0 && flg
; x
-- )
299 if ( wrk
[INDEX_2(x
,y
,m
)] != 0 )
301 if ( wk
[INDEX_2(x
,y
,m
)] == -1 ) goto breakout
;
302 if ( wk
[INDEX_2(x
,y
,m
)] != -1 ) flg
= 0 ;
307 for ( x
= n
-1 ; x
>=0 ; x
-- )
310 for ( y
= m
-1 ; y
>=0 && flg
; y
-- )
312 if ( wrk
[INDEX_2(x
,y
,m
)] != 0 )
314 if ( wk
[INDEX_2(x
,y
,m
)] == -1 ) goto breakout
;
315 if ( wk
[INDEX_2(x
,y
,m
)] != -1 ) flg
= 0 ;
320 for ( y
= m
-1 ; y
>= 0 ; y
-- )
323 for ( x
= 0 ; x
< n
&& flg
; x
++ )
325 if ( wrk
[INDEX_2(x
,y
,m
)] != 0 )
327 if ( wk
[INDEX_2(x
,y
,m
)] == -1 ) goto breakout
;
328 if ( wk
[INDEX_2(x
,y
,m
)] != -1 ) flg
= 0 ;
333 for ( x
= 0 ; x
< n
; x
++ )
335 for ( y
= 0 ; y
< m
; y
++ )
337 v
= wk
[INDEX_2(x
,y
,m
)] ;
338 if ( v
== -1 && wrk
[INDEX_2(x
,y
,m
)] != 0 )
346 if ( x
== n
) return ; /* done, none found */
348 printf("dc2: p %d v %d x %d y %d wrk %d\n", p
,v
,x
,y
,wrk
[INDEX_2(x
,y
,m
)]) ;
352 /* start acreting outward until we're stopped dead or we get enough */
357 acrete( wk
, wrk
, p
, &i
, n_p
, reach
, x
, y
, m
, n
) ;
358 if ( i
== oldi
) break ;
362 print_region( wk
, m
, n
) ;
364 dc2( p
+1, nprocs
, wk
, wrk
, m
, n
, py
, px
, n_p
) ;
369 if( (X) >= 0 && (X) < n && (Y) >= 0 && (Y) < m && *i < n_p ) \
370 if (wk[INDEX_2((X),(Y),m)]==-1&&wrk[INDEX_2((X),(Y),m)]!=0) \
373 wk[INDEX_2((X),(Y),m)] = p ; \
378 acrete( wk
, wrk
, p
, i
, n_p
, reach
, x
, y
, m
, n
)
379 int wk
[], wrk
[], p
, *i
, n_p
;
383 if ( reach
== 0 ) return ;
384 if ( *i
>= n_p
) return ;
385 if ( !(x
>= 0 && x
< n
&& y
>= 0 && y
< m
) ) return ;
386 if ( wrk
[INDEX_2(x
,y
,m
)]==0 ) return ;
387 if ( wk
[INDEX_2(x
,y
,m
)]!=-1 && wk
[INDEX_2(x
,y
,m
)]!= p
) return ;
390 if ( p == 5 && reach == 1 )
391 printf("acrete(wk,wrk, p %d, *i %d, n_p %d, reach %d, x %d, y %d, m %d, n %d)\n",p, *i, n_p, reach, x, y, m, n ) ;
404 acrete( wk
, wrk
, p
, i
, n_p
, reach
-1, x
-1 , y
-1 , m
, n
) ;
405 acrete( wk
, wrk
, p
, i
, n_p
, reach
-1, x
-1 , y
, m
, n
) ;
406 acrete( wk
, wrk
, p
, i
, n_p
, reach
-1, x
-1 , y
+1 , m
, n
) ;
407 acrete( wk
, wrk
, p
, i
, n_p
, reach
-1, x
, y
+1 , m
, n
) ;
408 acrete( wk
, wrk
, p
, i
, n_p
, reach
-1, x
+1 , y
+1 , m
, n
) ;
409 acrete( wk
, wrk
, p
, i
, n_p
, reach
-1, x
+1 , y
, m
, n
) ;
410 acrete( wk
, wrk
, p
, i
, n_p
, reach
-1, x
+1 , y
-1 , m
, n
) ;
411 acrete( wk
, wrk
, p
, i
, n_p
, reach
-1, x
, y
-1 , m
, n
) ;
416 flood( x
, y
, v
, v2
, wrk
, m
, n
)
417 int x
, y
, v
, v2
, wrk
[], m
, n
;
419 if ( x
< 0 || x
>= n
|| y
< 0 || y
>= m
)
421 if ( wrk
[INDEX_2(x
,y
,m
)] == v
)
423 wrk
[INDEX_2(x
,y
,m
)] = v2
;
424 flood( x
+1, y
, v
, v2
, wrk
, m
, n
) ;
425 flood( x
-1, y
, v
, v2
, wrk
, m
, n
) ;
426 flood( x
, y
+1, v
, v2
, wrk
, m
, n
) ;
427 flood( x
, y
-1, v
, v2
, wrk
, m
, n
) ;
431 print_region( wrk
, m
, n
)
435 for ( i
= m
-1 ; i
>= 0 ; i
-- )
437 for ( j
= 0 ; j
< n
; j
++ )
439 if ( wrk
[ INDEX_2( j
, i
, m
) ] == -1 )
442 printf("%3d", wrk
[ INDEX_2( j
, i
, m
) ] ) ;
454 int i
, j
, m
, n
, x1
, y1
, x2
, y2
, py
, px
, opt
;
456 for ( i
= 0 ; i
< 100*100 ; i
++ ) wrk
[i
] = 0 ;
458 scanf("%d %d", &m
, &n
) ;
459 scanf("%d %d %d", &py
, &px
, &opt
) ;
460 scanf("%d %d", &x1
, &y1
) ;
461 while ( scanf("%d %d", &x2
, &y2
) != EOF
)
463 mark_line( wrk
, m
, n
, x1
, y1
, x2
, y2
) ;
468 /* print_region( wrk, m, n ) ; */
470 fill_region( wrk
, m
, n
) ;
472 /* print_region( wrk, m, n ) ; */
476 case 1 : decomp_region_1( wrk
, m
, n
, py
, px
) ;
477 print_region( wrk
, m
, n
) ;
479 case 2 : decomp_region_2( wrk
, m
, n
, py
, px
) ;