00001 00002 // 00003 // FreeLing - Open Source Language Analyzers 00004 // 00005 // Copyright (C) 2004 TALP Research Center 00006 // Universitat Politecnica de Catalunya 00007 // 00008 // This library is free software; you can redistribute it and/or 00009 // modify it under the terms of the GNU Lesser General Public 00010 // License as published by the Free Software Foundation; either 00011 // version 2.1 of the License, or (at your option) any later version. 00012 // 00013 // This library 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. See the GNU 00016 // Lesser General Public License for more details. 00017 // 00018 // You should have received a copy of the GNU Lesser General Public 00019 // License along with this library; if not, write to the Free Software 00020 // Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA 00021 // 00022 // contact: Lluis Padro (padro@lsi.upc.es) 00023 // TALP Research Center 00024 // despatx C6.212 - Campus Nord UPC 00025 // 08034 Barcelona. SPAIN 00026 // 00028 00029 #ifndef _TREE_TEMPLATE 00030 #define _TREE_TEMPLATE 00031 00032 00033 template <class T> 00034 class tree { 00035 00036 private: 00037 bool isempty; 00038 tree *parent; // parent node 00039 tree *first,*last; // first/last child 00040 tree *prev,*next; // prev/next sibling 00041 void clone(const tree<T>&); 00042 00043 public: 00044 T info; 00045 class generic_iterator; 00046 class preorder_iterator; 00047 // class const_preorder_iterator; 00048 class sibling_iterator; 00049 // class const_sibling_iterator; 00050 typedef preorder_iterator iterator; 00051 //typedef const_preorder_iterator const_iterator; 00052 00053 tree(); 00054 tree(const T&); 00055 tree(const tree<T>&); 00056 tree(const preorder_iterator&); 00057 ~tree(); 00058 tree<T>& operator=(const tree<T>&); 00059 00060 unsigned int num_children() const; 00061 sibling_iterator nth_child(unsigned int) const; 00062 void append_child(const tree<T> &); 00063 void hang_child(tree<T> &); 00064 void clear(); 00065 bool empty() const; 00066 00067 sibling_iterator sibling_begin(); 00068 //const_sibling_iterator sibling_begin() const; 00069 sibling_iterator sibling_end() const; 00070 00071 preorder_iterator begin(); 00072 // const_preorder_iterator begin() const; 00073 preorder_iterator end() const; 00074 00075 class generic_iterator { 00076 protected: 00077 tree *pnode; 00078 public: 00079 generic_iterator(); 00080 generic_iterator(tree *); 00081 tree<T>& operator*() const; 00082 tree<T>* operator->() const; 00083 bool operator==(const generic_iterator &) const; 00084 bool operator!=(const generic_iterator &) const; 00085 }; 00086 00088 class preorder_iterator : public generic_iterator { 00089 public: 00090 preorder_iterator(); 00091 preorder_iterator(tree *); 00092 preorder_iterator(sibling_iterator&); 00093 00094 preorder_iterator& operator++(); 00095 preorder_iterator& operator--(); 00096 preorder_iterator& operator+=(unsigned int); 00097 preorder_iterator& operator-=(unsigned int); 00098 }; 00099 00100 /* class const_preorder_iterator : public generic_iterator { */ 00101 /* public: */ 00102 /* const_preorder_iterator(); */ 00103 /* const_preorder_iterator(const tree *); */ 00104 /* const_preorder_iterator(const const_sibling_iterator &); */ 00105 00106 /* const_preorder_iterator& operator++(); */ 00107 /* const_preorder_iterator& operator--(); */ 00108 /* const_preorder_iterator& operator+=(unsigned int); */ 00109 /* const_preorder_iterator& operator-=(unsigned int); */ 00110 /* }; */ 00111 00113 class sibling_iterator : public generic_iterator { 00114 friend class preorder_iterator; 00115 public: 00116 sibling_iterator(); 00117 sibling_iterator(tree *); 00118 00119 sibling_iterator& operator++(); 00120 sibling_iterator& operator--(); 00121 sibling_iterator& operator+=(unsigned int); 00122 sibling_iterator& operator-=(unsigned int); 00123 }; 00124 00125 /* class const_sibling_iterator : public generic_iterator { */ 00126 /* friend class const_preorder_iterator; */ 00127 /* public: */ 00128 /* const_sibling_iterator(); */ 00129 /* const_sibling_iterator(const tree *); */ 00130 00131 /* const_sibling_iterator& operator++(); */ 00132 /* const_sibling_iterator& operator--(); */ 00133 /* const_sibling_iterator& operator+=(unsigned int); */ 00134 /* const_sibling_iterator& operator-=(unsigned int); */ 00135 /* }; */ 00136 }; 00137 00138 00140 00142 00143 template <class T> 00144 tree<T>::tree() { 00145 isempty = true; 00146 parent=NULL; 00147 first=NULL; last=NULL; 00148 prev=NULL; next=NULL; 00149 } 00150 00151 00153 00154 template <class T> 00155 tree<T>::tree(const T &x) : info(x) { 00156 isempty = false; 00157 parent=NULL; 00158 first=NULL; last=NULL; 00159 prev=NULL; next=NULL; 00160 } 00161 00163 00164 template <class T> 00165 tree<T>::tree(const tree<T>::preorder_iterator &p) { 00166 clone(*p); 00167 } 00168 00170 00171 template <class T> 00172 tree<T>::tree(const tree<T>& t) { 00173 clone(t); 00174 } 00175 00176 00178 00179 template <class T> 00180 tree<T>& tree<T>::operator=(const tree<T>& t) { 00181 if (this != &t) { 00182 clone(t); 00183 } 00184 return (*this); 00185 } 00186 00188 00189 template <class T> 00190 tree<T>::~tree() { 00191 for (tree* p=this->first; p!=NULL; p=p->next) p->~tree(); 00192 } 00193 00194 template <class T> 00195 void tree<T>::clear() { 00196 00197 // delete children 00198 for (tree* p=this->first; p!=NULL; p=p->next) p->~tree(); 00199 00200 // reset root node 00201 isempty = true; 00202 parent=NULL; 00203 first=NULL; last=NULL; 00204 prev=NULL; next=NULL; 00205 00206 } 00207 00209 00210 template <class T> 00211 unsigned int tree<T>::num_children() const { 00212 tree *s; 00213 unsigned int n=0; 00214 for (s=this->first; s!=NULL; s=s->next) n++; 00215 return n; 00216 } 00217 00219 00220 template <class T> 00221 typename tree<T>::sibling_iterator tree<T>::nth_child(unsigned int n) const { 00222 sibling_iterator i = this->first; 00223 while (n>0 && i!=NULL) { 00224 i = i->next; 00225 n--; 00226 } 00227 return i; 00228 } 00229 00231 00232 template <class T> 00233 bool tree<T>::empty() const { 00234 return isempty; 00235 } 00236 00238 00239 template <class T> 00240 typename tree<T>::sibling_iterator tree<T>::sibling_begin() { 00241 return sibling_iterator(this->first); 00242 } 00243 00244 /* template <class T> */ 00245 /* typename tree<T>::const_sibling_iterator tree<T>::sibling_begin() const { */ 00246 /* return const_sibling_iterator(this->first); */ 00247 /* } */ 00248 00249 template <class T> 00250 typename tree<T>::sibling_iterator tree<T>::sibling_end() const { 00251 return sibling_iterator(NULL); 00252 } 00253 00255 00256 template <class T> 00257 typename tree<T>::preorder_iterator tree<T>::begin() { 00258 return preorder_iterator(this); 00259 } 00260 00261 /* template <class T> */ 00262 /* typename tree<T>::const_preorder_iterator tree<T>::begin() const { */ 00263 /* return const_preorder_iterator(this); */ 00264 /* } */ 00265 00266 template <class T> 00267 typename tree<T>::preorder_iterator tree<T>::end() const { 00268 return preorder_iterator(NULL); 00269 } 00270 00272 00273 template <class T> 00274 void tree<T>::append_child(const tree<T>& child) { 00275 00276 // make a copy 00277 tree<T> *x = new tree<T>; 00278 x->clone(child); 00279 00280 x->next = NULL; x->prev = NULL; 00281 x->parent = this; 00282 00283 if (this->first != NULL) { // there are already children, join them 00284 x->prev = this->last; 00285 this->last->next = x; 00286 this->last = x; 00287 } 00288 else { 00289 // no children, new is the only one 00290 this->first = x; this->last = x; 00291 } 00292 } 00293 00295 00296 template <class T> 00297 void tree<T>::hang_child(tree<T>& child) { 00298 00299 child.next = NULL; 00300 child.prev = NULL; 00301 child.parent = this; 00302 00303 if (this->first != NULL) { // there are already children, join them 00304 child.prev = this->last; 00305 this->last->next = &child; 00306 this->last = &child; 00307 } 00308 else { 00309 // no children, new is the only one 00310 this->first = &child; 00311 this->last = &child; 00312 } 00313 } 00314 00316 00317 template <class T> 00318 void tree<T>::clone(const tree<T>& t) { 00319 00320 this->info = t.info; 00321 this->parent = NULL; 00322 this->first = NULL; 00323 this->last = NULL; 00324 this->prev=NULL; 00325 this->next=NULL; 00326 00327 for (tree* p=t.first; p!=NULL; p=p->next) { 00328 00329 tree<T>* c = new tree<T>; 00330 c->clone(*p); 00331 c->next = NULL; 00332 c->prev = NULL; 00333 c->parent = this; 00334 00335 if (this->first != NULL) { 00336 c->prev = this->last; 00337 this->last->next = c; 00338 this->last = c; 00339 } 00340 else { 00341 this->first = c; 00342 this->last = c; 00343 } 00344 } 00345 } 00346 00347 00349 00350 template <class T> 00351 tree<T>::generic_iterator::generic_iterator() {pnode = NULL;} 00352 00353 template <class T> 00354 tree<T>::generic_iterator::generic_iterator(tree *t) {pnode = t;} 00355 00356 template <class T> 00357 tree<T>& tree<T>::generic_iterator::operator*() const {return (*pnode);} 00358 00359 template <class T> 00360 tree<T>* tree<T>::generic_iterator::operator->() const {return pnode;} 00361 00362 template <class T> 00363 bool tree<T>::generic_iterator::operator==(const generic_iterator &t) const {return (t.pnode==this->pnode); } 00364 00365 template <class T> 00366 bool tree<T>::generic_iterator::operator!=(const generic_iterator &t) const {return (t.pnode!=this->pnode); } 00367 00368 00369 00370 00372 00373 template <class T> 00374 tree<T>::preorder_iterator::preorder_iterator() : generic_iterator() {} 00375 00376 template <class T> 00377 tree<T>::preorder_iterator::preorder_iterator(tree *t) : generic_iterator(t) {} 00378 00379 template <class T> 00380 tree<T>::preorder_iterator::preorder_iterator(sibling_iterator &t) : generic_iterator(t) {} 00381 00382 template <class T> 00383 typename tree<T>::preorder_iterator& tree<T>::preorder_iterator::operator++() { 00384 if (this->pnode->first != NULL) 00385 this->pnode=this->pnode->first; 00386 else { 00387 while (this->pnode!=NULL && this->pnode->next==NULL) 00388 this->pnode=this->pnode->parent; 00389 if (this->pnode!=NULL) this->pnode=this->pnode->next; 00390 } 00391 return *this; 00392 } 00393 00394 template <class T> 00395 typename tree<T>::preorder_iterator& tree<T>::preorder_iterator::operator--() { 00396 if (this->pnode->prev!=NULL) { 00397 this->pnode=this->pnode->prev; 00398 while (this->pnode->last != NULL) 00399 this->pnode=this->pnode->last; 00400 } 00401 else 00402 this->pnode = this->pnode->parent; 00403 00404 return *this; 00405 } 00406 00407 template <class T> 00408 typename tree<T>::preorder_iterator& tree<T>::preorder_iterator::operator+=(unsigned int n) { 00409 for (; n>0; n--) ++(*this); 00410 return *this; 00411 } 00412 00413 template <class T> 00414 typename tree<T>::preorder_iterator& tree<T>::preorder_iterator::operator-=(unsigned int n) { 00415 for (; n>0; n--) --(*this); 00416 return *this; 00417 } 00418 00420 00421 /* template <class T> */ 00422 /* tree<T>::const_preorder_iterator::const_preorder_iterator() : generic_iterator() {} */ 00423 00424 /* template <class T> */ 00425 /* tree<T>::const_preorder_iterator::const_preorder_iterator(const tree *t) : generic_iterator(t) {} */ 00426 00427 /* template <class T> */ 00428 /* tree<T>::const_preorder_iterator::const_preorder_iterator(const const_sibling_iterator &t) : generic_iterator(t) {} */ 00429 00430 /* template <class T> */ 00431 /* typename tree<T>::const_preorder_iterator& tree<T>::const_preorder_iterator::operator++() { */ 00432 /* if (this->pnode->first != NULL) */ 00433 /* this->pnode=this->pnode->first; */ 00434 /* else { */ 00435 /* while (this->pnode!=NULL && this->pnode->next==NULL) */ 00436 /* this->pnode=this->pnode->parent; */ 00437 /* if (this->pnode!=NULL) this->pnode=this->pnode->next; */ 00438 /* } */ 00439 /* return *this; */ 00440 /* } */ 00441 00442 /* template <class T> */ 00443 /* typename tree<T>::const_preorder_iterator& tree<T>::const_preorder_iterator::operator--() { */ 00444 /* if (this->pnode->prev!=NULL) { */ 00445 /* this->pnode=this->pnode->prev; */ 00446 /* while (this->pnode->last != NULL) */ 00447 /* this->pnode=this->pnode->last; */ 00448 /* } */ 00449 /* else */ 00450 /* this->pnode = this->pnode->parent; */ 00451 00452 /* return *this; */ 00453 /* } */ 00454 00455 /* template <class T> */ 00456 /* typename tree<T>::const_preorder_iterator& tree<T>::const_preorder_iterator::operator+=(unsigned int n) { */ 00457 /* for (; n>0; n--) ++(*this); */ 00458 /* return *this; */ 00459 /* } */ 00460 00461 /* template <class T> */ 00462 /* typename tree<T>::const_preorder_iterator& tree<T>::const_preorder_iterator::operator-=(unsigned int n) { */ 00463 /* for (; n>0; n--) --(*this); */ 00464 /* return *this; */ 00465 /* } */ 00466 00467 00469 00470 template <class T> 00471 tree<T>::sibling_iterator::sibling_iterator() : generic_iterator() {} 00472 00473 template <class T> 00474 tree<T>::sibling_iterator::sibling_iterator(tree *t) : generic_iterator(t) {} 00475 00476 template <class T> 00477 typename tree<T>::sibling_iterator& tree<T>::sibling_iterator::operator++() { 00478 this->pnode = this->pnode->next; 00479 return *this; 00480 } 00481 00482 template <class T> 00483 typename tree<T>::sibling_iterator& tree<T>::sibling_iterator::operator--() { 00484 this->pnode = this->pnode->prev; 00485 return *this; 00486 } 00487 00488 template <class T> 00489 typename tree<T>::sibling_iterator& tree<T>::sibling_iterator::operator+=(unsigned int n) { 00490 for (; n>0; n--) ++(*this); 00491 return *this; 00492 } 00493 00494 template <class T> 00495 typename tree<T>::sibling_iterator& tree<T>::sibling_iterator::operator-=(unsigned int n) { 00496 for (; n>0; n--) --(*this); 00497 return *this; 00498 } 00499 00500 00502 00503 /* template <class T> */ 00504 /* tree<T>::const_sibling_iterator::const_sibling_iterator() : generic_iterator() {} */ 00505 00506 /* template <class T> */ 00507 /* tree<T>::const_sibling_iterator::const_sibling_iterator(const tree *t) : generic_iterator(t) {} */ 00508 00509 /* template <class T> */ 00510 /* typename tree<T>::const_sibling_iterator& tree<T>::const_sibling_iterator::operator++() { */ 00511 /* this->pnode = this->pnode->next; */ 00512 /* return *this; */ 00513 /* } */ 00514 00515 /* template <class T> */ 00516 /* typename tree<T>::const_sibling_iterator& tree<T>::const_sibling_iterator::operator--() { */ 00517 /* this->pnode = this->pnode->prev; */ 00518 /* return *this; */ 00519 /* } */ 00520 00521 /* template <class T> */ 00522 /* typename tree<T>::const_sibling_iterator& tree<T>::const_sibling_iterator::operator+=(unsigned int n) { */ 00523 /* for (; n>0; n--) ++(*this); */ 00524 /* return *this; */ 00525 /* } */ 00526 00527 /* template <class T> */ 00528 /* typename tree<T>::const_sibling_iterator& tree<T>::const_sibling_iterator::operator-=(unsigned int n) { */ 00529 /* for (; n>0; n--) --(*this); */ 00530 /* return *this; */ 00531 /* } */ 00532 00533 #endif 00534