Debian Codegraph @

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