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 /MLRISC/trunk/graphs/node-partition.sml
ViewVC logotype

Annotation of /MLRISC/trunk/graphs/node-partition.sml

Parent Directory Parent Directory | Revision Log Revision Log


Revision 651 - (view) (download)
Original Path: sml/trunk/src/MLRISC/graphs/node-partition.sml

1 : monnier 411 (*
2 :     * This implenments node partitions (i.e. a union-find data structure)
3 :     * on nodes.
4 :     *
5 :     * -- Allen
6 :     *)
7 :    
8 : monnier 245 signature NODE_PARTITION =
9 :     sig
10 :    
11 :     type 'n node_partition
12 :    
13 :     val node_partition : ('n,'e,'g) Graph.graph -> 'n node_partition
14 :     val !! : 'n node_partition -> Graph.node_id -> 'n Graph.node
15 :     val == : 'n node_partition -> Graph.node_id * Graph.node_id -> bool
16 :     val union : 'n node_partition -> ('n Graph.node * 'n Graph.node ->
17 :     'n Graph.node) ->
18 : monnier 498 Graph.node_id * Graph.node_id -> bool
19 :     val union': 'n node_partition -> Graph.node_id * Graph.node_id -> bool
20 : monnier 245
21 :     end
22 :    
23 :     structure NodePartition :> NODE_PARTITION =
24 :     struct
25 :    
26 : monnier 429 structure U = URef
27 :     structure H = HashTable
28 : monnier 245 structure G = Graph
29 :    
30 : monnier 429 type 'n node_partition = (G.node_id,'n G.node U.uref) H.hash_table
31 : monnier 245
32 :     fun node_partition (G.GRAPH G) =
33 : monnier 429 let val P = H.mkTable (Word.fromInt,op =) (#order G () * 2,G.NotFound)
34 :     val ins = H.insert P
35 :     val _ = #forall_nodes G (fn n as (i,_) => ins(i,U.uRef n))
36 : monnier 245 in P
37 :     end
38 :    
39 : monnier 429 fun !! P x = U.!! (H.lookup P x)
40 :     fun == P (x,y) = U.equal (H.lookup P x, H.lookup P y)
41 :     fun union P f (x,y) = U.unify f (H.lookup P x, H.lookup P y)
42 :     fun union' P (x,y) = U.union (H.lookup P x, H.lookup P y)
43 : monnier 245 end
44 :    

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