Debian Codegraph @

Source/Utilities/Container/CSortedLinker.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_UTILITIES_CONTAINER_CSORTEDLINKER_CPP
22 #define KONCLUDE_UTILITIES_CONTAINER_CSORTEDLINKER_CPP
23
24
25 #include "CSortedLinker.h"
26
27
28 namespace Konclude {
29
30 namespace Utilities {
31
32 namespace Container {
33
34 template<class T, class S, class C>
35 CSortedLinkerBase<T,S,C>::CSortedLinkerBase() : CLinkerBase<T,S>() {
36 }
37
38 template<class T, class S, class C>
39 CSortedLinkerBase<T,S,C>::CSortedLinkerBase(const T& dataElement, CSortedLinkerBase<T,S,C>* nextLink) : CLinkerBase<T,S>(dataElement,nextLink) {
40 }
41
42 template<class T, class S, class C>
43 CSortedLinkerBase<T,S,C>::~CSortedLinkerBase() {
44 }
45
46
47 template<class T, class S, class C>
48 S* CSortedLinkerBase<T,S,C>::insertNextSorted(CSortedLinkerBase<T,S,C>* nextLink) {
49 CSortedLinkerBase<T,S,C>* firstLinker = this;
50 while (nextLink) {
51
52 CSortedLinkerBase<T,S,C>* nIns = nextLink;
53
54 nextLink = nextLink->getNext();
55 nIns->setNext(nullptr);
56
57 CSortedLinkerBase<T,S,C>* list = firstLinker;
58 CSortedLinkerBase<T,S,C>* lastList = nullptr;
59 bool inserted = false;
60 const T& dataIns = nIns->getData();
61 while (list) {
62 const T& dataList = list->getData();
63 // compare items
64 if (isSortedBeforeCompare(dataIns,dataList)) {
65 if (lastList == nullptr){
66 firstLinker = nIns->insertNext(firstLinker);
67 } else {
68 lastList->insertNext(nIns);
69 }
70 inserted = true;
71 break;
72 }
73 lastList = list;
74 list = (CSortedLinkerBase<T,S,C>*)list->next;
75 }
76 if (!inserted) {
77 lastList->insertNext(nIns);
78 }
79 }
80 return (S*)firstLinker;
81 }
82
83
84
85 template<class T, class S, class C>
86 S* CSortedLinkerBase<T,S,C>::insertSortedNextSorted(CSortedLinkerBase<T,S,C>* nextLink) {
87 // items from nextLink are already sorted!
88 CSortedLinkerBase<T,S,C>* firstLinker = this;
89
90 CSortedLinkerBase<T,S,C>* list = firstLinker;
91 CSortedLinkerBase<T,S,C>* lastList = nullptr;
92
93 while (nextLink) {
94
95 CSortedLinkerBase<T,S,C>* nIns = nextLink;
96
97 nextLink = nextLink->getNext();
98 nIns->setNext(nullptr);
99
100 bool inserted = false;
101 const T& dataIns = nIns->getData();
102 while (list) {
103 const T& dataList = list->getData();
104 if (isSortedBeforeCompare(dataIns,dataList)) {
105 if (lastList == 0){
106 firstLinker = nIns->insertNext(firstLinker);
107 list = (CSortedLinkerBase<T,S,C>*)firstLinker->next;
108 lastList = firstLinker;
109 } else {
110 lastList->insertNext(nIns);
111 lastList = (CSortedLinkerBase<T,S,C>*)lastList->next;
112 // list is already on the correct position
113 }
114 inserted = true;
115 break;
116 }
117 lastList = list;
118 list = (CSortedLinkerBase<T,S,C>*)list->next;
119 }
120 if (!inserted) {
121 lastList->insertNext(nIns);
122 lastList = nIns;
123 }
124 }
125 return (S*)firstLinker;
126 }
127
128
129 template<class T, class S, class C>
130 bool CSortedLinkerBase<T,S,C>::isSortedBeforeCompare(const T& checkData, const T& linkedData) const {
131 return C::sortedLinkerDataCompare(checkData,linkedData);
132 }
133
134
135 }; // end namespace Container
136
137 }; // end namespace Utilities
138
139 }; // end namespace Konclude
140
141 #endif // KONCLUDE_UTILITIES_CONTAINER_CSORTEDLINKER_CPP