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