From 0d9db86f764cc8d6f89599f1c3b168638b16197e Mon Sep 17 00:00:00 2001
From: Jean Privat <jean@pryen.org>
Date: Mon, 23 Mar 2015 13:23:14 +0700
Subject: [PATCH] coloring: new class `POSetGroupColorer` to colorize bucklets
 of things

The difference with `POSetBucketsColorer` is that the new one is faster
but the constraint is that an element is introduced by a single holder.

Signed-off-by: Jean Privat <jean@pryen.org>
---
 src/compiler/coloring.nit |  160 +++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 160 insertions(+)

diff --git a/src/compiler/coloring.nit b/src/compiler/coloring.nit
index 5a57774..e2afc48 100644
--- a/src/compiler/coloring.nit
+++ b/src/compiler/coloring.nit
@@ -274,6 +274,166 @@ class POSetColorer[E: Object]
 	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
-- 
1.7.9.5