# 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}
#
# Conflicts:
#
# * x1: {x2, x3, x4}
# * x2: {x1, x3}
# * x3: {x1, x2, x4}
# * x4: {x1, x3}
#
# Possible colors:
#
# * 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]]

	# Start bucket coloring
	fun colorize(buckets: Map[H, Set[E]]): Map[E, Int] do
		compute_conflicts(buckets)
		var min_color = 0
		for holder, hbuckets in buckets do
			for bucket in hbuckets do
				if colors.has_key(bucket) then continue
				var color = min_color
				while not is_color_free(bucket, color) do
					color += 1
				end
				colors[bucket] = color
				color = min_color
			end
		end
		return colors
	end

	private fun is_color_free(bucket: E, color: Int): Bool do
		if conflicts.has_key(bucket) then
			for other in conflicts[bucket] do
				if colors.has_key(other) and colors[other] == color then return false
			end
		end
		return true
	end

	private fun compute_conflicts(buckets: Map[H, Set[E]]) do
		conflicts.clear
		for holder, hbuckets in buckets do
			for bucket in hbuckets do
				if not conflicts.has_key(bucket) then conflicts[bucket] = new HashSet[E]
				for obucket in hbuckets do
					if obucket == bucket then continue
					if not conflicts.has_key(obucket) then conflicts[obucket] = new HashSet[E]
					conflicts[bucket].add(obucket)
					conflicts[obucket].add(bucket)
				end
			end
		end
	end
end