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