Home My Page Projects Code Snippets Project Openings SML/NJ
 Summary Activity Forums Tracker Lists Tasks Docs Surveys News SCM Files

SCM Repository

[smlnj] View of /sml/branches/SMLNJ/src/MLRISC/graphs/uniongraph.sml
 [smlnj] / sml / branches / SMLNJ / src / MLRISC / graphs / uniongraph.sml

View of /sml/branches/SMLNJ/src/MLRISC/graphs/uniongraph.sml

Fri Sep 3 00:25:03 1999 UTC (19 years, 11 months ago) by monnier
File size: 3794 byte(s)
```version 110.19
```
```(*
*  The union of two graphs.
*
*  -- Allen
*)

signature UNION_GRAPH_VIEW =
sig

val union_view : ('g1 * 'g2 -> 'g3) ->
('n,'e,'g1) Graph.graph * ('n,'e,'g2) Graph.graph ->
('n,'e,'g3) Graph.graph

end

structure UnionGraphView : UNION_GRAPH_VIEW =
struct

structure G = Graph
structure Sort = Sorting

fun union_view f (G.GRAPH A, G.GRAPH B) =
let
fun merge_nodes ns =
Sort.sort_uniq (fn ((i,_),(j,_)) => Int.<(i,j))
(fn ((i,_),(j,_)) => i = j) ns
fun merge_node_ids ns =
Sort.sort_uniq (fn (i,j) => Int.<(i,j))
(fn (i,j) => i = j) ns
fun merge_edges es =
Sort.sort_uniq (fn ((i,j,_),(m,n,_)) => Int.<(i,m)
orelse i = m andalso j < n)
(fn ((i,j,_),(m,n,_)) => i = m andalso j = n) es
fun new_id ()  = Int.max(#capacity A (), #capacity B ())
fun remove_node i = (#remove_node A i; #remove_node B i)
fun set_out_edges e = (#set_out_edges A e; #set_out_edges B e)
fun set_in_edges e = (#set_in_edges A e; #set_in_edges B e)
fun garbage_collect() = (#garbage_collect A (); #garbage_collect B ())
fun nodes() = merge_nodes (#nodes A() @ #nodes B())
fun edges() = merge_edges (#edges A() @ #edges B())
fun order() = length(nodes())
fun size()  = length(edges())
fun capacity() = #capacity A() + #capacity B()
fun out_edges i = merge_edges(#out_edges A i @ #out_edges B i)
fun in_edges i = merge_edges(#in_edges A i @ #in_edges B i)
fun succ i = merge_node_ids(#succ A i @ #succ B i)
fun pred i = merge_node_ids(#pred A i @ #pred B i)
fun has_edge e = #has_edge A e orelse #has_edge B e
fun has_node n = #has_node A n orelse #has_node B n
fun node_info n = #node_info A n handle _ => #node_info B n
fun entries() = merge_node_ids(#entries A () @ #entries B ())
fun exits() = merge_node_ids(#exits A () @ #exits B ())
fun entry_edges i = merge_edges(#entry_edges A i @ #entry_edges B i)
fun exit_edges i = merge_edges(#exit_edges A i @ #exit_edges B i)
fun forall_nodes f = app f (nodes())
fun forall_edges f = app f (edges())
(*
fun fold_nodes f u = List.foldr f u (nodes())
fun fold_edges f u = List.foldr f u (edges())
*)
in
G.GRAPH
{ name            = #name A ^ "+" ^ #name B,
graph_info      = f(#graph_info A, #graph_info B),
new_id          = new_id,
remove_node     = remove_node,
set_in_edges    = set_in_edges,
set_out_edges   = set_out_edges,
set_entries     = G.unimplemented,
set_exits       = G.unimplemented,
garbage_collect = garbage_collect,
nodes           = nodes,
edges           = edges,
order           = order,
size            = size,
capacity        = capacity,
out_edges       = out_edges,
in_edges        = in_edges,
succ            = pred,
pred            = succ,
has_edge        = has_edge,
has_node        = has_node,
node_info       = node_info,
entries         = entries,
exits           = exits,
entry_edges     = entry_edges,
exit_edges      = exit_edges,
forall_nodes    = forall_nodes,
forall_edges    = forall_edges
(*
fold_nodes      = fold_nodes,
fold_edges      = fold_edges
*)
}
end
end

```