Tulip  4.6.0
Better Visualization Through Research
library/tulip-core/include/tulip/cxx/BmdList.cxx
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 //=================================================================
 All Classes Files Functions Variables Enumerations Enumerator Properties