#
# Possible colors:
#
-# * A:0, B:1, C: 2, D: 1, E: 3, F:3, G:2, H:4
+# * A: 0
+# * B: 1
+# * C: 2
+# * D: 1
+# * E: 3
+# * F: 3
+# * G: 2
+# * H: 4
#
-# see: Ducournau, R. (2011).
+# SEE: Ducournau, R. (2011).
# Coloring, a versatile technique for implementing object-oriented languages.
# Software: Practice and Experience, 41(6), 627–659.
class POSetColorer[E: Object]
var is_colored = false
# Resulting ids
+ #
+ # All ids are strictly positive (`>= 1`).
+ #
# REQUIRE: is_colored
fun ids: Map[E, Int] do
assert is_colored
ids_cache.clear
var elements = new HashSet[E].from(poset_cache.to_a)
for e in poset_cache.linearize(elements) do
- ids_cache[e] = ids_cache.length
+ ids_cache[e] = ids_cache.length + 1
end
end
# No coloring order is garantied
#
# Example:
-# buckets[A] = {x1, x2}
-# buckets[B] = {x1, x3, x4}
-# buckets[C] = {x2, x3}
+#
+# * 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}
+#
+# * x1: {x2, x3, x4}
+# * x2: {x1, x3}
+# * x3: {x1, x2, x4}
+# * x4: {x1, x3}
+#
# Possible colors:
-# x1: 0, x2: 1, x3: 2, x4: 1
+#
+# * 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]]