# Pre order sets and partial order set (ie hierarchies)
module poset
-# Preorder set graph.
-# This class modelize an incremental preorder graph where new node and edges can be added (but no removal)
-# Preorder graph has two caracteristics:
+import serialization::serialization_core
+
+# Pre-order set graph.
+# This class models an incremental pre-order graph where new nodes and edges can be added (but not removed).
+# Pre-order graph has two characteristics:
# * reflexivity: an element is in relation with itself (ie `self.has(e) implies self.has_edge(e,e)`)
# * transitivity: `(self.has_edge(e,f) and self.has_edge(f,g)) implies self.has_edge(e,g)`
-class POSet[E: Object]
+#
+# Nodes and edges are added to the POSet.
+#
+# ~~~
+# var pos = new POSet[String]
+# pos.add_edge("A", "B") # add A->B
+# pos.add_edge("B", "C") # add B->C
+# pos.add_node("D") # add unconnected node "D"
+#
+# # A -> B -> C D
+#
+# assert pos.has_edge("A", "B") == true # direct
+# ~~~
+#
+# Since a poset is transitive, direct and indirect edges are considered by default.
+# Direct edges (transitive-reduction) can also be considered independently.
+#
+# ~~~
+# assert pos.has_edge("A", "C") == true # indirect
+# assert pos.has_edge("A", "D") == false # no edge
+# assert pos.has_edge("B", "A") == false # edges are directed
+#
+# assert pos.has_direct_edge("A", "B") == true # direct
+# assert pos.has_direct_edge("A", "C") == false # indirect
+# ~~~
+#
+# POSet are dynamic.
+# It means that the transitivity is updated while new nodes and edges are added.
+# The transitive-reduction (*direct edges*)) is also updated,
+# so adding new edges can make some direct edge to disappear.
+#
+# ~~~
+# pos.add_edge("A","D")
+# pos.add_edge("D","B")
+# pos.add_edge("A","E")
+# pos.add_edge("E","C")
+#
+# # A -> D -> B
+# # | |
+# # v v
+# # E ------> C
+#
+# assert pos.has_edge("D", "C") == true # new indirect edge
+# assert pos.has_edge("A", "B") == true # still an edge
+# assert pos.has_direct_edge("A", "B") == false # but no-more a direct one
+# ~~~
+#
+# Thanks to the `[]` method, elements can be considered relatively to the poset.
+# SEE `POSetElement`
+class POSet[E]
super Collection[E]
- super AbstractSorter[E]
+ super Comparator
+ super Cloneable
+ super Serializable
+
+ redef type COMPARED: E is fixed
redef fun iterator do return elements.keys.iterator
# All the nodes
- private var elements: HashMap[E, POSetElement[E]] = new HashMap[E, POSetElement[E]]
+ private var elements = new HashMap[E, POSetElement[E]]
redef fun has(e) do return self.elements.keys.has(e)
end
# Return a view of `e` in the poset.
- # This allows to asks manipulate elements in thier relation with others elements.
+ # This allows to view the elements in their relation with others elements.
#
- # var poset: POSet[Something] # ...
- # for x in poset do
- # for y in poset[x].direct_greaters do
- # print "{x} -> {y}"
- # end
- # end
+ # var poset = new POSet[String]
+ # poset.add_chain(["A", "B", "D"])
+ # poset.add_chain(["A", "C", "D"])
+ # var a = poset["A"]
+ # assert a.direct_greaters.has_exactly(["B", "C"])
+ # assert a.greaters.has_exactly(["A", "B", "C", "D"])
+ # assert a.direct_smallers.is_empty
#
# REQUIRE: has(e)
fun [](e: E): POSetElement[E]
# Add an edge from `f` to `t`.
# Because a POSet is transitive, all transitive edges are also added to the graph.
# If the edge already exists, the this function does nothing.
+ #
+ # ~~~
+ # var pos = new POSet[String]
+ # pos.add_edge("A", "B") # add A->B
+ # assert pos.has_edge("A", "C") == false
+ # pos.add_edge("B", "C") # add B->C
+ # assert pos.has_edge("A", "C") == true
+ # ~~~
+ #
# If a reverse edge (from `t` to `f`) already exists, a loop is created.
#
- # FIXME: Do somethind clever to manage loops.
+ # FIXME: Do something clever to manage loops.
fun add_edge(f, t: E)
do
var fe = add_node(f)
# Update the transitive reduction
if te.tos.has(f) then return # Skip the reduction if there is a loop
- for x in te.dfroms.to_a do
+ # Remove transitive edges.
+ # Because the sets of direct is iterated, the list of edges to remove
+ # is stored and is applied after the iteration.
+ # The usual case is that no direct edges need to be removed,
+ # so start with a `null` list of edges.
+ var to_remove: nullable Array[E] = null
+ for x in te.dfroms do
var xe = self.elements[x]
if xe.tos.has(f) then
- te.dfroms.remove(x)
+ if to_remove == null then to_remove = new Array[E]
+ to_remove.add x
xe.dtos.remove(t)
end
end
- for x in fe.dtos.to_a do
+ if to_remove != null then
+ for x in to_remove do te.dfroms.remove(x)
+ to_remove.clear
+ end
+
+ for x in fe.dtos do
var xe = self.elements[x]
if xe.froms.has(t) then
xe.dfroms.remove(f)
- fe.dtos.remove(x)
+ if to_remove == null then to_remove = new Array[E]
+ to_remove.add x
end
end
+ if to_remove != null then
+ for x in to_remove do fe.dtos.remove(x)
+ end
+
fe.dtos.add t
te.dfroms.add f
end
+ # Add an edge between all elements of `es` in order.
+ #
+ # ~~~~
+ # var pos = new POSet[String]
+ # pos.add_chain(["A", "B", "C", "D"])
+ # assert pos.has_direct_edge("A", "B")
+ # assert pos.has_direct_edge("B", "C")
+ # assert pos.has_direct_edge("C", "D")
+ # ~~~~
+ fun add_chain(es: SequenceRead[E])
+ do
+ if es.is_empty then return
+ var i = es.iterator
+ var e = i.item
+ i.next
+ for f in i do
+ add_edge(e, f)
+ e = f
+ end
+ end
+
# Is there an edge (transitive or not) from `f` to `t`?
+ #
+ # SEE: `add_edge`
+ #
# Since the POSet is reflexive, true is returned if `f == t`.
+ #
+ # ~~~
+ # var pos = new POSet[String]
+ # pos.add_node("A")
+ # assert pos.has_edge("A", "A") == true
+ # ~~~
fun has_edge(f,t: E): Bool
do
if not elements.keys.has(f) then return false
end
# Is there a direct edge from `f` to `t`?
+ #
+ # ~~~
+ # var pos = new POSet[String]
+ # pos.add_chain(["A", "B", "C"]) # add A->B->C
+ # assert pos.has_direct_edge("A", "B") == true
+ # assert pos.has_direct_edge("A", "C") == false
+ # assert pos.has_edge("A", "C") == true
+ # ~~~
+ #
# Note that because of loops, the result may not be the expected one.
fun has_direct_edge(f,t: E): Bool
do
return fe.dtos.has(t)
end
- # Display the POSet in a gaphical windows.
- # Graphviz with a working -Txlib is expected.
- # Used fo debugging.
- fun show_dot
+ # Write the POSet as a graphviz digraph.
+ #
+ # Nodes are labeled with their `to_s` so homonymous nodes may appear.
+ # Edges are unlabeled.
+ fun write_dot(f: Writer)
do
- var f = new OProcess("dot", "-Txlib")
- #var f = stdout
f.write "digraph \{\n"
+ var ids = new HashMap[E, Int]
+ for x in elements.keys do
+ ids[x] = ids.length
+ end
for x in elements.keys do
- f.write "\"{x}\";\n"
+ var xstr = (x or else "null").to_s.escape_to_dot
+ var nx = "n{ids[x]}"
+ f.write "{nx}[label=\"{xstr}\"];\n"
var xe = self.elements[x]
for y in xe.dtos do
+ var ny = "n{ids[y]}"
if self.has_edge(y,x) then
- f.write "\"{x}\" -> \"{y}\"[dir=both];\n"
+ f.write "{nx} -> {ny}[dir=both];\n"
else
- f.write "\"{x}\" -> \"{y}\";\n"
+ f.write "{nx} -> {ny};\n"
end
end
end
f.write "\}\n"
- #f.close
- #f.wait
+ end
+
+ # Display the POSet in a graphical windows.
+ # Graphviz with a working -Txlib is expected.
+ #
+ # See `write_dot` for details.
+ fun show_dot
+ do
+ var f = new ProcessWriter("dot", "-Txlib")
+ write_dot(f)
+ f.close
+ f.wait
end
# Compare two elements in an arbitrary total order.
- # Tis function is mainly used to sort elements of the set in an arbitrary linear extension.
- # if a<b then return -1
- # if a>b then return 1
+ #
+ # This function is mainly used to sort elements of the set in an coherent way.
+ #
+ # ~~~~
+ # var pos = new POSet[String]
+ # pos.add_chain(["A", "B", "C", "D", "E"])
+ # pos.add_chain(["A", "X", "C", "Y", "E"])
+ # var a = ["X", "C", "E", "A", "D"]
+ # pos.sort(a)
+ # assert a == ["E", "D", "C", "X", "A"]
+ # ~~~~
+ #
+ # POSet are not necessarily total orders because some distinct elements may be incomparable (neither greater or smaller).
+ # Therefore this method relies on arbitrary linear extension.
+ # This linear extension is a lawful total order (transitive, anti-symmetric, reflexive, and total), so can be used to compare the elements.
+ #
+ # The abstract behavior of the method is thus the following:
+ #
+ # ~~~~nitish
# if a == b then return 0
- # else return -1 or 1
- # The total order is stable unless a new node or a new edge is added
- redef fun compare(a, b: E): Int
+ # if has_edge(b, a) then return -1
+ # if has_edge(a, b) then return 1
+ # return -1 or 1 # according to the linear extension.
+ # ~~~~
+ #
+ # Note that the linear extension is stable, unless a new node or a new edge is added.
+ redef fun compare(a, b)
do
var ae = self.elements[a]
var be = self.elements[b]
if res != 0 then return res
return elements[a].count <=> elements[b].count
end
+
+ # Filter elements to return only the smallest ones
+ #
+ # ~~~
+ # var s = new POSet[String]
+ # s.add_edge("B", "A")
+ # s.add_edge("C", "A")
+ # s.add_edge("D", "B")
+ # s.add_edge("D", "C")
+ # assert s.select_smallest(["A", "B"]) == ["B"]
+ # assert s.select_smallest(["A", "B", "C"]) == ["B", "C"]
+ # assert s.select_smallest(["B", "C", "D"]) == ["D"]
+ # ~~~
+ fun select_smallest(elements: Collection[E]): Array[E]
+ do
+ var res = new Array[E]
+ for e in elements do
+ for f in elements do
+ if e == f then continue
+ if has_edge(f, e) then continue label
+ end
+ res.add(e)
+ end label
+ return res
+ end
+
+ # Filter elements to return only the greatest ones
+ #
+ # ~~~
+ # var s = new POSet[String]
+ # s.add_edge("B", "A")
+ # s.add_edge("C", "A")
+ # s.add_edge("D", "B")
+ # s.add_edge("D", "C")
+ # assert s.select_greatest(["A", "B"]) == ["A"]
+ # assert s.select_greatest(["A", "B", "C"]) == ["A"]
+ # assert s.select_greatest(["B", "C", "D"]) == ["B", "C"]
+ # ~~~
+ fun select_greatest(elements: Collection[E]): Array[E]
+ do
+ var res = new Array[E]
+ for e in elements do
+ for f in elements do
+ if e == f then continue
+ if has_edge(e, f) then continue label
+ end
+ res.add(e)
+ end label
+ return res
+ end
+
+ # Sort a sorted array of poset elements using linearization order
+ # ~~~~
+ # var pos = new POSet[String]
+ # pos.add_chain(["A", "B", "C", "D", "E"])
+ # pos.add_chain(["A", "X", "C", "Y", "E"])
+ # var a = pos.linearize(["X", "C", "E", "A", "D"])
+ # assert a == ["E", "D", "C", "X", "A"]
+ # ~~~~
+ fun linearize(elements: Collection[E]): Array[E] do
+ var lin = elements.to_a
+ sort(lin)
+ return lin
+ end
+
+ redef fun clone do return sub(self)
+
+ # Return an induced sub-poset
+ #
+ # The elements of the result are those given in argument.
+ #
+ # ~~~
+ # var pos = new POSet[String]
+ # pos.add_chain(["A", "B", "C", "D", "E"])
+ # pos.add_chain(["A", "X", "C", "Y", "E"])
+ #
+ # var pos2 = pos.sub(["A", "B", "D", "Y", "E"])
+ # assert pos2.has_exactly(["A", "B", "D", "Y", "E"])
+ # ~~~
+ #
+ # The full relationship is preserved between the provided elements.
+ #
+ # ~~~
+ # for e1 in pos2 do for e2 in pos2 do
+ # assert pos2.has_edge(e1, e2) == pos.has_edge(e1, e2)
+ # end
+ # ~~~
+ #
+ # Not that by definition, the direct relationship is the transitive
+ # reduction of the full reduction. Thus, the direct relationship of the
+ # sub-poset may not be included in the direct relationship of self because an
+ # indirect edge becomes a direct one if all the intermediates elements
+ # are absent in the sub-poset.
+ #
+ # ~~~
+ # assert pos.has_direct_edge("B", "D") == false
+ # assert pos2.has_direct_edge("B", "D") == true
+ #
+ # assert pos2["B"].direct_greaters.has_exactly(["D", "Y"])
+ # ~~~
+ #
+ # If the `elements` contains all then the result is a clone of self.
+ #
+ # ~~~
+ # var pos3 = pos.sub(pos)
+ # assert pos3 == pos
+ # assert pos3 == pos.clone
+ # ~~~
+ fun sub(elements: Collection[E]): POSet[E]
+ do
+ var res = new POSet[E]
+ for e in self do
+ if not elements.has(e) then continue
+ res.add_node(e)
+ end
+ for e in res do
+ for f in self[e].greaters do
+ if not elements.has(f) then continue
+ res.add_edge(e, f)
+ end
+ end
+ return res
+ end
+
+ # Two posets are equal if they contain the same elements and edges.
+ #
+ # ~~~
+ # var pos1 = new POSet[String]
+ # pos1.add_chain(["A", "B", "C", "D", "E"])
+ # pos1.add_chain(["A", "X", "C", "Y", "E"])
+ #
+ # var pos2 = new POSet[Object]
+ # pos2.add_edge("Y", "E")
+ # pos2.add_chain(["A", "X", "C", "D", "E"])
+ # pos2.add_chain(["A", "B", "C", "Y"])
+ #
+ # assert pos1 == pos2
+ #
+ # pos1.add_edge("D", "Y")
+ # assert pos1 != pos2
+ #
+ # pos2.add_edge("D", "Y")
+ # assert pos1 == pos2
+ #
+ # pos1.add_node("Z")
+ # assert pos1 != pos2
+ # ~~~
+ redef fun ==(other) do
+ if not other isa POSet[nullable Object] then return false
+ if not self.elements.keys.has_exactly(other.elements.keys) then return false
+ for e, ee in elements do
+ if ee.direct_greaters != other[e].direct_greaters then return false
+ end
+ assert hash == other.hash
+ return true
+ end
+
+ redef fun hash
+ do
+ var res = 0
+ for e, ee in elements do
+ if e == null then continue
+ res += e.hash
+ res += ee.direct_greaters.length
+ end
+ return res
+ end
+
+ redef fun core_serialize_to(serializer)
+ do
+ # Optimize written data because this structure has duplicated data
+ # For example, serializing the class hierarchy of a simple program where E is String
+ # result is before: 200k, after: 56k.
+ serializer.serialize_attribute("elements", elements)
+ end
+
+ redef init from_deserializer(deserializer)
+ do
+ deserializer.notify_of_creation self
+ var elements = deserializer.deserialize_attribute("elements")
+ if elements isa HashMap[E, POSetElement[E]] then
+ self.elements = elements
+ end
+ end
end
-# View of an objet in a poset
+# View of an object in a poset
# This class is a helper to handle specific queries on a same object
#
# For instance, one common usage is to add a specific attribute for each poset a class belong.
#
-# class Thing
-# var in_some_relation: POSetElement[Thing]
-# var in_other_relation: POSetElement[Thing]
-# end
-# var t: Thing # ...
-# t.in_some_relation.greaters
-#
-class POSetElement[E: Object]
+# ~~~nitish
+# class Thing
+# var in_some_relation: POSetElement[Thing]
+# var in_other_relation: POSetElement[Thing]
+# end
+# var t: Thing
+# # ...
+# t.in_some_relation.greaters
+# ~~~
+class POSetElement[E]
+ super Serializable
+
# The poset self belong to
var poset: POSet[E]
# Return the set of all elements `t` that have an edge from `element` to `t`.
# Since the POSet is reflexive, element is included in the set.
+ #
+ # ~~~~
+ # var pos = new POSet[String]
+ # pos.add_chain(["A", "B", "C", "D"])
+ # assert pos["B"].greaters.has_exactly(["B", "C", "D"])
+ # ~~~~
fun greaters: Collection[E]
do
return self.tos
end
# Return the set of all elements `t` that have a direct edge from `element` to `t`.
+ #
+ # ~~~~
+ # var pos = new POSet[String]
+ # pos.add_chain(["A", "B", "C", "D"])
+ # assert pos["B"].direct_greaters.has_exactly(["C"])
+ # ~~~~
fun direct_greaters: Collection[E]
do
return self.dtos
# Return the set of all elements `f` that have an edge from `f` to `element`.
# Since the POSet is reflexive, element is included in the set.
+ #
+ # ~~~~
+ # var pos = new POSet[String]
+ # pos.add_chain(["A", "B", "C", "D"])
+ # assert pos["C"].smallers.has_exactly(["A", "B", "C"])
+ # ~~~~
fun smallers: Collection[E]
do
return self.froms
end
# Return the set of all elements `f` that have an edge from `f` to `element`.
+ #
+ # ~~~~
+ # var pos = new POSet[String]
+ # pos.add_chain(["A", "B", "C", "D"])
+ # assert pos["C"].direct_smallers.has_exactly(["B"])
+ # ~~~~
fun direct_smallers: Collection[E]
do
return self.dfroms
end
# Is there an edge from `element` to `t`?
+ #
+ # ~~~~
+ # var pos = new POSet[String]
+ # pos.add_chain(["A", "B", "C", "D"])
+ # assert pos["B"] <= "D"
+ # assert pos["B"] <= "C"
+ # assert pos["B"] <= "B"
+ # assert not pos["B"] <= "A"
+ # ~~~~
fun <=(t: E): Bool
do
return self.tos.has(t)
end
# Is `t != element` and is there an edge from `element` to `t`?
+ #
+ # ~~~~
+ # var pos = new POSet[String]
+ # pos.add_chain(["A", "B", "C", "D"])
+ # assert pos["B"] < "D"
+ # assert pos["B"] < "C"
+ # assert not pos["B"] < "B"
+ # assert not pos["B"] < "A"
+ # ~~~~
fun <(t: E): Bool
do
return t != self.element and self.tos.has(t)
end
+
+ # The length of the shortest path to the root of the poset hierarchy
+ #
+ # ~~~~
+ # var pos = new POSet[String]
+ # pos.add_chain(["A", "B", "C", "D"])
+ # assert pos["A"].depth == 3
+ # assert pos["D"].depth == 0
+ # ~~~~
+ fun depth: Int do
+ if direct_greaters.is_empty then
+ return 0
+ end
+ var min = -1
+ for p in direct_greaters do
+ var d = poset[p].depth + 1
+ if min == -1 or d < min then
+ min = d
+ end
+ end
+ return min
+ end
+
+ redef fun core_serialize_to(serializer)
+ do
+ serializer.serialize_attribute("poset", poset)
+ serializer.serialize_attribute("element", element)
+ serializer.serialize_attribute("tos", tos)
+ serializer.serialize_attribute("froms", froms)
+ serializer.serialize_attribute("dtos", dtos)
+ serializer.serialize_attribute("dfroms", dfroms)
+ serializer.serialize_attribute("count", count)
+
+ # Don't serialize `froms`, `dtos` and `tos` as they duplicate information.
+ # TODO serialize them if a flag for extra info is set on `serializer`.
+ end
+
+ redef init from_deserializer(v)
+ do
+ # Code generated by the serialization_phase from the compiler frontend,
+ # copied here for compatibility with nith.
+
+ super
+ v.notify_of_creation self
+
+ var poset = v.deserialize_attribute("poset", "POSet[nullable Object]")
+ if v.deserialize_attribute_missing then
+ v.errors.add new Error("Deserialization Error: attribute `{class_name}::poset` missing from JSON object")
+ else if not poset isa POSet[E] then
+ v.errors.add new AttributeTypeError(self, "poset", poset, "POSet[nullable Object]")
+ if v.keep_going == false then return
+ else
+ self.poset = poset
+ end
+
+ var element = v.deserialize_attribute("element", "nullable Object")
+ if v.deserialize_attribute_missing then
+ v.errors.add new Error("Deserialization Error: attribute `{class_name}::element` missing from JSON object")
+ else if not element isa E then
+ v.errors.add new AttributeTypeError(self, "element", element, "nullable Object")
+ if v.keep_going == false then return
+ else
+ self.element = element
+ end
+
+ var tos = v.deserialize_attribute("tos", "HashSet[nullable Object]")
+ if v.deserialize_attribute_missing then
+ else if not tos isa HashSet[E] then
+ v.errors.add new AttributeTypeError(self, "tos", tos, "HashSet[nullable Object]")
+ if v.keep_going == false then return
+ else
+ self.tos = tos
+ end
+
+ var froms = v.deserialize_attribute("froms", "HashSet[nullable Object]")
+ if v.deserialize_attribute_missing then
+ else if not froms isa HashSet[E] then
+ v.errors.add new AttributeTypeError(self, "froms", froms, "HashSet[nullable Object]")
+ if v.keep_going == false then return
+ else
+ self.froms = froms
+ end
+
+ var dtos = v.deserialize_attribute("dtos", "HashSet[nullable Object]")
+ if v.deserialize_attribute_missing then
+ else if not dtos isa HashSet[E] then
+ v.errors.add new AttributeTypeError(self, "dtos", dtos, "HashSet[nullable Object]")
+ if v.keep_going == false then return
+ else
+ self.dtos = dtos
+ end
+
+ var dfroms = v.deserialize_attribute("dfroms", "HashSet[nullable Object]")
+ if v.deserialize_attribute_missing then
+ else if not dfroms isa HashSet[E] then
+ v.errors.add new AttributeTypeError(self, "dfroms", dfroms, "HashSet[nullable Object]")
+ if v.keep_going == false then return
+ else
+ self.dfroms = dfroms
+ end
+
+ var count = v.deserialize_attribute("count", "Int")
+ if v.deserialize_attribute_missing then
+ v.errors.add new Error("Deserialization Error: attribute `{class_name}::count` missing from JSON object")
+ else if not count isa Int then
+ v.errors.add new AttributeTypeError(self, "count", count, "Int")
+ if v.keep_going == false then return
+ else
+ self.count = count
+ end
+ end
+end
+
+redef class MapRead[K, V]
+ # Return all elements of `keys` that have a value.
+ #
+ # ~~~
+ # var map = new Map[String, String]
+ # map["A"] = "a"
+ # map["B"] = "b"
+ # map["C"] = "c"
+ #
+ # assert map.filter_keys(["B"]) == ["B"]
+ # assert map.filter_keys(["A", "Z", "C"]) == ["A", "C"]
+ # assert map.filter_keys(["X", "Y", "Z"]).is_empty
+ # ~~~
+ #
+ # `has_key` is used to filter.
+ fun filter_keys(keys: Collection[nullable Object]): Array[K]
+ do
+ var res = new Array[K]
+ for e in keys do
+ if has_key(e) then res.add e
+ end
+ return res
+ end
+
+ # Search all the values in `pe.greaters`.
+ #
+ # Elements without values are ignored.
+ #
+ # Basically, values defined in all greater elements of `pe` are inherited.
+ #
+ # ~~~
+ # var pos = new POSet[String]
+ # pos.add_chain(["E", "D", "C", "B", "A"])
+ # pos.add_chain(["D", "X", "B"])
+ #
+ # var map = new HashMap[String, String]
+ # map["A"] = "a"
+ # map["C"] = "c"
+ # map["X"] = "x"
+ # map["E"] = "e"
+ #
+ # assert map.lookup_all_values(pos["B"]).has_exactly(["a"])
+ # assert map.lookup_all_values(pos["C"]).has_exactly(["a", "c"])
+ # assert map.lookup_all_values(pos["D"]).has_exactly(["a", "c", "x"])
+ # ~~~
+ fun lookup_all_values(pe: POSetElement[K]): Set[V]
+ do
+ var res = new Set[V]
+ for k in filter_keys(pe.greaters) do res.add self[k]
+ return res
+ end
+
+ # Combine the values in `pe.greaters` from the most smaller elements that have a value.
+ #
+ # Elements without values are ignored.
+ #
+ # Basically, values defined in nearest greater elements of `pe` are inherited.
+ #
+ # ~~~
+ # var pos = new POSet[String]
+ # pos.add_chain(["E", "D", "C", "B", "A"])
+ # pos.add_chain(["D", "X", "B"])
+ #
+ # var map = new HashMap[String, String]
+ # map["A"] = "a"
+ # map["C"] = "c"
+ # map["X"] = "x"
+ # map["E"] = "e"
+ #
+ # assert map.lookup_values(pos["B"]).has_exactly(["a"])
+ # assert map.lookup_values(pos["C"]).has_exactly(["c"])
+ # assert map.lookup_values(pos["D"]).has_exactly(["c", "x"])
+ # ~~~
+ fun lookup_values(pe: POSetElement[K]): Set[V]
+ do
+ var res = new Set[V]
+ for k in pe.poset.select_smallest(filter_keys(pe.greaters)) do res.add self[k]
+ return res
+ end
end
nitlanguage / nit.git / blobdiff