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