Debian Codegraph @

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