Tulip  5.1.0
Large graphs analysis and drawing
BmdList.cxx
1 /*
2  *
3  * This file is part of Tulip (http://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(0),tail(0),count(0) {
23 }
24 //=================================================================
25 template <typename TYPE>
26 tlp::BmdList<TYPE>::~BmdList() {
27  clear();
28 }
29 //=================================================================
30 template <typename TYPE>
31 tlp::BmdLink<TYPE> *tlp::BmdList<TYPE>::firstItem() {
32  return head;
33 }
34 //=================================================================
35 template <typename TYPE>
36 tlp::BmdLink<TYPE> *tlp::BmdList<TYPE>::lastItem() {
37  return tail;
38 }
39 //=================================================================
40 template <typename TYPE>
41 TYPE tlp::BmdList<TYPE>::entry(tlp::BmdLink<TYPE> *it) {
42  return it->data;
43 }
44 //=================================================================
45 template <typename TYPE>
46 int BmdList<TYPE>::size() {
47  return count;
48 }
49 //=================================================================
50 template <typename TYPE>
51 tlp::BmdLink<TYPE>* BmdList<TYPE>::nextItem(tlp::BmdLink<TYPE> *p, tlp::BmdLink<TYPE> *predP) {
52  if (p != NULL) {
53  if (p == tail)
54  return NULL;
55 
56  if (p == head)
57  predP = NULL;
58 
59  if (p->prev() != predP)
60  return p->prev();
61  else
62  return p->succ();
63  }
64  else
65  return NULL;
66 }
67 //=================================================================
68 template <typename TYPE>
69 tlp::BmdLink<TYPE> *tlp::BmdList<TYPE>::predItem(tlp::BmdLink<TYPE> *p, tlp::BmdLink<TYPE> *succP) {
70  if (p != NULL) {
71  if (p == head)
72  return NULL;
73 
74  if (p == tail)
75  succP = NULL;
76 
77  if (p->succ() != succP)
78  return p->succ();
79  else
80  return p->prev();
81  }
82  else
83  return NULL;
84 }
85 //=================================================================
86 template <typename TYPE>
87 tlp::BmdLink<TYPE> *tlp::BmdList<TYPE>::cyclicPred(tlp::BmdLink<TYPE> *it, tlp::BmdLink<TYPE> *succIt) {
88  if (it == NULL)
89  return NULL;
90 
91  if (it == head)
92  return tail;
93 
94  if (it == tail)
95  succIt = NULL;
96 
97  return predItem(it, succIt);
98 }
99 //=================================================================
100 template <typename TYPE>
101 tlp::BmdLink<TYPE> *tlp::BmdList<TYPE>::cyclicSucc(tlp::BmdLink<TYPE> *it, tlp::BmdLink<TYPE> *predIt) {
102  if (it == NULL)
103  return NULL;
104 
105  if (it == tail)
106  return head;
107 
108  if (it == head)
109  predIt = NULL;
110 
111  return nextItem(it, predIt);
112 }
113 //=================================================================
114 template <typename TYPE>
115 tlp::BmdLink<TYPE> *tlp::BmdList<TYPE>::push(const TYPE &data) {
116  count++;
117 
118  if (head != NULL) {
119  if (head->suc != NULL)
120  head = head->pre = new tlp::BmdLink<TYPE>(data, NULL, head);
121  else
122  head = head->suc = new tlp::BmdLink<TYPE>(data, NULL, head);
123  }
124  else
125  head = tail = new tlp::BmdLink<TYPE>(data, NULL, NULL);
126 
127  return head;
128 }
129 //=================================================================
130 template <typename TYPE>
131 tlp::BmdLink<TYPE> *tlp::BmdList<TYPE>::append(const TYPE &data) {
132  count++;
133 
134  if (tail != NULL) {
135  if (tail->pre != NULL)
136  tail = tail->suc = new tlp::BmdLink<TYPE>(data, tail, NULL);
137  else
138  tail = tail->pre = new tlp::BmdLink<TYPE>(data, tail, NULL);
139 
140  }
141  else {
142  tail = head = new tlp::BmdLink<TYPE>(data, NULL, NULL);
143  }
144 
145  return tail;
146 }
147 //=================================================================
148 template <typename TYPE>
149 TYPE tlp::BmdList<TYPE>::delItem(tlp::BmdLink<TYPE> *it) {
150  assert(it != NULL);
151 
152  if (it == head)
153  return pop();
154 
155  if (it == tail)
156  return popBack();
157 
158  tlp::BmdLink<TYPE> *p = predItem(it, NULL);
159  tlp::BmdLink<TYPE> *s = nextItem(it, p);
160  TYPE x = it->data;
161 
162  if (p->pre == it)
163  p->pre = s;
164  else
165  p->suc = s;
166 
167  if (s->suc == it)
168  s->suc = p;
169  else
170  s->pre = p;
171 
172  count--;
173  delete it;
174  return x;
175 }
176 //=================================================================
177 template <typename TYPE>
178 TYPE tlp::BmdList<TYPE>::pop() {
179  assert(head != NULL);
180  tlp::BmdLink<TYPE> *x = head;
181  head = nextItem(head, NULL);
182 
183  if (head) {
184  if (head->suc == x)
185  head->suc = NULL;
186  else
187  head->pre = NULL;
188  }
189  else
190  tail = NULL;
191 
192  TYPE p = x->data;
193  delete x;
194  count--;
195  return p;
196 }
197 //=================================================================
198 template <typename TYPE>
199 TYPE tlp::BmdList<TYPE>::popBack() {
200  assert(head != NULL);
201  tlp::BmdLink<TYPE> *x= tail;
202  tail = predItem(tail, NULL);
203 
204  if (tail) {
205  if (tail->pre == x)
206  tail->pre = NULL;
207  else
208  tail->suc = NULL;
209  }
210  else
211  head = NULL;
212 
213  TYPE p = x->data;
214  delete x;
215  count--;
216  return p;
217 }
218 //=================================================================
219 template <typename TYPE>
220 void tlp::BmdList<TYPE>::reverse() {
221  tlp::BmdLink<TYPE> *x = head;
222  head = tail;
223  tail = x;
224 }
225 //=================================================================
226 template <typename TYPE>
227 void tlp::BmdList<TYPE>::conc(tlp::BmdList<TYPE> &l) {
228  if (head == NULL) {
229  head = l.head;
230  tail = l.tail;
231  }
232  else {
233  if (tail->pre == NULL)
234  tail->pre = l.head;
235  else
236  tail->suc = l.head;
237 
238  if (l.head) {
239  if (l.head->suc == NULL)
240  l.head->suc = tail;
241  else
242  l.head->pre = tail;
243 
244  tail = l.tail;
245  }
246  }
247 
248  count += l.count;
249  l.head = l.tail = NULL;
250  l.count = 0;
251 }
252 //=================================================================
253 template <typename TYPE>
254 void tlp::BmdList<TYPE>::clear() {
255  if (head == NULL) return;
256 
257  tlp::BmdLink<TYPE> *it = head;
258  tlp::BmdLink<TYPE> *p = head;
259 
260  for (int i = 0 ; i < count ; i++) {
261  tlp::BmdLink<TYPE> *x = it;
262  it = nextItem(it, p);
263 
264  if (p != x)
265  delete p;
266 
267  p = x;
268  }
269 
270  delete p;
271  count = 0;
272  head = tail = NULL;
273 }
274 //=================================================================
275 template <typename TYPE>
276 void tlp::BmdList<TYPE>::swap(tlp::BmdList<TYPE>& l) {
277  tlp::BmdLink<TYPE> *tmp;
278  int tmp1;
279  tmp = l.head;
280  l.head = head;
281  head = tmp;
282  tmp = l.tail;
283  l.tail = tail;
284  tail = tmp;
285  tmp1 = l.count;
286  l.count = count;
287  count = tmp1;
288 }
289 //=================================================================