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