1 //===- BinTree.h ----------------------------------------------------------===//
2 //
3 //                     The MCLinker Project
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 #ifndef MCLD_ADT_BINTREE_H_
10 #define MCLD_ADT_BINTREE_H_
11 
12 #include "mcld/ADT/TreeAllocator.h"
13 #include "mcld/ADT/TreeBase.h"
14 #include "mcld/Support/Compiler.h"
15 
16 #include <cstddef>
17 #include <iterator>
18 #include <memory>
19 #include <queue>
20 #include <stack>
21 
22 namespace mcld {
23 
24 template <class DataType>
25 class BinaryTree;
26 
27 class DFSIterator : public TreeIteratorBase {
28  public:
DFSIterator()29   DFSIterator() : TreeIteratorBase() {}
30 
DFSIterator(NodeBase * X)31   explicit DFSIterator(NodeBase* X) : TreeIteratorBase(X) {
32     if (hasRightChild())
33       m_Stack.push(m_pNode->right);
34     if (hasLeftChild())
35       m_Stack.push(m_pNode->left);
36   }
37 
~DFSIterator()38   virtual ~DFSIterator() {}
39 
advance()40   void advance() {
41     if (m_Stack.empty()) {       // reach the end
42       m_pNode = m_pNode->right;  // should be root
43       return;
44     }
45     m_pNode = m_Stack.top();
46     m_Stack.pop();
47     if (hasRightChild())
48       m_Stack.push(m_pNode->right);
49     if (hasLeftChild())
50       m_Stack.push(m_pNode->left);
51   }
52 
53  private:
54   std::stack<NodeBase*> m_Stack;
55 };
56 
57 class BFSIterator : public TreeIteratorBase {
58  public:
BFSIterator()59   BFSIterator() : TreeIteratorBase() {}
60 
BFSIterator(NodeBase * X)61   explicit BFSIterator(NodeBase* X) : TreeIteratorBase(X) {
62     if (hasRightChild())
63       m_Queue.push(m_pNode->right);
64     if (hasLeftChild())
65       m_Queue.push(m_pNode->left);
66   }
67 
~BFSIterator()68   virtual ~BFSIterator() {}
69 
advance()70   void advance() {
71     if (m_Queue.empty()) {       // reach the end
72       m_pNode = m_pNode->right;  // should be root
73       return;
74     }
75     m_pNode = m_Queue.front();
76     m_Queue.pop();
77     if (hasRightChild())
78       m_Queue.push(m_pNode->right);
79     if (hasLeftChild())
80       m_Queue.push(m_pNode->left);
81   }
82 
83  private:
84   std::queue<NodeBase*> m_Queue;
85 };
86 
87 template <class DataType, class Traits, class IteratorType>
88 class PolicyIteratorBase : public IteratorType {
89  public:
90   typedef DataType value_type;
91   typedef Traits traits;
92   typedef typename traits::pointer pointer;
93   typedef typename traits::reference reference;
94 
95   typedef PolicyIteratorBase<value_type, Traits, IteratorType> Self;
96   typedef Node<value_type> node_type;
97 
98   typedef typename traits::nonconst_traits nonconst_traits;
99   typedef typename traits::const_traits const_traits;
100 
101   typedef PolicyIteratorBase<value_type, nonconst_traits, IteratorType>
102       iterator;
103   typedef PolicyIteratorBase<value_type, const_traits, IteratorType>
104       const_iterator;
105 
106   typedef std::forward_iterator_tag iterator_category;
107   typedef size_t size_type;
108   typedef ptrdiff_t difference_type;
109 
110  public:
PolicyIteratorBase()111   PolicyIteratorBase() : IteratorType() {}
112 
PolicyIteratorBase(const iterator & X)113   PolicyIteratorBase(const iterator& X) : IteratorType(X.m_pNode) {}
114 
PolicyIteratorBase(NodeBase * X)115   explicit PolicyIteratorBase(NodeBase* X) : IteratorType(X) {}
116 
~PolicyIteratorBase()117   virtual ~PolicyIteratorBase() {}
118 
119   // -----  operators  ----- //
120   pointer operator*() const {
121     return static_cast<node_type*>(IteratorType::m_pNode)->data;
122   }
123 
124   reference operator->() const {
125     return *static_cast<node_type*>(IteratorType::m_pNode)->data;
126   }
127 
hasData()128   bool hasData() const {
129     return (!IteratorType::isRoot() &&
130             (0 != static_cast<node_type*>(IteratorType::m_pNode)->data));
131   }
132 };
133 
134 template <class DataType, class Traits, class IteratorType>
135 class PolicyIterator
136     : public PolicyIteratorBase<DataType, Traits, IteratorType> {
137  public:
138   typedef PolicyIterator<DataType, Traits, IteratorType> Self;
139   typedef PolicyIteratorBase<DataType, Traits, IteratorType> Base;
140   typedef PolicyIterator<DataType,
141                          typename Traits::nonconst_traits,
142                          IteratorType> iterator;
143   typedef PolicyIterator<DataType, typename Traits::const_traits, IteratorType>
144       const_iterator;
145 
146  public:
PolicyIterator()147   PolicyIterator() : Base() {}
148 
PolicyIterator(const iterator & X)149   PolicyIterator(const iterator& X) : Base(X.m_pNode) {}
150 
PolicyIterator(NodeBase * X)151   explicit PolicyIterator(NodeBase* X) : Base(X) {}
152 
~PolicyIterator()153   virtual ~PolicyIterator() {}
154 
155   Self& operator++() {
156     IteratorType::advance();
157     return *this;
158   }
159 
160   Self operator++(int) {
161     Self tmp = *this;
162     IteratorType::advance();
163     return tmp;
164   }
165 };
166 
167 template <class DataType>
168 class BinaryTree;
169 
170 /** \class TreeIterator
171  *  \brief TreeIterator provides full functions of binary tree's iterator.
172  *
173  *  TreeIterator is designed to compatible with STL iterators.
174  *  TreeIterator is bi-directional. Incremental direction means to move
175  *  rightward, and decremental direction is leftward.
176  *
177  *  @see TreeIteratorBase
178  */
179 template <class DataType, class Traits>
180 struct TreeIterator : public TreeIteratorBase {
181  public:
182   typedef DataType value_type;
183   typedef Traits traits;
184   typedef typename traits::pointer pointer;
185   typedef typename traits::reference reference;
186 
187   typedef TreeIterator<value_type, Traits> Self;
188   typedef Node<value_type> node_type;
189 
190   typedef typename traits::nonconst_traits nonconst_traits;
191   typedef TreeIterator<value_type, nonconst_traits> iterator;
192   typedef typename traits::const_traits const_traits;
193   typedef TreeIterator<value_type, const_traits> const_iterator;
194   typedef std::bidirectional_iterator_tag iterator_category;
195   typedef size_t size_type;
196   typedef ptrdiff_t difference_type;
197 
198  public:
TreeIteratorTreeIterator199   TreeIterator() : TreeIteratorBase() {}
200 
TreeIteratorTreeIterator201   TreeIterator(const iterator& X) : TreeIteratorBase(X.m_pNode) {}
202 
~TreeIteratorTreeIterator203   ~TreeIterator() {}
204 
205   // -----  operators  ----- //
206   pointer operator*() const { return static_cast<node_type*>(m_pNode)->data; }
207 
208   reference operator->() const {
209     return *static_cast<node_type*>(m_pNode)->data;
210   }
211 
isRootTreeIterator212   bool isRoot() const { return (m_pNode->right == m_pNode); }
213 
hasDataTreeIterator214   bool hasData() const {
215     return (!isRoot() && (0 != static_cast<node_type*>(m_pNode)->data));
216   }
217 
218   Self& operator++() {
219     this->move<TreeIteratorBase::Rightward>();
220     return *this;
221   }
222 
223   Self operator++(int) {
224     Self tmp = *this;
225     this->move<TreeIteratorBase::Rightward>();
226     return tmp;
227   }
228 
229   Self& operator--() {
230     this->move<TreeIteratorBase::Leftward>();
231     return *this;
232   }
233 
234   Self operator--(int) {
235     Self tmp = *this;
236     this->move<TreeIteratorBase::Leftward>();
237     return tmp;
238   }
239 
TreeIteratorTreeIterator240   explicit TreeIterator(NodeBase* X) : TreeIteratorBase(X) {}
241 };
242 
243 /** \class BinaryTreeBase
244  *  \brief BinaryTreeBase gives root node and memory management.
245  *
246  *  The memory management of nodes in is hidden by BinaryTreeBase.
247  *  BinaryTreeBase also provides the basic functions for merging a tree and
248  *  inserton of a node.
249  *
250  *  @see BinaryTree
251  */
252 template <class DataType>
253 class BinaryTreeBase {
254  public:
255   typedef Node<DataType> NodeType;
256 
257  protected:
258   /// TreeImpl - TreeImpl records the root node and the number of nodes
259   //
260   //    +---> Root(end) <---+
261   //    |        |left      |
262   //    |      begin        |
263   //    |     /     \       |
264   //    |  Left     Right   |
265   //    +---/         \-----+
266   //
267   class TreeImpl : public NodeFactory<DataType> {
268     typedef typename NodeFactory<DataType>::iterator iterator;
269     typedef typename NodeFactory<DataType>::const_iterator const_iterator;
270 
271    public:
272     NodeBase node;
273 
274    public:
TreeImpl()275     TreeImpl() : NodeFactory<DataType>() { node.left = node.right = &node; }
276 
~TreeImpl()277     ~TreeImpl() {}
278 
279     /// summon - change the final edges of pClient to our root
summon(TreeImpl & pClient)280     void summon(TreeImpl& pClient) {
281       if (this == &pClient)
282         return;
283 
284       iterator data;
285       iterator dEnd = pClient.end();
286       for (data = pClient.begin(); data != dEnd; ++data) {
287         if ((*data).left == &pClient.node)
288           (*data).left = &node;
289         if ((*data).right == &pClient.node)
290           (*data).right = &node;
291       }
292     }
293   };  // TreeImpl
294 
295  protected:
296   /// m_Root is a special object who responses:
297   //  - the pointer of root
298   //  - the simple factory of nodes.
299   TreeImpl m_Root;
300 
301  protected:
createNode()302   NodeType* createNode() {
303     NodeType* result = m_Root.produce();
304     result->left = result->right = &m_Root.node;
305     return result;
306   }
307 
destroyNode(NodeType * pNode)308   void destroyNode(NodeType* pNode) {
309     pNode->left = pNode->right = 0;
310     pNode->data = 0;
311     m_Root.deallocate(pNode);
312   }
313 
314  public:
BinaryTreeBase()315   BinaryTreeBase() : m_Root() {}
316 
~BinaryTreeBase()317   virtual ~BinaryTreeBase() {}
318 
size()319   size_t size() const { return m_Root.size(); }
320 
empty()321   bool empty() const { return m_Root.empty(); }
322 
323  protected:
clear()324   void clear() { m_Root.clear(); }
325 
326  private:
327   DISALLOW_COPY_AND_ASSIGN(BinaryTreeBase);
328 };
329 
330 /** \class BinaryTree
331  *  \brief An abstract data type of binary tree.
332  *
333  *  @see mcld::InputTree
334  */
335 template <class DataType>
336 class BinaryTree : public BinaryTreeBase<DataType> {
337  public:
338   typedef size_t size_type;
339   typedef ptrdiff_t difference_type;
340   typedef DataType value_type;
341   typedef value_type* pointer;
342   typedef value_type& reference;
343   typedef const value_type* const_pointer;
344   typedef const value_type& const_reference;
345 
346   typedef BinaryTree<DataType> Self;
347   typedef TreeIterator<value_type, NonConstTraits<value_type> > iterator;
348   typedef TreeIterator<value_type, ConstTraits<value_type> > const_iterator;
349 
350   typedef PolicyIterator<value_type, NonConstTraits<value_type>, DFSIterator>
351       dfs_iterator;
352   typedef PolicyIterator<value_type, ConstTraits<value_type>, DFSIterator>
353       const_dfs_iterator;
354 
355   typedef PolicyIterator<value_type, NonConstTraits<value_type>, BFSIterator>
356       bfs_iterator;
357   typedef PolicyIterator<value_type, ConstTraits<value_type>, BFSIterator>
358       const_bfs_iterator;
359 
360  protected:
361   typedef Node<value_type> node_type;
362 
363  public:
364   // -----  constructors and destructor  ----- //
BinaryTree()365   BinaryTree() : BinaryTreeBase<DataType>() {}
366 
~BinaryTree()367   ~BinaryTree() {}
368 
369   // -----  iterators  ----- //
bfs_begin()370   bfs_iterator bfs_begin() {
371     return bfs_iterator(BinaryTreeBase<DataType>::m_Root.node.left);
372   }
373 
bfs_end()374   bfs_iterator bfs_end() {
375     return bfs_iterator(BinaryTreeBase<DataType>::m_Root.node.right);
376   }
377 
bfs_begin()378   const_bfs_iterator bfs_begin() const {
379     return const_bfs_iterator(BinaryTreeBase<DataType>::m_Root.node.left);
380   }
381 
bfs_end()382   const_bfs_iterator bfs_end() const {
383     return const_bfs_iterator(BinaryTreeBase<DataType>::m_Root.node.right);
384   }
385 
dfs_begin()386   dfs_iterator dfs_begin() {
387     return dfs_iterator(BinaryTreeBase<DataType>::m_Root.node.left);
388   }
389 
dfs_end()390   dfs_iterator dfs_end() {
391     return dfs_iterator(BinaryTreeBase<DataType>::m_Root.node.right);
392   }
393 
dfs_begin()394   const_dfs_iterator dfs_begin() const {
395     return const_dfs_iterator(BinaryTreeBase<DataType>::m_Root.node.left);
396   }
397 
dfs_end()398   const_dfs_iterator dfs_end() const {
399     return const_dfs_iterator(BinaryTreeBase<DataType>::m_Root.node.right);
400   }
401 
root()402   iterator root() { return iterator(&(BinaryTreeBase<DataType>::m_Root.node)); }
403 
root()404   const_iterator root() const {
405     return const_iterator(&(BinaryTreeBase<DataType>::m_Root.node));
406   }
407 
begin()408   iterator begin() {
409     return iterator(BinaryTreeBase<DataType>::m_Root.node.left);
410   }
411 
end()412   iterator end() {
413     return iterator(BinaryTreeBase<DataType>::m_Root.node.right);
414   }
415 
begin()416   const_iterator begin() const {
417     return const_iterator(BinaryTreeBase<DataType>::m_Root.node.left);
418   }
419 
end()420   const_iterator end() const {
421     return const_iterator(BinaryTreeBase<DataType>::m_Root.node.right);
422   }
423 
424   // ----- modifiers  ----- //
425   /// join - create a leaf node and merge it in the tree.
426   //  This version of join determines the direction on compilation time.
427   //  @param DIRECT the direction of the connecting edge of the parent node.
428   //  @param position the parent node
429   //  @param value the value being pushed.
430   template <size_t DIRECT>
join(TreeIteratorBase & pPosition,const DataType & pValue)431   BinaryTree& join(TreeIteratorBase& pPosition, const DataType& pValue) {
432     node_type* node = BinaryTreeBase<DataType>::createNode();
433     node->data = const_cast<DataType*>(&pValue);
434 
435     if (pPosition.isRoot())
436       pPosition.hook<TreeIteratorBase::Leftward>(node);
437     else
438       pPosition.hook<DIRECT>(node);
439 
440     return *this;
441   }
442 
443   /// merge - merge the tree
444   //  @param DIRECT the direction of the connecting edge of the parent node.
445   //  @param position the parent node
446   //  @param the tree being joined.
447   //  @return the joined tree
448   template <size_t DIRECT>
merge(TreeIteratorBase & pPosition,BinaryTree & pTree)449   BinaryTree& merge(TreeIteratorBase& pPosition, BinaryTree& pTree) {
450     if (this == &pTree)
451       return *this;
452 
453     if (!pTree.empty()) {
454       pPosition.hook<DIRECT>(pTree.m_Root.node.left);
455       BinaryTreeBase<DataType>::m_Root.summon(
456           pTree.BinaryTreeBase<DataType>::m_Root);
457       BinaryTreeBase<DataType>::m_Root.delegate(pTree.m_Root);
458       pTree.m_Root.node.left = pTree.m_Root.node.right = &pTree.m_Root.node;
459     }
460     return *this;
461   }
462 };
463 
464 }  // namespace mcld
465 
466 #endif  // MCLD_ADT_BINTREE_H_
467