# Colorize elements from a POSet
# Two elements from a POSet cannot have the same color if they share common subelements
#
# Example:
#
# ~~~raw
#       A
#     / | \
#    /  |  \
#   B   C   D
#   |  /|   |
#   | / |   |
#   |/  |   |
#   E   F   G
#   |
#   H
# ~~~
#
# Conflicts:
#
# * A: {B, C, D, E, F, G, H}
# * B: {A, C, E, H}
# * C: {A, E, H, F}
# * D: {A, G}
# * E: {A, B, C, H}
# * F: {A, C}
# * G: {A, D}
# * H: {A, B, C, E}
#
# Possible colors:
#
# * A: 0
# * B: 1
# * C: 2
# * D: 1
# * E: 3
# * F: 3
# * G: 2
# * H: 4
#
# 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]

	# Is the poset already colored?
	var is_colored = false

	# Resulting ids
	#
	# All ids are strictly positive (`>= 1`).
	#
	# REQUIRE: is_colored
	fun ids: Map[E, Int] do
		assert is_colored
		return ids_cache
	end
	private var ids_cache = new HashMap[E, Int]

	# Resulting colors
	# REQUIRE: is_colored
	fun colors: Map[E, Int] do
		assert is_colored
		return colors_cache
	end
	private var colors_cache = new HashMap[E, Int]

	# REQUIRE: is_colored
	fun poset: POSet[E] do
		assert is_colored
		return poset_cache
	end
	private var poset_cache: POSet[E] is noinit

	# REQUIRE: is_colored
	fun conflicts: Map[E, Set[E]] do
		assert is_colored
		return conflicts_cache
	end
	private var conflicts_cache: Map[E, Set[E]] is noinit

	private var graph: POSetConflictGraph[E] is noinit

	# Start coloring on given POSet
	fun colorize(poset: POSet[E]) do
		poset_cache = poset
		graph = new POSetConflictGraph[E](poset)
		allocate_ids
		compute_colors
		conflicts_cache = graph.conflicts
		is_colored = true
	end

	private fun allocate_ids do
		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 + 1
		end
	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 e in poset_cache.linearize(graph.core) do
			var color = min_color(e)
			var conflicts = graph.conflicts[e]
			while not is_color_free(color, conflicts) do
				color += 1
			end
			colors_cache[e] = color
		end
	end

	# Other elements inherit color fron their direct parents
	private fun colorize_set(set: Set[E]) do
		for e in poset_cache.linearize(set) do colors_cache[e] = min_color(e)
	end

	# Get the next minimal color from direct parents
	private fun min_color(e: E): Int do
		var max_color = -1
		for p in poset_cache[e].direct_greaters do
			if not colors_cache.has_key(p) then continue
			var color = colors_cache[p]
			if color > max_color then max_color = color
		end
		return max_color + 1
	end

	private fun is_color_free(color: Int, set: Collection[E]): Bool do
		for e in set do
			if colors_cache.has_key(e) and colors_cache[e] == color then return false
		end
		return true
	end

	# Used for debugging only
	fun pretty_print do
		print "ids:"
		for e, id in ids do print "  {e}: {id}"
		print "colors:"
		for e, c in colors do print "  {e}: {c}"
	end
end