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 /MLRISC/trunk/graphs/uniongraph.sml
 [smlnj] / MLRISC / trunk / graphs / uniongraph.sml # View of /MLRISC/trunk/graphs/uniongraph.sml

Thu Nov 2 16:11:29 2006 UTC (12 years, 10 months ago) by blume
File size: 3874 byte(s)
`moved MLRISC to toplevel`
```(*
*  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 = ListMergeSort

fun union_view f (G.GRAPH A, G.GRAPH B) =
let
fun merge_nodes ns =
Sort.uniqueSort (fn ((i,_),(j,_)) => Int.compare(i,j)) ns
fun merge_node_ids ns =
Sort.uniqueSort (fn (i,j) => Int.compare(i,j)) ns
fun merge_edges es =
Sort.uniqueSort (fn ((i,j,_),(m,n,_)) =>
if i < m then LESS
else if i = m then
if j < n then LESS
else if j = n then EQUAL
else GREATER
else GREATER) es
fun new_id ()  = Int.max(#capacity A (), #capacity B ())
fun add_node n = (#add_node A n; #add_node B n)
fun add_edge e = (#add_edge A e; #add_edge B e)
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

```

 root@smlnj-gforge.cs.uchicago.edu ViewVC Help Powered by ViewVC 1.0.0