//===- TreeBase.h ---------------------------------------------------------===//
//
// The MCLinker Project
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
#ifndef MCLD_TREE_BASE_H
#define MCLD_TREE_BASE_H
#include "mcld/ADT/TypeTraits.h"
#include <cstddef>
namespace mcld
{
class NodeBase
{
public:
NodeBase *left;
NodeBase *right;
public:
NodeBase()
: left(0), right(0)
{ }
};
namespace proxy
{
template<size_t DIRECT>
inline void move(NodeBase *&X)
{ assert(0 && "not allowed"); }
template<size_t DIRECT>
inline void hook(NodeBase *X, const NodeBase *Y)
{ assert(0 && "not allowed"); }
} // namespace of template proxy
struct TreeIteratorBase
{
public:
enum Direct {
Leftward,
Rightward
};
typedef size_t size_type;
typedef ptrdiff_t difference_type;
typedef std::bidirectional_iterator_tag iterator_category;
public:
NodeBase* m_pNode;
public:
TreeIteratorBase()
: m_pNode(0)
{ }
TreeIteratorBase(NodeBase *X)
: m_pNode(X)
{ }
virtual ~TreeIteratorBase(){};
template<size_t DIRECT>
inline void move() {
proxy::move<DIRECT>(m_pNode);
}
bool isRoot() const
{ return (m_pNode->right == m_pNode); }
bool hasRightChild() const
{ return ((m_pNode->right) != (m_pNode->right->right)); }
bool hasLeftChild() const
{ return ((m_pNode->left) != (m_pNode->left->right)); }
bool operator==(const TreeIteratorBase& y) const
{ return this->m_pNode == y.m_pNode; }
bool operator!=(const TreeIteratorBase& y) const
{ return this->m_pNode != y.m_pNode; }
};
namespace proxy
{
template<>
inline void move<TreeIteratorBase::Leftward>(NodeBase *&X)
{ X = X->left; }
template<>
inline void move<TreeIteratorBase::Rightward>(NodeBase *&X)
{ X = X->right; }
template<>
inline void hook<TreeIteratorBase::Leftward>(NodeBase *X, const NodeBase *Y)
{ X->left = const_cast<NodeBase*>(Y); }
template<>
inline void hook<TreeIteratorBase::Rightward>(NodeBase* X, const NodeBase* Y)
{ X->right = const_cast<NodeBase*>(Y); }
} //namespace of template proxy
template<typename DataType>
class Node : public NodeBase
{
public:
typedef DataType value_type;
public:
value_type* data;
public:
Node()
: NodeBase(), data(0)
{ }
Node(const value_type& pValue)
: NodeBase(), data(&pValue)
{ }
};
} // namespace of mcld
#endif