Debian Codegraph @

Source/Utilities/CSortedNegLinker.hpp

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_UTILITIES_CSortedNegLinker_H
22 #define KONCLUDE_UTILITIES_CSortedNegLinker_H
23
24 // Libraries includes
25
26
27 // Namespace includes
28 #include <QLinkedListIterator>
29 #include "CAllocationObject.h"
30
31 // Other includes
32
33
34 // Logger includes
35 #include "Logger/CLogger.h"
36
37
38
39 namespace Konclude {
40
41 namespace Utilities {
42
43
44 template<class T> class CSortedNegLinker;
45
46
47
48 /*!
49 *
50 * \class CSortedNegLinker
51 * \author Andreas Steigmiller
52 * \version 0.1
53 * \brief Spezialised Pointer Version to avoid comparison between addresses
54 *
55 */
56 template<class T>
57 class CSortedNegLinker<T*> : public CAllocationObject {
58 // public methods
59 public:
60 //! Constructor
61 CSortedNegLinker();
62 CSortedNegLinker(T* dataElement, bool isNegated = false, CSortedNegLinker<T*> *nextLink = 0);
63
64 //! Destructor
65 virtual ~CSortedNegLinker();
66
67
68 CSortedNegLinker<T*> *init(T* dataElement, bool isNegated = false, CSortedNegLinker<T*> *nextLink = 0);
69
70 bool hasNext();
71
72 CSortedNegLinker<T*> *insertSortedNextSorted(CSortedNegLinker<T*> *nextLink);
73 CSortedNegLinker<T*> *insertNextSorted(CSortedNegLinker<T*> *nextLink);
74
75
76 CSortedNegLinker<T*> *insertNext(CSortedNegLinker<T*> *nextLink);
77 CSortedNegLinker<T*> *getNext();
78
79 CSortedNegLinker<T*> *setNext(CSortedNegLinker<T*> *nextLink);
80
81 T* getData();
82 CSortedNegLinker<T*> *setData(T* dataElement);
83
84 bool isNegated();
85 CSortedNegLinker<T*> *setNegated(bool isNegated);
86
87
88 CSortedNegLinker<T*> *append(CSortedNegLinker<T*> *appendingList);
89
90 CSortedNegLinker<T*> *removeNext();
91
92 CSortedNegLinker<T*> *getLastListLink();
93
94 qint64 getCount();
95
96 bool resortLinkerData();
97
98
99 // protected methods
100 protected:
101
102 // private methods
103 private:
104
105 // private variables
106 private:
107 CSortedNegLinker<T*> *next;
108 T* data;
109 bool negated;
110
111 };
112
113
114 template<class T>
115 CSortedNegLinker<T*>::CSortedNegLinker() {
116 next = 0;
117 negated = false;
118 }
119
120 template<class T>
121 CSortedNegLinker<T*>::CSortedNegLinker(T* dataElement, bool isNegated, CSortedNegLinker<T*> *nextLink) {
122 next = 0;
123 setNext(nextLink);
124 data = dataElement;
125 negated = isNegated;
126 }
127
128 template<class T>
129 CSortedNegLinker<T*> *CSortedNegLinker<T*>::init(T* dataElement, bool isNegated, CSortedNegLinker<T*> *nextLink) {
130 next = 0;
131 setNext(nextLink);
132 data = dataElement;
133 negated = isNegated;
134 return this;
135 }
136
137
138 template<class T>
139 CSortedNegLinker<T*>::~CSortedNegLinker() {
140 }
141
142
143 template<class T>
144 bool CSortedNegLinker<T*>::resortLinkerData() {
145 bool hasResorted = false;
146 if (next) {
147 bool nextHasResorted = true;
148 while (nextHasResorted) {
149 nextHasResorted = next->resortLinkerData();
150 }
151 if (next->getData() > data) {
152 T *tmpData = data;
153 bool tmpNeg = negated;
154 data = next->getData();
155 negated = next->isNegated();
156 next->setData(tmpData);
157 next->setNegated(tmpNeg);
158 hasResorted = true;
159 }
160 }
161 return hasResorted;
162 }
163
164
165 template<class T>
166 bool CSortedNegLinker<T*>::hasNext() {
167 return next != 0;
168 }
169
170
171 template<class T>
172 CSortedNegLinker<T*> *CSortedNegLinker<T*>::insertNext(CSortedNegLinker<T*> *nextLink) {
173 if (nextLink) {
174 CSortedNegLinker<T*> *tmpNext = next;
175 next = nextLink;
176 if (tmpNext) {
177 nextLink->append(tmpNext);
178 }
179 }
180 return this;
181 }
182
183
184 template<class T>
185 CSortedNegLinker<T*> *CSortedNegLinker<T*>::insertNextSorted(CSortedNegLinker<T*> *nextLink) {
186 CSortedNegLinker<T*> *firstLinker = this;
187 while (nextLink) {
188
189 CSortedNegLinker<T*> *nIns = nextLink;
190
191 if (nextLink->hasNext()) {
192 nextLink = nextLink->getNext();
193 } else {
194 nextLink = 0;
195 }
196 nIns->setNext(0);
197
198 CSortedNegLinker<T*> *list = firstLinker;
199 CSortedNegLinker<T*> *lastList = 0;
200 bool inserted = false;
201 T* dataIns = nIns->getData();
202 while (list) {
203 T* dataList = list->getData();
204 if (*dataIns <= *dataList) {
205 if (lastList == 0){
206 firstLinker = nIns->insertNext(firstLinker);
207 } else {
208 lastList->insertNext(nIns);
209 }
210 inserted = true;
211 break;
212 }
213 lastList = list;
214 list = list->next;
215 }
216 if (!inserted) {
217 lastList->insertNext(nIns);
218 }
219
220 }
221 return firstLinker;
222 }
223
224
225
226 template<class T>
227 CSortedNegLinker<T*> *CSortedNegLinker<T*>::insertSortedNextSorted(CSortedNegLinker<T*> *nextLink) {
228 // items from nextLink are already sorted!
229 CSortedNegLinker<T*> *firstLinker = this;
230
231 CSortedNegLinker<T*> *list = firstLinker;
232 CSortedNegLinker<T*> *lastList = 0;
233
234 while (nextLink) {
235
236 CSortedNegLinker<T*> *nIns = nextLink;
237
238 if (nextLink->hasNext()) {
239 nextLink = nextLink->getNext();
240 } else {
241 nextLink = 0;
242 }
243 nIns->setNext(0);
244
245 bool inserted = false;
246 T* dataIns = nIns->getData();
247 while (list) {
248 T* dataList = list->getData();
249 if (*dataIns <= *dataList) {
250 if (lastList == 0){
251 firstLinker = nIns->insertNext(firstLinker);
252 list = firstLinker->next;
253 lastList = firstLinker;
254 } else {
255 lastList->insertNext(nIns);
256 lastList = lastList->next;
257 // list is already on the correct position
258 }
259 inserted = true;
260 break;
261 }
262 lastList = list;
263 list = list->next;
264 }
265 if (!inserted) {
266 lastList->insertNext(nIns);
267 lastList = nIns;
268 }
269 }
270 return firstLinker;
271 }
272
273
274
275
276 template<class T>
277 CSortedNegLinker<T*> *CSortedNegLinker<T*>::setNext(CSortedNegLinker<T*> *nextLink) {
278 next = nextLink;
279 return this;
280 }
281
282
283
284 template<class T>
285 CSortedNegLinker<T*> *CSortedNegLinker<T*>::getNext() {
286 return next;
287 }
288
289
290
291 template<class T>
292 T* CSortedNegLinker<T*>::getData() {
293 return data;
294 }
295
296
297
298 template<class T>
299 CSortedNegLinker<T*> *CSortedNegLinker<T*>::setData(T* dataElement) {
300 data = dataElement;
301 return this;
302 }
303
304 template<class T>
305 bool CSortedNegLinker<T*>::isNegated() {
306 return negated;
307 }
308
309 template<class T>
310 CSortedNegLinker<T*> *CSortedNegLinker<T*>::setNegated(bool isNegated) {
311 negated = isNegated;
312 return this;
313 }
314
315
316
317 template<class T>
318 CSortedNegLinker<T*> *CSortedNegLinker<T*>::append(CSortedNegLinker<T*> *appendingList) {
319 CSortedNegLinker<T*> *last = getLastListLink();
320 last->insertNext(appendingList);
321 return this;
322 }
323
324 template<class T>
325 CSortedNegLinker<T*> *CSortedNegLinker<T*>::removeNext() {
326 CSortedNegLinker<T*> *tmpNext = next;
327 if (next) {
328 CSortedNegLinker<T*> *tmpNextNext = next->next;
329 next->next = 0;
330 setNext(tmpNextNext);
331 }
332 return tmpNext;
333 }
334
335
336
337
338 template<class T>
339 CSortedNegLinker<T*> *CSortedNegLinker<T*>::getLastListLink() {
340 CSortedNegLinker<T*> *lastListLink = this;
341 while (lastListLink->hasNext()) {
342 lastListLink = lastListLink->getNext();
343 }
344 return lastListLink;
345 }
346
347
348
349 template<class T>
350 qint64 CSortedNegLinker<T*>::getCount() {
351 qint64 count = 0;
352 CSortedNegLinker<T*> *linkIt = this;
353 while (linkIt) {
354 ++count;
355 linkIt = linkIt->getNext();
356 }
357 return count;
358 }
359
360
361
362
363
364 /*!
365 *
366 * \class CSortedNegLinker
367 * \author Andreas Steigmiller
368 * \version 0.1
369 * \brief TODO
370 *
371 */
372 template<class T>
373 class CSortedNegLinker : public CAllocationObject {
374 // public methods
375 public:
376 //! Constructor
377 CSortedNegLinker();
378 CSortedNegLinker(T dataElement, bool isNegated = false, CSortedNegLinker<T> *nextLink = 0);
379
380 //! Destructor
381 virtual ~CSortedNegLinker();
382
383
384 CSortedNegLinker<T> *init(T dataElement, bool isNegated = false, CSortedNegLinker<T> *nextLink = 0);
385
386 bool hasNext();
387
388 CSortedNegLinker<T> *insertSortedNextSorted(CSortedNegLinker<T> *nextLink);
389 CSortedNegLinker<T> *insertNextSorted(CSortedNegLinker<T> *nextLink);
390
391
392 CSortedNegLinker<T> *insertNext(CSortedNegLinker<T> *nextLink);
393 CSortedNegLinker<T> *getNext();
394
395 CSortedNegLinker<T> *setNext(CSortedNegLinker<T> *nextLink);
396
397 T getData();
398 CSortedNegLinker<T> *setData(T dataElement);
399
400 bool isNegated();
401 CSortedNegLinker<T> *setNegated(bool isNegated);
402
403
404 CSortedNegLinker<T> *append(CSortedNegLinker<T> *appendingList);
405
406 CSortedNegLinker<T> *removeNext();
407
408 CSortedNegLinker<T> *getLastListLink();
409
410 qint64 getCount();
411
412 bool resortLinkerData();
413
414
415 // protected methods
416 protected:
417
418 // protected variables
419 protected:
420 CSortedNegLinker<T> *next;
421 T data;
422 bool negated;
423
424 // private methods
425 private:
426
427 // private variables
428 private:
429
430 };
431
432
433 template<class T>
434 CSortedNegLinker<T>::CSortedNegLinker() {
435 next = 0;
436 negated = false;
437 }
438
439 template<class T>
440 CSortedNegLinker<T>::CSortedNegLinker(T dataElement, bool isNegated, CSortedNegLinker<T> *nextLink) {
441 next = 0;
442 setNext(nextLink);
443 data = dataElement;
444 negated = isNegated;
445 }
446
447 template<class T>
448 CSortedNegLinker<T> *CSortedNegLinker<T>::init(T dataElement, bool isNegated, CSortedNegLinker<T> *nextLink) {
449 next = 0;
450 setNext(nextLink);
451 data = dataElement;
452 negated = isNegated;
453 return this;
454 }
455
456
457 template<class T>
458 CSortedNegLinker<T>::~CSortedNegLinker() {
459 }
460
461
462 template<class T>
463 bool CSortedNegLinker<T>::resortLinkerData() {
464 bool hasResorted = false;
465 if (next) {
466 bool nextHasResorted = true;
467 while (nextHasResorted) {
468 nextHasResorted = next->resortLinkerData();
469 }
470 if (next->getData() > data) {
471 T tmpData = data;
472 bool tmpNeg = negated;
473 data = next->getData();
474 negated = next->isNegated();
475 next->setData(tmpData);
476 next->setNegated(tmpNeg);
477 hasResorted = true;
478 }
479 }
480 return hasResorted;
481 }
482
483
484 template<class T>
485 bool CSortedNegLinker<T>::hasNext() {
486 return next != 0;
487 }
488
489
490 template<class T>
491 CSortedNegLinker<T> *CSortedNegLinker<T>::insertNext(CSortedNegLinker<T> *nextLink) {
492 if (nextLink) {
493 CSortedNegLinker<T> *tmpNext = next;
494 next = nextLink;
495 if (tmpNext) {
496 nextLink->append(tmpNext);
497 }
498 }
499 return this;
500 }
501
502
503 template<class T>
504 CSortedNegLinker<T> *CSortedNegLinker<T>::insertNextSorted(CSortedNegLinker<T> *nextLink) {
505 CSortedNegLinker<T> *firstLinker = this;
506 while (nextLink) {
507
508 CSortedNegLinker<T> *nIns = nextLink;
509
510 if (nextLink->hasNext()) {
511 nextLink = nextLink->getNext();
512 } else {
513 nextLink = 0;
514 }
515 nIns->setNext(0);
516
517 CSortedNegLinker<T> *list = firstLinker;
518 CSortedNegLinker<T> *lastList = 0;
519 bool inserted = false;
520 T dataIns = nIns->getData();
521 while (list) {
522 T dataList = list->getData();
523 if (dataIns <= dataList) {
524 if (lastList == 0){
525 firstLinker = nIns->insertNext(firstLinker);
526 } else {
527 lastList->insertNext(nIns);
528 }
529 inserted = true;
530 break;
531 }
532 lastList = list;
533 list = list->next;
534 }
535 if (!inserted) {
536 lastList->insertNext(nIns);
537 }
538 }
539 return firstLinker;
540 }
541
542
543
544 template<class T>
545 CSortedNegLinker<T> *CSortedNegLinker<T>::insertSortedNextSorted(CSortedNegLinker<T> *nextLink) {
546 // items from nextLink are already sorted!
547 CSortedNegLinker<T> *firstLinker = this;
548
549 CSortedNegLinker<T> *list = firstLinker;
550 CSortedNegLinker<T> *lastList = 0;
551
552 while (nextLink) {
553
554 CSortedNegLinker<T> *nIns = nextLink;
555
556 if (nextLink->hasNext()) {
557 nextLink = nextLink->getNext();
558 } else {
559 nextLink = 0;
560 }
561 nIns->setNext(0);
562
563 bool inserted = false;
564 T dataIns = nIns->getData();
565 while (list) {
566 T dataList = list->getData();
567 if (dataIns <= dataList) {
568 if (lastList == 0){
569 firstLinker = nIns->insertNext(firstLinker);
570 list = firstLinker->next;
571 lastList = firstLinker;
572 } else {
573 lastList->insertNext(nIns);
574 lastList = lastList->next;
575 // list is already on the correct position
576 }
577 inserted = true;
578 break;
579 }
580 lastList = list;
581 list = list->next;
582 }
583 if (!inserted) {
584 lastList->insertNext(nIns);
585 lastList = nIns;
586 }
587 }
588 return firstLinker;
589 }
590
591
592
593
594 template<class T>
595 CSortedNegLinker<T> *CSortedNegLinker<T>::setNext(CSortedNegLinker<T> *nextLink) {
596 next = nextLink;
597 return this;
598 }
599
600
601
602 template<class T>
603 CSortedNegLinker<T> *CSortedNegLinker<T>::getNext() {
604 return next;
605 }
606
607
608
609 template<class T>
610 T CSortedNegLinker<T>::getData() {
611 return data;
612 }
613
614
615
616 template<class T>
617 CSortedNegLinker<T> *CSortedNegLinker<T>::setData(T dataElement) {
618 data = dataElement;
619 return this;
620 }
621
622 template<class T>
623 bool CSortedNegLinker<T>::isNegated() {
624 return negated;
625 }
626
627 template<class T>
628 CSortedNegLinker<T> *CSortedNegLinker<T>::setNegated(bool isNegated) {
629 negated = isNegated;
630 return this;
631 }
632
633
634
635 template<class T>
636 CSortedNegLinker<T> *CSortedNegLinker<T>::append(CSortedNegLinker<T> *appendingList) {
637 CSortedNegLinker<T> *last = getLastListLink();
638 last->insertNext(appendingList);
639 return this;
640 }
641
642 template<class T>
643 CSortedNegLinker<T> *CSortedNegLinker<T>::removeNext() {
644 CSortedNegLinker<T> *tmpNext = next;
645 if (next) {
646 CSortedNegLinker<T> *tmpNextNext = next->next;
647 next->next = 0;
648 setNext(tmpNextNext);
649 }
650 return tmpNext;
651 }
652
653
654
655
656 template<class T>
657 CSortedNegLinker<T> *CSortedNegLinker<T>::getLastListLink() {
658 CSortedNegLinker<T> *lastListLink = this;
659 while (lastListLink->hasNext()) {
660 lastListLink = lastListLink->getNext();
661 }
662 return lastListLink;
663 }
664
665
666 template<class T>
667 qint64 CSortedNegLinker<T>::getCount() {
668 qint64 count = 0;
669 CSortedNegLinker<T> *linkIt = this;
670 while (linkIt) {
671 ++count;
672 linkIt = linkIt->getNext();
673 }
674 return count;
675 }
676
677 }; // end namespace Utilities
678
679 }; // end namespace Konclude
680
681 #endif // KONCLUDE_UTILITIES_CSortedNegLinker_H