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