# Build a conflict graph from a POSet
class POSetConflictGraph[E]

	# Core is composed by:
	#  * elements that have mutiple direct parents
	#  * parents of elements that have multiple direct parents
	# REQUIRE: is_colored
	var core = new HashSet[E]

	# Border is composed by minimal elements of the core:
	#  * that have multiple direct parents
	#  * but whose subelements are all in single inheritance
	# REQUIRE: is_colored
	var border = new HashSet[E]

	# The crown is composed by the elements that are:
	#  * not part of the core nor the border
	#  * are in single inheritance
	# REQUIRE: is_colored
	var crown = new HashSet[E]

	# Conflict graph of the POSet
	# Elements X and Y are in conflict if either:
	#  * X and Y are the same element
	#  * Y is a subelement of X
	#  * X and Y have common sub elements
	# REQUIRE: is_colored
	var conflicts = new HashMap[E, Set[E]]

	# The associated poset
	var poset: POSet[E]

	# The linearisation order to visit elements in the poset
	var order: Array[E] is noinit

	init do
		extract_core
		extract_border
		extract_crown
		compute_conflicts
		order = poset.linearize(poset)
	end

	# Compute the set of elements forming the core of the poset hierarchy.
	private fun extract_core do
		core.clear
		for e in poset do
			if poset[e].direct_greaters.length > 1 then
				core.add_all(poset[e].greaters)
			end
		end
	end

	# Compute the set of elements composing the border of the core
	# Elements belonging to the `border` are removed from the `core`
	private fun extract_border do
		border.clear
		for e in core do
			if not is_border(e) then continue
			border.add(e)
		end
		for e in border do core.remove(e)
	end

	private fun is_border(e: E): Bool do
		for child in poset[e].direct_smallers do
			if core.has(child) then return false
		end
		return true
	end

	# Compute the set of elements belonging to the crown of the inheritance hierarchy.
	private fun extract_crown do
		crown.clear
		for e in poset do
			if not core.has(e) and not border.has(e) then crown.add(e)
		end
	end

	# Check for conflict in the core.
	# Start from border and tag every ancestors
	private fun compute_conflicts do
		conflicts.clear
		for e in border do add_conflicts(poset[e].greaters)
	end

	private fun add_conflict(e, o: E) do
		if not conflicts.has_key(e) then conflicts[e] = new HashSet[E]
		if not conflicts.has_key(o) then conflicts[o] = new HashSet[E]
		conflicts[e].add(o)
		conflicts[o].add(e)
	end

	private fun add_conflicts(es: Collection[E]) do
		for e1 in es do
			for e2 in es do add_conflict(e1, e2)
		end
	end

	# Used for debugging only
	fun pretty_print do
		#print "core: {core.join(" ")} ({core.length})"
		#print "border: {border.join(" ")} ({border.length})"
		#print "crown: {crown.join(" ")} ({crown.length})"
		print "conflicts:"
		for e, c in conflicts do print "  {e or else "NULL"}: {c.join(" ")}"
	end
end