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 #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:
     26   NodeBase()
     27   : left(0), right(0)
     28   { }
     29 };
     30 
     31 class TreeIteratorBase
     32 {
     33 public:
     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 
     43 public:
     44   NodeBase* m_pNode;
     45 
     46 public:
     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 
     79 template<> inline
     80 void TreeIteratorBase::move<TreeIteratorBase::Leftward>()
     81 {
     82   this->m_pNode = this->m_pNode->left;
     83 }
     84 
     85 template<> inline
     86 void TreeIteratorBase::move<TreeIteratorBase::Rightward>()
     87 {
     88   this->m_pNode = this->m_pNode->right;
     89 }
     90 
     91 template<> inline
     92 void TreeIteratorBase::hook<TreeIteratorBase::Leftward>(NodeBase* pOther)
     93 {
     94   this->m_pNode->left = pOther;
     95 }
     96 
     97 template<> inline
     98 void TreeIteratorBase::hook<TreeIteratorBase::Rightward>(NodeBase* pOther)
     99 {
    100   this->m_pNode->right = pOther;
    101 }
    102 
    103 template<typename DataType>
    104 class Node : public NodeBase
    105 {
    106 public:
    107   typedef DataType        value_type;
    108 
    109 public:
    110   value_type* data;
    111 
    112 public:
    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