Topological sort/Extracted top item: Difference between revisions

Line 623:

=={{header|Phix}}==

Minor tweaks to the Topological_sort code: top_levels, propagate() and -1 now means "not required".

<lang Phix>~~sequence names~~

sequence names

enum RANK, NAME, DEP -- content of names

enum RANK, NAME, DEP -- content of names

-- rank is 1 for items to compile first, then 2, etc,

-- or 0 if cyclic dependencies prevent compilation.

-- - ~~and~~ -1 ~~now~~ ~~means~~ ~~"not~~ ~~required"~~.

-- or 0 if cyclic dependencies prevent compilation.

-- ~~name~~ is ~~handy,~~ and ~~makes~~ ~~the~~ ~~result~~ ~~order~~ ~~alphabetic!~~

-- - and -1 now means "not required".

-- name is handy, and makes the result order alphabetic!

-- dep is a list of dependencies (indexes to other names)

-- dep is a list of dependencies (indexes to other names)

function add_dependency(string name)

function add_dependency(string name)

integer k = find(name,vslice(names,NAME))

integer k = find(name,vslice(names,NAME))

if k=0 then

if k=0 then

names = append(names,{-1,name,{}})

names = append(names,{-1,name,{}})

k = length(names)

k = length(names)

end if

end if

return k

return k

end function

end function

procedure propagate(integer t)

procedure propagate(integer t)

if names[t][RANK]!=0 then

if names[t][RANK]!=0 then

names[t][RANK] = 0

names[t][RANK] = 0

for i=1 to length(names[t][DEP]) do

for i=1 to length(names[t][DEP]) do

propagate(names[t][DEP][i])

propagate(names[t][DEP][i])

end for

end for

end if

end if

end procedure

end procedure

procedure topsort(string input, sequence tops)

procedure topsort(string input, sequence tops)

names = {}

names = {}

sequence lines = split(input,'\n')

sequence lines = split(input,'\n')

for i=1 to length(lines) do

for i=1 to length(lines) do

sequence line = split(lines[i]),

sequence line = split(lines[i]),

dependencies = {}

dependencies = {}

integer k = add_dependency(line[1])

integer k = add_dependency(line[1])

for j=2 to length(line) do

for j=2 to length(line) do

integer l = add_dependency(line[j])

integer l = add_dependency(line[j])

if l!=k then -- ignore self-references

if l!=k then -- ignore self-references

dependencies &= l

dependencies &= l

end if

end if

end for

end for

names[k][DEP] = dependencies

names[k][DEP] = dependencies

end for

end for

if tops={} then

if tops={} then

-- show top levels

-- show top levels

for i=1 to length(names) do

for i=1 to length(names) do

for j=1 to length(names[i][DEP]) do

for j=1 to length(names[i][DEP]) do

integer ji = names[i][DEP][j]

integer ji = names[i][DEP][j]

names[ji][RANK] = 0

names[ji][RANK] = 0

end for

end for

end for

end for

sequence top_levels = {}

sequence top_levels = {}

for i=1 to length(names) do

for i=1 to length(names) do

if names[i][RANK]=-1 then

if names[i][RANK]=-1 then

top_levels = append(top_levels,names[i][NAME])

top_levels = append(top_levels,names[i][NAME])

end if

end if

end for

end for

printf(1,"top levels: %s\n",{join(top_levels)})

printf(1,"top levels: %s\n",{join(top_levels)})

return

return

end if

end if

-- Propagate required by setting RANK to 0:

-- Propagate required by setting RANK to 0:

for i=1 to length(tops) do

for i=1 to length(tops) do

integer t = add_dependency(tops[i])

integer t = add_dependency(tops[i])

propagate(t)

propagate(t)

end for

end for

-- Now populate names[RANK] iteratively:

-- Now populate names[RANK] iteratively:

bool more = true

bool more = true

integer rank = 0

integer rank = 0

while more do

while more do

more = false

more = false

rank += 1

rank += 1

for i=1 to length(names) do

for i=1 to length(names) do

if names[i][RANK]=0 then

if names[i][RANK]=0 then

bool ok = true

bool ok = true

for j=1 to length(names[i][DEP]) do

for j=1 to length(names[i][DEP]) do

integer ji = names[i][DEP][j],

integer ji = names[i][DEP][j],

nr = names[ji][RANK]

nr = names[ji][RANK]

if nr=0 or nr=rank then

if nr=0 or nr=rank then

-- not yet compiled, or same pass

ok = ~~false~~

-- not yet compiled, or same pass

ok = false

exit

~~end~~ if

exit

end if

end for

end for

if ok then

if ok then

names[i][RANK] = rank

names[i][RANK] = rank

more = true

more = true

end if

end if

end if

end if

end for

end for

end while

end while

names = sort(names) -- (ie by [RANK=1] then [NAME=2])

names = sort(names) -- (ie by [RANK=1] then [NAME=2])

integer prank = -1

integer prank = -1

for i=1 to length(names) do

for i=1 to length(names) do

rank = names[i][RANK]

rank = names[i][RANK]

if rank>-1 then

if rank>-1 then

puts(1,iff(rank=prank?" ":sprintf("\nlevel %d:",rank)))

puts(1,iff(rank=prank?" ":sprintf("\nlevel %d:",rank)))

puts(1,names[i][NAME])

puts(1,names[i][NAME])

prank = rank

prank = rank

end if

end if

end for

end for

puts(1,"\n")

puts(1,"\n")

end procedure

end procedure

constant input = """

constant input = """

top1 des1 ip1 ip2

~~top2~~ des1 ~~ip2~~ ~~ip3~~

top1 des1 ip1 ip2

top2 des1 ip2 ip3

ip1 extra1 ip1a ipcommon

~~ip2~~ ~~ip2a~~ ~~ip2b ip2c~~ ipcommon

ip1 extra1 ip1a ipcommon

ip2 ip2a ip2b ip2c ipcommon

des1 des1a des1b des1c

des1a des1a1 des1a2

des1c des1c1 extra1"""

des1c des1c1 extra1"""

topsort(input,{})

topsort(input,{})

topsort(input,{"top1"})

topsort(input,{"top1"})

topsort(input,{"top2"})

topsort(input,{"top2"})

topsort(input,{"top1","top2"})

topsort(input,{"top1","top2"})

topsort(input,{"ip1"})</lang>

topsort(input,{"ip1"})

Items on the same line can be compiled at the same time, and each line is alphabetic.