X-Git-Url: http://nitlanguage.org

diff --git a/lib/poset.nit b/lib/poset.nit
index cb4fa87..767b27d 100644
--- a/lib/poset.nit
+++ b/lib/poset.nit
@@ -17,21 +17,74 @@
 # 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
+
+# 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 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)
 
@@ -50,16 +103,15 @@ class POSet[E: Object]
 	end
 
 	# Return a view of `e` in the poset.
-	# This allows to asks manipulate elements in thier relation with others elements.
-	#
-	# ~~~nitish
-	# var poset: POSet[Something] # ...
-	# for x in poset do
-	#     for y in poset[x].direct_greaters do
-	#         print "{x} -> {y}"
-	#     end
-	# end
-	# ~~~
+	# This allows to view the elements in their relation with others elements.
+	#
+	#     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]
@@ -71,9 +123,18 @@ class POSet[E: Object]
 	# 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)
@@ -92,26 +153,73 @@ class POSet[E: Object]
 		# 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
@@ -120,6 +228,15 @@ class POSet[E: Object]
 	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
@@ -130,21 +247,26 @@ class POSet[E: Object]
 
 	# Write the POSet as a graphviz digraph.
 	#
-	# Nodes are identified with their `to_s`.
+	# Nodes are labeled with their `to_s` so homonymous nodes may appear.
 	# Edges are unlabeled.
-	fun write_dot(f: OStream)
+	fun write_dot(f: Writer)
 	do
 		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
-			var xstr = x.to_s.escape_to_dot
-			f.write "\"{xstr}\";\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 ystr = y.to_s.escape_to_dot
+				var ny = "n{ids[y]}"
 				if self.has_edge(y,x) then
-					f.write "\"{xstr}\" -> \"{ystr}\"[dir=both];\n"
+					f.write "{nx} -> {ny}[dir=both];\n"
 				else
-					f.write "\"{xstr}\" -> \"{ystr}\";\n"
+					f.write "{nx} -> {ny};\n"
 				end
 			end
 		end
@@ -157,21 +279,40 @@ class POSet[E: Object]
 	# See `write_dot` for details.
 	fun show_dot
 	do
-		var f = new OProcess("dot", "-Txlib")
-		f.write "\}\n"
+		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]
@@ -205,6 +346,8 @@ class POSet[E: Object]
 		return res
 	end
 
+	# Filter elements to return only the greatest ones
+	#
 	# ~~~
 	# var s = new POSet[String]
 	# s.add_edge("B", "A")
@@ -215,7 +358,6 @@ class POSet[E: Object]
 	# assert s.select_greatest(["A", "B", "C"]) == ["A"]
 	# assert s.select_greatest(["B", "C", "D"]) == ["B", "C"]
 	# ~~~
-	# Filter elements to return only the greatest ones
 	fun select_greatest(elements: Collection[E]): Array[E]
 	do
 		var res = new Array[E]
@@ -230,14 +372,141 @@ class POSet[E: Object]
 	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.
@@ -251,7 +520,9 @@ end
 # # ...
 # t.in_some_relation.greaters
 # ~~~
-class POSetElement[E: Object]
+class POSetElement[E]
+	super Serializable
+
 	# The poset self belong to
 	var poset: POSet[E]
 
@@ -269,12 +540,24 @@ class POSetElement[E: Object]
 
 	# 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
@@ -282,30 +565,67 @@ class POSetElement[E: Object]
 
 	# 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
@@ -318,6 +638,175 @@ class POSetElement[E: Object]
 			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