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