Commit | Line | Data |
---|---|---|
7f918cf1 CE |
1 | (* Copyright (C) 1999-2006 Henry Cejtin, Matthew Fluet, Suresh |
2 | * Jagannathan, and Stephen Weeks. | |
3 | * Copyright (C) 1997-2000 NEC Research Institute. | |
4 | * | |
5 | * MLton is released under a BSD-style license. | |
6 | * See the file MLton-LICENSE for details. | |
7 | *) | |
8 | ||
9 | functor EquivalenceGraph (S: EQUIVALENCE_GRAPH_STRUCTS): EQUIVALENCE_GRAPH = | |
10 | struct | |
11 | ||
12 | open S | |
13 | ||
14 | structure Set = DisjointSet | |
15 | structure Plist = PropertyList | |
16 | ||
17 | structure Class = | |
18 | struct | |
19 | datatype t = T of {plist: Plist.t, | |
20 | size: int ref} Set.t | |
21 | ||
22 | local | |
23 | fun make sel (T s) = sel (Set.! s) | |
24 | in | |
25 | val plist = make #plist | |
26 | val size = make (! o #size) | |
27 | end | |
28 | ||
29 | fun setSize (T s, n) = #size (Set.! s) := n | |
30 | ||
31 | fun new (size: int): t = | |
32 | T (Set.singleton {plist = Plist.new (), | |
33 | size = ref size}) | |
34 | ||
35 | fun == (c as T s, T s') = | |
36 | if Set.equals (s, s') | |
37 | then () | |
38 | else | |
39 | let | |
40 | val {size = ref n, ...} = Set.! s | |
41 | val {size = ref n', ...} = Set.! s' | |
42 | in | |
43 | Set.union (s, s') | |
44 | ; setSize (c, n + n') | |
45 | end | |
46 | end | |
47 | ||
48 | datatype t = T of {classes: Class.t list ref, | |
49 | edges: (Class.t * Class.t) list ref} | |
50 | ||
51 | fun new () = T {classes = ref [], | |
52 | edges = ref []} | |
53 | ||
54 | fun newClass (T {classes, ...}, {size}) = | |
55 | let | |
56 | val c = Class.new size | |
57 | val _ = List.push (classes, c) | |
58 | in | |
59 | c | |
60 | end | |
61 | ||
62 | fun addEdge (T {edges, ...}, c, c') = | |
63 | List.push (edges, (c, c')) | |
64 | ||
65 | fun == (_, c, c') = Class.== (c, c') | |
66 | ||
67 | fun coarsen (T {classes, edges, ...}, {maxClassSize}) = | |
68 | let | |
69 | (* Combine classes with an edge between them where possible. *) | |
70 | val _ = | |
71 | List.foreach (!edges, fn (c, c') => | |
72 | if Class.size c + Class.size c' <= maxClassSize | |
73 | then Class.== (c, c') | |
74 | else ()) | |
75 | (* Get a list of all classes without duplicates. *) | |
76 | val {get, ...} = | |
77 | Property.get (Class.plist, Property.initFun (fn _ => ref false)) | |
78 | val classes = | |
79 | List.fold | |
80 | (!classes, [], fn (class, ac) => | |
81 | let | |
82 | val r = get class | |
83 | in | |
84 | if !r | |
85 | then ac | |
86 | else (r := true | |
87 | ; class :: ac) | |
88 | end) | |
89 | (* Sort classes in decreasing order of size. *) | |
90 | val classes = | |
91 | QuickSort.sortList (classes, fn (c, c') => | |
92 | Class.size c >= Class.size c') | |
93 | (* Combine classes where possible. *) | |
94 | fun loop (cs: Class.t list): unit = | |
95 | case cs of | |
96 | [] => () | |
97 | | c :: cs => | |
98 | loop | |
99 | (rev | |
100 | (List.fold | |
101 | (cs, [], fn (c', ac) => | |
102 | if Class.size c + Class.size c' <= maxClassSize | |
103 | then (Class.== (c, c') | |
104 | ; ac) | |
105 | else c' :: ac))) | |
106 | val _ = loop classes | |
107 | in | |
108 | () | |
109 | end | |
110 | ||
111 | end | |
112 | ||
113 | structure EquivalenceGraph = EquivalenceGraph () |