1 # This file is part of NIT ( http://www.nitlanguage.org ).
3 # Copyright 2012 Jean Privat <jean@pryen.org>
5 # Licensed under the Apache License, Version 2.0 (the "License");
6 # you may not use this file except in compliance with the License.
7 # You may obtain a copy of the License at
9 # http://www.apache.org/licenses/LICENSE-2.0
11 # Unless required by applicable law or agreed to in writing, software
12 # distributed under the License is distributed on an "AS IS" BASIS,
13 # WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14 # See the License for the specific language governing permissions and
15 # limitations under the License.
17 # Pre order sets and partial order set (ie hierarchies)
22 # Pre-order set graph.
23 # This class models an incremental pre-order graph where new nodes and edges can be added (but not removed).
24 # Pre-order graph has two characteristics:
25 # * reflexivity: an element is in relation with itself (ie `self.has(e) implies self.has_edge(e,e)`)
26 # * transitivity: `(self.has_edge(e,f) and self.has_edge(f,g)) implies self.has_edge(e,g)`
28 # Nodes and edges are added to the POSet.
31 # var pos = new POSet[String]
32 # pos.add_edge("A", "B") # add A->B
33 # pos.add_edge("B", "C") # add B->C
34 # pos.add_node("D") # add unconnected node "D"
38 # assert pos.has_edge("A", "B") == true # direct
41 # Since a poset is transitive, direct and indirect edges are considered by default.
42 # Direct edges (transitive-reduction) can also be considered independently.
45 # assert pos.has_edge("A", "C") == true # indirect
46 # assert pos.has_edge("A", "D") == false # no edge
47 # assert pos.has_edge("B", "A") == false # edges are directed
49 # assert pos.has_direct_edge("A", "B") == true # direct
50 # assert pos.has_direct_edge("A", "C") == false # indirect
54 # It means that the transitivity is updated while new nodes and edges are added.
55 # The transitive-reduction (*direct edges*)) is also updated,
56 # so adding new edges can make some direct edge to disappear.
59 # pos.add_edge("A","D")
60 # pos.add_edge("D","B")
61 # pos.add_edge("A","E")
62 # pos.add_edge("E","C")
69 # assert pos.has_edge("D", "C") == true # new indirect edge
70 # assert pos.has_edge("A", "B") == true # still an edge
71 # assert pos.has_direct_edge("A", "B") == false # but no-more a direct one
74 # Thanks to the `[]` method, elements can be considered relatively to the poset.
82 redef type COMPARED: E
is fixed
84 redef fun iterator
do return elements
.keys
.iterator
87 private var elements
= new HashMap[E
, POSetElement[E
]]
89 redef fun has
(e
) do return self.elements
.keys
.has
(e
)
91 # Add a node (an element) to the posed
92 # The new element is added unconnected to any other nodes (it is both a new root and a new leaf).
93 # Return the POSetElement associated to `e`.
94 # If `e` is already present in the POSet then just return the POSetElement (usually you will prefer []) is this case.
95 fun add_node
(e
: E
): POSetElement[E
]
97 if elements
.keys
.has
(e
) then return self.elements
[e
]
98 var poe
= new POSetElement[E
](self, e
, elements
.length
)
101 self.elements
[e
] = poe
105 # Return a view of `e` in the poset.
106 # This allows to view the elements in their relation with others elements.
108 # var poset = new POSet[String]
109 # poset.add_chain(["A", "B", "D"])
110 # poset.add_chain(["A", "C", "D"])
112 # assert a.direct_greaters.has_exactly(["B", "C"])
113 # assert a.greaters.has_exactly(["A", "B", "C", "D"])
114 # assert a.direct_smallers.is_empty
117 fun [](e
: E
): POSetElement[E
]
119 assert elements
.keys
.has
(e
)
120 return self.elements
[e
]
123 # Add an edge from `f` to `t`.
124 # Because a POSet is transitive, all transitive edges are also added to the graph.
125 # If the edge already exists, the this function does nothing.
128 # var pos = new POSet[String]
129 # pos.add_edge("A", "B") # add A->B
130 # assert pos.has_edge("A", "C") == false
131 # pos.add_edge("B", "C") # add B->C
132 # assert pos.has_edge("A", "C") == true
135 # If a reverse edge (from `t` to `f`) already exists, a loop is created.
137 # FIXME: Do something clever to manage loops.
138 fun add_edge
(f
, t
: E
)
142 # Skip if edge already present
143 if fe
.tos
.has
(t
) then return
144 # Add the edge and close the transitivity
145 for ff
in fe
.froms
do
146 var ffe
= self.elements
[ff
]
148 var tte
= self.elements
[tt
]
153 # Update the transitive reduction
154 if te
.tos
.has
(f
) then return # Skip the reduction if there is a loop
156 # Remove transitive edges.
157 # Because the sets of direct is iterated, the list of edges to remove
158 # is stored and is applied after the iteration.
159 # The usual case is that no direct edges need to be removed,
160 # so start with a `null` list of edges.
161 var to_remove
: nullable Array[E
] = null
162 for x
in te
.dfroms
do
163 var xe
= self.elements
[x
]
164 if xe
.tos
.has
(f
) then
165 if to_remove
== null then to_remove
= new Array[E
]
170 if to_remove
!= null then
171 for x
in to_remove
do te
.dfroms
.remove
(x
)
176 var xe
= self.elements
[x
]
177 if xe
.froms
.has
(t
) then
179 if to_remove
== null then to_remove
= new Array[E
]
183 if to_remove
!= null then
184 for x
in to_remove
do fe
.dtos
.remove
(x
)
191 # Add an edge between all elements of `es` in order.
194 # var pos = new POSet[String]
195 # pos.add_chain(["A", "B", "C", "D"])
196 # assert pos.has_direct_edge("A", "B")
197 # assert pos.has_direct_edge("B", "C")
198 # assert pos.has_direct_edge("C", "D")
200 fun add_chain
(es
: SequenceRead[E
])
202 if es
.is_empty
then return
212 # Is there an edge (transitive or not) from `f` to `t`?
216 # Since the POSet is reflexive, true is returned if `f == t`.
219 # var pos = new POSet[String]
221 # assert pos.has_edge("A", "A") == true
223 fun has_edge
(f
,t
: E
): Bool
225 if not elements
.keys
.has
(f
) then return false
226 var fe
= self.elements
[f
]
230 # Is there a direct edge from `f` to `t`?
233 # var pos = new POSet[String]
234 # pos.add_chain(["A", "B", "C"]) # add A->B->C
235 # assert pos.has_direct_edge("A", "B") == true
236 # assert pos.has_direct_edge("A", "C") == false
237 # assert pos.has_edge("A", "C") == true
240 # Note that because of loops, the result may not be the expected one.
241 fun has_direct_edge
(f
,t
: E
): Bool
243 if not elements
.keys
.has
(f
) then return false
244 var fe
= self.elements
[f
]
245 return fe
.dtos
.has
(t
)
248 # Write the POSet as a graphviz digraph.
250 # Nodes are labeled with their `to_s` so homonymous nodes may appear.
251 # Edges are unlabeled.
252 fun write_dot
(f
: Writer)
254 f
.write
"digraph \{\n"
255 var ids
= new HashMap[E
, Int]
256 for x
in elements
.keys
do
259 for x
in elements
.keys
do
260 var xstr
= (x
or else "null").to_s
.escape_to_dot
262 f
.write
"{nx}[label=\"{xstr}\
"];\n"
263 var xe
= self.elements
[x
]
266 if self.has_edge
(y
,x
) then
267 f
.write
"{nx} -> {ny}[dir=both];\n"
269 f
.write
"{nx} -> {ny};\n"
276 # Display the POSet in a graphical windows.
277 # Graphviz with a working -Txlib is expected.
279 # See `write_dot` for details.
282 var f
= new ProcessWriter("dot", "-Txlib")
288 # Compare two elements in an arbitrary total order.
290 # This function is mainly used to sort elements of the set in an coherent way.
293 # var pos = new POSet[String]
294 # pos.add_chain(["A", "B", "C", "D", "E"])
295 # pos.add_chain(["A", "X", "C", "Y", "E"])
296 # var a = ["X", "C", "E", "A", "D"]
298 # assert a == ["E", "D", "C", "X", "A"]
301 # POSet are not necessarily total orders because some distinct elements may be incomparable (neither greater or smaller).
302 # Therefore this method relies on arbitrary linear extension.
303 # This linear extension is a lawful total order (transitive, anti-symmetric, reflexive, and total), so can be used to compare the elements.
305 # The abstract behavior of the method is thus the following:
308 # if a == b then return 0
309 # if has_edge(b, a) then return -1
310 # if has_edge(a, b) then return 1
311 # return -1 or 1 # according to the linear extension.
314 # Note that the linear extension is stable, unless a new node or a new edge is added.
315 redef fun compare
(a
, b
)
317 var ae
= self.elements
[a
]
318 var be
= self.elements
[b
]
319 var res
= ae
.tos
.length
<=> be
.tos
.length
320 if res
!= 0 then return res
321 return elements
[a
].count
<=> elements
[b
].count
324 # Filter elements to return only the smallest ones
327 # var s = new POSet[String]
328 # s.add_edge("B", "A")
329 # s.add_edge("C", "A")
330 # s.add_edge("D", "B")
331 # s.add_edge("D", "C")
332 # assert s.select_smallest(["A", "B"]) == ["B"]
333 # assert s.select_smallest(["A", "B", "C"]) == ["B", "C"]
334 # assert s.select_smallest(["B", "C", "D"]) == ["D"]
336 fun select_smallest
(elements
: Collection[E
]): Array[E
]
338 var res
= new Array[E
]
341 if e
== f
then continue
342 if has_edge
(f
, e
) then continue label
349 # Filter elements to return only the greatest ones
352 # var s = new POSet[String]
353 # s.add_edge("B", "A")
354 # s.add_edge("C", "A")
355 # s.add_edge("D", "B")
356 # s.add_edge("D", "C")
357 # assert s.select_greatest(["A", "B"]) == ["A"]
358 # assert s.select_greatest(["A", "B", "C"]) == ["A"]
359 # assert s.select_greatest(["B", "C", "D"]) == ["B", "C"]
361 fun select_greatest
(elements
: Collection[E
]): Array[E
]
363 var res
= new Array[E
]
366 if e
== f
then continue
367 if has_edge
(e
, f
) then continue label
374 # Sort a sorted array of poset elements using linearization order
376 # var pos = new POSet[String]
377 # pos.add_chain(["A", "B", "C", "D", "E"])
378 # pos.add_chain(["A", "X", "C", "Y", "E"])
379 # var a = pos.linearize(["X", "C", "E", "A", "D"])
380 # assert a == ["E", "D", "C", "X", "A"]
382 fun linearize
(elements
: Collection[E
]): Array[E
] do
383 var lin
= elements
.to_a
388 redef fun clone
do return sub
(self)
390 # Return an induced sub-poset
392 # The elements of the result are those given in argument.
395 # var pos = new POSet[String]
396 # pos.add_chain(["A", "B", "C", "D", "E"])
397 # pos.add_chain(["A", "X", "C", "Y", "E"])
399 # var pos2 = pos.sub(["A", "B", "D", "Y", "E"])
400 # assert pos2.has_exactly(["A", "B", "D", "Y", "E"])
403 # The full relationship is preserved between the provided elements.
406 # for e1 in pos2 do for e2 in pos2 do
407 # assert pos2.has_edge(e1, e2) == pos.has_edge(e1, e2)
411 # Not that by definition, the direct relationship is the transitive
412 # reduction of the full reduction. Thus, the direct relationship of the
413 # sub-poset may not be included in the direct relationship of self because an
414 # indirect edge becomes a direct one if all the intermediates elements
415 # are absent in the sub-poset.
418 # assert pos.has_direct_edge("B", "D") == false
419 # assert pos2.has_direct_edge("B", "D") == true
421 # assert pos2["B"].direct_greaters.has_exactly(["D", "Y"])
424 # If the `elements` contains all then the result is a clone of self.
427 # var pos3 = pos.sub(pos)
429 # assert pos3 == pos.clone
431 fun sub
(elements
: Collection[E
]): POSet[E
]
433 var res
= new POSet[E
]
435 if not elements
.has
(e
) then continue
439 for f
in self[e
].greaters
do
440 if not elements
.has
(f
) then continue
447 # Two posets are equal if they contain the same elements and edges.
450 # var pos1 = new POSet[String]
451 # pos1.add_chain(["A", "B", "C", "D", "E"])
452 # pos1.add_chain(["A", "X", "C", "Y", "E"])
454 # var pos2 = new POSet[Object]
455 # pos2.add_edge("Y", "E")
456 # pos2.add_chain(["A", "X", "C", "D", "E"])
457 # pos2.add_chain(["A", "B", "C", "Y"])
459 # assert pos1 == pos2
461 # pos1.add_edge("D", "Y")
462 # assert pos1 != pos2
464 # pos2.add_edge("D", "Y")
465 # assert pos1 == pos2
468 # assert pos1 != pos2
470 redef fun ==(other
) do
471 if not other
isa POSet[nullable Object] then return false
472 if not self.elements
.keys
.has_exactly
(other
.elements
.keys
) then return false
473 for e
, ee
in elements
do
474 if ee
.direct_greaters
!= other
[e
].direct_greaters
then return false
476 assert hash
== other
.hash
483 for e
, ee
in elements
do
484 if e
== null then continue
486 res
+= ee
.direct_greaters
.length
491 redef fun core_serialize_to
(serializer
)
493 # Optimize written data because this structure has duplicated data
494 # For example, serializing the class hierarchy of a simple program where E is String
495 # result is before: 200k, after: 56k.
496 serializer
.serialize_attribute
("elements", elements
)
499 redef init from_deserializer
(deserializer
)
501 deserializer
.notify_of_creation
self
502 var elements
= deserializer
.deserialize_attribute
("elements")
503 if elements
isa HashMap[E
, POSetElement[E
]] then
504 self.elements
= elements
509 # View of an object in a poset
510 # This class is a helper to handle specific queries on a same object
512 # For instance, one common usage is to add a specific attribute for each poset a class belong.
516 # var in_some_relation: POSetElement[Thing]
517 # var in_other_relation: POSetElement[Thing]
521 # t.in_some_relation.greaters
523 class POSetElement[E
]
526 # The poset self belong to
529 # The real object behind the view
532 private var tos
= new HashSet[E
]
533 private var froms
= new HashSet[E
]
534 private var dtos
= new HashSet[E
]
535 private var dfroms
= new HashSet[E
]
538 # This attribute is used to force a total order for POSet#compare
539 private var count
: Int
541 # Return the set of all elements `t` that have an edge from `element` to `t`.
542 # Since the POSet is reflexive, element is included in the set.
545 # var pos = new POSet[String]
546 # pos.add_chain(["A", "B", "C", "D"])
547 # assert pos["B"].greaters.has_exactly(["B", "C", "D"])
549 fun greaters
: Collection[E
]
554 # Return the set of all elements `t` that have a direct edge from `element` to `t`.
557 # var pos = new POSet[String]
558 # pos.add_chain(["A", "B", "C", "D"])
559 # assert pos["B"].direct_greaters.has_exactly(["C"])
561 fun direct_greaters
: Collection[E
]
566 # Return the set of all elements `f` that have an edge from `f` to `element`.
567 # Since the POSet is reflexive, element is included in the set.
570 # var pos = new POSet[String]
571 # pos.add_chain(["A", "B", "C", "D"])
572 # assert pos["C"].smallers.has_exactly(["A", "B", "C"])
574 fun smallers
: Collection[E
]
579 # Return the set of all elements `f` that have an edge from `f` to `element`.
582 # var pos = new POSet[String]
583 # pos.add_chain(["A", "B", "C", "D"])
584 # assert pos["C"].direct_smallers.has_exactly(["B"])
586 fun direct_smallers
: Collection[E
]
591 # Is there an edge from `element` to `t`?
594 # var pos = new POSet[String]
595 # pos.add_chain(["A", "B", "C", "D"])
596 # assert pos["B"] <= "D"
597 # assert pos["B"] <= "C"
598 # assert pos["B"] <= "B"
599 # assert not pos["B"] <= "A"
603 return self.tos
.has
(t
)
606 # Is `t != element` and is there an edge from `element` to `t`?
609 # var pos = new POSet[String]
610 # pos.add_chain(["A", "B", "C", "D"])
611 # assert pos["B"] < "D"
612 # assert pos["B"] < "C"
613 # assert not pos["B"] < "B"
614 # assert not pos["B"] < "A"
618 return t
!= self.element
and self.tos
.has
(t
)
621 # The length of the shortest path to the root of the poset hierarchy
624 # var pos = new POSet[String]
625 # pos.add_chain(["A", "B", "C", "D"])
626 # assert pos["A"].depth == 3
627 # assert pos["D"].depth == 0
630 if direct_greaters
.is_empty
then
634 for p
in direct_greaters
do
635 var d
= poset
[p
].depth
+ 1
636 if min
== -1 or d
< min
then
643 redef fun core_serialize_to
(serializer
)
645 serializer
.serialize_attribute
("poset", poset
)
646 serializer
.serialize_attribute
("element", element
)
647 serializer
.serialize_attribute
("tos", tos
)
648 serializer
.serialize_attribute
("froms", froms
)
649 serializer
.serialize_attribute
("dtos", dtos
)
650 serializer
.serialize_attribute
("dfroms", dfroms
)
651 serializer
.serialize_attribute
("count", count
)
653 # Don't serialize `froms`, `dtos` and `tos` as they duplicate information.
654 # TODO serialize them if a flag for extra info is set on `serializer`.
657 redef init from_deserializer
(v
)
659 # Code generated by the serialization_phase from the compiler frontend,
660 # copied here for compatibility with nith.
663 v
.notify_of_creation
self
665 var poset
= v
.deserialize_attribute
("poset", "POSet[nullable Object]")
666 if v
.deserialize_attribute_missing
then
667 v
.errors
.add
new Error("Deserialization Error: attribute `{class_name}::poset` missing from JSON object")
668 else if not poset
isa POSet[E
] then
669 v
.errors
.add
new AttributeTypeError(self, "poset", poset
, "POSet[nullable Object]")
670 if v
.keep_going
== false then return
675 var element
= v
.deserialize_attribute
("element", "nullable Object")
676 if v
.deserialize_attribute_missing
then
677 v
.errors
.add
new Error("Deserialization Error: attribute `{class_name}::element` missing from JSON object")
678 else if not element
isa E
then
679 v
.errors
.add
new AttributeTypeError(self, "element", element
, "nullable Object")
680 if v
.keep_going
== false then return
682 self.element
= element
685 var tos
= v
.deserialize_attribute
("tos", "HashSet[nullable Object]")
686 if v
.deserialize_attribute_missing
then
687 else if not tos
isa HashSet[E
] then
688 v
.errors
.add
new AttributeTypeError(self, "tos", tos
, "HashSet[nullable Object]")
689 if v
.keep_going
== false then return
694 var froms
= v
.deserialize_attribute
("froms", "HashSet[nullable Object]")
695 if v
.deserialize_attribute_missing
then
696 else if not froms
isa HashSet[E
] then
697 v
.errors
.add
new AttributeTypeError(self, "froms", froms
, "HashSet[nullable Object]")
698 if v
.keep_going
== false then return
703 var dtos
= v
.deserialize_attribute
("dtos", "HashSet[nullable Object]")
704 if v
.deserialize_attribute_missing
then
705 else if not dtos
isa HashSet[E
] then
706 v
.errors
.add
new AttributeTypeError(self, "dtos", dtos
, "HashSet[nullable Object]")
707 if v
.keep_going
== false then return
712 var dfroms
= v
.deserialize_attribute
("dfroms", "HashSet[nullable Object]")
713 if v
.deserialize_attribute_missing
then
714 else if not dfroms
isa HashSet[E
] then
715 v
.errors
.add
new AttributeTypeError(self, "dfroms", dfroms
, "HashSet[nullable Object]")
716 if v
.keep_going
== false then return
721 var count
= v
.deserialize_attribute
("count", "Int")
722 if v
.deserialize_attribute_missing
then
723 v
.errors
.add
new Error("Deserialization Error: attribute `{class_name}::count` missing from JSON object")
724 else if not count
isa Int then
725 v
.errors
.add
new AttributeTypeError(self, "count", count
, "Int")
726 if v
.keep_going
== false then return
733 redef class MapRead[K
, V
]
734 # Return all elements of `keys` that have a value.
737 # var map = new Map[String, String]
742 # assert map.filter_keys(["B"]) == ["B"]
743 # assert map.filter_keys(["A", "Z", "C"]) == ["A", "C"]
744 # assert map.filter_keys(["X", "Y", "Z"]).is_empty
747 # `has_key` is used to filter.
748 fun filter_keys
(keys
: Collection[nullable Object]): Array[K
]
750 var res
= new Array[K
]
752 if has_key
(e
) then res
.add e
757 # Search all the values in `pe.greaters`.
759 # Elements without values are ignored.
761 # Basically, values defined in all greater elements of `pe` are inherited.
764 # var pos = new POSet[String]
765 # pos.add_chain(["E", "D", "C", "B", "A"])
766 # pos.add_chain(["D", "X", "B"])
768 # var map = new HashMap[String, String]
774 # assert map.lookup_all_values(pos["B"]).has_exactly(["a"])
775 # assert map.lookup_all_values(pos["C"]).has_exactly(["a", "c"])
776 # assert map.lookup_all_values(pos["D"]).has_exactly(["a", "c", "x"])
778 fun lookup_all_values
(pe
: POSetElement[K
]): Set[V
]
781 for k
in filter_keys
(pe
.greaters
) do res
.add
self[k
]
785 # Combine the values in `pe.greaters` from the most smaller elements that have a value.
787 # Elements without values are ignored.
789 # Basically, values defined in nearest greater elements of `pe` are inherited.
792 # var pos = new POSet[String]
793 # pos.add_chain(["E", "D", "C", "B", "A"])
794 # pos.add_chain(["D", "X", "B"])
796 # var map = new HashMap[String, String]
802 # assert map.lookup_values(pos["B"]).has_exactly(["a"])
803 # assert map.lookup_values(pos["C"]).has_exactly(["c"])
804 # assert map.lookup_values(pos["D"]).has_exactly(["c", "x"])
806 fun lookup_values
(pe
: POSetElement[K
]): Set[V
]
809 for k
in pe
.poset
.select_smallest
(filter_keys
(pe
.greaters
)) do res
.add
self[k
]