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

CTree.h

Go to the documentation of this file.
00001 /*
00002  * CTree.h
00003  * $Id: CTree.h,v 1.10 2001/11/23 02:03:35 mjanich 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 #include <iostream.h>
00044 
00045 
00046 // forward declarations
00048 class CTreeTraverserBase;
00049 
00050 
00051 
00054 class CTreeNode {
00055 public:
00056 
00057   enum Where { Front, End }; 
00060   CTreeNode() 
00061     : m_pcParent(0)
00062     {
00063 #ifdef DEBUG_TREE
00064       cerr << "called CTreeNode<NodeDataType>::CTreeNode()" << endl;
00065 #endif
00066       /* nothing to do */};
00067 
00068 
00070   CTreeNode(const CTreeNode &cSource);
00071 
00073   virtual ~CTreeNode();
00074 
00075 
00078   virtual CTreeNode *append(CTreeNode *pcNode, Where w=End) {
00079     return append(this, pcNode, w);
00080   };
00081 
00085   virtual CTreeNode *append(CTreeNode *pcWhere,
00086                             CTreeNode *pcAppend, Where w=End) {
00087     if (pcWhere) {
00088       switch (w) {
00089       case End: 
00090         pcWhere->m_cChildrenList.insertAsLast(pcAppend);
00091         break;
00092       case Front:
00093         pcWhere->m_cChildrenList.insertAsFirst(pcAppend);
00094         break;
00095       }
00096       pcAppend->m_pcParent = pcWhere;
00097 
00098       return pcAppend;
00099     }
00100     return 0;
00101   };
00102 
00106   virtual CTreeNode *insert(CTreeNode *pcWhere,
00107                             CTreeNode *pcInsert);
00108 
00109 
00110   // FIXME: conflicts with traversers
00112   /** Remove the specified node from the tree. */
00113   virtual void remove(CTreeNode *pcRemove);
00114 
00116   virtual void remove(CTreeTraverserBase *pcTraverser);
00117 
00120   virtual void replace(CTreeNode *pcReplace, CTreeNode *pcWith);
00121 
00123   virtual CTreeNode *getParent() const { return m_pcParent; };
00124 
00126   virtual int numChildren() const {
00127     return m_cChildrenList.getNumObjects();
00128   };
00129 
00131   virtual const CList<CTreeNode> &getChildrenList() const {
00132     return m_cChildrenList;
00133   }
00134 
00136   virtual CTreeNode &operator=(const CTreeNode &cSource);
00137 
00141   virtual CTreeNode &operator[](int i) const;
00142 
00144   virtual bool isEqual(const CTreeNode *pcNode) const; 
00145 
00147   virtual void printTree(ostream &out=cout) const;
00148 
00149   friend ostream& operator<<(ostream &out, CTreeNode *pcTreeNode);
00150 
00151 
00152 protected:
00153 
00155   virtual void print(ostream &out) const;
00156 
00157 
00159   // DATA  //
00161 
00162   CTreeNode *m_pcParent;
00163   CList<CTreeNode> m_cChildrenList;
00164 };
00165 
00166 
00167 
00171 
00172 
00173 
00177 class CTreeTraverserBase {
00178   friend class CTreeNode;
00179 
00180 public:
00181 
00182   CTreeTraverserBase() {};
00183   CTreeTraverserBase(CTreeNode *) {};
00184   virtual ~CTreeTraverserBase() {};
00185 
00186   virtual bool atStart() = 0;
00187   virtual bool atEnd() = 0;
00188 
00189   virtual const CTreeNode *operator++() = 0;
00190   virtual const CTreeNode *operator++(int dummy) = 0;
00191 
00192   //virtual const CTreeNode *operator--() = 0;
00193   //virtual const CTreeNode *operator--(int dummy) = 0;
00194 
00195   virtual CTreeNode *operator*() = 0;
00196 
00197 
00198 protected:
00199 
00200   virtual CTreeNode *getCurrentNode() const = 0;
00201   virtual void removeCurrentNode() = 0;
00202 };
00203 
00204 
00205 
00210 
00211 // FIXME:: They better should do their work directly
00212 //         on the data of the tree instead of making
00213 //         a list
00214 
00217 class CDepthFirstTraverser : public CTreeTraverserBase {
00218 public:
00219 
00220   CDepthFirstTraverser(CTreeNode *pcNode);
00221   virtual ~CDepthFirstTraverser() {};
00222 
00223   virtual bool atStart();
00224   virtual bool atEnd();
00225 
00226   virtual const CTreeNode *operator++();
00227   virtual const CTreeNode *operator++(int dummy);
00228 
00229   //virtual const CTreeNode *operator--();
00230   //virtual const CTreeNode *operator--(int dummy);
00231 
00232   virtual CTreeNode *operator*() {
00233     return getCurrentNode();
00234   }
00235 
00236 
00237 protected:
00238 
00239   virtual CTreeNode *getCurrentNode() const;
00240   virtual void removeCurrentNode();
00241 
00242 
00243 private:
00244 
00245   void parseSubTree(CTreeNode *pcNode);
00246 
00247   CList<CTreeNode> m_cNodeList;
00248   CListContainer<CTreeNode> *m_pcCurrentNode;
00249   bool m_fAtEnd, m_fAtStart;
00250   int m_nLastOp;  // 0: ++, 1: --
00251 };
00252 
00253 
00254 
00257 class CBreathFirstTraverser : public CTreeTraverserBase {
00258 public:
00259 
00260   CBreathFirstTraverser(CTreeNode *pcNode);
00261   virtual ~CBreathFirstTraverser() {};
00262 
00263   virtual bool atStart();
00264   virtual bool atEnd();
00265 
00266   virtual const CTreeNode *operator++();
00267   virtual const CTreeNode *operator++(int dummy);
00268 
00269   //virtual const CTreeNode *operator--();
00270   //virtual const CTreeNode *operator--(int dummy);
00271 
00272   virtual CTreeNode *operator*() {
00273     return getCurrentNode();
00274   }
00275 
00276 
00277 protected:
00278 
00279   virtual CTreeNode *getCurrentNode() const;
00280   virtual void removeCurrentNode();
00281 
00282 
00283 private:
00284 
00285   CList<CTreeNode> m_cNodeList;
00286   CListContainer<CTreeNode> *m_pcCurrentNode;
00287   bool m_fAtEnd, m_fAtStart;
00288   int m_nLastOp;  // 0: ++, 1: --
00289 };
00290 
00291 
00292 #endif // CTREE_H

Generated on Wed Mar 5 18:23:25 2003 for QGLViewer by doxygen1.3-rc3