-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
+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)