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
25 attr _elements
: Map[E
, PartialOrderElement[E
]]
28 attr _elements_list
: Array[E
]
30 # The roots of the hierarchy are elements without greaters
31 readable attr _roots
: Array[E
]
35 redef meth is_empty
do return _elements
.is_empty
37 redef meth length
do return _elements
.length
39 redef meth first
do return _elements_list
.first
41 redef meth has
(e
) do return _elements
.has_key
(e
)
43 redef meth has_only
(e
) do return _elements
.length
== 1 and _elements
.first
== e
54 redef meth iterator
do return _elements_list
.iterator
58 # Return the element associed with the item
59 meth
[](e
: E
): PartialOrderElement[E
]
61 if _elements
.has_key
(e
) then
68 # Return a dot representation
72 s
.append
(to_dot_header
)
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
))
83 # Called to display the header
84 protected meth to_dot_header
: String
86 return "digraph G \{\ngraph [rankdir=BT];\n"
89 # Called to display a node
90 protected meth to_dot_node
(e
: E
): String
95 # Called to draw an edge between `e1' and `e2' when `e1' < `e2'
96 protected meth to_dot_edge
(e1
: E
, e2
: E
): String
98 return "\"{e1}\
" -> \"{e2}\
";\n"
101 # Get an array consisting of only minimal elements
102 meth select_smallests
(c
: Collection[E
]): Array[E
]
104 if c
== null then return new Array[E
]
106 var res
= new Array[E
].with_capacity
(c
.length
)
107 var tmp
= new Array[E
].with_capacity
(c
.length
)
109 # try to add `e' to the set of smallests
110 var r
= add_to_smallests
(e
, res
, tmp
)
112 # `tmp' contains the new smallests
122 # Add a new element inferior of some others
123 meth add
(e
: E
, supers
: Collection[E
]): PartialOrderElement[E
]
126 assert supers
== null or has_all
(supers
)
127 var directs
= select_smallests
(supers
)
128 var poe
= new_poe
(e
, directs
)
130 _elements_list
.add
(e
)
131 if supers
== null or supers
.is_empty
then
137 # Are all these elements in the order
138 meth has_all
(e
: Collection[E
]): Bool
148 # factory for partial order elements
149 protected meth new_poe
(e
: E
, directs
: Array[E
]): PartialOrderElement[E
]
151 return new PartialOrderElement[E
](self, e
, directs
)
154 protected meth add_to_smallests
(e
: E
, from
: Array[E
], to
: Array[E
]): Bool
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')
175 protected meth compute_smallers_for
(poe
: PartialOrderElement[E
], set
: Set[E
])
178 for s
in _elements
do
187 _elements
= new HashMap[E
, PartialOrderElement[E
]]
188 _elements_list
= new Array[E
]
189 _roots
= new Array[E
]
193 class PartialOrderElement[E
]
194 # The partial order where belong self
195 readable attr _order
: PartialOrder[E
]
197 # The value handled by self
198 readable attr _value
: E
200 # Current rank in the hierarchy
202 # Sons of roots have 1
204 readable attr _rank
: Int
206 # Elements that are direclty greater than self
207 readable attr _direct_greaters
: Array[E
]
209 # Elements that are direclty smallers than self
210 readable attr _direct_smallers
: Array[E
]
212 # Elements that are strictly greater than self
213 readable attr _greaters
: Set[E
]
215 # Cached result of greaters_and_self
216 attr _greaters_and_self_cache
: Array[E
]
218 # Elements that are self or greater than self
219 meth greaters_and_self
: Collection[E
]
221 if _greaters_and_self_cache
== null then
222 _greaters_and_self_cache
= _greaters
.to_a
223 _greaters_and_self_cache
.add
(_value
)
225 return _greaters_and_self_cache
228 # Cached value of _order.length to validade smallers_cache
229 attr _smallers_last_length
: Int
231 # Cached result of smallers
232 attr _smallers_cache
: Set[E
]
234 # Elements that are strictly smaller than self
235 meth smallers
: Collection[E
]
237 if _smallers_last_length
< _order
.length
then
238 _order
.compute_smallers_for
(self, _smallers_cache
)
239 _smallers_last_length
= _order
.length
241 return _smallers_cache
244 # Cached result of linear_extension
245 attr _linear_extension_cache
: Array[E
]
247 # Return a linear extension of self
248 # FIXME: Uses the C++ algo that is not good!
249 meth linear_extension
: Array[E
]
251 if _linear_extension_cache
== null then
252 var res
= new Array[E
]
253 var res2
= new Array[E
]
255 for s
in direct_greaters
do
256 var sl
= order
[s
].linear_extension
259 if not sl
.has
(e
) then res2
.add
(e
)
267 _linear_extension_cache
= res
269 return _linear_extension_cache
272 # Cached result of reverse_linear_extension
273 attr _reverse_linear_extension_cache
: Array[E
]
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
]
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
286 _linear_extension_cache
= res
.to_a
288 return _linear_extension_cache
291 # Is value < o according to order?
294 return _greaters
.has
(o
)
297 # Is value <= o according to order?
300 return _value
== o
or _greaters
.has
(o
)
303 # Is value > o according to order?
306 return _order
[o
] < _value
309 # Is value >= o according to order?
312 return _value
== o
or _order
[o
] < _value
315 protected meth register_direct_smallers
(e
: E
)
317 _direct_smallers
.add
(e
)
320 protected init(o
: PartialOrder[E
], e
: E
, directs
: Array[E
])
324 _direct_greaters
= directs
325 _direct_smallers
= new Array[E
]
327 _greaters
= new HashSet[E
]
328 _smallers_cache
= new HashSet[E
]
334 var poee
= _order
[ee
]
335 if poee
.rank
>= r
then
338 poee
.register_direct_smallers
(e
)
339 for eee
in poee
.greaters
do