Main Page | Namespace List | Class Hierarchy | Alphabetical List | Class List | File List | Namespace Members | Class Members | File Members | Related Pages

CTree.h

Go to the documentation of this file.
00001 /*
00002  * CTree.h
00003  * $Id: CTree.h,v 1.11 2003/06/24 14:50:02 anxo Exp $
00004  *
00005  * Copyright (C) 2001 Markus Janich
00006  *
00007  * This program is free software; you can redistribute it and/or modify
00008  * it under the terms of the GNU General Public License as published by
00009  * the Free Software Foundation; either version 2 of the License, or
00010  * (at your option) any later version.
00011  *
00012  * This program is distributed in the hope that it will be useful,
00013  * but WITHOUT ANY WARRANTY; without even the implied warranty of
00014  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00015  * GNU General Public License for more details.
00016  *
00017  * You should have received a copy of the GNU General Public License
00018  * along with this program; if not, write to the Free Software
00019  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
00020  *
00021  * As a special exception to the GPL, the QGLViewer authors (Markus
00022  * Janich, Michael Meissner, Richard Guenther, Alexander Buck and Thomas
00023  * Woerner) give permission to link this program with Qt (non-)commercial
00024  * edition, and distribute the resulting executable, without including
00025  * the source code for the Qt (non-)commercial edition in the source
00026  * distribution.
00027  *
00028  */
00029 
00030 
00031 
00032 #ifndef CTREE_H
00033 #define CTREE_H
00034 
00035 
00036 // Own
00038 #include "CList.h"
00039 
00040 
00041 // System
00043 #ifdef _MSC_VER
00044 #if _MSC_VER >= 1300
00045 #include <iostream>
00046 #endif
00047 #else
00048 #include <iostream.h>
00049 #endif
00050 
00051 
00052 // forward declarations
00054 class CTreeTraverserBase;
00055 
00056 using namespace std;
00057 
00060 class CTreeNode {
00061 public:
00062 
00063   enum Where { Front, End }; 
00066   CTreeNode() 
00067     : m_pcParent(0)
00068     {
00069 #ifdef DEBUG_TREE
00070       cerr << "called CTreeNode<NodeDataType>::CTreeNode()" << endl;
00071 #endif
00072       /* nothing to do */};
00073 
00074 
00076   CTreeNode(const CTreeNode &cSource);
00077 
00079   virtual ~CTreeNode();
00080 
00081 
00084   virtual CTreeNode *append(CTreeNode *pcNode, Where w=End) {
00085     return append(this, pcNode, w);
00086   };
00087 
00091   virtual CTreeNode *append(CTreeNode *pcWhere,
00092                             CTreeNode *pcAppend, Where w=End) {
00093     if (pcWhere) {
00094       switch (w) {
00095       case End: 
00096         pcWhere->m_cChildrenList.insertAsLast(pcAppend);
00097         break;
00098       case Front:
00099         pcWhere->m_cChildrenList.insertAsFirst(pcAppend);
00100         break;
00101       }
00102       pcAppend->m_pcParent = pcWhere;
00103 
00104       return pcAppend;
00105     }
00106     return 0;
00107   };
00108 
00112   virtual CTreeNode *insert(CTreeNode *pcWhere,
00113                             CTreeNode *pcInsert);
00114 
00115 
00116   // FIXME: conflicts with traversers
00118 
00119   virtual void remove(CTreeNode *pcRemove);
00120 
00122   virtual void remove(CTreeTraverserBase *pcTraverser);
00123 
00126   virtual void replace(CTreeNode *pcReplace, CTreeNode *pcWith);
00127 
00129   virtual CTreeNode *getParent() const { return m_pcParent; };
00130 
00132   virtual int numChildren() const {
00133     return m_cChildrenList.getNumObjects();
00134   };
00135 
00137   virtual const CList<CTreeNode> &getChildrenList() const {
00138     return m_cChildrenList;
00139   }
00140 
00142   virtual CTreeNode &operator=(const CTreeNode &cSource);
00143 
00147   virtual CTreeNode &operator[](int i) const;
00148 
00150   virtual bool isEqual(const CTreeNode *pcNode) const; 
00151 
00153   virtual void printTree(ostream &out=cout) const;
00154 
00155   friend ostream& operator<<(ostream &out, CTreeNode *pcTreeNode);
00156 
00157 
00158 protected:
00159 
00161   virtual void print(ostream &out) const;
00162 
00163 
00165   // DATA  //
00167 
00168   CTreeNode *m_pcParent;
00169   CList<CTreeNode> m_cChildrenList;
00170 };
00171 
00172 
00173 
00177 
00178 
00179 
00183 class CTreeTraverserBase {
00184   friend class CTreeNode;
00185 
00186 public:
00187 
00188   CTreeTraverserBase() {};
00189   CTreeTraverserBase(CTreeNode *) {};
00190   virtual ~CTreeTraverserBase() {};
00191 
00192   virtual bool atStart() = 0;
00193   virtual bool atEnd() = 0;
00194 
00195   virtual const CTreeNode *operator++() = 0;
00196   virtual const CTreeNode *operator++(int dummy) = 0;
00197 
00198   //virtual const CTreeNode *operator--() = 0;
00199   //virtual const CTreeNode *operator--(int dummy) = 0;
00200 
00201   virtual CTreeNode *operator*() = 0;
00202 
00203 
00204 protected:
00205 
00206   virtual CTreeNode *getCurrentNode() const = 0;
00207   virtual void removeCurrentNode() = 0;
00208 };
00209 
00210 
00211 
00216 
00217 // FIXME:: They better should do their work directly
00218 //         on the data of the tree instead of making
00219 //         a list
00220 
00223 class CDepthFirstTraverser : public CTreeTraverserBase {
00224 public:
00225 
00226   CDepthFirstTraverser(CTreeNode *pcNode);
00227   virtual ~CDepthFirstTraverser() {};
00228 
00229   virtual bool atStart();
00230   virtual bool atEnd();
00231 
00232   virtual const CTreeNode *operator++();
00233   virtual const CTreeNode *operator++(int dummy);
00234 
00235   //virtual const CTreeNode *operator--();
00236   //virtual const CTreeNode *operator--(int dummy);
00237 
00238   virtual CTreeNode *operator*() {
00239     return getCurrentNode();
00240   }
00241 
00242 
00243 protected:
00244 
00245   virtual CTreeNode *getCurrentNode() const;
00246   virtual void removeCurrentNode();
00247 
00248 
00249 private:
00250 
00251   void parseSubTree(CTreeNode *pcNode);
00252 
00253   CList<CTreeNode> m_cNodeList;
00254   CListContainer<CTreeNode> *m_pcCurrentNode;
00255   bool m_fAtEnd, m_fAtStart;
00256   int m_nLastOp;  // 0: ++, 1: --
00257 };
00258 
00259 
00260 
00263 class CBreathFirstTraverser : public CTreeTraverserBase {
00264 public:
00265 
00266   CBreathFirstTraverser(CTreeNode *pcNode);
00267   virtual ~CBreathFirstTraverser() {};
00268 
00269   virtual bool atStart();
00270   virtual bool atEnd();
00271 
00272   virtual const CTreeNode *operator++();
00273   virtual const CTreeNode *operator++(int dummy);
00274 
00275   //virtual const CTreeNode *operator--();
00276   //virtual const CTreeNode *operator--(int dummy);
00277 
00278   virtual CTreeNode *operator*() {
00279     return getCurrentNode();
00280   }
00281 
00282 
00283 protected:
00284 
00285   virtual CTreeNode *getCurrentNode() const;
00286   virtual void removeCurrentNode();
00287 
00288 
00289 private:
00290 
00291   CList<CTreeNode> m_cNodeList;
00292   CListContainer<CTreeNode> *m_pcCurrentNode;
00293   bool m_fAtEnd, m_fAtStart;
00294   int m_nLastOp;  // 0: ++, 1: --
00295 };
00296 
00297 
00298 #endif // CTREE_H

Generated on Tue Oct 21 02:54:54 2003 for QGLViewer by doxygen 1.3.4