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

View of /sml/branches/SMLNJ/src/MLRISC/graphs/node-partition.sml

Parent Directory Parent Directory | Revision Log Revision Log


Revision 245 - (download) (annotate)
Sat Apr 17 18:47:12 1999 UTC (20 years, 4 months ago) by monnier
File size: 1340 byte(s)
version 110.16
signature NODE_PARTITION =
sig

   type 'n node_partition 

   val node_partition : ('n,'e,'g) Graph.graph -> 'n node_partition
   val !!    : 'n node_partition -> Graph.node_id -> 'n Graph.node
   val ==    : 'n node_partition -> Graph.node_id * Graph.node_id -> bool
   val union : 'n node_partition -> ('n Graph.node * 'n Graph.node ->
                                        'n Graph.node) ->
                                        Graph.node_id * Graph.node_id -> bool
   val union': 'n node_partition -> Graph.node_id * Graph.node_id -> bool

end

structure NodePartition :> NODE_PARTITION =
struct

   structure U = UnionFindRef
   structure M = HashMap
   structure G = Graph

   type 'n node_partition = (G.node_id,'n G.node U.uref) M.map

   fun node_partition (G.GRAPH G) =
   let val P   = M.create { order = Int.compare, 
                            hash = fn i => i, 
                            exn = G.NotFound 
                          } (#order G () * 2)
       val ins = M.insert P
       val _   = #forall_nodes G (fn n as (i,_) => ins(i,U.uref n))
   in  P
   end

   fun !! P x          = U.!! (M.lookup P x)
   fun == P (x,y)      = U.== (M.lookup P x, M.lookup P y)
   fun union P f (x,y) = U.union f (M.lookup P x, M.lookup P y)
   fun union' P (x,y)  = U.union' (M.lookup P x, M.lookup P y)
end

(*
 * $Log$
 *)

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