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