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 #ifndef CTREE_H
00026 #define CTREE_H
00027
00028
00029
00031
00032
00033
00034
00036
00037
00038
00039
00041
00042
00043
00044
00047 class CTreeNode {
00048 public:
00049
00050 enum Where { Front, End };
00053 CTreeNode()
00054 : m_pcParent(0)
00055 {
00056 #ifdef DEBUG_TREE
00057 cerr << "called CTreeNode<NodeDataType>::CTreeNode()" << endl;
00058 #endif
00059 };
00060
00061
00063 CTreeNode(const CTreeNode &cSource);
00064
00066 virtual ~CTreeNode();
00067
00068
00071 virtual CTreeNode *append(CTreeNode *pcNode, Where w=End) {
00072 return append(this, pcNode, w);
00073 };
00074
00078 virtual CTreeNode *append(CTreeNode *pcWhere,
00079 CTreeNode *pcAppend, Where w=End) {
00080 if (pcWhere) {
00081 switch (w) {
00082 case End:
00083 pcWhere->m_cChildrenList.insertAsLast(pcAppend);
00084 break;
00085 case Front:
00086 pcWhere->m_cChildrenList.insertAsFirst(pcAppend);
00087 break;
00088 }
00089 pcAppend->m_pcParent = pcWhere;
00090
00091 return pcAppend;
00092 }
00093 return 0;
00094 };
00095
00099 virtual CTreeNode *insert(CTreeNode *pcWhere,
00100 CTreeNode *pcInsert);
00101
00102
00103
00105
00106 virtual void remove(CTreeNode *pcRemove);
00107
00109 virtual void remove(CTreeTraverserBase *pcTraverser);
00110
00111
00113 virtual CTreeNode *getParent() const { return m_pcParent; };
00114
00116 virtual int numChildren() const {
00117 return m_cChildrenList.getNumObjects();
00118 };
00119
00121 virtual const CList<CTreeNode> &getChildrenList() const {
00122 return m_cChildrenList;
00123 }
00124
00126 virtual CTreeNode &operator=(const CTreeNode &cSource);
00127
00131 virtual CTreeNode &operator[](int i) const;
00132
00134 virtual bool isEqual(const CTreeNode *pcNode) const;
00135
00137 virtual void printTree(ostream &out=cout) const;
00138
00139 friend ostream& operator<<(ostream &out, CTreeNode *pcTreeNode);
00140
00141
00142 protected:
00143
00145 virtual void print(ostream &out) const;
00146
00147
00149
00151
00152 CTreeNode *m_pcParent;
00153 CList<CTreeNode> m_cChildrenList;
00154 };
00155
00156
00157
00161
00162
00163
00167 class CTreeTraverserBase {
00168 friend class CTreeNode;
00169
00170 public:
00171
00172 CTreeTraverserBase() {};
00173 CTreeTraverserBase(CTreeNode *pcNode) {};
00174 virtual ~CTreeTraverserBase() {};
00175
00176 virtual bool atStart() = 0;
00177 virtual bool atEnd() = 0;
00178
00179 virtual const CTreeNode *operator++() = 0;
00180 virtual const CTreeNode *operator++(int dummy) = 0;
00181
00182
00183
00184
00185 virtual CTreeNode *operator*() = 0;
00186
00187
00188 protected:
00189
00190 virtual CTreeNode *getCurrentNode() const = 0;
00191 virtual void removeCurrentNode() = 0;
00192 };
00193
00194
00195
00200
00201
00202
00203
00204
00207 class CDepthFirstTraverser : public CTreeTraverserBase {
00208 public:
00209
00210 CDepthFirstTraverser(CTreeNode *pcNode);
00211 virtual ~CDepthFirstTraverser() {};
00212
00213 virtual bool atStart();
00214 virtual bool atEnd();
00215
00216 virtual const CTreeNode *operator++();
00217 virtual const CTreeNode *operator++(int dummy);
00218
00219
00220
00221
00222 virtual CTreeNode *operator*() {
00223 return getCurrentNode();
00224 }
00225
00226
00227 protected:
00228
00229 virtual CTreeNode *getCurrentNode() const;
00230 virtual void removeCurrentNode();
00231
00232
00233 private:
00234
00235 void parseSubTree(CTreeNode *pcNode);
00236
00237 CList<CTreeNode> m_cNodeList;
00238 CListContainer<CTreeNode> *m_pcCurrentNode;
00239 bool m_fAtEnd, m_fAtStart;
00240 int m_nLastOp;
00241 };
00242
00243
00244
00247 class CBreathFirstTraverser : public CTreeTraverserBase {
00248 public:
00249
00250 CBreathFirstTraverser(CTreeNode *pcNode);
00251 virtual ~CBreathFirstTraverser() {};
00252
00253 virtual bool atStart();
00254 virtual bool atEnd();
00255
00256 virtual const CTreeNode *operator++();
00257 virtual const CTreeNode *operator++(int dummy);
00258
00259
00260
00261
00262 virtual CTreeNode *operator*() {
00263 return getCurrentNode();
00264 }
00265
00266
00267 protected:
00268
00269 virtual CTreeNode *getCurrentNode() const;
00270 virtual void removeCurrentNode();
00271
00272
00273 private:
00274
00275 CList<CTreeNode> m_cNodeList;
00276 CListContainer<CTreeNode> *m_pcCurrentNode;
00277 bool m_fAtEnd, m_fAtStart;
00278 int m_nLastOp;
00279 };
00280
00281
00282 #endif // CTREE_H