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

SCM Repository

[smlnj] Annotation of /sml/trunk/src/MLRISC/graphs/uniongraph.sml
ViewVC logotype

Annotation of /sml/trunk/src/MLRISC/graphs/uniongraph.sml

Parent Directory Parent Directory | Revision Log Revision Log


Revision 245 - (view) (download)
Original Path: sml/branches/SMLNJ/src/MLRISC/graphs/uniongraph.sml

1 : monnier 245 (*
2 :     * The union of two graphs
3 :     *)
4 :    
5 :     signature UNION_GRAPH_VIEW =
6 :     sig
7 :    
8 :     val union_view : ('g1 * 'g2 -> 'g3) ->
9 :     ('n,'e,'g1) Graph.graph * ('n,'e,'g2) Graph.graph ->
10 :     ('n,'e,'g3) Graph.graph
11 :    
12 :     end
13 :    
14 :     structure UnionGraphView : UNION_GRAPH_VIEW =
15 :     struct
16 :    
17 :     structure G = Graph
18 :     structure Sort = Sorting
19 :    
20 :     fun union_view f (G.GRAPH A, G.GRAPH B) =
21 :     let
22 :     fun merge_nodes ns =
23 :     Sort.sort_uniq (fn ((i,_),(j,_)) => Int.<(i,j))
24 :     (fn ((i,_),(j,_)) => i = j) ns
25 :     fun merge_node_ids ns =
26 :     Sort.sort_uniq (fn (i,j) => Int.<(i,j))
27 :     (fn (i,j) => i = j) ns
28 :     fun merge_edges es =
29 :     Sort.sort_uniq (fn ((i,j,_),(m,n,_)) => Int.<(i,m)
30 :     orelse i = m andalso j < n)
31 :     (fn ((i,j,_),(m,n,_)) => i = m andalso j = n) es
32 :     fun new_id () = Int.max(#capacity A (), #capacity B ())
33 :     fun add_node n = (#add_node A n; #add_node B n)
34 :     fun add_edge e = (#add_edge A e; #add_edge B e)
35 :     fun remove_node i = (#remove_node A i; #remove_node B i)
36 :     fun set_out_edges e = (#set_out_edges A e; #set_out_edges B e)
37 :     fun set_in_edges e = (#set_in_edges A e; #set_in_edges B e)
38 :     fun garbage_collect() = (#garbage_collect A (); #garbage_collect B ())
39 :     fun nodes() = merge_nodes (#nodes A() @ #nodes B())
40 :     fun edges() = merge_edges (#edges A() @ #edges B())
41 :     fun order() = length(nodes())
42 :     fun size() = length(edges())
43 :     fun capacity() = #capacity A() + #capacity B()
44 :     fun out_edges i = merge_edges(#out_edges A i @ #out_edges B i)
45 :     fun in_edges i = merge_edges(#in_edges A i @ #in_edges B i)
46 :     fun succ i = merge_node_ids(#succ A i @ #succ B i)
47 :     fun pred i = merge_node_ids(#pred A i @ #pred B i)
48 :     fun has_edge e = #has_edge A e orelse #has_edge B e
49 :     fun has_node n = #has_node A n orelse #has_node B n
50 :     fun node_info n = #node_info A n handle _ => #node_info B n
51 :     fun entries() = merge_node_ids(#entries A () @ #entries B ())
52 :     fun exits() = merge_node_ids(#exits A () @ #exits B ())
53 :     fun entry_edges i = merge_edges(#entry_edges A i @ #entry_edges B i)
54 :     fun exit_edges i = merge_edges(#exit_edges A i @ #exit_edges B i)
55 :     fun forall_nodes f = app f (nodes())
56 :     fun forall_edges f = app f (edges())
57 :     (*
58 :     fun fold_nodes f u = List.foldr f u (nodes())
59 :     fun fold_edges f u = List.foldr f u (edges())
60 :     *)
61 :     in
62 :     G.GRAPH
63 :     { name = #name A ^ "+" ^ #name B,
64 :     graph_info = f(#graph_info A, #graph_info B),
65 :     new_id = new_id,
66 :     add_node = add_node,
67 :     add_edge = add_edge,
68 :     remove_node = remove_node,
69 :     set_in_edges = set_in_edges,
70 :     set_out_edges = set_out_edges,
71 :     set_entries = G.unimplemented,
72 :     set_exits = G.unimplemented,
73 :     garbage_collect = garbage_collect,
74 :     nodes = nodes,
75 :     edges = edges,
76 :     order = order,
77 :     size = size,
78 :     capacity = capacity,
79 :     out_edges = out_edges,
80 :     in_edges = in_edges,
81 :     succ = pred,
82 :     pred = succ,
83 :     has_edge = has_edge,
84 :     has_node = has_node,
85 :     node_info = node_info,
86 :     entries = entries,
87 :     exits = exits,
88 :     entry_edges = entry_edges,
89 :     exit_edges = exit_edges,
90 :     forall_nodes = forall_nodes,
91 :     forall_edges = forall_edges
92 :     (*
93 :     fold_nodes = fold_nodes,
94 :     fold_edges = fold_edges
95 :     *)
96 :     }
97 :     end
98 :     end
99 :    
100 :     (*
101 :     * $Log$
102 :     *)

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