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