1 # This file is part of NIT ( http://www.nitlanguage.org ).
3 # Copyright 2012 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 # Pre order sets and partial order set (ie hierarchies)
21 # This class modelize an incremental preorder graph where new node and edges can be added (but no removal)
22 # Preorder graph has two caracteristics:
23 # * reflexivity: an element is in relation with itself (ie `self.has(e)' implies `self.has_edge(e,e)')
24 # * transitivity: `self.has_edge(e,f)' and `self.has_edge(f,g)' implies `self.has_edge(e,g)'
25 class POSet[E
: Object]
26 super NaiveCollection[E
]
27 super AbstractSorter[E
]
29 redef fun iterator
do return nodes
.iterator
32 private var nodes
: Set[E
] = new HashSet[E
]
33 private var tos
: HashMap[E
, Set[E
]] = new HashMap[E
, Set[E
]]
34 private var froms
: HashMap[E
, Set[E
]] = new HashMap[E
, Set[E
]]
35 private var dtos
: HashMap[E
, Set[E
]] = new HashMap[E
, Set[E
]]
36 private var dfroms
: HashMap[E
, Set[E
]] = new HashMap[E
, Set[E
]]
37 private var elements
: HashMap[E
, POSetElement[E
]] = new HashMap[E
, POSetElement[E
]]
39 redef fun has
(e
) do return self.nodes
.has
(e
)
41 # Add a node (an element) to the posed
42 # The new element is added unconnected to any other nodes (it is both a new root and a new leaf).
43 # Return the POSetElement associated to `e'.
44 # If `e' is already present in the POSet then just return the POSetElement (usually you will prefer []) is this case.
45 fun add_node
(e
: E
): POSetElement[E
]
47 if nodes
.has
(e
) then return self.elements
[e
]
49 tos
[e
] = new HashSet[E
]
51 froms
[e
] = new HashSet[E
]
53 dtos
[e
] = new HashSet[E
]
54 dfroms
[e
] = new HashSet[E
]
55 var poe
= new POSetElement[E
](self, e
, nodes
.length
)
56 self.elements
[e
] = poe
60 # Return a view of `e' in the poset.
61 # This allows to asks manipulate elements in thier relation with others elements.
63 # var poset = POSet[Something] = ...
65 # for y in poset[x].direct_greaters do
71 fun [](e
: E
): POSetElement[E
]
74 return self.elements
[e
]
77 # Add an edge from `f' to `t'.
78 # Because a POSet is transitive, all transitive edges are also added to the graph.
79 # If the edge already exists, the this function does nothing.
80 # If a reverse edge (from `t' to 'f') already exists, a loop is created.
82 # FIXME: Do somethind clever to manage loops.
87 # Skip if edge already present
88 if tos
[f
].has
(t
) then return
89 # Add the edge and close the transitivity
96 # Update the transitive reduction
97 if tos
[t
].has
(f
) then return # Skip the reduction if there is a loop
99 for x
in dfroms
[t
].to_a
do
100 if tos
[x
].has
(f
) then
105 for x
in dtos
[f
].to_a
do
106 if froms
[x
].has
(t
) then
115 # Is there an edge (transitive or not) from `f' to `t'?
116 # Since the POSet is reflexive, true is returned if `f == t'.
117 fun has_edge
(f
,t
: E
): Bool
119 return nodes
.has
(f
) and tos
[f
].has
(t
)
122 # Is there a direct edge from `f' to `t'?
123 # Note that because of loops, the result may not be the expected one.
124 fun has_direct_edge
(f
,t
: E
): Bool
126 return nodes
.has
(f
) and dtos
[f
].has
(t
)
129 # Display the POSet in a gaphical windows.
130 # Graphviz with a working -Txlib is expected.
134 var f
= new OProcess("dot", "-Txlib")
136 f
.write
"digraph \{\n"
139 if self.has_edge
(y
,x
) then
140 f
.write
"\"{x}\
" -> \"{y}\
"[dir=both];\n"
142 f
.write
"\"{x}\
" -> \"{y}\
";\n"
151 # Compare two elements in an arbitrary total order.
152 # Tis function is mainly used to sort elements of the set in an arbitrary linear extension.
153 # if a<b then return -1
154 # if a>b then return 1
155 # if a == b then return 0
156 # else return -1 or 1
157 # The total order is stable unless a new node or a new edge is added
158 redef fun compare
(a
, b
: E
): Int
160 var res
= tos
[a
].length
<=> tos
[b
].length
161 if res
!= 0 then return res
162 return elements
[a
].count
<=> elements
[b
].count
166 # View of an objet in a poset
167 # This class is a helper to handle specific queries on a same object
169 # For instance, one common usage is to add a specific attribute for each poset a class belong.
172 # var in_some_relation: POSetElement[Thing]
173 # var in_other_relation: POSetElement[Thing]
176 # t.in_some_relation.greaters
178 class POSetElement[E
: Object]
179 # The poset self belong to
182 # The real object behind the view
186 # This attribute is used to force a total order for POSet#compare
187 private var count
: Int
189 # Return the set of all elements `t' that have an edge from `element' to `t'.
190 # Since the POSet is reflexive, element is included in the set.
191 fun greaters
: Collection[E
]
193 return self.poset
.tos
[self.element
]
196 # Return the set of all elements `t' that have a direct edge from `element' to `t'.
197 fun direct_greaters
: Collection[E
]
199 return self.poset
.dtos
[self.element
]
202 # Return the set of all elements `f' that have an edge from `f' to `element'.
203 # Since the POSet is reflexive, element is included in the set.
204 fun smallers
: Collection[E
]
206 return self.poset
.froms
[self.element
]
209 # Return the set of all elements `f' that have an edge from `f' to `element'.
210 fun direct_smallers
: Collection[E
]
212 return self.poset
.dfroms
[self.element
]
215 # Is there an edge from `object' to `t'?
218 return self.poset
.tos
[self.element
].has
(t
)
221 # Is `t != element' and is there an edge from `object' to `t'?
224 return t
!= self.element
and self.poset
.tos
[self.element
].has
(t
)