Debian Codegraph @

Source/Reasoner/Taxonomy/CParentChildPredecessorHierarchy.cpp

raw
1 /*
2 * Copyright (C) 2013-2015, 2019 by the Konclude Developer Team.
3 *
4 * This file is part of the reasoning system Konclude.
5 * For details and support, see <http://konclude.com/>.
6 *
7 * Konclude is free software: you can redistribute it and/or modify
8 * it under the terms of version 3 of the GNU Lesser General Public
9 * License (LGPLv3) as published by the Free Software Foundation.
10 *
11 * Konclude is distributed in the hope that it will be useful,
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 * GNU (Lesser) General Public License for more details.
15 *
16 * You should have received a copy of the GNU (Lesser) General Public
17 * License along with Konclude. If not, see <http://www.gnu.org/licenses/>.
18 *
19 */
20
21 #ifndef KONCLUDE_REASONER_TAXONOMY_CPARENTCHILDPREDECESSORHIERARCHY_CPP
22 #define KONCLUDE_REASONER_TAXONOMY_CPARENTCHILDPREDECESSORHIERARCHY_CPP
23
24 #include "CParentChildPredecessorHierarchy.h"
25
26
27 namespace Konclude {
28
29 namespace Reasoner {
30
31 namespace Taxonomy {
32
33
34
35 template<class T, class N, class E>
36 CParentChildPredecessorHierarchy<T,N,E>::CParentChildPredecessorHierarchy() {
37 topNode = nullptr;
38 bottomNode = nullptr;
39 }
40
41 template<class T, class N, class E>
42 CParentChildPredecessorHierarchy<T,N,E>::CParentChildPredecessorHierarchy(N* topHierarchyNode, N* bottomHierarchyNode) {
43 topNode = topHierarchyNode;
44 bottomNode = bottomHierarchyNode;
45 nodeContainer.append(topNode);
46 nodeContainer.append(bottomNode);
47
48 bottomNode->makeParent(topNode);
49 }
50
51 template<class T, class N, class E>
52 CParentChildPredecessorHierarchy<T,N,E>::CParentChildPredecessorHierarchy(const E& topElement, const E& bottomElement) {
53 topNode = createHierarchyNode(topElement);
54 bottomNode = createHierarchyNode(bottomElement);
55
56 bottomNode->makeParent(topNode);
57
58 }
59
60
61 template<class T, class N, class E>
62 T* CParentChildPredecessorHierarchy<T,N,E>::initHierarchy(const E& topElement, const E& bottomElement) {
63 qDeleteAll(nodeContainer);
64 nodeContainer.clear();
65 elmNodeHash.clear();
66 topNode = createHierarchyNode(topElement);
67 bottomNode = createHierarchyNode(bottomElement);
68
69 bottomNode->makeParent(topNode);
70 return (T*)this;
71 }
72
73
74 template<class T, class N, class E>
75 CParentChildPredecessorHierarchy<T,N,E>::~CParentChildPredecessorHierarchy() {
76 qDeleteAll(nodeContainer);
77 }
78
79
80 template<class T, class N, class E>
81 N* CParentChildPredecessorHierarchy<T,N,E>::createHierarchyNode(const E& element) {
82 N* node = new N(element);
83 nodeContainer.append(node);
84 elmNodeHash.insert(element,node);
85 return node;
86 }
87
88
89
90
91 template<class T, class N, class E>
92 N* CParentChildPredecessorHierarchy<T,N,E>::getTopHierarchyNode() {
93 return topNode;
94 }
95
96 template<class T, class N, class E>
97 N* CParentChildPredecessorHierarchy<T,N,E>::getBottomHierarchyNode() {
98 return bottomNode;
99 }
100
101
102 template<class T, class N, class E>
103 N* CParentChildPredecessorHierarchy<T,N,E>::getHierarchyNode(const E& element) {
104 return elmNodeHash.value(element,nullptr);
105 }
106
107
108 template<class T, class N, class E>
109 N* CParentChildPredecessorHierarchy<T,N,E>::getHierarchyNode(const E& element, bool create) {
110 N* node = getHierarchyNode(element);
111 if (!node) {
112 node = createHierarchyNode(element);
113 }
114 return node;
115 }
116
117
118 template<class T, class N, class E>
119 bool CParentChildPredecessorHierarchy<T,N,E>::hasHierarchyNode(const E& element) {
120 return elmNodeHash.contains(element);
121 }
122
123
124
125 template<class T, class N, class E>
126 bool CParentChildPredecessorHierarchy<T,N,E>::isNodeSubsumption(N* subsumerNode, N* subsumedNode) {
127 if (!subsumerNode || !subsumedNode) {
128 return false;
129 }
130 if (subsumerNode == subsumedNode) {
131 return true;
132 }
133 return subsumerNode->hasPredecessorNode(subsumedNode);
134 }
135
136 template<class T, class N, class E>
137 bool CParentChildPredecessorHierarchy<T,N,E>::isNodeEquivalence(N* node1, N* node2) {
138 if (!node1 || !node2) {
139 return false;
140 }
141 if (node1 == node2) {
142 return true;
143 }
144 return node1->hasPredecessorNode(node2) && node2->hasPredecessorNode(node1);
145 }
146
147
148 template<class T, class N, class E>
149 T* CParentChildPredecessorHierarchy<T,N,E>::updateNodeEquivalentElements(N* node) {
150 E topElement = topNode->getOneEquivalentElement();
151 E bottomElement = bottomNode->getOneEquivalentElement();
152 if (node) {
153 QList<E>* equivalentElementList = node->getEquivalentElementList();
154 for (typename QList<E>::const_iterator it = equivalentElementList->constBegin(), itEnd = equivalentElementList->constEnd(); it != itEnd; ++it) {
155 E element(*it);
156 if (element == topElement) {
157 topNode = node;
158 }
159 if (element == bottomElement) {
160 bottomNode = node;
161 }
162 elmNodeHash.insert(element,node);
163 }
164 }
165 return (T*)this;
166 }
167
168
169 template<class T, class N, class E>
170 bool CParentChildPredecessorHierarchy<T,N,E>::isNodeSatisfiable(N* node) {
171 return node != bottomNode && !node->hasPredecessorNode(bottomNode);
172 }
173
174 template<class T, class N, class E>
175 bool CParentChildPredecessorHierarchy<T,N,E>::isNodeNotSatisfiable(N* node) {
176 return node = bottomNode;
177 }
178
179
180 template<class T, class N, class E>
181 bool CParentChildPredecessorHierarchy<T,N,E>::isTopHierarchyNode(N* node) {
182 return node && topNode == node;
183 }
184
185 template<class T, class N, class E>
186 bool CParentChildPredecessorHierarchy<T,N,E>::isBottomHierarchyNode(N* node) {
187 return node && bottomNode == node;
188 }
189
190
191
192 template<class T, class N, class E>
193 bool CParentChildPredecessorHierarchy<T,N,E>::repairInsertion(N* node, N* insertParentNode) {
194 QSet<N*>* nodeChildSet = insertParentNode->getChildNodeSet();
195 for (typename QSet<N*>::iterator it = nodeChildSet->begin(), itEnd = nodeChildSet->end(); it != itEnd; ++it) {
196 N* childNode = *it;
197 if (childNode != node && childNode->hasPredecessorNode(node)) {
198 // now indirect predecessor
199 childNode->removeParent(insertParentNode);
200 it = nodeChildSet->erase(it);
201 if (it == itEnd) {
202 break;
203 }
204 }
205 }
206 QSet<N*>* nodeParentSet = node->getParentNodeSet();
207 for (typename QSet<N*>::iterator it = nodeParentSet->begin(), itEnd = nodeParentSet->end(); it != itEnd; ++it) {
208 N* parentNode = *it;
209 if (parentNode != insertParentNode && insertParentNode->hasPredecessorNode(parentNode)) {
210 // now indirect predecessor
211 parentNode->removeChild(node);
212 it = nodeParentSet->erase(it);
213 if (it == itEnd) {
214 break;
215 }
216 }
217 }
218 return true;
219 }
220
221
222
223 template<class T, class N, class E>
224 bool CParentChildPredecessorHierarchy<T,N,E>::repairedParentNodeInsertion(N* node, N* insertParentNode) {
225 if (!node->hasPredecessorNode(insertParentNode)) {
226 node->makeParent(insertParentNode);
227
228 repairInsertion(node,insertParentNode);
229
230 N* updatePredNode = insertParentNode;
231 QSet<N*>* updatePredSet = updatePredNode->getPredecessorNodeSet();
232 for (typename QSet<N*>::const_iterator predIt = updatePredSet->constBegin(), predItEnd = updatePredSet->constEnd(); predIt != predItEnd; ++predIt) {
233 updatePredNode = *predIt;
234 QList<N*> updateList(node->getChildNodeList());
235 while (!updateList.isEmpty()) {
236 N* updateNode = updateList.takeFirst();
237 if (!updateNode->hasPredecessorNode(updatePredNode)) {
238 updateNode->makePredecessor(updatePredNode);
239 QSet<N*>* updateNodeChildSet = updateNode->getChildNodeSet();
240 for (typename QSet<N*>::const_iterator it = updateNodeChildSet->constBegin(), itEnd = updateNodeChildSet->constEnd(); it != itEnd; ++it) {
241 updateList.append(*it);
242 }
243 }
244 }
245 updatePredNode = nullptr;
246 }
247 }
248 return false;
249 }
250
251
252 template<class T, class N, class E>
253 T* CParentChildPredecessorHierarchy<T,N,E>::setNodeSatisfiable(N* node) {
254 KONCLUDE_ASSERT_X(node != bottomNode,"hierarchy satisfiable","bottom element can not be satisfiable");
255 bottomNode->makeParent(node);
256 node->makeParent(topNode);
257 repairInsertion(bottomNode,node);
258 repairInsertion(node,topNode);
259 return (T*)this;
260 }
261
262 template<class T, class N, class E>
263 T* CParentChildPredecessorHierarchy<T,N,E>::setNodeUnsatisfiable(N* node) {
264 QList<N*> updateList;
265 updateList.append(node);
266 while (!updateList.isEmpty()) {
267 N* updateNode = updateList.takeFirst();
268 QList<E>* elementList = updateNode->getEquivalentElementList();
269 for (typename QList<E>::const_iterator it = elementList->constBegin(), itEnd = elementList->constEnd(); it != itEnd; ++it) {
270 E element = *it;
271 bottomNode->addEquivalentElement(element);
272 elmNodeHash.insert(element,bottomNode);
273 }
274 QSet<N*>* updateNodeChildSet = updateNode->getChildNodeSet();
275 for (typename QSet<N*>::const_iterator it = updateNodeChildSet->constBegin(), itEnd = updateNodeChildSet->constEnd(); it != itEnd; ++it) {
276 updateList.append(*it);
277 }
278 }
279 QSet<N*>* nodeParentSet = node->getParentNodeSet();
280 for (typename QSet<N*>::iterator it = nodeParentSet->begin(), itEnd = nodeParentSet->end(); it != itEnd; ++it) {
281 N* parentNode = *it;
282 it = nodeParentSet->erase(it);
283 node->removeParent(parentNode);
284 repairedParentNodeInsertion(bottomNode,parentNode);
285 if (it == itEnd) {
286 break;
287 }
288 }
289
290 return (T*)this;
291 }
292
293 template<class T, class N, class E>
294 T* CParentChildPredecessorHierarchy<T,N,E>::setNodeSubsumption(N* subsumerNode, N* subsumedNode) {
295 if (subsumerNode != subsumedNode) {
296 if (subsumedNode == bottomNode) {
297 // unsatisfiable
298 setNodeUnsatisfiable(subsumerNode);
299 }
300 if (subsumerNode->hasPredecessorNode(subsumedNode)) {
301 // make equivalent
302 N* mergeIntoNode = subsumedNode;
303 N* mergingNode = subsumerNode;
304 if (subsumerNode == bottomNode || subsumerNode == topNode) {
305 mergeIntoNode = subsumerNode;
306 mergingNode = subsumedNode;
307 }
308
309 QList<E>* elementList = mergingNode->getEquivalentElementList();
310 for (typename QList<E>::const_iterator it = elementList->constBegin(), itEnd = elementList->constEnd(); it != itEnd; ++it) {
311 E element = *it;
312 mergeIntoNode->addEquivalentElement(element);
313 elmNodeHash.insert(element,mergeIntoNode);
314 }
315
316 QList<N*> nodeChildList(mergingNode->getChildNodeList());
317 QList<N*> updateList(nodeChildList);
318 QList<N*> nodeParentList(mergingNode->getParentNodeList());
319 for (typename QList<N*>::const_iterator it = nodeChildList.constBegin(), itEnd = nodeChildList.constEnd(); it != itEnd; ++it) {
320 N* parentNode = *it;
321 parentNode->removeChild(mergingNode);
322 mergingNode->removeParent(parentNode);
323 }
324 for (typename QList<N*>::const_iterator it = nodeChildList.constBegin(), itEnd = nodeChildList.constEnd(); it != itEnd; ++it) {
325 N* childNode = *it;
326 childNode->removeParent(mergingNode);
327 mergingNode->removeChild(childNode);
328 }
329 while (!updateList.isEmpty()) {
330 N* updateNode = updateList.takeFirst();
331 if (updateNode->hasPredecessorNode(mergingNode)) {
332 updateNode->removePredecessor(mergingNode);
333 QSet<N*>* updateNodeChildSet = updateNode->getChildNodeSet();
334 for (typename QSet<N*>::const_iterator it = updateNodeChildSet->constBegin(), itEnd = updateNodeChildSet->constEnd(); it != itEnd; ++it) {
335 updateList.append(*it);
336 }
337 }
338 }
339 for (typename QList<N*>::const_iterator it = nodeChildList.constBegin(), itEnd = nodeChildList.constEnd(); it != itEnd; ++it) {
340 N* parentNode = *it;
341 setNodeSubsumption(mergeIntoNode,parentNode);
342 }
343 for (typename QList<N*>::const_iterator it = nodeChildList.constBegin(), itEnd = nodeChildList.constEnd(); it != itEnd; ++it) {
344 N* childNode = *it;
345 setNodeSubsumption(childNode,mergeIntoNode);
346 }
347
348 } else {
349 repairedParentNodeInsertion(subsumerNode,subsumedNode);
350 }
351 }
352 return (T*)this;
353 }
354
355 template<class T, class N, class E>
356 T* CParentChildPredecessorHierarchy<T,N,E>::setNodeEquivalence(N* eqNode1, N* eqNode2) {
357 if (eqNode1 != eqNode2) {
358 setNodeSubsumption(eqNode1,eqNode2);
359 setNodeSubsumption(eqNode2,eqNode1);
360 }
361 return (T*)this;
362 }
363
364
365 template<class T, class N, class E>
366 CHierarchyDepthTraversalIterator<N> CParentChildPredecessorHierarchy<T,N,E>::getDepthTraversalIterator(bool forceUnique) {
367 return CHierarchyDepthTraversalIterator<N>(topNode,bottomNode,forceUnique);
368 }
369
370
371 }; // end namespace Taxonomy
372
373 }; // end namespace Reasoner
374
375 }; // end namespace Konclude
376
377 #endif // KONCLUDE_REASONER_TAXONOMY_CPARENTCHILDPREDECESSORHIERARCHY_CPP