Tulip 5.7.1
Large graphs analysis and drawing
Loading...
Searching...
No Matches
BmdList.cxx
1/*
2 *
3 * This file is part of Tulip (https://tulip.labri.fr)
4 *
5 * Authors: David Auber and the Tulip development Team
6 * from LaBRI, University of Bordeaux
7 *
8 * Tulip is free software; you can redistribute it and/or modify
9 * it under the terms of the GNU Lesser General Public License
10 * as published by the Free Software Foundation, either version 3
11 * of the License, or (at your option) any later version.
12 *
13 * Tulip is distributed in the hope that it will be useful,
14 * but WITHOUT ANY WARRANTY; without even the implied warranty of
15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
16 * See the GNU General Public License for more details.
17 *
18 */
19
20//=================================================================
21template <typename TYPE>
22tlp::BmdList<TYPE>::BmdList() : head(nullptr), tail(nullptr), count(0) {}
23//=================================================================
24template <typename TYPE>
25tlp::BmdList<TYPE>::~BmdList() {
26 clear();
27}
28//=================================================================
29template <typename TYPE>
30tlp::BmdLink<TYPE> *tlp::BmdList<TYPE>::firstItem() {
31 return head;
32}
33//=================================================================
34template <typename TYPE>
35tlp::BmdLink<TYPE> *tlp::BmdList<TYPE>::lastItem() {
36 return tail;
37}
38//=================================================================
39template <typename TYPE>
40TYPE tlp::BmdList<TYPE>::entry(tlp::BmdLink<TYPE> *it) {
41 return it->data;
42}
43//=================================================================
44template <typename TYPE>
45int BmdList<TYPE>::size() {
46 return count;
47}
48//=================================================================
49template <typename TYPE>
50tlp::BmdLink<TYPE> *BmdList<TYPE>::nextItem(tlp::BmdLink<TYPE> *p, tlp::BmdLink<TYPE> *predP) {
51 if (p != nullptr) {
52 if (p == tail)
53 return nullptr;
54
55 if (p == head)
56 predP = nullptr;
57
58 if (p->prev() != predP)
59 return p->prev();
60 else
61 return p->succ();
62 } else
63 return nullptr;
64}
65//=================================================================
66template <typename TYPE>
67tlp::BmdLink<TYPE> *tlp::BmdList<TYPE>::predItem(tlp::BmdLink<TYPE> *p, tlp::BmdLink<TYPE> *succP) {
68 if (p != nullptr) {
69 if (p == head)
70 return nullptr;
71
72 if (p == tail)
73 succP = nullptr;
74
75 if (p->succ() != succP)
76 return p->succ();
77 else
78 return p->prev();
79 } else
80 return nullptr;
81}
82//=================================================================
83template <typename TYPE>
84tlp::BmdLink<TYPE> *tlp::BmdList<TYPE>::cyclicPred(tlp::BmdLink<TYPE> *it,
85 tlp::BmdLink<TYPE> *succIt) {
86 if (it == nullptr)
87 return nullptr;
88
89 if (it == head)
90 return tail;
91
92 if (it == tail)
93 succIt = nullptr;
94
95 return predItem(it, succIt);
96}
97//=================================================================
98template <typename TYPE>
99tlp::BmdLink<TYPE> *tlp::BmdList<TYPE>::cyclicSucc(tlp::BmdLink<TYPE> *it,
100 tlp::BmdLink<TYPE> *predIt) {
101 if (it == nullptr)
102 return nullptr;
103
104 if (it == tail)
105 return head;
106
107 if (it == head)
108 predIt = nullptr;
109
110 return nextItem(it, predIt);
111}
112//=================================================================
113template <typename TYPE>
114tlp::BmdLink<TYPE> *tlp::BmdList<TYPE>::push(const TYPE &data) {
115 count++;
116
117 if (head != nullptr) {
118 if (head->suc != nullptr)
119 head = head->pre = new tlp::BmdLink<TYPE>(data, nullptr, head);
120 else
121 head = head->suc = new tlp::BmdLink<TYPE>(data, nullptr, head);
122 } else
123 head = tail = new tlp::BmdLink<TYPE>(data, nullptr, nullptr);
124
125 return head;
126}
127//=================================================================
128template <typename TYPE>
129tlp::BmdLink<TYPE> *tlp::BmdList<TYPE>::append(const TYPE &data) {
130 count++;
131
132 if (tail != nullptr) {
133 if (tail->pre != nullptr)
134 tail = tail->suc = new tlp::BmdLink<TYPE>(data, tail, nullptr);
135 else
136 tail = tail->pre = new tlp::BmdLink<TYPE>(data, tail, nullptr);
137
138 } else {
139 tail = head = new tlp::BmdLink<TYPE>(data, nullptr, nullptr);
140 }
141
142 return tail;
143}
144//=================================================================
145template <typename TYPE>
146TYPE tlp::BmdList<TYPE>::delItem(tlp::BmdLink<TYPE> *it) {
147 assert(it != nullptr);
148
149 if (it == head)
150 return pop();
151
152 if (it == tail)
153 return popBack();
154
155 tlp::BmdLink<TYPE> *p = predItem(it, nullptr);
156 tlp::BmdLink<TYPE> *s = nextItem(it, p);
157 TYPE x = it->data;
158
159 if (p->pre == it)
160 p->pre = s;
161 else
162 p->suc = s;
163
164 if (s->suc == it)
165 s->suc = p;
166 else
167 s->pre = p;
168
169 count--;
170 delete it;
171 return x;
172}
173//=================================================================
174template <typename TYPE>
175TYPE tlp::BmdList<TYPE>::pop() {
176 assert(head != nullptr);
177 tlp::BmdLink<TYPE> *x = head;
178 head = nextItem(head, nullptr);
179
180 if (head) {
181 if (head->suc == x)
182 head->suc = nullptr;
183 else
184 head->pre = nullptr;
185 } else
186 tail = nullptr;
187
188 TYPE p = x->data;
189 delete x;
190 count--;
191 return p;
192}
193//=================================================================
194template <typename TYPE>
195TYPE tlp::BmdList<TYPE>::popBack() {
196 assert(head != nullptr);
197 tlp::BmdLink<TYPE> *x = tail;
198 tail = predItem(tail, nullptr);
199
200 if (tail) {
201 if (tail->pre == x)
202 tail->pre = nullptr;
203 else
204 tail->suc = nullptr;
205 } else
206 head = nullptr;
207
208 TYPE p = x->data;
209 delete x;
210 count--;
211 return p;
212}
213//=================================================================
214template <typename TYPE>
215void tlp::BmdList<TYPE>::reverse() {
216 tlp::BmdLink<TYPE> *x = head;
217 head = tail;
218 tail = x;
219}
220//=================================================================
221template <typename TYPE>
222void tlp::BmdList<TYPE>::conc(tlp::BmdList<TYPE> &l) {
223 if (head == nullptr) {
224 head = l.head;
225 tail = l.tail;
226 } else {
227 if (tail->pre == nullptr)
228 tail->pre = l.head;
229 else
230 tail->suc = l.head;
231
232 if (l.head) {
233 if (l.head->suc == nullptr)
234 l.head->suc = tail;
235 else
236 l.head->pre = tail;
237
238 tail = l.tail;
239 }
240 }
241
242 count += l.count;
243 l.head = l.tail = nullptr;
244 l.count = 0;
245}
246//=================================================================
247template <typename TYPE>
248void tlp::BmdList<TYPE>::clear() {
249 if (head == nullptr)
250 return;
251
252 tlp::BmdLink<TYPE> *it = head;
253 tlp::BmdLink<TYPE> *p = head;
254
255 for (int i = 0; i < count; i++) {
256 tlp::BmdLink<TYPE> *x = it;
257 it = nextItem(it, p);
258
259 if (p != x)
260 delete p;
261
262 p = x;
263 }
264
265 delete p;
266 count = 0;
267 head = tail = nullptr;
268}
269//=================================================================
270template <typename TYPE>
271void tlp::BmdList<TYPE>::swap(tlp::BmdList<TYPE> &l) {
272 tlp::BmdLink<TYPE> *tmp;
273 int tmp1;
274 tmp = l.head;
275 l.head = head;
276 head = tmp;
277 tmp = l.tail;
278 l.tail = tail;
279 tail = tmp;
280 tmp1 = l.count;
281 l.count = count;
282 count = tmp1;
283}
284//=================================================================