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