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 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 namespace proxy 32 { 33 template<size_t DIRECT> move(NodeBase * & X)34 inline void move(NodeBase *&X) 35 { assert(0 && "not allowed"); } 36 37 template<size_t DIRECT> hook(NodeBase * X,const NodeBase * Y)38 inline void hook(NodeBase *X, const NodeBase *Y) 39 { assert(0 && "not allowed"); } 40 41 } // namespace of template proxy 42 43 class TreeIteratorBase 44 { 45 public: 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 55 public: 56 NodeBase* m_pNode; 57 58 public: TreeIteratorBase()59 TreeIteratorBase() 60 : m_pNode(0) 61 { } 62 TreeIteratorBase(NodeBase * X)63 TreeIteratorBase(NodeBase *X) 64 : m_pNode(X) 65 { } 66 ~TreeIteratorBase()67 virtual ~TreeIteratorBase(){}; 68 69 template<size_t DIRECT> move()70 inline void move() { 71 proxy::move<DIRECT>(m_pNode); 72 } 73 isRoot()74 bool isRoot() const 75 { return (m_pNode->right == m_pNode); } 76 hasRightChild()77 bool hasRightChild() const 78 { return ((m_pNode->right) != (m_pNode->right->right)); } 79 hasLeftChild()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 90 namespace 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 110 template<typename DataType> 111 class Node : public NodeBase 112 { 113 public: 114 typedef DataType value_type; 115 116 public: 117 value_type* data; 118 119 public: Node()120 Node() 121 : NodeBase(), data(0) 122 { } 123 Node(const value_type & pValue)124 Node(const value_type& pValue) 125 : NodeBase(), data(&pValue) 126 { } 127 128 }; 129 130 } // namespace of mcld 131 132 #endif 133 134