![]() |
Tulip
4.6.0
Better Visualization Through Research
|
00001 /* 00002 * 00003 * This file is part of Tulip (www.tulip-software.org) 00004 * 00005 * Authors: David Auber and the Tulip development Team 00006 * from LaBRI, University of Bordeaux 00007 * 00008 * Tulip is free software; you can redistribute it and/or modify 00009 * it under the terms of the GNU Lesser General Public License 00010 * as published by the Free Software Foundation, either version 3 00011 * of the License, or (at your option) any later version. 00012 * 00013 * Tulip is distributed in the hope that it will be useful, 00014 * but WITHOUT ANY WARRANTY; without even the implied warranty of 00015 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. 00016 * See the GNU General Public License for more details. 00017 * 00018 */ 00019 00020 //================================================================= 00021 template <typename TYPE> 00022 tlp::BmdList<TYPE>::BmdList():head(0),tail(0),count(0) { 00023 } 00024 //================================================================= 00025 template <typename TYPE> 00026 tlp::BmdList<TYPE>::~BmdList() { 00027 clear(); 00028 } 00029 //================================================================= 00030 template <typename TYPE> 00031 tlp::BmdLink<TYPE> *tlp::BmdList<TYPE>::firstItem() { 00032 return head; 00033 } 00034 //================================================================= 00035 template <typename TYPE> 00036 tlp::BmdLink<TYPE> *tlp::BmdList<TYPE>::lastItem() { 00037 return tail; 00038 } 00039 //================================================================= 00040 template <typename TYPE> 00041 TYPE tlp::BmdList<TYPE>::entry(tlp::BmdLink<TYPE> *it) { 00042 return it->data; 00043 } 00044 //================================================================= 00045 template <typename TYPE> 00046 int BmdList<TYPE>::size() { 00047 return count; 00048 } 00049 //================================================================= 00050 template <typename TYPE> 00051 tlp::BmdLink<TYPE>* BmdList<TYPE>::nextItem(tlp::BmdLink<TYPE> *p, tlp::BmdLink<TYPE> *predP) { 00052 if (p != NULL) { 00053 if (p == tail) 00054 return NULL; 00055 00056 if (p == head) 00057 predP = NULL; 00058 00059 if (p->prev() != predP) 00060 return p->prev(); 00061 else 00062 return p->succ(); 00063 } 00064 else 00065 return NULL; 00066 } 00067 //================================================================= 00068 template <typename TYPE> 00069 tlp::BmdLink<TYPE> *tlp::BmdList<TYPE>::predItem(tlp::BmdLink<TYPE> *p, tlp::BmdLink<TYPE> *succP) { 00070 if (p != NULL) { 00071 if (p == head) 00072 return NULL; 00073 00074 if (p == tail) 00075 succP = NULL; 00076 00077 if (p->succ() != succP) 00078 return p->succ(); 00079 else 00080 return p->prev(); 00081 } 00082 else 00083 return NULL; 00084 } 00085 //================================================================= 00086 template <typename TYPE> 00087 tlp::BmdLink<TYPE> *tlp::BmdList<TYPE>::cyclicPred(tlp::BmdLink<TYPE> *it, tlp::BmdLink<TYPE> *succIt) { 00088 if (it == NULL) 00089 return NULL; 00090 00091 if (it == head) 00092 return tail; 00093 00094 if (it == tail) 00095 succIt = NULL; 00096 00097 return predItem(it, succIt); 00098 } 00099 //================================================================= 00100 template <typename TYPE> 00101 tlp::BmdLink<TYPE> *tlp::BmdList<TYPE>::cyclicSucc(tlp::BmdLink<TYPE> *it, tlp::BmdLink<TYPE> *predIt) { 00102 if (it == NULL) 00103 return NULL; 00104 00105 if (it == tail) 00106 return head; 00107 00108 if (it == head) 00109 predIt = NULL; 00110 00111 return nextItem(it, predIt); 00112 } 00113 //================================================================= 00114 template <typename TYPE> 00115 tlp::BmdLink<TYPE> *tlp::BmdList<TYPE>::push(const TYPE &data) { 00116 count++; 00117 00118 if (head != NULL) { 00119 if (head->suc != NULL) 00120 head = head->pre = new tlp::BmdLink<TYPE>(data, NULL, head); 00121 else 00122 head = head->suc = new tlp::BmdLink<TYPE>(data, NULL, head); 00123 } 00124 else 00125 head = tail = new tlp::BmdLink<TYPE>(data, NULL, NULL); 00126 00127 return head; 00128 } 00129 //================================================================= 00130 template <typename TYPE> 00131 tlp::BmdLink<TYPE> *tlp::BmdList<TYPE>::append(const TYPE &data) { 00132 count++; 00133 00134 if (tail != NULL) { 00135 if (tail->pre != NULL) 00136 tail = tail->suc = new tlp::BmdLink<TYPE>(data, tail, NULL); 00137 else 00138 tail = tail->pre = new tlp::BmdLink<TYPE>(data, tail, NULL); 00139 00140 } 00141 else { 00142 tail = head = new tlp::BmdLink<TYPE>(data, NULL, NULL); 00143 } 00144 00145 return tail; 00146 } 00147 //================================================================= 00148 template <typename TYPE> 00149 TYPE tlp::BmdList<TYPE>::delItem(tlp::BmdLink<TYPE> *it) { 00150 assert(it != NULL); 00151 00152 if (it == head) 00153 return pop(); 00154 00155 if (it == tail) 00156 return popBack(); 00157 00158 tlp::BmdLink<TYPE> *p = predItem(it, NULL); 00159 tlp::BmdLink<TYPE> *s = nextItem(it, p); 00160 TYPE x = it->data; 00161 00162 if (p->pre == it) 00163 p->pre = s; 00164 else 00165 p->suc = s; 00166 00167 if (s->suc == it) 00168 s->suc = p; 00169 else 00170 s->pre = p; 00171 00172 count--; 00173 delete it; 00174 return x; 00175 } 00176 //================================================================= 00177 template <typename TYPE> 00178 TYPE tlp::BmdList<TYPE>::pop() { 00179 assert(head != NULL); 00180 tlp::BmdLink<TYPE> *x = head; 00181 head = nextItem(head, NULL); 00182 00183 if (head) { 00184 if (head->suc == x) 00185 head->suc = NULL; 00186 else 00187 head->pre = NULL; 00188 } 00189 else 00190 tail = NULL; 00191 00192 TYPE p = x->data; 00193 delete x; 00194 count--; 00195 return p; 00196 } 00197 //================================================================= 00198 template <typename TYPE> 00199 TYPE tlp::BmdList<TYPE>::popBack() { 00200 assert(head != NULL); 00201 tlp::BmdLink<TYPE> *x= tail; 00202 tail = predItem(tail, NULL); 00203 00204 if (tail) { 00205 if (tail->pre == x) 00206 tail->pre = NULL; 00207 else 00208 tail->suc = NULL; 00209 } 00210 else 00211 head = NULL; 00212 00213 TYPE p = x->data; 00214 delete x; 00215 count--; 00216 return p; 00217 } 00218 //================================================================= 00219 template <typename TYPE> 00220 void tlp::BmdList<TYPE>::reverse() { 00221 tlp::BmdLink<TYPE> *x = head; 00222 head = tail; 00223 tail = x; 00224 } 00225 //================================================================= 00226 template <typename TYPE> 00227 void tlp::BmdList<TYPE>::conc(tlp::BmdList<TYPE> &l) { 00228 if (head == NULL) { 00229 head = l.head; 00230 tail = l.tail; 00231 } 00232 else { 00233 if (tail->pre == NULL) 00234 tail->pre = l.head; 00235 else 00236 tail->suc = l.head; 00237 00238 if (l.head) { 00239 if (l.head->suc == NULL) 00240 l.head->suc = tail; 00241 else 00242 l.head->pre = tail; 00243 00244 tail = l.tail; 00245 } 00246 } 00247 00248 count += l.count; 00249 l.head = l.tail = NULL; 00250 l.count = 0; 00251 } 00252 //================================================================= 00253 template <typename TYPE> 00254 void tlp::BmdList<TYPE>::clear() { 00255 if (head == NULL) return; 00256 00257 tlp::BmdLink<TYPE> *it = head; 00258 tlp::BmdLink<TYPE> *p = head; 00259 00260 for (int i = 0 ; i < count ; i++) { 00261 tlp::BmdLink<TYPE> *x = it; 00262 it = nextItem(it, p); 00263 00264 if (p != x) 00265 delete p; 00266 00267 p = x; 00268 } 00269 00270 delete p; 00271 count = 0; 00272 head = tail = NULL; 00273 } 00274 //================================================================= 00275 template <typename TYPE> 00276 void tlp::BmdList<TYPE>::swap(tlp::BmdList<TYPE>& l) { 00277 tlp::BmdLink<TYPE> *tmp; 00278 int tmp1; 00279 tmp = l.head; 00280 l.head = head; 00281 head = tmp; 00282 tmp = l.tail; 00283 l.tail = tail; 00284 tail = tmp; 00285 tmp1 = l.count; 00286 l.count = count; 00287 count = tmp1; 00288 } 00289 //=================================================================