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 
     15 namespace mcld
     16 {
     17 
     18 class NodeBase
     19 {
     20 public:
     21   NodeBase *left;
     22   NodeBase *right;
     23 
     24 public:
     25   NodeBase()
     26   : left(0), right(0)
     27   { }
     28 };
     29 
     30 namespace proxy
     31 {
     32   template<size_t DIRECT>
     33   inline void move(NodeBase *&X)
     34   { assert(0 && "not allowed"); }
     35 
     36   template<size_t DIRECT>
     37   inline void hook(NodeBase *X, const NodeBase *Y)
     38   { assert(0 && "not allowed"); }
     39 
     40 } // namespace of template proxy
     41 
     42 struct TreeIteratorBase
     43 {
     44 public:
     45   enum Direct {
     46     Leftward,
     47     Rightward
     48   };
     49 
     50   typedef size_t                          size_type;
     51   typedef ptrdiff_t                       difference_type;
     52   typedef std::bidirectional_iterator_tag iterator_category;
     53 
     54 public:
     55   NodeBase* m_pNode;
     56 
     57 public:
     58   TreeIteratorBase()
     59   : m_pNode(0)
     60   { }
     61 
     62   TreeIteratorBase(NodeBase *X)
     63   : m_pNode(X)
     64   { }
     65 
     66   virtual ~TreeIteratorBase(){};
     67 
     68   template<size_t DIRECT>
     69   inline void move() {
     70     proxy::move<DIRECT>(m_pNode);
     71   }
     72 
     73   bool hasRightChild() const
     74   { return ((m_pNode->right) != (m_pNode->right->right)); }
     75 
     76   bool hasLeftChild() const
     77   { return ((m_pNode->left) != (m_pNode->left->right)); }
     78 
     79   bool operator==(const TreeIteratorBase& y) const
     80   { return this->m_pNode == y.m_pNode; }
     81 
     82   bool operator!=(const TreeIteratorBase& y) const
     83   { return this->m_pNode != y.m_pNode; }
     84 };
     85 
     86 namespace proxy
     87 {
     88   template<>
     89   inline void move<TreeIteratorBase::Leftward>(NodeBase *&X)
     90   { X = X->left; }
     91 
     92   template<>
     93   inline void move<TreeIteratorBase::Rightward>(NodeBase *&X)
     94   { X = X->right; }
     95 
     96   template<>
     97   inline void hook<TreeIteratorBase::Leftward>(NodeBase *X, const NodeBase *Y)
     98   { X->left = const_cast<NodeBase*>(Y); }
     99 
    100   template<>
    101   inline void hook<TreeIteratorBase::Rightward>(NodeBase* X, const NodeBase* Y)
    102   { X->right = const_cast<NodeBase*>(Y); }
    103 
    104 } //namespace of template proxy
    105 
    106 template<typename DataType>
    107 class Node : public NodeBase
    108 {
    109 public:
    110   typedef DataType        value_type;
    111 
    112 public:
    113   value_type* data;
    114 
    115 public:
    116   Node()
    117   : NodeBase(), data(0)
    118   { }
    119 
    120   Node(const value_type& pValue)
    121   : NodeBase(), data(&pValue)
    122   { }
    123 
    124 };
    125 
    126 } // namespace of mcld
    127 
    128 #endif
    129