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 17 namespace mcld { 18 19 class NodeBase 20 { 21 public: 22 NodeBase *left; 23 NodeBase *right; 24 25 public: NodeBase()26 NodeBase() 27 : left(0), right(0) 28 { } 29 }; 30 31 class TreeIteratorBase 32 { 33 public: 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 43 public: 44 NodeBase* m_pNode; 45 46 public: TreeIteratorBase()47 TreeIteratorBase() 48 : m_pNode(0) 49 { } 50 TreeIteratorBase(NodeBase * X)51 TreeIteratorBase(NodeBase *X) 52 : m_pNode(X) 53 { } 54 ~TreeIteratorBase()55 virtual ~TreeIteratorBase(){}; 56 57 template<size_t DIRECT> move()58 void move() { assert(0 && "not allowed"); } 59 60 template<size_t DIRECT> hook(NodeBase * pNode)61 void hook(NodeBase* pNode) { assert(0 && "not allowed"); } 62 isRoot()63 bool isRoot() const 64 { return (m_pNode->right == m_pNode); } 65 hasRightChild()66 bool hasRightChild() const 67 { return ((m_pNode->right) != (m_pNode->right->right)); } 68 hasLeftChild()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 79 template<> inline 80 void TreeIteratorBase::move<TreeIteratorBase::Leftward>() 81 { 82 this->m_pNode = this->m_pNode->left; 83 } 84 85 template<> inline 86 void TreeIteratorBase::move<TreeIteratorBase::Rightward>() 87 { 88 this->m_pNode = this->m_pNode->right; 89 } 90 91 template<> inline 92 void TreeIteratorBase::hook<TreeIteratorBase::Leftward>(NodeBase* pOther) 93 { 94 this->m_pNode->left = pOther; 95 } 96 97 template<> inline 98 void TreeIteratorBase::hook<TreeIteratorBase::Rightward>(NodeBase* pOther) 99 { 100 this->m_pNode->right = pOther; 101 } 102 103 template<typename DataType> 104 class Node : public NodeBase 105 { 106 public: 107 typedef DataType value_type; 108 109 public: 110 value_type* data; 111 112 public: Node()113 Node() 114 : NodeBase(), data(0) 115 { } 116 Node(const value_type & pValue)117 Node(const value_type& pValue) 118 : NodeBase(), data(&pValue) 119 { } 120 121 }; 122 123 } // namespace of mcld 124 125 #endif 126 127