1 # This file is part of NIT ( http://www.nitlanguage.org ).
3 # Licensed under the Apache License, Version 2.0 (the "License");
4 # you may not use this file except in compliance with the License.
5 # You may obtain a copy of the License at
7 # http://www.apache.org/licenses/LICENSE-2.0
9 # Unless required by applicable law or agreed to in writing, software
10 # distributed under the License is distributed on an "AS IS" BASIS,
11 # WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 # See the License for the specific language governing permissions and
13 # limitations under the License.
19 # Build a conflict graph from a POSet
20 class POSetConflictGraph[E
: Object]
22 # Core is composed by:
23 # * elements that have mutiple direct parents
24 # * parents of elements that have multiple direct parents
26 var core
= new HashSet[E
]
28 # Border is composed by minimal elements of the core:
29 # * that have multiple direct parents
30 # * but whose subelements are all in single inheritance
32 var border
= new HashSet[E
]
34 # The crown is composed by the elements that are:
35 # * not part of the core nor the border
36 # * are in single inheritance
38 var crown
= new HashSet[E
]
40 # Conflict graph of the POSet
41 # Elements X and Y are in conflict if either:
42 # * X and Y are the same element
43 # * Y is a subelement of X
44 # * X and Y have common sub elements
46 var conflicts
= new HashMap[E
, Set[E
]]
50 init(poset
: POSet[E
]) do
58 # Compute the set of elements forming the core of the poset hierarchy.
59 private fun extract_core
do
62 if poset
[e
].direct_greaters
.length
> 1 then
63 core
.add_all
(poset
[e
].greaters
)
68 # Compute the set of elements composing the border of the core
69 # Elements belonging to the `border` are removed from the `core`
70 private fun extract_border
do
73 if not is_border
(e
) then continue
76 for e
in border
do core
.remove
(e
)
79 private fun is_border
(e
: E
): Bool do
80 for child
in poset
[e
].direct_smallers
do
81 if core
.has
(child
) then return false
86 # Compute the set of elements belonging to the crown of the inheritance hierarchy.
87 private fun extract_crown
do
90 if not core
.has
(e
) and not border
.has
(e
) then crown
.add
(e
)
94 # Check for conflict in the core.
95 # Start from border and tag every ancestors
96 private fun compute_conflicts
do
98 for e
in border
do add_conflicts
(poset
[e
].greaters
)
101 private fun add_conflict
(e
, o
: E
) do
102 if not conflicts
.has_key
(e
) then conflicts
[e
] = new HashSet[E
]
103 if not conflicts
.has_key
(o
) then conflicts
[o
] = new HashSet[E
]
108 private fun add_conflicts
(es
: Collection[E
]) do
110 for e2
in es
do add_conflict
(e1
, e2
)
114 # Used for debugging only
116 #print "core: {core.join(" ")} ({core.length})"
117 #print "border: {border.join(" ")} ({border.length})"
118 #print "crown: {crown.join(" ")} ({crown.length})"
120 for e
, c
in conflicts
do print
" {e}: {c.join(" ")}"
124 # Colorize elements from a POSet
125 # Two elements from a POSet cannot have the same color if they share common subelements
139 # A: {B, C, D, E, F, G, H}
148 # A:0, B:1, C: 2, D: 1, E: 3, F:3, G:2, H:4
151 # Ducournau, R. (2011).
152 # Coloring, a versatile technique for implementing object-oriented languages.
153 # Software: Practice and Experience, 41(6), 627–659.
154 class POSetColorer[E
: Object]
156 # Is the poset already colored?
157 var is_colored
= false
160 # REQUIRE: is_colored
161 fun ids
: Map[E
, Int] do
165 private var ids_cache
= new HashMap[E
, Int]
168 # REQUIRE: is_colored
169 fun colors
: Map[E
, Int] do
173 private var colors_cache
= new HashMap[E
, Int]
175 # REQUIRE: is_colored
176 fun poset
: POSet[E
] do
180 private var poset_cache
: POSet[E
] is noinit
182 # REQUIRE: is_colored
183 fun conflicts
: Map[E
, Set[E
]] do
185 return conflicts_cache
187 private var conflicts_cache
: Map[E
, Set[E
]] is noinit
189 private var graph
: POSetConflictGraph[E
] is noinit
191 # Start coloring on given POSet
192 fun colorize
(poset
: POSet[E
]) do
194 graph
= new POSetConflictGraph[E
](poset
)
197 conflicts_cache
= graph
.conflicts
201 private fun allocate_ids
do
203 var elements
= new HashSet[E
].from
(poset_cache
.to_a
)
204 for e
in poset_cache
.linearize
(elements
) do
205 ids_cache
[e
] = ids_cache
.length
209 # Colorize core, border and crown in that order
210 private fun compute_colors
do
213 colorize_set
(graph
.border
)
214 colorize_set
(graph
.crown
)
217 # Core elements cannot have the same color than:
218 # * one of their parents
219 # * one of their conflicting elements
220 private fun colorize_core
do
221 for e
in poset_cache
.linearize
(graph
.core
) do
222 var color
= min_color
(e
)
223 var conflicts
= graph
.conflicts
[e
]
224 while not is_color_free
(color
, conflicts
) do
227 colors_cache
[e
] = color
231 # Other elements inherit color fron their direct parents
232 private fun colorize_set
(set
: Set[E
]) do
233 for e
in poset_cache
.linearize
(set
) do colors_cache
[e
] = min_color
(e
)
236 # Get the next minimal color from direct parents
237 private fun min_color
(e
: E
): Int do
239 for p
in poset_cache
[e
].direct_greaters
do
240 if not colors_cache
.has_key
(p
) then continue
241 var color
= colors_cache
[p
]
242 if color
> max_color
then max_color
= color
247 private fun is_color_free
(color
: Int, set
: Collection[E
]): Bool do
249 if colors_cache
.has_key
(e
) and colors_cache
[e
] == color
then return false
254 # Used for debugging only
257 for e
, id
in ids
do print
" {e}: {id}"
259 for e
, c
in colors
do print
" {e}: {c}"
263 # Colorize a collection of buckets
264 # Two elements cannot have the same color if they both appear in the same bucket
265 # No coloring order is garantied
268 # buckets[A] = {x1, x2}
269 # buckets[B] = {x1, x3, x4}
270 # buckets[C] = {x2, x3}
277 # x1: 0, x2: 1, x3: 2, x4: 1
278 class BucketsColorer[H
: Object, E
: Object]
279 private var colors
= new HashMap[E
, Int]
280 private var conflicts
= new HashMap[E
, Set[E
]]
284 # Start bucket coloring
285 fun colorize
(buckets
: Map[H
, Set[E
]]): Map[E
, Int] do
286 compute_conflicts
(buckets
)
288 for holder
, hbuckets
in buckets
do
289 for bucket
in hbuckets
do
290 if colors
.has_key
(bucket
) then continue
291 var color
= min_color
292 while not is_color_free
(bucket
, color
) do
295 colors
[bucket
] = color
302 private fun is_color_free
(bucket
: E
, color
: Int): Bool do
303 if conflicts
.has_key
(bucket
) then
304 for other
in conflicts
[bucket
] do
305 if colors
.has_key
(other
) and colors
[other
] == color
then return false
311 private fun compute_conflicts
(buckets
: Map[H
, Set[E
]]) do
313 for holder
, hbuckets
in buckets
do
314 for bucket
in hbuckets
do
315 if not conflicts
.has_key
(bucket
) then conflicts
[bucket
] = new HashSet[E
]
316 for obucket
in hbuckets
do
317 if obucket
== bucket
then continue
318 if not conflicts
.has_key
(obucket
) then conflicts
[obucket
] = new HashSet[E
]
319 conflicts
[bucket
].add
(obucket
)
320 conflicts
[obucket
].add
(bucket
)
327 # Colorize a collection of buckets using a poset and a conflict graph
328 # Two elements cannot have the same color if they both appear in the same bucket
329 # The use of a POSet hierarchy optimize the coloring
330 # Buckets elements are colored using linearization order starting
331 class POSetBucketsColorer[H
: Object, E
: Object]
332 private var colors
= new HashMap[E
, Int]
333 private var poset
: POSet[H
]
334 private var conflicts
: Map[H
, Set[H
]]
336 init(poset
: POSet[H
], conflicts
: Map[H
, Set[H
]]) do
338 self.conflicts
= conflicts
341 # Colorize buckets using the POSet and conflict graph
342 fun colorize
(buckets
: Map[H
, Set[E
]]): Map[E
, Int] do
344 for h
in poset
.linearize
(buckets
.keys
) do
345 var color
= min_color
(poset
[h
].direct_greaters
, buckets
)
346 for bucket
in buckets
[h
] do
347 if colors
.has_key
(bucket
) then continue
348 while not is_color_free
(color
, h
, buckets
) do color
+= 1
349 colors
[bucket
] = color
356 # Get the next available color considering used colors by other buckets
357 private fun min_color
(others
: Collection[H
], buckets
: Map[H
, Set[E
]]): Int do
359 for holder
in others
do
360 var color
= max_color
(holder
, buckets
)
361 if color
> min
then min
= color
366 # Return the max color used by a class
367 private fun max_color
(holder
: H
, buckets
: Map[H
, Set[E
]]): Int do
369 for bucket
in buckets
[holder
] do
370 if not colors
.has_key
(bucket
) then continue
371 var color
= colors
[bucket
]
372 if color
> max
then max
= color
377 # Check if the color is free for this holder
378 private fun is_color_free
(color
: Int, holder
: H
, buckets
: Map[H
, Set[E
]]): Bool do
379 if not conflicts
.has_key
(holder
) then return true
380 for conflict
in conflicts
[holder
] do
381 for bucket
in buckets
[conflict
] do
382 if not colors
.has_key
(bucket
) then continue
383 if colors
[bucket
] == color
then return false