Tulip  5.7.4
Large graphs analysis and drawing
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 //=================================================================
21 template <typename TYPE>
22 tlp::BmdList<TYPE>::BmdList() : head(nullptr), tail(nullptr), count(0) {}
23 //=================================================================
24 template <typename TYPE>
25 tlp::BmdList<TYPE>::~BmdList() {
26  clear();
27 }
28 //=================================================================
29 template <typename TYPE>
30 tlp::BmdLink<TYPE> *tlp::BmdList<TYPE>::firstItem() {
31  return head;
32 }
33 //=================================================================
34 template <typename TYPE>
35 tlp::BmdLink<TYPE> *tlp::BmdList<TYPE>::lastItem() {
36  return tail;
37 }
38 //=================================================================
39 template <typename TYPE>
40 TYPE tlp::BmdList<TYPE>::entry(tlp::BmdLink<TYPE> *it) {
41  return it->data;
42 }
43 //=================================================================
44 template <typename TYPE>
45 int BmdList<TYPE>::size() {
46  return count;
47 }
48 //=================================================================
49 template <typename TYPE>
50 tlp::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 //=================================================================
66 template <typename TYPE>
67 tlp::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 //=================================================================
83 template <typename TYPE>
84 tlp::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 //=================================================================
98 template <typename TYPE>
99 tlp::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 //=================================================================
113 template <typename TYPE>
114 tlp::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 //=================================================================
128 template <typename TYPE>
129 tlp::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 //=================================================================
145 template <typename TYPE>
146 TYPE 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 //=================================================================
174 template <typename TYPE>
175 TYPE 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 //=================================================================
194 template <typename TYPE>
195 TYPE 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 //=================================================================
214 template <typename TYPE>
215 void tlp::BmdList<TYPE>::reverse() {
216  tlp::BmdLink<TYPE> *x = head;
217  head = tail;
218  tail = x;
219 }
220 //=================================================================
221 template <typename TYPE>
222 void 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 //=================================================================
247 template <typename TYPE>
248 void 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 //=================================================================
270 template <typename TYPE>
271 void 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 //=================================================================