1//===- TreeBase.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_TREEBASE_H
10#define MCLD_ADT_TREEBASE_H
11#include <mcld/ADT/TypeTraits.h>
12
13#include <cstddef>
14#include <cassert>
15#include <iterator>
16
17namespace mcld {
18
19class NodeBase
20{
21public:
22  NodeBase *left;
23  NodeBase *right;
24
25public:
26  NodeBase()
27  : left(0), right(0)
28  { }
29};
30
31class TreeIteratorBase
32{
33public:
34  enum Direct {
35    Leftward,
36    Rightward
37  };
38
39  typedef size_t                          size_type;
40  typedef ptrdiff_t                       difference_type;
41  typedef std::bidirectional_iterator_tag iterator_category;
42
43public:
44  NodeBase* m_pNode;
45
46public:
47  TreeIteratorBase()
48  : m_pNode(0)
49  { }
50
51  TreeIteratorBase(NodeBase *X)
52  : m_pNode(X)
53  { }
54
55  virtual ~TreeIteratorBase(){};
56
57  template<size_t DIRECT>
58  void move() { assert(0 && "not allowed"); }
59
60  template<size_t DIRECT>
61  void hook(NodeBase* pNode) { assert(0 && "not allowed"); }
62
63  bool isRoot() const
64  { return (m_pNode->right == m_pNode); }
65
66  bool hasRightChild() const
67  { return ((m_pNode->right) != (m_pNode->right->right)); }
68
69  bool hasLeftChild() const
70  { return ((m_pNode->left) != (m_pNode->left->right)); }
71
72  bool operator==(const TreeIteratorBase& y) const
73  { return this->m_pNode == y.m_pNode; }
74
75  bool operator!=(const TreeIteratorBase& y) const
76  { return this->m_pNode != y.m_pNode; }
77};
78
79template<> inline
80void TreeIteratorBase::move<TreeIteratorBase::Leftward>()
81{
82  this->m_pNode = this->m_pNode->left;
83}
84
85template<> inline
86void TreeIteratorBase::move<TreeIteratorBase::Rightward>()
87{
88  this->m_pNode = this->m_pNode->right;
89}
90
91template<> inline
92void TreeIteratorBase::hook<TreeIteratorBase::Leftward>(NodeBase* pOther)
93{
94  this->m_pNode->left = pOther;
95}
96
97template<> inline
98void TreeIteratorBase::hook<TreeIteratorBase::Rightward>(NodeBase* pOther)
99{
100  this->m_pNode->right = pOther;
101}
102
103template<typename DataType>
104class Node : public NodeBase
105{
106public:
107  typedef DataType        value_type;
108
109public:
110  value_type* data;
111
112public:
113  Node()
114  : NodeBase(), data(0)
115  { }
116
117  Node(const value_type& pValue)
118  : NodeBase(), data(&pValue)
119  { }
120
121};
122
123} // namespace of mcld
124
125#endif
126
127