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