lib/poset.nit

   1 # This file is part of NIT ( http://www.nitlanguage.org ).
   2 #
   3 # Copyright 2012 Jean Privat <jean@pryen.org>
   4 #
   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
   8 #
   9 #     http://www.apache.org/licenses/LICENSE-2.0
  10 #
  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.
  16
  17 # Pre order sets and partial order set (ie hierarchies)
  18 module poset
  19
  20 import serialization::serialization_core
  21
  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)`
  27 #
  28 # Nodes and edges are added to the POSet.
  29 #
  30 # ~~~
  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"
  35 #
  36 # # A -> B -> C    D
  37 #
  38 # assert pos.has_edge("A", "B") == true  # direct
  39 # ~~~
  40 #
  41 # Since a poset is transitive, direct and indirect edges are considered by default.
  42 # Direct edges (transitive-reduction) can also be considered independently.
  43 #
  44 # ~~~
  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
  48 #
  49 # assert pos.has_direct_edge("A", "B") == true  # direct
  50 # assert pos.has_direct_edge("A", "C") == false # indirect
  51 # ~~~
  52 #
  53 # POSet are dynamic.
  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.
  57 #
  58 # ~~~
  59 # pos.add_edge("A","D")
  60 # pos.add_edge("D","B")
  61 # pos.add_edge("A","E")
  62 # pos.add_edge("E","C")
  63 #
  64 # # A -> D -> B
  65 # # |         |
  66 # # v         v
  67 # # E ------> C
  68 #
  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
  72 # ~~~
  73 #
  74 # Thanks to the `[]` method, elements can be considered relatively to the poset.
  75 # SEE `POSetElement`
  76 class POSet[E]
  77         super Collection[E]
  78         super Comparator
  79         super Cloneable
  80         super Serializable
  81
  82         redef type COMPARED: E is fixed
  83
  84         redef fun iterator do return elements.keys.iterator
  85
  86         # All the nodes
  87         private var elements = new HashMap[E, POSetElement[E]]
  88
  89         redef fun has(e) do return self.elements.keys.has(e)
  90
  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]
  96         do
  97                 if elements.keys.has(e) then return self.elements[e]
  98                 var poe = new POSetElement[E](self, e, elements.length)
  99                 poe.tos.add(e)
 100                 poe.froms.add(e)
 101                 self.elements[e] = poe
 102                 return poe
 103         end
 104
 105         # Return a view of `e` in the poset.
 106         # This allows to view the elements in their relation with others elements.
 107         #
 108         #     var poset = new POSet[String]
 109         #     poset.add_chain(["A", "B", "D"])
 110         #     poset.add_chain(["A", "C", "D"])
 111         #     var a = poset["A"]
 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
 115         #
 116         # REQUIRE: has(e)
 117         fun [](e: E): POSetElement[E]
 118         do
 119                 assert elements.keys.has(e)
 120                 return self.elements[e]
 121         end
 122
 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.
 126         #
 127         # ~~~
 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
 133         # ~~~
 134         #
 135         # If a reverse edge (from `t` to `f`) already exists, a loop is created.
 136         #
 137         # FIXME: Do something clever to manage loops.
 138         fun add_edge(f, t: E)
 139         do
 140                 var fe = add_node(f)
 141                 var te = add_node(t)
 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]
 147                         for tt in te.tos do
 148                                 var tte = self.elements[tt]
 149                                 tte.froms.add ff
 150                                 ffe.tos.add tt
 151                         end
 152                 end
 153                 # Update the transitive reduction
 154                 if te.tos.has(f) then return # Skip the reduction if there is a loop
 155
 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]
 166                                 to_remove.add x
 167                                 xe.dtos.remove(t)
 168                         end
 169                 end
 170                 if to_remove != null then
 171                         for x in to_remove do te.dfroms.remove(x)
 172                         to_remove.clear
 173                 end
 174
 175                 for x in fe.dtos do
 176                         var xe = self.elements[x]
 177                         if xe.froms.has(t) then
 178                                 xe.dfroms.remove(f)
 179                                 if to_remove == null then to_remove = new Array[E]
 180                                 to_remove.add x
 181                         end
 182                 end
 183                 if to_remove != null then
 184                         for x in to_remove do fe.dtos.remove(x)
 185                 end
 186
 187                 fe.dtos.add t
 188                 te.dfroms.add f
 189         end
 190
 191         # Add an edge between all elements of `es` in order.
 192         #
 193         # ~~~~
 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")
 199         # ~~~~
 200         fun add_chain(es: SequenceRead[E])
 201         do
 202                 if es.is_empty then return
 203                 var i = es.iterator
 204                 var e = i.item
 205                 i.next
 206                 for f in i do
 207                         add_edge(e, f)
 208                         e = f
 209                 end
 210         end
 211
 212         # Is there an edge (transitive or not) from `f` to `t`?
 213         #
 214         # SEE: `add_edge`
 215         #
 216         # Since the POSet is reflexive, true is returned if `f == t`.
 217         #
 218         # ~~~
 219         # var pos = new POSet[String]
 220         # pos.add_node("A")
 221         # assert pos.has_edge("A", "A") == true
 222         # ~~~
 223         fun has_edge(f,t: E): Bool
 224         do
 225                 if not elements.keys.has(f) then return false
 226                 var fe = self.elements[f]
 227                 return fe.tos.has(t)
 228         end
 229
 230         # Is there a direct edge from `f` to `t`?
 231         #
 232         # ~~~
 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
 238         # ~~~
 239         #
 240         # Note that because of loops, the result may not be the expected one.
 241         fun has_direct_edge(f,t: E): Bool
 242         do
 243                 if not elements.keys.has(f) then return false
 244                 var fe = self.elements[f]
 245                 return fe.dtos.has(t)
 246         end
 247
 248         # Write the POSet as a graphviz digraph.
 249         #
 250         # Nodes are labeled with their `to_s` so homonymous nodes may appear.
 251         # Edges are unlabeled.
 252         fun write_dot(f: Writer)
 253         do
 254                 f.write "digraph \{\n"
 255                 var ids = new HashMap[E, Int]
 256                 for x in elements.keys do
 257                         ids[x] = ids.length
 258                 end
 259                 for x in elements.keys do
 260                         var xstr = (x or else "null").to_s.escape_to_dot
 261                         var nx = "n{ids[x]}"
 262                         f.write "{nx}[label=\"{xstr}\"];\n"
 263                         var xe = self.elements[x]
 264                         for y in xe.dtos do
 265                                 var ny = "n{ids[y]}"
 266                                 if self.has_edge(y,x) then
 267                                         f.write "{nx} -> {ny}[dir=both];\n"
 268                                 else
 269                                         f.write "{nx} -> {ny};\n"
 270                                 end
 271                         end
 272                 end
 273                 f.write "\}\n"
 274         end
 275
 276         # Display the POSet in a graphical windows.
 277         # Graphviz with a working -Txlib is expected.
 278         #
 279         # See `write_dot` for details.
 280         fun show_dot
 281         do
 282                 var f = new ProcessWriter("dot", "-Txlib")
 283                 write_dot(f)
 284                 f.close
 285                 f.wait
 286         end
 287
 288         # Compare two elements in an arbitrary total order.
 289         #
 290         # This function is mainly used to sort elements of the set in an coherent way.
 291         #
 292         # ~~~~
 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"]
 297         # pos.sort(a)
 298         # assert a == ["E", "D", "C", "X", "A"]
 299         # ~~~~
 300         #
 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.
 304         #
 305         # The abstract behavior of the method is thus the following:
 306         #
 307         # ~~~~nitish
 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.
 312         # ~~~~
 313         #
 314         # Note that the linear extension is stable, unless a new node or a new edge is added.
 315         redef fun compare(a, b)
 316         do
 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
 322         end
 323
 324         # Filter elements to return only the smallest ones
 325         #
 326         # ~~~
 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"]
 335         # ~~~
 336         fun select_smallest(elements: Collection[E]): Array[E]
 337         do
 338                 var res = new Array[E]
 339                 for e in elements do
 340                         for f in elements do
 341                                 if e == f then continue
 342                                 if has_edge(f, e) then continue label
 343                         end
 344                         res.add(e)
 345                 end label
 346                 return res
 347         end
 348
 349         # Filter elements to return only the greatest ones
 350         #
 351         # ~~~
 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"]
 360         # ~~~
 361         fun select_greatest(elements: Collection[E]): Array[E]
 362         do
 363                 var res = new Array[E]
 364                 for e in elements do
 365                         for f in elements do
 366                                 if e == f then continue
 367                                 if has_edge(e, f) then continue label
 368                         end
 369                         res.add(e)
 370                 end label
 371                 return res
 372         end
 373
 374         # Sort a sorted array of poset elements using linearization order
 375         # ~~~~
 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"]
 381         # ~~~~
 382         fun linearize(elements: Collection[E]): Array[E] do
 383                 var lin = elements.to_a
 384                 sort(lin)
 385                 return lin
 386         end
 387
 388         redef fun clone do return sub(self)
 389
 390         # Return an induced sub-poset
 391         #
 392         # The elements of the result are those given in argument.
 393         #
 394         # ~~~
 395         # var pos = new POSet[String]
 396         # pos.add_chain(["A", "B", "C", "D", "E"])
 397         # pos.add_chain(["A", "X", "C", "Y", "E"])
 398         #
 399         # var pos2 = pos.sub(["A", "B", "D", "Y", "E"])
 400         # assert pos2.has_exactly(["A", "B", "D", "Y", "E"])
 401         # ~~~
 402         #
 403         # The full relationship is preserved between the provided elements.
 404         #
 405         # ~~~
 406         # for e1 in pos2 do for e2 in pos2 do
 407         #    assert pos2.has_edge(e1, e2) == pos.has_edge(e1, e2)
 408         # end
 409         # ~~~
 410         #
 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.
 416         #
 417         # ~~~
 418         # assert pos.has_direct_edge("B", "D")  == false
 419         # assert pos2.has_direct_edge("B", "D") == true
 420         #
 421         # assert pos2["B"].direct_greaters.has_exactly(["D", "Y"])
 422         # ~~~
 423         #
 424         # If the `elements` contains all then the result is a clone of self.
 425         #
 426         # ~~~
 427         # var pos3 = pos.sub(pos)
 428         # assert pos3 == pos
 429         # assert pos3 == pos.clone
 430         # ~~~
 431         fun sub(elements: Collection[E]): POSet[E]
 432         do
 433                 var res = new POSet[E]
 434                 for e in self do
 435                         if not elements.has(e) then continue
 436                         res.add_node(e)
 437                 end
 438                 for e in res do
 439                         for f in self[e].greaters do
 440                                 if not elements.has(f) then continue
 441                                 res.add_edge(e, f)
 442                         end
 443                 end
 444                 return res
 445         end
 446
 447         # Two posets are equal if they contain the same elements and edges.
 448         #
 449         # ~~~
 450         # var pos1 = new POSet[String]
 451         # pos1.add_chain(["A", "B", "C", "D", "E"])
 452         # pos1.add_chain(["A", "X", "C", "Y", "E"])
 453         #
 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"])
 458         #
 459         # assert pos1 == pos2
 460         #
 461         # pos1.add_edge("D", "Y")
 462         # assert pos1 != pos2
 463         #
 464         # pos2.add_edge("D", "Y")
 465         # assert pos1 == pos2
 466         #
 467         # pos1.add_node("Z")
 468         # assert pos1 != pos2
 469         # ~~~
 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
 475                 end
 476                 assert hash == other.hash
 477                 return true
 478         end
 479
 480         redef fun hash
 481         do
 482                 var res = 0
 483                 for e, ee in elements do
 484                         if e == null then continue
 485                         res += e.hash
 486                         res += ee.direct_greaters.length
 487                 end
 488                 return res
 489         end
 490
 491         redef fun core_serialize_to(serializer)
 492         do
 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)
 497         end
 498
 499         redef init from_deserializer(deserializer)
 500         do
 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
 505                 end
 506         end
 507 end
 508
 509 # View of an object in a poset
 510 # This class is a helper to handle specific queries on a same object
 511 #
 512 # For instance, one common usage is to add a specific attribute for each poset a class belong.
 513 #
 514 # ~~~nitish
 515 # class Thing
 516 #     var in_some_relation: POSetElement[Thing]
 517 #     var in_other_relation: POSetElement[Thing]
 518 # end
 519 # var t: Thing
 520 # # ...
 521 # t.in_some_relation.greaters
 522 # ~~~
 523 class POSetElement[E]
 524         super Serializable
 525
 526         # The poset self belong to
 527         var poset: POSet[E]
 528
 529         # The real object behind the view
 530         var element: E
 531
 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]
 536
 537         # The rank of the
 538         # This attribute is used to force a total order for POSet#compare
 539         private var count: Int
 540
 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.
 543         #
 544         # ~~~~
 545         # var pos = new POSet[String]
 546         # pos.add_chain(["A", "B", "C", "D"])
 547         # assert pos["B"].greaters.has_exactly(["B", "C", "D"])
 548         # ~~~~
 549         fun greaters: Collection[E]
 550         do
 551                 return self.tos
 552         end
 553
 554         # Return the set of all elements `t` that have a direct edge from `element` to `t`.
 555         #
 556         # ~~~~
 557         # var pos = new POSet[String]
 558         # pos.add_chain(["A", "B", "C", "D"])
 559         # assert pos["B"].direct_greaters.has_exactly(["C"])
 560         # ~~~~
 561         fun direct_greaters: Collection[E]
 562         do
 563                 return self.dtos
 564         end
 565
 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.
 568         #
 569         # ~~~~
 570         # var pos = new POSet[String]
 571         # pos.add_chain(["A", "B", "C", "D"])
 572         # assert pos["C"].smallers.has_exactly(["A", "B", "C"])
 573         # ~~~~
 574         fun smallers: Collection[E]
 575         do
 576                 return self.froms
 577         end
 578
 579         # Return the set of all elements `f` that have an edge from `f` to `element`.
 580         #
 581         # ~~~~
 582         # var pos = new POSet[String]
 583         # pos.add_chain(["A", "B", "C", "D"])
 584         # assert pos["C"].direct_smallers.has_exactly(["B"])
 585         # ~~~~
 586         fun direct_smallers: Collection[E]
 587         do
 588                 return self.dfroms
 589         end
 590
 591         # Is there an edge from `element` to `t`?
 592         #
 593         # ~~~~
 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"
 600         # ~~~~
 601         fun <=(t: E): Bool
 602         do
 603                 return self.tos.has(t)
 604         end
 605
 606         # Is `t != element` and is there an edge from `element` to `t`?
 607         #
 608         # ~~~~
 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"
 615         # ~~~~
 616         fun <(t: E): Bool
 617         do
 618                 return t != self.element and self.tos.has(t)
 619         end
 620
 621         # The length of the shortest path to the root of the poset hierarchy
 622         #
 623         # ~~~~
 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
 628         # ~~~~
 629         fun depth: Int do
 630                 if direct_greaters.is_empty then
 631                         return 0
 632                 end
 633                 var min = -1
 634                 for p in direct_greaters do
 635                         var d = poset[p].depth + 1
 636                         if min == -1 or d < min then
 637                                 min = d
 638                         end
 639                 end
 640                 return min
 641         end
 642
 643         redef fun core_serialize_to(serializer)
 644         do
 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)
 652
 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`.
 655         end
 656
 657         redef init from_deserializer(v)
 658         do
 659                 # Code generated by the serialization_phase from the compiler frontend,
 660                 # copied here for compatibility with nith.
 661
 662                 super
 663                 v.notify_of_creation self
 664
 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
 671                 else
 672                         self.poset = poset
 673                 end
 674
 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
 681                 else
 682                         self.element = element
 683                 end
 684
 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
 690                 else
 691                         self.tos = tos
 692                 end
 693
 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
 699                 else
 700                         self.froms = froms
 701                 end
 702
 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
 708                 else
 709                         self.dtos = dtos
 710                 end
 711
 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
 717                 else
 718                         self.dfroms = dfroms
 719                 end
 720
 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
 727                 else
 728                         self.count = count
 729                 end
 730         end
 731 end
 732
 733 redef class MapRead[K, V]
 734         # Return all elements of `keys` that have a value.
 735         #
 736         # ~~~
 737         # var map = new Map[String, String]
 738         # map["A"] = "a"
 739         # map["B"] = "b"
 740         # map["C"] = "c"
 741         #
 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
 745         # ~~~
 746         #
 747         # `has_key` is used to filter.
 748         fun filter_keys(keys: Collection[nullable Object]): Array[K]
 749         do
 750                 var res = new Array[K]
 751                 for e in keys do
 752                         if has_key(e) then res.add e
 753                 end
 754                 return res
 755         end
 756
 757         # Search all the values in `pe.greaters`.
 758         #
 759         # Elements without values are ignored.
 760         #
 761         # Basically, values defined in all greater elements of `pe` are inherited.
 762         #
 763         # ~~~
 764         # var pos = new POSet[String]
 765         # pos.add_chain(["E", "D", "C", "B", "A"])
 766         # pos.add_chain(["D", "X", "B"])
 767         #
 768         # var map = new HashMap[String, String]
 769         # map["A"] = "a"
 770         # map["C"] = "c"
 771         # map["X"] = "x"
 772         # map["E"] = "e"
 773         #
 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"])
 777         # ~~~
 778         fun lookup_all_values(pe: POSetElement[K]): Set[V]
 779         do
 780                 var res = new Set[V]
 781                 for k in filter_keys(pe.greaters) do res.add self[k]
 782                 return res
 783         end
 784
 785         # Combine the values in `pe.greaters` from the most smaller elements that have a value.
 786         #
 787         # Elements without values are ignored.
 788         #
 789         # Basically, values defined in nearest greater elements of `pe` are inherited.
 790         #
 791         # ~~~
 792         # var pos = new POSet[String]
 793         # pos.add_chain(["E", "D", "C", "B", "A"])
 794         # pos.add_chain(["D", "X", "B"])
 795         #
 796         # var map = new HashMap[String, String]
 797         # map["A"] = "a"
 798         # map["C"] = "c"
 799         # map["X"] = "x"
 800         # map["E"] = "e"
 801         #
 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"])
 805         # ~~~
 806         fun lookup_values(pe: POSetElement[K]): Set[V]
 807         do
 808                 var res = new Set[V]
 809                 for k in pe.poset.select_smallest(filter_keys(pe.greaters)) do res.add self[k]
 810                 return res
 811         end
 812 end