Main Page | Namespace List | Class Hierarchy | Alphabetical List | Class List | Directories | File List | Class Members | File Members

tree.h

Go to the documentation of this file.
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 

Generated on Wed Apr 26 12:55:30 2006 for FreeLing by  doxygen 1.4.4