-import rapid_type_analysis # for type coloration
-
-abstract class AbstractColoring[E: Object]
-
- private var sorter: AbstractSorter[E]
- private var reverse_sorter: AbstractSorter[E]
-
- private var core: OrderedSet[E] = new OrderedSet[E]
- private var crown: OrderedSet[E] = new OrderedSet[E]
- private var border: OrderedSet[E] = new OrderedSet[E]
-
- private var coloration_result: Map[E, Int] = new HashMap[E, Int]
- private var conflicts_graph_cache: nullable HashMap[E, Set[E]]
-
- init(sorter: AbstractSorter[E], reverse_sorter: AbstractSorter[E]) do
- self.sorter = sorter
- self.reverse_sorter = reverse_sorter
- end
-
- fun colorize(elements: Collection[E]): Map[E, Int] do
- # tag each element as part of group core, crown or border
- for e in elements do
- tag_element(e)
- end
-
- #print "core: {core.join(", ")}"
- #print "border: {border.join(", ")}"
- #print "crown: {crown.join(", ")}"
-
- # sort by reverse linearization order
- reverse_sorter.sort(core)
- reverse_sorter.sort(border)
- reverse_sorter.sort(crown)
-
- #print "conflicts"
- #for k, v in conflicts_graph do
- # if k isa MType then
- # print "{k}: {v.join(", ")}"
- # end
- #end
-
- # colorize graph
- colorize_elements(core)
- colorize_elements(border)
- colorize_elements(crown)
-
- return coloration_result
- end
-
- # Colorize a collection of elements
- private fun colorize_elements(elements: Collection[E]) do
- var min_color = 0
-
- for element in elements do
- var color = min_color
- while not self.is_color_free(element, color) do
- color += 1
- end
- coloration_result[element] = color
- color = min_color
- end
- end
-
- # Check if a related element to the element already use the color
- private fun is_color_free(element: E, color: Int): Bool do
- if conflicts_graph.has_key(element) then
- for st in conflicts_graph[element] do
- if coloration_result.has_key(st) and coloration_result[st] == color then return false
- end
- end
- for st in self.super_elements(element) do
- if coloration_result.has_key(st) and coloration_result[st] == color then return false
- end
- return true
- end
-
- # Tag element as core, crown or border
- private fun tag_element(element: E) do
- # Check if sub elements are all in single inheritance
- var all_subelements_si = true
- for subelem in self.sub_elements(element) do
- if self.is_element_mi(subelem) then
- all_subelements_si = false
- break
- end
- end
-
- # Tag as core, crown or border
- if self.is_element_mi(element) then
- core.add_all(self.super_elements(element))
- core.add(element)
- if all_subelements_si then
- border.add(element)
- end
- else if not all_subelements_si then
- core.add_all(self.super_elements(element))
- core.add(element)
- else
- crown.add(element)
- end
- end
-
- # Conflicts graph of elements hierarchy (two types are in conflict if they have common subelements)
- private fun conflicts_graph: Map[E, Set[E]] do
- if self.conflicts_graph_cache == null then
- self.conflicts_graph_cache = new HashMap[E, HashSet[E]]
- for t in self.core do
- for i in self.linear_extension(t) do
- if t == i then continue
-
- var lin_i = self.linear_extension(i)
-
- for j in self.linear_extension(t) do
- if i == j or j == t then continue
- var lin_j = self.linear_extension(j)
-
- var d_ij = lin_i - lin_j
- var d_ji = lin_j - lin_i
-
- for ed1 in d_ij do
- if not conflicts_graph_cache.has_key(ed1) then conflicts_graph_cache[ed1] = new HashSet[E]
- # add ed1 x ed2 to conflicts graph
- for ed2 in d_ji do conflicts_graph_cache[ed1].add(ed2)
- end
- for ed1 in d_ij do
- if not conflicts_graph_cache.has_key(ed1) then conflicts_graph_cache[ed1] = new HashSet[E]
- # add ed1 x ed2 to conflicts graph
- for ed2 in d_ji do conflicts_graph_cache[ed1].add(ed2)
- end
- end
- end
+import poset
+
+# Build a conflict graph from a POSet
+class POSetConflictGraph[E: Object]
+
+ # 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]]
+
+ var poset: POSet[E]
+
+ init(poset: POSet[E]) do
+ self.poset = poset
+ extract_core
+ extract_border
+ extract_crown
+ compute_conflicts
+ 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)