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
nitlanguage / nit.git / commitdiff