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