00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032 #ifndef CTREE_H
00033 #define CTREE_H
00034
00035
00036
00038 #include "CList.h"
00039
00040
00041
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
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 };
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
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
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
00199
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
00218
00219
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
00236
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;
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
00276
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;
00295 };
00296
00297
00298 #endif // CTREE_H