lib: remove warnings on hash_debug, more_collections, ordered_tree, and poset

[nit.git] / lib / poset.nit

diff --git a/lib/poset.nit b/lib/poset.nit
index 65695da..6117ce5 100644 (file)
--- a/lib/poset.nit
+++ b/lib/poset.nit
@@ -24,12 +24,14 @@ module poset
 #  * transitivity: `(self.has_edge(e,f) and self.has_edge(f,g)) implies self.has_edge(e,g)`
 class POSet[E: Object]
        super Collection[E]
-       super Comparator[E]
+       super Comparator
+
+       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)
 
@@ -124,28 +126,40 @@ class POSet[E: Object]
                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 identified with their `to_s`.
+       # Edges are unlabeled.
+       fun write_dot(f: OStream)
        do
-               var f = new OProcess("dot", "-Txlib")
-               #var f = stdout
                f.write "digraph \{\n"
                for x in elements.keys do
-                       f.write "\"{x}\";\n"
+                       var xstr = x.to_s.escape_to_dot
+                       f.write "\"{xstr}\";\n"
                        var xe = self.elements[x]
                        for y in xe.dtos do
+                               var ystr = y.to_s.escape_to_dot
                                if self.has_edge(y,x) then
-                                       f.write "\"{x}\" -> \"{y}\"[dir=both];\n"
+                                       f.write "\"{xstr}\" -> \"{ystr}\"[dir=both];\n"
                                else
-                                       f.write "\"{x}\" -> \"{y}\";\n"
+                                       f.write "\"{xstr}\" -> \"{ystr}\";\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 OProcess("dot", "-Txlib")
+               f.write "\}\n"
+               write_dot(f)
+               f.close
+               f.wait
        end
 
        # Compare two elements in an arbitrary total order.
@@ -163,6 +177,62 @@ class POSet[E: Object]
                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
+
+       # ~~~
+       # 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"]
+       # ~~~
+       # Filter elements to return only the greatest ones
+       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
+       fun linearize(elements: Collection[E]): Array[E] do
+               var lin = elements.to_a
+               sort(lin)
+               return lin
+       end
 end
 
 # View of an objet in a poset