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