1 # This file is part of NIT ( http://www.nitlanguage.org ).
3 # Copyright 2004-2008 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 # Partial ordered sets (ie hierarchies)
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
: Object]
25 var _elements
: Map[E
, PartialOrderElement[E
]]
28 var _elements_list
: Array[E
]
30 # The roots of the hierarchy are elements without greaters
31 readable var _roots
: Array[E
]
35 redef fun is_empty
do return _elements
.is_empty
37 redef fun length
do return _elements
.length
39 redef fun first
do return _elements_list
.first
41 redef fun has
(e
) do return _elements
.has_key
(e
)
43 redef fun has_only
(e
) do return _elements
.length
== 1 and _elements
.values
.first
== e
54 redef fun iterator
do return _elements_list
.iterator
58 # Return the element associed with the item
59 fun [](e
: E
): PartialOrderElement[E
]
64 # Return a dot representation
68 s
.append
(to_dot_header
)
69 for e
in _elements
.values
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
))
79 # Called to display the header
80 protected fun to_dot_header
: String
82 return "digraph G \{\ngraph [rankdir=BT];\n"
85 # Called to display a node
86 protected fun to_dot_node
(e
: E
): String
91 # Called to draw an edge between `e1' and `e2' when `e1' < `e2'
92 protected fun to_dot_edge
(e1
: E
, e2
: E
): String
94 return "\"{e1}\
" -> \"{e2}\
";\n"
97 # Get an array consisting of only minimal elements
98 fun select_smallests
(c
: nullable Collection[E
]): Array[E
]
100 if c
== null then return new Array[E
]
102 var res
= new Array[E
].with_capacity
(c
.length
)
103 var tmp
= new Array[E
].with_capacity
(c
.length
)
105 # try to add `e' to the set of smallests
106 var r
= add_to_smallests
(e
, res
, tmp
)
108 # `tmp' contains the new smallests
118 # Add a new element inferior of some others
119 fun add
(e
: E
, supers
: nullable Collection[E
]): PartialOrderElement[E
]
122 assert supers
== null or has_all
(supers
)
123 var directs
= select_smallests
(supers
)
124 var poe
= new_poe
(e
, directs
)
126 _elements_list
.add
(e
)
127 if supers
== null or supers
.is_empty
then
133 # Are all these elements in the order
134 fun has_all
(e
: Collection[E
]): Bool
144 # factory for partial order elements
145 protected fun new_poe
(e
: E
, directs
: Array[E
]): PartialOrderElement[E
]
147 return new PartialOrderElement[E
](self, e
, directs
)
150 protected fun add_to_smallests
(e
: E
, from
: Array[E
], to
: Array[E
]): Bool
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')
171 protected fun compute_smallers_for
(poe
: PartialOrderElement[E
], set
: Set[E
])
174 for s
in _elements
.values
do
183 _elements
= new HashMap[E
, PartialOrderElement[E
]]
184 _elements_list
= new Array[E
]
185 _roots
= new Array[E
]
189 class PartialOrderElement[E
: Object]
190 # The partial order where belong self
191 readable var _order
: PartialOrder[E
]
193 # The value handled by self
194 readable var _value
: E
196 # Current rank in the hierarchy
198 # Sons of roots have 1
200 readable var _rank
: Int
202 # Elements that are direclty greater than self
203 readable var _direct_greaters
: Array[E
]
205 # Elements that are direclty smallers than self
206 readable var _direct_smallers
: Array[E
]
208 # Elements that are strictly greater than self
209 readable var _greaters
: Set[E
]
211 # Cached result of greaters_and_self
212 var _greaters_and_self_cache
: nullable Array[E
]
214 # Elements that are self or greater than self
215 fun greaters_and_self
: Collection[E
]
217 if _greaters_and_self_cache
== null then
218 _greaters_and_self_cache
= _greaters
.to_a
219 _greaters_and_self_cache
.add
(_value
)
221 return _greaters_and_self_cache
.as(not null)
224 # Cached value of _order.length to validade smallers_cache
225 var _smallers_last_length
: Int = 0
227 # Cached result of smallers
228 var _smallers_cache
: Set[E
]
230 # Elements that are strictly smaller than self
231 fun smallers
: Collection[E
]
233 if _smallers_last_length
< _order
.length
then
234 _order
.compute_smallers_for
(self, _smallers_cache
)
235 _smallers_last_length
= _order
.length
237 return _smallers_cache
240 # Cached result of linear_extension
241 var _linear_extension_cache
: nullable Array[E
]
243 # Return a linear extension of self
244 # FIXME: Uses the C++ algo that is not good!
245 fun linear_extension
: Array[E
]
247 if _linear_extension_cache
== null then
248 var res
= new Array[E
]
249 var res2
= new Array[E
]
251 for s
in direct_greaters
do
252 var sl
= order
[s
].linear_extension
255 if not sl
.has
(e
) then res2
.add
(e
)
263 _linear_extension_cache
= res
265 return _linear_extension_cache
.as(not null)
268 # Cached result of reverse_linear_extension
269 var _reverse_linear_extension_cache
: nullable Array[E
]
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
]
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
282 _linear_extension_cache
= res
.to_a
284 return _linear_extension_cache
.as(not null)
287 # Is value < o according to order?
290 return _greaters
.has
(o
)
293 # Is value <= o according to order?
296 return _value
== o
or _greaters
.has
(o
)
299 # Is value > o according to order?
302 return _order
[o
] < _value
305 # Is value >= o according to order?
308 return _value
== o
or _order
[o
] < _value
311 protected fun register_direct_smallers
(e
: E
)
313 _direct_smallers
.add
(e
)
316 protected init(o
: PartialOrder[E
], e
: E
, directs
: Array[E
])
320 _direct_greaters
= directs
321 _direct_smallers
= new Array[E
]
323 _greaters
= new HashSet[E
]
324 _smallers_cache
= new HashSet[E
]
330 var poee
= _order
[ee
]
331 if poee
.rank
>= r
then
334 poee
.register_direct_smallers
(e
)
335 for eee
in poee
.greaters
do