Topological sort: Difference between revisions
m
→{{header|Wren}}: Changed to Wren S/H
m (→{{header|ATS}}) |
m (→{{header|Wren}}: Changed to Wren S/H) |
||
| (6 intermediate revisions by 4 users not shown) | |||
Line 512:
staload UN = "prelude/SATS/unsafe.sats"
(* Macros for list construction. *)
#define NIL list_nil ()
#define :: list_cons
(*------------------------------------------------------------------*)
(* A shorthand for list reversal. This could also have been written as
a macro. *)
fn {a : t@ype}
rev {n : int}
(lst : list (INV(a), n))
:<!wrt> list (a, n) =
(* The list_reverse template function returns a linear list. Convert
that result to a "regular" list. *)
list_vt2t (list_reverse<a> lst)
(*------------------------------------------------------------------*)
(* Some shorthands for string operations. These are written as
macros. *)
macdef substr (s, i, n) =
(* string_make_substring returns a linear strnptr, but we want a
"regular" string. *)
macdef copystr (s) =
(* string0 copy returns a linear strptr, but we want a "regular"
strptr2string (string0_copy (,(s)))
(*------------------------------------------------------------------*)
Line 523 ⟶ 550:
typedef _marksvec_t (n : int) = arrayref (_mark_t, n)
(* Some type casts that seem not to be implemented in the
prelude. *)
implement g1int2uint<intknd, uint8knd> i = $UN.cast i
implement g1uint2int<uint8knd, intknd> i = $UN.cast i
Line 656 ⟶ 685:
in
if i = n then
@(
else if is_end_of_list text[i] then
@(
else
let
val j = skip_ident (text, n, i)
val () = $effmask_exn assertloc (i < j)
val nodename = substr (text, i, j - i)
▲ (string_make_substring (text, i, j - i))
in
loop (nodename :: row, j)
Line 694 ⟶ 721:
in
if i = n then
@(
else if is_end_of_list text[i] then
@(
else
let
Line 729 ⟶ 756:
c := $extfcall (int, "getchar")
end;
end
Line 751 ⟶ 778:
typedef nodenames (n : int) = list (String1, n)
(* A more efficient representation for nodes: integers in 0..n-1. *)
typedef nodenum (n : int) = [num : nat | num <= n - 1] size_t num
(* A collection of directed edges.
represented by the array index, to each of the nodenums listed in
the corresponding array entry. *)
typedef edges (n : int) = arrayref (List0 (nodenum n), n)
Line 820 ⟶ 849:
in
collect (desc, names, n);
@(
end
Line 1,112 ⟶ 1,141:
nodenames_array[i]
macdef map (lst) =
list_vt2t (list_map<nodenum n><String1> ,(lst))
in
case+ topological_sort topo of
| Topo_SUCCESS valid_order => Topo_SUCCESS (map valid_order)
| Topo_CYCLE
end
Line 1,134 ⟶ 1,163:
let
val last = list_last cycle
val cycl =
in
println! ("COMPILATION CYCLE: ", cycl : List0 string)
Line 3,583 ⟶ 3,612:
=={{header|J}}==
(see [[Talk:Topological_sort#J_implementation|talk page]] for some details about what happens here.)
<syntaxhighlight lang="j">dependencySort=: monad define
Line 5,430 ⟶ 5,461:
if not TryGetValue(s, Result) then
Result := nil;
end;▼
▲ t: string;
end;▼
end;
function TDigraph.TryToposort(out aOutSeq: TStringArray): Boolean;
var
Parents: TDictionary<string, string>;// stores the traversal tree as pairs
begin //
▲ procedure ExtractCycle(const BackPoint, Prev: string);
with TList<string>.Create do begin
repeat▼
▲ aOutSeq[0] := Prev; // starting from Prev until BackPoint is encountered
until Prev = BackPoint;
▲ repeat
▲ aOutSeq[I] := Parents[aOutSeq[I-1]];
▲ Inc(I);
▲ end;
▲ Reverse(aOutSeq); //this is required since we moved backwards through the tree
var
Visited, // set of already visited nodes
Line 5,481 ⟶ 5,495:
end else
if not Closed.Contains(Next) then begin//back edge found(i.e. cycle)
ExtractCycle(Next, aNode);
exit(False);
end;
Line 6,923 ⟶ 6,937:
composer depRecord
(<WS>? def node: <~WS>; <WS>? <dep>* <WS>? $node -> ..|@collectDeps.v: {node: $};)
rule dep: (<~WS> -> ..|@collectDeps.e: {from: node´$node, to: node´$}; <WS>?)
end depRecord
$(3..last)... -> !depRecord
Line 7,723 ⟶ 7,737:
=={{header|Wren}}==
{{trans|Kotlin}}
<syntaxhighlight lang="
construct new(s, edges) {
_vertices = s.split(", ")
| |||