libUTL++
BinTreeBfsIt.h
1 #pragma once
2 
4 
5 #include <libutl/FwdIt.h>
6 #include <libutl/Queue.h>
7 
9 
10 #undef new
11 #include <queue>
12 #include <libutl/gblnew_macros.h>
13 
15 
16 UTL_NS_BEGIN;
17 
19 
20 class BinTree;
21 class BinTreeNode;
22 
24 
32 
34 class BinTreeBfsIt : public FwdIt
35 {
37 
38 public:
44  BinTreeBfsIt(const BinTree* tree, BinTreeNode* node)
45  {
46  init(tree, node);
47  }
48 
49  virtual int compare(const Object& rhs) const;
50 
51  virtual void copy(const Object& rhs);
52 
53  virtual void forward(size_t dist = 1);
54 
55  virtual Object* get() const;
56 
59  getNode() const
60  {
61  return _node;
62  }
63 
65  BinTree*
66  getTree() const
67  {
68  return _tree;
69  }
70 
71  virtual void set(const Object* object);
72 
74  void
76  {
77  _node = node;
78  }
79 
80  BinTreeBfsIt& operator++()
81  {
82  forward();
83  return *this;
84  }
85 
86  BinTreeBfsIt operator++(int)
87  {
88  BinTreeBfsIt res = *this;
89  forward();
90  return res;
91  }
92 
93 private:
94  typedef std::queue<BinTreeNode*> nodeq_t;
95 
96 private:
97  void init(const BinTree* tree = nullptr, BinTreeNode* node = nullptr);
98  void
99  deInit()
100  {
101  }
102 
103 private:
104  BinTree* _tree;
105  BinTreeNode* _node;
106  nodeq_t _queue;
107 };
108 
110 
112 BinTree::beginBFS() const
113 {
114  BinTreeBfsIt it(this, _root);
115  if (it.get() == nullptr) it.forward();
116  IFDEBUG(it.setConst(true));
117  return it;
118 }
119 
121 
123 BinTree::beginBFS()
124 {
125  BinTreeBfsIt it(this, _root);
126  if (it.get() == nullptr) it.forward();
127  return it;
128 }
129 
131 
133 BinTree::beginBFSNew() const
134 {
135  BinTreeBfsIt* it = new BinTreeBfsIt(this, _root);
136  if (it->get() == nullptr) it->forward();
137  IFDEBUG(it->setConst(true));
138  return it;
139 }
140 
142 
144 BinTree::beginBFSNew()
145 {
146  BinTreeBfsIt* it = new BinTreeBfsIt(this, _root);
147  if (it->get() == nullptr) it->forward();
148  return it;
149 }
150 
152 
154 BinTree::endBFS() const
155 {
156  BinTreeBfsIt it(this, _root->rightMost());
157  IFDEBUG(it.setConst(true));
158  return it;
159 }
160 
162 
164 BinTree::endBFS()
165 {
166  return BinTreeBfsIt(this, _root->rightMost());
167 }
168 
170 
172 BinTree::endBFSNew() const
173 {
174  BinTreeBfsIt* it = new BinTreeBfsIt(this, _root->rightMost());
175  IFDEBUG(it->setConst(true));
176  return it;
177 }
178 
180 
182 BinTree::endBFSNew()
183 {
184  return new BinTreeBfsIt(this, _root->rightMost());
185 }
186 
188 
189 UTL_NS_END;
Binary tree abstraction.
Definition: BinTree.h:33
BinTree * getTree() const
Get the associated BinTree.
Definition: BinTreeBfsIt.h:66
void deInit()
De-initialize UTL++.
#define UTL_CLASS_DECL(DC, BC)
Declaration of standard UTL++ functionality for a non-template class.
Definition: macros.h:688
BinTreeBfsIt(const BinTree *tree, BinTreeNode *node)
Constructor.
Definition: BinTreeBfsIt.h:44
#define IFDEBUG(x)
Do x in DEBUG mode only.
void copy(T *dest, const T *src, size_t len)
Copy one array of objects to another.
Definition: util_inl.h:690
virtual void forward(size_t dist=1)
Move forward the given number of objects.
virtual Object * get() const
Get the current object.
Forward iterator abstraction.
Definition: FwdIt.h:26
void setNode(BinTreeNode *node)
Set the node.
Definition: BinTreeBfsIt.h:75
void setConst(bool p_const)
Set the const flag.
Definition: FwdIt.h:68
Binary tree node.
Definition: BinTreeNode.h:31
Breadth-first BinTree iterator.
Definition: BinTreeBfsIt.h:34
BinTreeNode * getNode() const
Get the current node.
Definition: BinTreeBfsIt.h:59
Root of UTL++ class hierarchy.
Definition: Object.h:52
int compare(bool lhs, bool rhs)
Compare two boolean values.
void init()
Initialize UTL++.