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