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