src/metamodel/partial_order.nit

   1 # This file is part of NIT ( http://www.nitlanguage.org ).
   2 #
   3 # Copyright 2004-2008 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 # Partial ordered sets (ie hierarchies)
  18 package partial_order
  19
  20 # Handles partial ordered sets (ie hierarchies)
  21 # Thez are built by adding new element at the bottom of the hierarchy
  22 class PartialOrder[E]
  23 special Collection[E]
  24         # Elements
  25         attr _elements: Map[E, PartialOrderElement[E]]
  26
  27         # Elements
  28         attr _elements_list: Array[E]
  29
  30         # The roots of the hierarchy are elements without greaters
  31         readable attr _roots: Array[E]
  32
  33 # Collection
  34
  35         redef meth is_empty do return _elements.is_empty
  36
  37         redef meth length do return _elements.length
  38
  39         redef meth first do return _elements_list.first
  40
  41         redef meth has(e) do return _elements.has_key(e)
  42
  43         redef meth has_only(e) do return _elements.length == 1 and _elements.first == e
  44
  45         redef meth count(e)
  46         do
  47                 if has(e) then
  48                         return 1
  49                 else
  50                         return 0
  51                 end
  52         end
  53
  54         redef meth iterator do return _elements_list.iterator
  55
  56 # Access
  57
  58         # Return the element associed with the item
  59         meth [](e: E): PartialOrderElement[E]
  60         do
  61                 if _elements.has_key(e) then
  62                         return _elements[e]
  63                 else
  64                         return null
  65                 end
  66         end
  67
  68         # Return a dot representation
  69         meth to_dot: String
  70         do
  71                 var s = new String
  72                 s.append(to_dot_header)
  73                 for e in _elements do
  74                         s.append(to_dot_node(e.value))
  75                         for d in e.direct_greaters do
  76                                 s.append(to_dot_edge(e.value, d))
  77                         end
  78                 end
  79                 s.append("}\n")
  80                 return s
  81         end
  82
  83         # Called to display the header
  84         protected meth to_dot_header: String
  85         do
  86                 return "digraph G \{\ngraph [rankdir=BT];\n"
  87         end
  88
  89         # Called to display a node
  90         protected meth to_dot_node(e: E): String
  91         do
  92                 return "\"{e}\";\n"
  93         end
  94
  95         # Called to draw an edge between `e1' and `e2' when `e1' < `e2'
  96         protected meth to_dot_edge(e1: E, e2: E): String
  97         do
  98                 return "\"{e1}\" -> \"{e2}\";\n"
  99         end
 100
 101         # Get an array consisting of only minimal elements
 102         meth select_smallests(c: Collection[E]): Array[E]
 103         do
 104                 if c == null then return new Array[E]
 105                 assert has_all(c)
 106                 var res = new Array[E].with_capacity(c.length)
 107                 var tmp = new Array[E].with_capacity(c.length)
 108                 for e in c do
 109                         # try to add `e' to the set of smallests
 110                         var r = add_to_smallests(e, res, tmp)
 111                         if r then
 112                                 # `tmp' contains the new smallests
 113                                 # therefore swap
 114                                 var t = tmp
 115                                 tmp = res
 116                                 res = t
 117                         end
 118                 end
 119                 return res
 120         end
 121
 122         # Add a new element inferior of some others
 123         meth add(e: E, supers: Collection[E]): PartialOrderElement[E]
 124         do
 125                 assert not has(e)
 126                 assert supers == null or has_all(supers)
 127                 var directs = select_smallests(supers)
 128                 var poe = new_poe(e, directs)
 129                 _elements[e] = poe
 130                 _elements_list.add(e)
 131                 if supers == null or supers.is_empty then
 132                         _roots.add(e)
 133                 end
 134                 return poe
 135         end
 136
 137         # Are all these elements in the order
 138         meth has_all(e: Collection[E]): Bool
 139         do
 140                 for i in e do
 141                         if not has(i) then
 142                                 return false
 143                         end
 144                 end
 145                 return true
 146         end
 147
 148         # factory for partial order elements
 149         protected meth new_poe(e: E, directs: Array[E]): PartialOrderElement[E]
 150         do
 151                 return new PartialOrderElement[E](self, e, directs)
 152         end
 153
 154         protected meth add_to_smallests(e: E, from: Array[E], to: Array[E]): Bool
 155         # an element `e'
 156         # some others elements `from' incomparable two by two
 157         # Return false if `from' < e
 158         # else return false and
 159         # fill `to' with smallests incomparable elements (including `e')
 160         do
 161                 to.clear
 162                 var poe = self[e]
 163                 for i in from do
 164                         if poe > i then
 165                                 return false
 166                         end
 167                         if not poe < i then
 168                                 to.add(i)
 169                         end
 170                 end
 171                 to.add(e)
 172                 return true
 173         end
 174
 175         protected meth compute_smallers_for(poe: PartialOrderElement[E], set: Set[E])
 176         do
 177                 var e = poe.value
 178                 for s in _elements do
 179                         if s < e then
 180                                 set.add(s.value)
 181                         end
 182                 end
 183         end
 184
 185         init
 186         do
 187                 _elements = new HashMap[E, PartialOrderElement[E]]
 188                 _elements_list = new Array[E]
 189                 _roots = new Array[E]
 190         end
 191 end
 192
 193 class PartialOrderElement[E]
 194         # The partial order where belong self
 195         readable attr _order: PartialOrder[E]
 196
 197         # The value handled by self
 198         readable attr _value: E
 199
 200         # Current rank in the hierarchy
 201         # Roots have 0
 202         # Sons of roots have 1
 203         # Etc.
 204         readable attr _rank: Int
 205
 206         # Elements that are direclty greater than self
 207         readable attr _direct_greaters: Array[E]
 208
 209         # Elements that are direclty smallers than self
 210         readable attr _direct_smallers: Array[E]
 211
 212         # Elements that are strictly greater than self
 213         readable attr _greaters: Set[E]
 214
 215         # Cached result of greaters_and_self
 216         attr _greaters_and_self_cache: Array[E]
 217
 218         # Elements that are self or greater than self
 219         meth greaters_and_self: Collection[E]
 220         do
 221                 if _greaters_and_self_cache == null then
 222                         _greaters_and_self_cache = _greaters.to_a
 223                         _greaters_and_self_cache.add(_value)
 224                 end
 225                 return _greaters_and_self_cache
 226         end
 227
 228         # Cached value of _order.length to validade smallers_cache
 229         attr _smallers_last_length: Int
 230
 231         # Cached result of smallers
 232         attr _smallers_cache: Set[E]
 233
 234         # Elements that are strictly smaller than self
 235         meth smallers: Collection[E]
 236         do
 237                 if _smallers_last_length < _order.length then
 238                         _order.compute_smallers_for(self, _smallers_cache)
 239                         _smallers_last_length = _order.length
 240                 end
 241                 return _smallers_cache
 242         end
 243
 244         # Cached result of linear_extension
 245         attr _linear_extension_cache: Array[E]
 246
 247         # Return a linear extension of self
 248         # FIXME: Uses the C++ algo that is not good!
 249         meth linear_extension: Array[E]
 250         do
 251                 if _linear_extension_cache == null then
 252                         var res = new Array[E]
 253                         var res2 = new Array[E]
 254                         res.add(value)
 255                         for s in direct_greaters do
 256                                 var sl = order[s].linear_extension
 257                                 res2.clear
 258                                 for e in res do
 259                                         if not sl.has(e) then res2.add(e)
 260                                 end
 261                                 res2.append(sl)
 262
 263                                 var tmp = res
 264                                 res = res2
 265                                 res2 = tmp
 266                         end
 267                         _linear_extension_cache = res
 268                 end
 269                 return _linear_extension_cache
 270         end
 271
 272         # Cached result of reverse_linear_extension
 273         attr _reverse_linear_extension_cache: Array[E]
 274
 275         # Return a reverse linear extension of self
 276         # FIXME: Uses the C++ algo that is not good!
 277         meth reverse_linear_extension: Array[E]
 278         do
 279                 if _reverse_linear_extension_cache == null then
 280                         var res = new HashSet[E]
 281                         for s in direct_greaters do
 282                                 var sl = order[s].linear_extension
 283                                 res.add_all(sl)
 284                         end
 285                         res.add(value)
 286                         _linear_extension_cache = res.to_a
 287                 end
 288                 return _linear_extension_cache
 289         end
 290
 291         # Is value < o according to order?
 292         meth <(o: E): Bool
 293         do
 294                 return _greaters.has(o)
 295         end
 296
 297         # Is value <= o according to order?
 298         meth <=(o: E): Bool
 299         do
 300                 return _value == o or _greaters.has(o)
 301         end
 302
 303         # Is value > o according to order?
 304         meth >(o: E): Bool
 305         do
 306                 return _order[o] < _value
 307         end
 308
 309         # Is value >= o according to order?
 310         meth >=(o: E): Bool
 311         do
 312                 return _value == o or _order[o] < _value
 313         end
 314
 315         protected meth register_direct_smallers(e: E)
 316         do
 317                 _direct_smallers.add(e)
 318         end
 319
 320         protected init(o: PartialOrder[E], e: E, directs: Array[E])
 321         do
 322                 _order = o
 323                 _value = e
 324                 _direct_greaters = directs
 325                 _direct_smallers = new Array[E]
 326
 327                 _greaters = new HashSet[E]
 328                 _smallers_cache = new HashSet[E]
 329
 330                 var g = _greaters
 331                 var r = 0
 332                 for ee in directs do
 333                         g.add(ee)
 334                         var poee = _order[ee]
 335                         if poee.rank >= r then
 336                                 r = poee.rank + 1
 337                         end
 338                         poee.register_direct_smallers(e)
 339                         for eee in poee.greaters do
 340                                 g.add(eee)
 341                         end
 342                 end
 343                 _rank = r
 344         end
 345 end