BinTree.h revision 67e37f1be98c926645219cfb47fab9e90d8c725c 
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
24namespace mcld
25{
26
27template<class DataType>
28class BinaryTree;
29
30class DFSIterator : public TreeIteratorBase
31{
32public:
33  DFSIterator()
34  : TreeIteratorBase()
35  { }
36
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
45  virtual ~DFSIterator()
46  { }
47
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
61private:
62    std::stack<NodeBase *> m_Stack;
63};
64
65class BFSIterator : public TreeIteratorBase
66{
67public:
68  BFSIterator()
69  : TreeIteratorBase()
70  { }
71
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
80  virtual ~BFSIterator()
81  { }
82
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
96private:
97    std::queue<NodeBase *> m_Queue;
98};
99
100template<class DataType, class Traits, class IteratorType>
101class PolicyIteratorBase : public IteratorType
102{
103public:
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
119public:
120  PolicyIteratorBase()
121    : IteratorType() {}
122
123  PolicyIteratorBase(const iterator &X)
124    : IteratorType(X.m_pNode) {}
125
126  explicit PolicyIteratorBase(NodeBase* X)
127    : IteratorType(X) {}
128
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
138  bool hasData() const
139  { return (!IteratorType::isRoot() && (0 != static_cast<node_type*>(IteratorType::m_pNode)->data)); }
140
141};
142
143template<class DataType, class Traits, class IteratorType>
144class PolicyIterator : public PolicyIteratorBase<DataType, Traits, IteratorType>
145{
146public:
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
152public:
153  PolicyIterator()
154    : Base() {}
155
156  PolicyIterator(const iterator &X)
157    : Base(X.m_pNode) {}
158
159  explicit PolicyIterator(NodeBase* X)
160    : Base(X) {}
161
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
176template<class DataType>
177class 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 */
188template<class DataType, class Traits>
189struct TreeIterator : public TreeIteratorBase
190{
191public:
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
208public:
209  TreeIterator()
210  : TreeIteratorBase() {}
211
212  TreeIterator(const iterator &X)
213    : TreeIteratorBase(X.m_pNode) {}
214
215  ~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
224  bool isRoot() const
225  { return (m_pNode->right == m_pNode); }
226
227  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
252  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 */
265template<class DataType>
266class BinaryTreeBase : private Uncopyable
267{
268public:
269  typedef Node<DataType> NodeType;
270protected:
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:
289    TreeImpl()
290      : NodeFactory<DataType>() {
291      node.left = node.right = &node;
292    }
293
294    ~TreeImpl()
295    { }
296
297    /// summon - change the final edges of pClient to our root
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
313protected:
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
319protected:
320  NodeType *createNode() {
321    NodeType *result = m_Root.produce();
322    result->left = result->right = &m_Root.node;
323    return result;
324  }
325
326  void destroyNode(NodeType *pNode) {
327    pNode->left = pNode->right = 0;
328    pNode->data = 0;
329    m_Root.deallocate(pNode);
330  }
331
332public:
333  BinaryTreeBase()
334  : m_Root()
335  { }
336
337  virtual ~BinaryTreeBase()
338  { }
339
340  size_t size() const {
341    return m_Root.size();
342  }
343
344  bool empty() const {
345    return m_Root.empty();
346  }
347
348protected:
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 */
359template<class DataType>
360class BinaryTree : public BinaryTreeBase<DataType>
361{
362public:
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
380protected:
381  typedef Node<value_type> node_type;
382
383public:
384  // -----  constructors and destructor  ----- //
385  BinaryTree()
386  : BinaryTreeBase<DataType>()
387  { }
388
389  ~BinaryTree() {
390  }
391
392  // -----  iterators  ----- //
393  bfs_iterator bfs_begin()
394  { return bfs_iterator(BinaryTreeBase<DataType>::m_Root.node.left); }
395
396  bfs_iterator bfs_end()
397  { return bfs_iterator(BinaryTreeBase<DataType>::m_Root.node.right); }
398
399  const_bfs_iterator bfs_begin() const
400  { return const_bfs_iterator(BinaryTreeBase<DataType>::m_Root.node.left); }
401
402  const_bfs_iterator bfs_end() const
403  { return const_bfs_iterator(BinaryTreeBase<DataType>::m_Root.node.right); }
404
405  dfs_iterator dfs_begin()
406  { return dfs_iterator(BinaryTreeBase<DataType>::m_Root.node.left); }
407
408  dfs_iterator dfs_end()
409  { return dfs_iterator(BinaryTreeBase<DataType>::m_Root.node.right); }
410
411  const_dfs_iterator dfs_begin() const
412  { return const_dfs_iterator(BinaryTreeBase<DataType>::m_Root.node.left); }
413
414  const_dfs_iterator dfs_end() const
415  { return const_dfs_iterator(BinaryTreeBase<DataType>::m_Root.node.right); }
416
417  iterator root()
418  { return iterator(&(BinaryTreeBase<DataType>::m_Root.node)); }
419
420  const_iterator root() const
421  { return const_iterator(&(BinaryTreeBase<DataType>::m_Root.node)); }
422
423  iterator begin()
424  { return iterator(BinaryTreeBase<DataType>::m_Root.node.left); }
425
426  iterator end()
427  { return iterator(BinaryTreeBase<DataType>::m_Root.node.right); }
428
429  const_iterator begin() const
430  { return const_iterator(BinaryTreeBase<DataType>::m_Root.node.left); }
431
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>
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>
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