include/mcld/ADT/TreeBase.h

//===- 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>
#include <cassert>
#include <iterator>

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

class 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