- 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
- end
- end
- return conflicts_graph_cache.as(not null)
- end
-
- # cache for linear_extensions
- private var linear_extensions_cache: Map[E, OrderedSet[E]] = new HashMap[E, OrderedSet[E]]
-
- # Return a linear_extension of super_elements of the element
- private fun linear_extension(element: E): OrderedSet[E] do
- if not self.linear_extensions_cache.has_key(element) then
- var lin = new OrderedSet[E]
- lin.add(element)
- lin.add_all(self.super_elements(element))
- self.sorter.sort(lin)
- self.linear_extensions_cache[element] = lin
- end
- return self.linear_extensions_cache[element]
- end
-
- # Return all super elements (directs and indirects) of an element
- private fun super_elements(element: E): Collection[E] is abstract
-
- # Return all sub elements (directs and indirects) of an element
- private fun sub_elements(element: E): Collection[E] is abstract
-
- # Is the element in multiple inheritance ?
- private fun is_element_mi(element: E): Bool is abstract
-end
-
-# MClassType coloring
-class TypeColoring
- super AbstractColoring[MType]
-
- type T: MType
-
- private var mmodule: MModule
- private var mtypes: Set[T]
-
- # caches
- private var super_elements_cache: Map[T, Set[T]] = new HashMap[T, Set[T]]
- private var sub_elements_cache: Map[T, Set[T]] = new HashMap[T, Set[T]]
-
- init(mainmodule: MModule, mtypes: Set[T]) do
- super(new TypeSorter(mainmodule), new ReverseTypeSorter(mainmodule))
- self.mmodule = mainmodule
- self.mtypes = mtypes
- end
-
- # Build type tables
- fun build_type_tables(mtypes: Set[T], colors: Map[T, Int]): Map[T, Array[nullable T]] do
- var tables = new HashMap[T, Array[nullable T]]
-
- for mtype in mtypes do
- var table = new Array[nullable T]
- var supers = new HashSet[T]
- supers.add_all(self.super_elements(mtype))
- supers.add(mtype)
- for sup in supers do
- var color = colors[sup]
- if table.length <= color then
- for i in [table.length .. color[ do
- table[i] = null
- end
- end
- table[color] = sup
- end
- tables[mtype] = table
- end
- return tables
- end
-
- redef fun super_elements(element) do
- if not self.super_elements_cache.has_key(element) then
- var supers = new HashSet[T]
- for mtype in self.mtypes do
- if element == mtype then continue
- if element.is_subtype(self.mmodule, null, mtype) then
- supers.add(mtype)
- end
- end
- self.super_elements_cache[element] = supers
- end
- return self.super_elements_cache[element]
- end
-
- # Return all direct super elements of an element
- redef fun is_element_mi(element) do
- return self.super_elements(element).length > 1
- end
-
- # Return all sub elements (directs and indirects) of an element
- redef fun sub_elements(element) do
- if not self.sub_elements_cache.has_key(element) then
- var subs = new HashSet[T]
- for mtype in self.mtypes do
- if element == mtype then continue
- if mtype.is_subtype(self.mmodule, null, element) then
- subs.add(mtype)
- end
- end
- self.sub_elements_cache[element] = subs
- end
- return self.sub_elements_cache[element]
- end
-end