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

diff --git a/lib/poset.nit b/lib/poset.nit
index a5425dd..f7d6283 100644
--- a/lib/poset.nit
+++ b/lib/poset.nit
@@ -71,9 +71,10 @@ module poset
 #
 # Thanks to the `[]` method, elements can be considered relatively to the poset.
 # SEE `POSetElement`
-class POSet[E: Object]
+class POSet[E]
 	super Collection[E]
 	super Comparator
+	super Cloneable
 
 	redef type COMPARED: E is fixed
 
@@ -149,20 +150,37 @@ 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
@@ -228,7 +246,7 @@ class POSet[E: Object]
 	#
 	# 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]
@@ -258,7 +276,7 @@ class POSet[E: Object]
 	# See `write_dot` for details.
 	fun show_dot
 	do
-		var f = new OProcess("dot", "-Txlib")
+		var f = new ProcessWriter("dot", "-Txlib")
 		write_dot(f)
 		f.close
 		f.wait
@@ -363,6 +381,109 @@ class POSet[E: Object]
 		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
 end
 
 # View of an objet in a poset
@@ -379,7 +500,7 @@ end
 # # ...
 # t.in_some_relation.greaters
 # ~~~
-class POSetElement[E: Object]
+class POSetElement[E]
 	# The poset self belong to
 	var poset: POSet[E]