#
# Possible colors:
#
-# * A:0, B:1, C: 2, D: 1, E: 3, F:3, G:2, H:4
+# * A: 0
+# * B: 1
+# * C: 2
+# * D: 1
+# * E: 3
+# * F: 3
+# * G: 2
+# * H: 4
#
-# see: Ducournau, R. (2011).
+# SEE: Ducournau, R. (2011).
# Coloring, a versatile technique for implementing object-oriented languages.
# Software: Practice and Experience, 41(6), 627–659.
class POSetColorer[E: Object]
var is_colored = false
# Resulting ids
+ #
+ # All ids are strictly positive (`>= 1`).
+ #
# REQUIRE: is_colored
fun ids: Map[E, Int] do
assert is_colored
ids_cache.clear
var elements = new HashSet[E].from(poset_cache.to_a)
for e in poset_cache.linearize(elements) do
- ids_cache[e] = ids_cache.length
+ ids_cache[e] = ids_cache.length + 1
end
end
end
end
+# Colorize elements `E` introduced by holders `H` in a `POSet`.
+#
+# Two elements cannot have the same color if they are introduced or inherited by a same holder.
+class POSetGroupColorer[H: Object, E: Object]
+
+ # The associated conflict graph containing the poset.
+ #
+ # The conflict graph is used instead of the original poset so that the conflict graph can be reused
+ # in different coloration based on the same poset.
+ var graph: POSetConflictGraph[H]
+
+ # The elements to color.
+ #
+ # For each holder, the collection of introduced elements is given.
+ #
+ # A single element must not be introduced in more than one holder.
+ var buckets: Map[H, Collection[E]]
+
+ # The associated poset.
+ #
+ # alias for `graph.poset`
+ fun poset: POSet[H] do return graph.poset
+
+ # The resulting coloring
+ #
+ # Each element from buckets is associated to its own color
+ var colors: Map[E, Int] is lazy do
+ for h in graph.poset do
+ used_colors[h] = new HashSet[Int]
+ end
+ compute_colors
+ return colors_cache
+ end
+
+ # Resulting colors
+ private var colors_cache = new HashMap[E, Int]
+
+ # Set of known used colors
+ private var used_colors = new HashMap[H, HashSet[Int]]
+
+ # Build table layout of elements `E` for the holder `h`.
+ #
+ # `null` is used to fill places without elements (holes).
+ fun build_layout(h: H): Array[nullable E]
+ do
+ var table = new Array[nullable E]
+ for s in poset[h].greaters do
+ var bucket = buckets.get_or_null(s)
+ if bucket == null then continue
+ for e in bucket do
+ var color = colors[e]
+ if table.length <= color then
+ for i in [table.length .. color[ do
+ table[i] = null
+ end
+ else
+ assert table[color] == null else print "in {h}, for {color}: {table[color] or else ""} vs {e}"
+ end
+ table[color] = e
+ end
+ end
+ return table
+ end
+
+ # Colorize core, border and crown in that order
+ private fun compute_colors do
+ colors_cache.clear
+ colorize_core
+ colorize_set(graph.border)
+ colorize_set(graph.crown)
+ end
+
+ # Core elements cannot have the same color than:
+ # * one of their parents
+ # * one of their conflicting elements
+ private fun colorize_core do
+ for h in graph.order do
+ if not graph.core.has(h) then continue
+
+ var color = inherit_color(h)
+ var mincolor = color
+ var bucket = buckets.get_or_null(h)
+ if bucket == null then continue
+ var conflicts = graph.conflicts[h]
+ var parents = poset[h].greaters
+ for e in bucket do
+ color = next_free_color(color, parents)
+ color = next_free_color(color, conflicts)
+ colors_cache[e] = color
+ used_colors[h].add color
+ #print "{h}: color[{color}] <- {e}"
+ if mincolor == color then mincolor += 1
+ color += 1
+ end
+ min_colors[h] = mincolor
+ end
+ end
+
+ # Other elements inherit color from their direct parents
+ private fun colorize_set(set: Set[H]) do
+ for h in graph.order do
+ if not set.has(h) then continue
+
+ var color = inherit_color(h)
+ var mincolor = color
+ var bucket = buckets.get_or_null(h)
+ if bucket == null then continue
+ var parents = poset[h].greaters
+ for e in bucket do
+ color = next_free_color(color, parents)
+ colors_cache[e] = color
+ used_colors[h].add color
+ #print "{h}: color[{color}] <- {e} (set)"
+ if mincolor == color then mincolor += 1
+ color += 1
+ end
+ min_colors[h] = mincolor
+ end
+ end
+
+ # Get the first available free color.
+ private fun inherit_color(h: H): Int
+ do
+ var res = 0
+ for p in poset[h].direct_greaters do
+ var m = min_colors[p]
+ if m > res then res = m
+ end
+ min_colors[h] = res
+ return res
+ end
+
+ # The first available color for each holder.
+ #
+ # Is used by children to start their coloring.
+ #
+ # Is updated at the end of a coloring step.
+ private var min_colors = new HashMap[H, Int]
+
+ private fun next_free_color(color: Int, set: Collection[H]): Int do
+ loop
+ for h in set do
+ if used_colors[h].has(color) then
+ #print "\tin {h}, {color} is used"
+ color += 1
+ continue label
+ end
+ end
+ break
+ end label
+ return color
+ end
+
+ # Used for debugging only
+ fun pretty_print do
+ print "colors:"
+ for e, c in colors do print " {e}: {c}"
+ end
+end
+
# Colorize a collection of buckets
# Two elements cannot have the same color if they both appear in the same bucket
# No coloring order is garantied
#
# Example:
-# buckets[A] = {x1, x2}
-# buckets[B] = {x1, x3, x4}
-# buckets[C] = {x2, x3}
+#
+# * buckets[A] = {x1, x2}
+# * buckets[B] = {x1, x3, x4}
+# * buckets[C] = {x2, x3}
+#
# Conflicts:
-# x1: {x2, x3, x4}
-# x2: {x1, x3}
-# x3: {x1, x2, x4}
-# x4: {x1, x3}
+#
+# * x1: {x2, x3, x4}
+# * x2: {x1, x3}
+# * x3: {x1, x2, x4}
+# * x4: {x1, x3}
+#
# Possible colors:
-# x1: 0, x2: 1, x3: 2, x4: 1
+#
+# * x1: 0, x2: 1, x3: 2, x4: 1
class BucketsColorer[H: Object, E: Object]
private var colors = new HashMap[E, Int]
private var conflicts = new HashMap[E, Set[E]]
nitlanguage / nit.git / blobdiff