#
# 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
# 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
# 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 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
# 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
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
# # ...
# t.in_some_relation.greaters
# ~~~
-class POSetElement[E: Object]
+class POSetElement[E]
# The poset self belong to
var poset: POSet[E]
nitlanguage / nit.git / blobdiff