Home | History | Annotate | Download | only in ADT 
      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:
     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:
     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 
     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:
    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