Topological sort/Extracted top item: Difference between revisions
Content added Content deleted
m (added Category:Sorting) |
m (→{{header|REXX}}: added/changed comments and whitespace, split a DO group statement.) |
||
Line 1,020: | Line 1,020: | ||
<lang REXX>/*REXX program displays the compile order of jobs (indicating the dependencies). */ |
<lang REXX>/*REXX program displays the compile order of jobs (indicating the dependencies). */ |
||
parse arg job /*obtain optional argument from the CL.*/ |
parse arg job /*obtain optional argument from the CL.*/ |
||
jobL. |
jobL.=; stage.=; #.=0; @.=; JL= /*define some handy─dandy variables. */ |
||
tree. |
tree.=; tree.1= ' top1 des1 ip1 ip2 ' |
||
tree.2= ' top2 des1 ip2 ip3 ' |
tree.2= ' top2 des1 ip2 ip3 ' |
||
tree.3= ' ip1 extra1 ip1a ipcommon ' |
tree.3= ' ip1 extra1 ip1a ipcommon ' |
||
Line 1,030: | Line 1,030: | ||
$= |
$= |
||
do j=1 while tree.j\=='' /*build job tree.*/ |
do j=1 while tree.j\=='' /*build job tree.*/ |
||
parse var tree.j x deps; @.x=space(deps) |
parse var tree.j x deps; @.x= space(deps) /*extract jobs. */ |
||
if wordpos(x, $)==0 then $=$ x |
if wordpos(x, $)==0 then $= $ x /*Unique? Add it.*/ |
||
do k=1 for words(@.x); _=word(@.x, k) |
do k=1 for words(@.x); _= word(@.x, k) |
||
if wordpos(_, $)==0 then $=space($ _) |
if wordpos(_, $)==0 then $= space($ _) |
||
end /*k*/ |
end /*k*/ |
||
end /*j*/ |
end /*j*/ |
||
!.=; !!.= !. /*init. 2 arrays.*/ |
|||
!.=; !!.= |
|||
do j=1 for words($); x=word($, j); |
do j=1 for words($); x= word($, j); !.x.0= words(@.x) |
||
do k=1 for !.x.0; !.x.k=word(@.x, k); |
do k=1 for !.x.0; !.x.k= word(@.x, k); !!.x.k= !.x.k |
||
end /*k*/ /* [↑] build arrays of job departments*/ |
end /*k*/ /* [↑] build arrays of job departments*/ |
||
end /*j*/ |
end /*j*/ |
||
do words($) /*process all the jobs specified. */ |
do words($) /*process all the jobs specified. */ |
||
do j=1 for words($); x=word($, j); |
do j=1 for words($); x= word($, j); z= words(@.x); allN= 1; m= 0 |
||
if z==0 then do; #.x=1; iterate; end /*if no dependents, then skip this one.*/ |
if z==0 then do; #.x=1; iterate; end /*if no dependents, then skip this one.*/ |
||
do k=1 for z; |
do k=1 for z; y= !.x.k /*examine all the stage numbers. */ |
||
if datatype(y, 'W') then m=max(m, y) |
if datatype(y, 'W') then m= max(m, y) /*find the highest stage number. */ |
||
else do; allN= |
else do; allN= 0 /*at least one entry isn't numeric. */ |
||
if #.y\==0 then !.x.k=#.y |
if #.y\==0 then !.x.k= #.y |
||
end /* [↑] replace with a number. */ |
end /* [↑] replace with a number. */ |
||
end /*k*/ |
end /*k*/ |
||
if allN & m\==0 then #.x=max(#.x, m + 1) |
if allN & m\==0 then #.x= max(#.x, m + 1) /*replace with the stage number max. */ |
||
end /*j*/ |
end /*j*/ /* [↑] maybe set the stage number. */ |
||
end /*words($)*/ |
end /*words($)*/ |
||
if job='' then job=word(tree.1, 1) |
if job='' then job= word(tree.1, 1) /*Not specified? Use 1st job in tree.*/ |
||
jobL.1= |
jobL.1= job /*define the bottom level jobList. */ |
||
s= |
s= 1 /*define the stage level for jobList. */ |
||
do j=1; yyy=jobL.j |
do j=1; yyy= jobL.j |
||
do r=1 for words(yyy) /*verify that there are no duplicates. */ |
do r=1 for words(yyy) /*verify that there are no duplicates. */ |
||
do c=1 while c<words(yyy); z=word(yyy,c) |
do c=1 while c<words(yyy); z= word(yyy,c) |
||
p=wordpos(z, yyy, c + 1); if p\==0 then yyy=delword(yyy, p, 1) |
p= wordpos(z, yyy, c + 1); if p\==0 then yyy= delword(yyy, p, 1) |
||
end /*c*/ /* [↑] Duplicate? Then delete it. */ |
end /*c*/ /* [↑] Duplicate? Then delete it. */ |
||
end /*r*/ |
end /*r*/ |
||
jobL.j=yyy |
jobL.j= yyy |
||
if yyy='' then leave /*if null, then we're done with jobList*/ |
if yyy='' then leave /*if null, then we're done with jobList*/ |
||
z=words(yyy) |
z= words(yyy) /*number of jobs in the jobList. */ |
||
s=s+1 |
s= s+1 /*bump the stage number. */ |
||
do k=1 for z; _=word(yyy, k) |
do k=1 for z; _= word(yyy, k) /*obtain a stage number for the job. */ |
||
jobL.s=jobL.s @._ |
jobL.s= jobL.s @._ /*add a job to a stage. */ |
||
end /*k*/ |
end /*k*/ |
||
end /*j*/ |
end /*j*/ |
||
do k=1 for s; JL=JL jobL.k |
do k=1 for s; JL= JL jobL.k /*build a complete jobList (JL). */ |
||
end /*k*/ |
|||
do s=1 for words(JL) |
do s=1 for words(JL); _= word(JL, s) /*process each job in the jobList. */ |
||
level= #._ /*get the proper level for the job. */ |
|||
stage.level= stage.level _ /*assign a level to job stage number. */ |
stage.level= stage.level _ /*assign a level to job stage number. */ |
||
end /*s*/ /* [↑] construct various job stages. */ |
end /*s*/ /* [↑] construct various job stages. */ |