my coalescer
Henry Cejtin
henry@research.nj.nec.com
Mon, 10 May 1999 17:37:12 -0400
The only changes I did (which were all in equivalence-graph.fun) were:
I deleted the unused version of Class and the t, new, newClass, addEdge, ==
and greedy defined first.
I replaced the old definition of greedy with the following (grotesque hack)
code:
(*
* Given an edge, return how desirable it is to merge the endpoints
* of the edge. The result is an int option because we return
* NONE if they are not mergable.
* Note, it looks at the details inside Class, but the whole thing
* is just a hack.
*)
fun goodness (Class.T lhs: Class.t, Class.T rhs: Class.t): int option =
if Set.equals (lhs, rhs)
then NONE
else let val {size = ref lsize, ...} = Set.value lhs
val {size = ref rsize, ...} = Set.value rhs
in SOME (~ (lsize + rsize))
end
fun findBest (edges: (Class.t * Class.t) list)
: (Class.t * Class.t) option =
let fun folder (e: Class.t * Class.t,
ac: (int * (Class.t * Class.t)) option) =
case goodness e of
NONE => ac
| SOME g =>
case ac of
NONE => SOME (g, e)
| SOME (g', _) =>
if g > g'
then SOME (g, e)
else ac
in case List.fold (edges, NONE, folder) of
NONE => NONE
| SOME (goodness, e) => (
print ("\nHCC:\tgoodness " ^
Int.toString goodness ^
"\n");
SOME e
)
end
fun greedy {graph = T {edges, ...}, maxClassSize} =
let fun loop () =
case findBest (! edges) of
NONE => ()
| SOME (lhs, rhs) =>
if Class.size lhs + Class.size rhs <= maxClassSize
then (
Class.== (lhs, rhs);
loop ()
)
else ()
in loop ()
end