• 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/TreeBase.h>
17 #include <mcld/ADT/TreeAllocator.h>
18 
19 #include <cstddef>
20 #include <iterator>
21 #include <memory>
22 #include <queue>
23 #include <stack>
24 
25 namespace mcld {
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 
hasData()138   bool hasData() const
139   { return (!IteratorType::isRoot() && (0 != static_cast<node_type*>(IteratorType::m_pNode)->data)); }
140 
141 };
142 
143 template<class DataType, class Traits, class IteratorType>
144 class PolicyIterator : public PolicyIteratorBase<DataType, Traits, IteratorType>
145 {
146 public:
147   typedef PolicyIterator<DataType, Traits, IteratorType> Self;
148   typedef PolicyIteratorBase<DataType, Traits, IteratorType> Base;
149   typedef PolicyIterator<DataType, typename Traits::nonconst_traits, IteratorType> iterator;
150   typedef PolicyIterator<DataType, typename Traits::const_traits, IteratorType>    const_iterator;
151 
152 public:
PolicyIterator()153   PolicyIterator()
154     : Base() {}
155 
PolicyIterator(const iterator & X)156   PolicyIterator(const iterator &X)
157     : Base(X.m_pNode) {}
158 
PolicyIterator(NodeBase * X)159   explicit PolicyIterator(NodeBase* X)
160     : Base(X) {}
161 
~PolicyIterator()162   virtual ~PolicyIterator() {}
163 
164   Self& operator++() {
165     IteratorType::advance();
166     return *this;
167   }
168 
169   Self operator++(int) {
170     Self tmp = *this;
171     IteratorType::advance();
172     return tmp;
173   }
174 };
175 
176 template<class DataType>
177 class BinaryTree;
178 
179 /** \class TreeIterator
180  *  \brief TreeIterator provides full functions of binary tree's iterator.
181  *
182  *  TreeIterator is designed to compatible with STL iterators.
183  *  TreeIterator is bi-directional. Incremental direction means to move
184  *  rightward, and decremental direction is leftward.
185  *
186  *  @see TreeIteratorBase
187  */
188 template<class DataType, class Traits>
189 struct TreeIterator : public TreeIteratorBase
190 {
191 public:
192   typedef DataType                       value_type;
193   typedef Traits                         traits;
194   typedef typename traits::pointer       pointer;
195   typedef typename traits::reference     reference;
196 
197   typedef TreeIterator<value_type, Traits>          Self;
198   typedef Node<value_type>                          node_type;
199 
200   typedef typename traits::nonconst_traits          nonconst_traits;
201   typedef TreeIterator<value_type, nonconst_traits> iterator;
202   typedef typename traits::const_traits             const_traits;
203   typedef TreeIterator<value_type, const_traits>    const_iterator;
204   typedef std::bidirectional_iterator_tag           iterator_category;
205   typedef size_t                                    size_type;
206   typedef ptrdiff_t                                 difference_type;
207 
208 public:
TreeIteratorTreeIterator209   TreeIterator()
210   : TreeIteratorBase() {}
211 
TreeIteratorTreeIterator212   TreeIterator(const iterator &X)
213     : TreeIteratorBase(X.m_pNode) {}
214 
~TreeIteratorTreeIterator215   ~TreeIterator() {}
216 
217   // -----  operators  ----- //
218   pointer operator*() const
219   { return static_cast<node_type*>(m_pNode)->data; }
220 
221   reference operator->() const
222   { return *static_cast<node_type*>(m_pNode)->data; }
223 
isRootTreeIterator224   bool isRoot() const
225   { return (m_pNode->right == m_pNode); }
226 
hasDataTreeIterator227   bool hasData() const
228   { return (!isRoot() && (0 != static_cast<node_type*>(m_pNode)->data)); }
229 
230   Self& operator++() {
231     this->move<TreeIteratorBase::Rightward>();
232     return *this;
233   }
234 
235   Self operator++(int) {
236     Self tmp = *this;
237     this->move<TreeIteratorBase::Rightward>();
238     return tmp;
239   }
240 
241   Self& operator--() {
242     this->move<TreeIteratorBase::Leftward>();
243     return *this;
244   }
245 
246   Self operator--(int) {
247     Self tmp = *this;
248     this->move<TreeIteratorBase::Leftward>();
249     return tmp;
250   }
251 
TreeIteratorTreeIterator252   explicit TreeIterator(NodeBase* X)
253     : TreeIteratorBase(X) {}
254 };
255 
256 /** \class BinaryTreeBase
257  *  \brief BinaryTreeBase gives root node and memory management.
258  *
259  *  The memory management of nodes in is hidden by BinaryTreeBase.
260  *  BinaryTreeBase also provides the basic functions for merging a tree and
261  *  inserton of a node.
262  *
263  *  @see BinaryTree
264  */
265 template<class DataType>
266 class BinaryTreeBase : private Uncopyable
267 {
268 public:
269   typedef Node<DataType> NodeType;
270 protected:
271   /// TreeImpl - TreeImpl records the root node and the number of nodes
272   //
273   //    +---> Root(end) <---+
274   //    |        |left      |
275   //    |      begin        |
276   //    |     /     \       |
277   //    |  Left     Right   |
278   //    +---/         \-----+
279   //
280   class TreeImpl : public NodeFactory<DataType>
281   {
282     typedef typename NodeFactory<DataType>::iterator       iterator;
283     typedef typename NodeFactory<DataType>::const_iterator const_iterator;
284 
285   public:
286     NodeBase node;
287 
288   public:
TreeImpl()289     TreeImpl()
290       : NodeFactory<DataType>() {
291       node.left = node.right = &node;
292     }
293 
~TreeImpl()294     ~TreeImpl()
295     { }
296 
297     /// summon - change the final edges of pClient to our root
summon(TreeImpl & pClient)298     void summon(TreeImpl& pClient) {
299       if (this == &pClient)
300         return;
301 
302       iterator data;
303       iterator dEnd = pClient.end();
304       for (data = pClient.begin(); data!=dEnd; ++data ) {
305         if ((*data).left == &pClient.node)
306           (*data).left = &node;
307         if ((*data).right == &pClient.node)
308           (*data).right = &node;
309       }
310     }
311   }; // TreeImpl
312 
313 protected:
314   /// m_Root is a special object who responses:
315   //  - the pointer of root
316   //  - the simple factory of nodes.
317   TreeImpl m_Root;
318 
319 protected:
createNode()320   NodeType *createNode() {
321     NodeType *result = m_Root.produce();
322     result->left = result->right = &m_Root.node;
323     return result;
324   }
325 
destroyNode(NodeType * pNode)326   void destroyNode(NodeType *pNode) {
327     pNode->left = pNode->right = 0;
328     pNode->data = 0;
329     m_Root.deallocate(pNode);
330   }
331 
332 public:
BinaryTreeBase()333   BinaryTreeBase()
334   : m_Root()
335   { }
336 
~BinaryTreeBase()337   virtual ~BinaryTreeBase()
338   { }
339 
size()340   size_t size() const {
341     return m_Root.size();
342   }
343 
empty()344   bool empty() const {
345     return m_Root.empty();
346   }
347 
348 protected:
clear()349   void clear() {
350     m_Root.clear();
351   }
352 };
353 
354 /** \class BinaryTree
355  *  \brief An abstract data type of binary tree.
356  *
357  *  @see mcld::InputTree
358  */
359 template<class DataType>
360 class BinaryTree : public BinaryTreeBase<DataType>
361 {
362 public:
363   typedef size_t             size_type;
364   typedef ptrdiff_t          difference_type;
365   typedef DataType           value_type;
366   typedef value_type*        pointer;
367   typedef value_type&        reference;
368   typedef const value_type*  const_pointer;
369   typedef const value_type&  const_reference;
370 
371   typedef BinaryTree<DataType>  Self;
372   typedef TreeIterator<value_type, NonConstTraits<value_type> > iterator;
373   typedef TreeIterator<value_type, ConstTraits<value_type> >    const_iterator;
374 
375   typedef PolicyIterator<value_type, NonConstTraits<value_type>, DFSIterator> dfs_iterator;
376   typedef PolicyIterator<value_type, ConstTraits<value_type>, DFSIterator>    const_dfs_iterator;
377   typedef PolicyIterator<value_type, NonConstTraits<value_type>, BFSIterator> bfs_iterator;
378   typedef PolicyIterator<value_type, ConstTraits<value_type>, BFSIterator>    const_bfs_iterator;
379 
380 protected:
381   typedef Node<value_type> node_type;
382 
383 public:
384   // -----  constructors and destructor  ----- //
BinaryTree()385   BinaryTree()
386   : BinaryTreeBase<DataType>()
387   { }
388 
~BinaryTree()389   ~BinaryTree() {
390   }
391 
392   // -----  iterators  ----- //
bfs_begin()393   bfs_iterator bfs_begin()
394   { return bfs_iterator(BinaryTreeBase<DataType>::m_Root.node.left); }
395 
bfs_end()396   bfs_iterator bfs_end()
397   { return bfs_iterator(BinaryTreeBase<DataType>::m_Root.node.right); }
398 
bfs_begin()399   const_bfs_iterator bfs_begin() const
400   { return const_bfs_iterator(BinaryTreeBase<DataType>::m_Root.node.left); }
401 
bfs_end()402   const_bfs_iterator bfs_end() const
403   { return const_bfs_iterator(BinaryTreeBase<DataType>::m_Root.node.right); }
404 
dfs_begin()405   dfs_iterator dfs_begin()
406   { return dfs_iterator(BinaryTreeBase<DataType>::m_Root.node.left); }
407 
dfs_end()408   dfs_iterator dfs_end()
409   { return dfs_iterator(BinaryTreeBase<DataType>::m_Root.node.right); }
410 
dfs_begin()411   const_dfs_iterator dfs_begin() const
412   { return const_dfs_iterator(BinaryTreeBase<DataType>::m_Root.node.left); }
413 
dfs_end()414   const_dfs_iterator dfs_end() const
415   { return const_dfs_iterator(BinaryTreeBase<DataType>::m_Root.node.right); }
416 
root()417   iterator root()
418   { return iterator(&(BinaryTreeBase<DataType>::m_Root.node)); }
419 
root()420   const_iterator root() const
421   { return const_iterator(&(BinaryTreeBase<DataType>::m_Root.node)); }
422 
begin()423   iterator begin()
424   { return iterator(BinaryTreeBase<DataType>::m_Root.node.left); }
425 
end()426   iterator end()
427   { return iterator(BinaryTreeBase<DataType>::m_Root.node.right); }
428 
begin()429   const_iterator begin() const
430   { return const_iterator(BinaryTreeBase<DataType>::m_Root.node.left); }
431 
end()432   const_iterator end() const
433   { return const_iterator(BinaryTreeBase<DataType>::m_Root.node.right); }
434 
435   // ----- modifiers  ----- //
436   /// join - create a leaf node and merge it in the tree.
437   //  This version of join determines the direction on compilation time.
438   //  @param DIRECT the direction of the connecting edge of the parent node.
439   //  @param position the parent node
440   //  @param value the value being pushed.
441   template<size_t DIRECT, class Pos>
join(Pos position,const DataType & value)442   BinaryTree& join(Pos position, const DataType& value) {
443     node_type *node = BinaryTreeBase<DataType>::createNode();
444     node->data = const_cast<DataType*>(&value);
445     if (position.isRoot())
446       proxy::hook<TreeIteratorBase::Leftward>(position.m_pNode,
447                           const_cast<const node_type*>(node));
448     else
449       proxy::hook<DIRECT>(position.m_pNode,
450                           const_cast<const node_type*>(node));
451     return *this;
452   }
453 
454   /// merge - merge the tree
455   //  @param DIRECT the direction of the connecting edge of the parent node.
456   //  @param position the parent node
457   //  @param the tree being joined.
458   //  @return the joined tree
459   template<size_t DIRECT, class Pos>
merge(Pos position,BinaryTree & pTree)460   BinaryTree& merge(Pos position, BinaryTree& pTree) {
461     if (this == &pTree)
462       return *this;
463 
464     if (!pTree.empty()) {
465       proxy::hook<DIRECT>(position.m_pNode,
466                         const_cast<const NodeBase*>(pTree.m_Root.node.left));
467       BinaryTreeBase<DataType>::m_Root.summon(
468                                    pTree.BinaryTreeBase<DataType>::m_Root);
469       BinaryTreeBase<DataType>::m_Root.delegate(pTree.m_Root);
470       pTree.m_Root.node.left = pTree.m_Root.node.right = &pTree.m_Root.node;
471     }
472     return *this;
473   }
474 };
475 
476 } // namespace of mcld
477 
478 #endif
479 
480