/// ****************************************************************************
/// @file   
/// @author Dr.Neeton
/// @date   200X/X/X - 2014/01/14
/// 
/// @brief  ２分岐ノードクラス。
///
/// これらの動作検証はほとんどしていないので非推奨。
/// 
/// ****************************************************************************

#pragma once

#include "CPL_Core_BinaryTreeElement.h"

namespace CPL {
namespace Core {
namespace List {



// _____________________________________________________________________________
/// @brief ２分木ノードクラス
/// 
/// @tparam T_Instance : 保持するデータの型。大小比較ができること。
///
// *****************************************************************************
template<class T_Instance>
class BinaryTreeNode
  : public BinaryTreeElement< BinaryTreeNode<T_Instance> >
{
  friend class BinaryTreeNode<T_Instance>;

  using type_this          = BinaryTreeNode<T_Instance>;
  using type_this_ptr      = type_this*;
  using type_this_cptr     = type_this const*;
  using type_this_ref      = type_this&;
  using type_this_cref     = type_this const&;
  using type_instance_ptr  = T_Instance*;
  using type_instance_cptr = T_Instance const*;
  using type_instance_ref  = T_Instance&;
  using type_instance_cref = T_Instance const&;

protected:
  T_Instance m_instance;

public:
//  T_Instance&       Get()       { return m_instance; }
//  const T_Instance& Get() const { return m_instance; }

  type_instance_ptr  operator ->()       { return &m_instance; }
  type_instance_cptr operator ->() const { return &m_instance; }
  type_instance_ref  get()       { return m_instance; }
  type_instance_cref get() const { return m_instance; }

  template<class T>
  bool operator < ( BinaryTreeNode<T> const& btn ) const {
    return m_instance < btn.m_instance; }
  template<class T>
  bool operator <= ( BinaryTreeNode<T> const& btn ) const {
    return m_instance <= btn.m_instance; }

  template<class T>
  bool operator > ( BinaryTreeNode<T> const& btn ) const {
    return m_instance > btn.m_instance; }
  template<class T>
  bool operator >= ( BinaryTreeNode<T> const& btn ) const {
    return m_instance >= btn.m_instance; }
  
  // _____________________________________________________________________________
  /// @brief 自身を含む、下位の２分木から一致するノードを検索。
  /// @param[in] in_data : 検索するデータ。
  /// @return
  /// 該当するノードのポインタを返す。\n
  /// 該当しない場合、nullptrを返す。
  // ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  type_this_ptr Find( type_instance_cref in_data )
  {
    auto node = this;
    while( node )
    {
      if( in_data == node->get() )
      {
        return node;
      }
      else
      if( in_data < node->get() )
      {
        node = node->GetLow();
      }
      else
      if( in_data > node->get() )
      {
        node = node->GetHigh();
      }
      else
      {
        return nullptr;
      }
    }
    return nullptr;
  }
  
  // _____________________________________________________________________________
  /// @brief 追加。
  /// @return 追加したノードのポインタを返す。
  // ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  type_this_ptr Add( type_instance_cref in_data )
  {
    type_this_ptr ptr_tree_node = static_cast<type_this_ptr>(this);
    while( ptr_tree_node )
    {
      if( ptr_tree_node->get() == in_data )
      {
        return nullptr;
      }
      else
      if( in_data < ptr_tree_node->get() )
      {
        if( ptr_tree_node->GetLow() )
        {
          ptr_tree_node = ptr_tree_node->GetLow();
        }
        else
        {
          ptr_tree_node->m_ptr_low = CPL_NEW(type_this)( in_data, ptr_tree_node );
          return ptr_tree_node->GetLow();
        }
      }
      else
      if( ptr_tree_node->get() < in_data )
      {
        if( ptr_tree_node->GetHigh() )
        {
          ptr_tree_node = ptr_tree_node->GetHigh();
        }
        else
        {
          ptr_tree_node->m_ptr_high = CPL_NEW(type_this)( in_data, ptr_tree_node );
          return ptr_tree_node->GetHigh();
        }
      }
    }
    return nullptr;
  }

  // _____________________________________________________________________________
  /// @brief 下位ツリーから指定したデータのノードを削除。
  /// 
  /// @param[in] in_data : 削除するノードへの参照を指定します。
  /// @return
  /// 削除した位置に設定されたノードのポインタを返す。\n
  /// 削除対象が見つからない場合、-1相当のポインタを返す。
  // ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  type_this_ptr Del( type_instance_cref in_data )
  {
    type_this_ptr ptr_node_del = Find( in_data );
    if( ptr_node_del == nullptr )
    {
      return (type_this_ptr)-1;
    }
    auto ret = ptr_node_del->Detach();
    DEL( ptr_node_del );
    return ret;
  }

  // _____________________________________________________________________________
  /// @brief 下位ツリーから指定したノードを削除。
  /// 
  /// @param[in] in_ptr_node_del : 削除するノードのポインタを指定します。
  /// @return
  /// 削除した位置に設定されたノードのポインタを返す。\n
  /// 削除対象が見つからない場合、-1相当のポインタを返す。
  // ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  type_this_ptr Del( type_this_ptr in_ptr_node_del )
  {
    // 指定されたノードが、自身に含まれているかチェック。
    auto ptr_node_del = in_ptr_node_del;
    while( ptr_node_del )
    {
      if( ptr_node_del == this )
        break;
      ptr_node_del = ptr_node_del->GetParent();
    }
    if( ptr_node_del == nullptr ) // 自身に属するツリーに含まれていない。
    {
      return (type_this_ptr)-1;
    }

    auto ret = ptr_node_del->Detach();
    DEL( ptr_node_del );
    return ret;
  }

  // ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  BinaryTreeNode() {}
  // ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  BinaryTreeNode( type_instance_cref in_ref_data, type_this_ptr in_ptr_parent )
    : BinaryTreeElement<type_this>(in_ptr_parent)
    , m_instance(in_ref_data)
  {}
  // ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  ~BinaryTreeNode()
  {
    this->Detach();
  }
};




} // namespace List
} // namespace Core
} // namespace CPL

