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
00039
00040
00041
00043
00044
00045
00046
00048
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 };
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
00112
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
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
00193
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
00212
00213
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
00230
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;
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
00270
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;
00289 };
00290
00291
00292 #endif // CTREE_H