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_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 
     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 namespace 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 
     43 class TreeIteratorBase
     44 {
     45 public:
     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 
     55 public:
     56   NodeBase* m_pNode;
     57 
     58 public:
     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 
     90 namespace 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 
    110 template<typename DataType>
    111 class Node : public NodeBase
    112 {
    113 public:
    114   typedef DataType        value_type;
    115 
    116 public:
    117   value_type* data;
    118 
    119 public:
    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