//===- TreeBase.h ---------------------------------------------------------===//
//
//                     The MCLinker Project
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
#ifndef MCLD_ADT_TREEBASE_H
#define MCLD_ADT_TREEBASE_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)
  { }
};

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>
  void move() { assert(0 && "not allowed"); }

  template<size_t DIRECT>
  void hook(NodeBase* pNode) { assert(0 && "not allowed"); }

  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; }
};

template<> inline
void TreeIteratorBase::move<TreeIteratorBase::Leftward>()
{
  this->m_pNode = this->m_pNode->left;
}

template<> inline
void TreeIteratorBase::move<TreeIteratorBase::Rightward>()
{
  this->m_pNode = this->m_pNode->right;
}

template<> inline
void TreeIteratorBase::hook<TreeIteratorBase::Leftward>(NodeBase* pOther)
{
  this->m_pNode->left = pOther;
}

template<> inline
void TreeIteratorBase::hook<TreeIteratorBase::Rightward>(NodeBase* pOther)
{
  this->m_pNode->right = pOther;
}

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