/// ****************************************************************************
/// @file   
/// @author Dr.Neeton
/// @date   200X/X/X - 2014/01/22
/// 
/// @brief  ２分木クラス　基本要素
/// 
/// これらの動作検証はほとんどしていないので非推奨。
///
/// ****************************************************************************

#pragma once

#include "../../Base/CPL_Core_Basic.h"
#include "../../Pointer/CPL_Core_Iterator.h"

namespace CPL {
namespace Core {
namespace List {


// _____________________________________________________________________________
/// @brief ２分岐要素クラス
///
/// @tparam T_TypeElm
///   : BinaryTreeElementを継承したクラスであること。\n
/// 　　また、大小の比較が可能であること。
///
// *****************************************************************************
template<class T_TypeElm>
class BinaryTreeElement
  : public Core::BaseObject
{
private:
  typedef T_TypeElm*       type_target_ptr;
  typedef T_TypeElm const* type_target_cptr;
  typedef T_TypeElm&       type_target_ref;
  typedef T_TypeElm const& type_target_cref;

  typedef BinaryTreeElement<T_TypeElm> type_this;
  //typedef type_this                    binary_tree_element_;

protected:
  friend type_this;
//  typedef T_TypeElm BTREE_NODE;
  type_target_ptr m_ptr_low;
  type_target_ptr m_ptr_high;
  type_target_ptr m_ptr_parent;
  size_t          m_node_count; // なるべくツリーを最適化するため、カウンタを保持してみた。

public:
  // _____________________________________________________________________________
  /// @brief 低位のノードポインタを取得。
  // ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  type_target_ptr GetLow()    const { return m_ptr_low; }

  // _____________________________________________________________________________
  /// @brief 高位のノードポインタを取得。
  // ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  type_target_ptr GetHigh()   const { return m_ptr_high; }

  // _____________________________________________________________________________
  /// @brief 親ノードポインタを取得。
  // ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  type_target_ptr GetParent() const { return m_ptr_parent; }

  // _____________________________________________________________________________
  /// @brief 最上階のノードポインタを取得。
  // ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  type_target_ptr GetRoot() const
  {
    auto node = this;
    while( node->GetParent() )
    {
      node = node->GetParent();
    }
    return node;
  }
  
  // _____________________________________________________________________________
  /// @brief 自分から一番近い高位のノードポインタを取得。
  ///
  /// ※ 大きいノードがなければ自身を返す。
  // ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  type_target_cptr GetNearHigh() const
  {
    return m_ptr_high ? m_ptr_high->GetNearLow()
                      : static_cast<type_target_cptr>(this);
  }
  /// @copydoc GetNearHigh
  type_target_ptr GetNearHigh()
  {
    return m_ptr_high ? m_ptr_high->GetNearLow()
                      : static_cast<type_target_ptr>(this);
  }
  
  // _____________________________________________________________________________
  /// @brief 自分から一番近い低位のノードポインタを取得。
  ///
  /// ※ 小さいノードがなければ自身を返す。
  // ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  type_target_cptr GetNearLow() const
  {
    return m_ptr_low ? m_ptr_low->GetNearHigh()
                     : static_cast<type_target_cptr>(this);
  }
  /// @copydoc GetNearLow
  type_target_ptr GetNearLow()
  {
    return m_ptr_low ? m_ptr_low->GetNearHigh()
                     : static_cast<type_target_ptr>(this);
  }

  // _____________________________________________________________________________
  /// @brief 自分を含む低位ノードから最低位のノードポインタを取得。
  // ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  type_target_ptr GetMin() const
  {
    type_target_cptr ptr_tree_node     = static_cast<type_target_cptr>(this);
    type_target_cptr ptr_ret_tree_node = nullptr;
    while( ptr_tree_node )
    {
      ptr_ret_tree_node = ptr_tree_node;
      ptr_tree_node     = ptr_tree_node->GetLow();
    }
    return const_cast<type_target_ptr>(ptr_ret_tree_node);
  }

  // _____________________________________________________________________________
  /// @brief 自分を含む高位ノードから最高位のノードポインタを取得。
  // ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  type_target_ptr GetMax() const
  {
    type_target_cptr ptr_tree_node     = static_cast<type_target_cptr>(this);
    type_target_cptr ptr_ret_tree_node = nullptr;
    while( ptr_tree_node )
    {
      ptr_ret_tree_node = ptr_tree_node;
      ptr_tree_node = ptr_tree_node->GetHigh();
    }
    return const_cast<type_target_ptr>(ptr_ret_tree_node);
  }

  // _____________________________________________________________________________
  /// @brief 保持する下位ノード数を取得（自身も含む）
  // ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  size_t GetNum() const
  {
    return m_node_count;
  }

  // _____________________________________________________________________________
  /// @brief 自分を含む、低位の２分木から一致するノードを検索。
  ///
  /// @param[in] in_data : 比較する要素。
  // ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  type_target_ptr Find( type_target_cref in_data ) const
  {
    type_target_cptr ptr_tree_node = static_cast<type_target_cptr>(this);
    while( ptr_tree_node )
    {
      if( in_data == *ptr_tree_node )
      {
        return const_cast<type_target_ptr>(ptr_tree_node);
      }
      else
      if( in_data < *ptr_tree_node )
      {
        ptr_tree_node = ptr_tree_node->GetLow();
      }
      else
      if( in_data > *ptr_tree_node )
      {
        ptr_tree_node = ptr_tree_node->GetHigh();
      }
      else
      {
        return nullptr;
      }
    }
    return nullptr;
  }

  // _____________________________________________________________________________
  /// @brief 追加。
  ///
  /// 同一のデータがある場合は追加しない(失敗とする)。\n
  /// @param[in] in_data : 追加する要素。
  /// @return
  /// 追加したノードのポインタを返す。\n
  /// 追加できなかった場合、nullptrを返す。
  // ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  type_target_ptr Add( type_target_cref in_data )
  {
    type_target_cptr ptr_tree_node = static_cast<type_target_cptr>(this);
    while( ptr_tree_node )
    {
      if( *ptr_tree_node == in_data )
      {
        return nullptr;
      }
      else
      if( in_data < *ptr_tree_node )
      {
        if( auto parent = ptr_tree_node->GetParent() )
        {
          if( *parent > in_data )
          {
            return parent->Add( in_data );
          }
        }
        if( ptr_tree_node->GetLow() )
        {
          ptr_tree_node = ptr_tree_node->GetLow();
        }
        else
        {
          // 追加。
          ptr_tree_node->m_ptr_low = CPL_NEW(T_TypeElm)( in_data );
          // カウンタ調整。
          auto parent = ptr_tree_node->GetParent();
          while( parent )
          {
            parent->m_node_count++;
            parent = parent->GetParent();
          }
          //
          return ptr_tree_node->m_ptr_low;
        }
      }
      else
      if( in_data > *ptr_tree_node )
      {
        if( auto parent = ptr_tree_node->GetParent() )
        {
          if( *parent < in_data )
          {
            return parent->Add( in_data );
          }
        }
        if( ptr_tree_node->GetHigh() )
        {
          ptr_tree_node = ptr_tree_node->GetHigh();
        }
        else
        {
          // 追加。
          ptr_tree_node->m_ptr_high = CPL_NEW(T_TypeElm)( in_data );
          // カウンタ調整。
          auto parent = ptr_tree_node->GetParent();
          while( parent )
          {
            parent->m_node_count++;
            parent = parent->GetParent();
          }
          //
          return ptr_tree_node->m_ptr_high;
        }
      }
    }
    return nullptr;
  }

  // _____________________________________________________________________________
  /// @brief 低位ツリーから指定したデータのノードを削除。
  ///
  /// @param[in] in_data : 削除要素への参照。
  ///
  /// @return
  /// 削除したノードの位置に新たに設定されたノードを指すポインタを返す。\n
  /// 削除ノードが末端の場合(新たに設定されない場合)、nullptrを返す。\n
  /// 削除に失敗した場合、-1相当のポインタを返す。
  // ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  type_target_ptr Del( type_target_cref in_data )
  {
    type_target_cptr ptr_node_del = Find( in_data );
    if( ptr_node_del == nullptr )
    {
      return (type_target_ptr)-1;
    }
    else
    if( ptr_node_del )
    {
      auto ret = ptr_node_del->Detach();
      DEL( ptr_node_del );
      return ret;
    }
  }
  
private:
  void zzf_decCntParents_( type_target_ptr parent )
  {
    while( parent )
    {
      --parent->m_node_count;
      parent = parent->GetParent();
    }
  }
public:
  // _____________________________________________________________________________
  /// @brief デタッチ（切り離し）
  /// @return
  /// 同じ位置に新しく設定されたノードのポインタを返す。\n
  /// 削除対象が末端の場合(同じ位置に設定されない場合)nullptrを返す。
  // ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  type_target_ptr Detach()
  {
    //******  ツリーから自身を除外する  *****//
    static type_target_ptr this_link_dummy = nullptr;
    type_target_ptr& node_this_link   =
      (m_ptr_parent == nullptr)
        ? this_link_dummy
        : (m_ptr_parent->m_ptr_low == this)
            ? m_ptr_parent->m_ptr_low
            : m_ptr_parent->m_ptr_high;
    type_target_ptr ret_node = nullptr;

    // 子が無い場合。
    if( !m_ptr_low  &&  !m_ptr_high )
    {
      if( m_ptr_parent ) // 親がある場合、親のリンクを調整。
      {
        if( *type_target_ptr(this) < *m_ptr_parent ) // 自身が親の小さい側ならば。
        {
          m_ptr_parent->m_ptr_low = nullptr;
        }
        else
        if( *type_target_ptr( this ) > *m_ptr_parent ) // 自身が親の大きい側ならば。
        {
          m_ptr_parent->m_ptr_high = nullptr;
        }
        m_ptr_parent->m_node_count--;
      }
    }
    // 低ノードが無い(高ノードのみある)場合。
    else
    if( !m_ptr_low )
    {
      if( m_ptr_parent )
      {
        zzf_decCntParents_( m_ptr_parent );
        if( node_this_link )
        {
          node_this_link = m_ptr_high;
        }
      }
      ret_node = m_ptr_high;
    }
    // 高ノードが無い(低ノードのみある)場合。
    else
    if( !m_ptr_high )
    {
      if( m_ptr_parent )
      {
        zzf_decCntParents_( m_ptr_parent );
        if( node_this_link )
        {
          node_this_link = m_ptr_low;
        }
      }
      ret_node = m_ptr_low;
    }
    // 両方の子を持つ場合。
    else
    {
      // 移動対象のノードを検索。
      size_t const low_cnt  = m_ptr_low->GetNum();
      size_t const high_cnt = m_ptr_high->GetNum();
      type_target_ptr
        node_move =
          (low_cnt < high_cnt)
            ? m_ptr_high->GetMin()
            : m_ptr_low->GetMax();
      // 移動対象ノードへのリンクを持つノード。
      auto const node_move_parent = node_move->GetParent(); // 必ず存在している。
      //auto const node_move_low    = node_move->GetLow();
      //auto const node_move_high   = node_move->GetHigh();
      //auto&      node_move_link   =
      //    (node_move_parent->m_ptr_low == this)
      //      ? node_move_parent->m_ptr_low
      //      : node_move_parent->m_ptr_high;

      // 移動元の上位階層のカウンタを調整。
      zzf_decCntParents_( node_move_parent );
      //***** 削除対象へのリンクの調整。 *****/
      // 親のリンク調整。
      if( node_this_link )
      {
        node_this_link = node_move;
      }
      // 低ノードのリンク調整。
      if( m_ptr_low )
      {
        m_ptr_low->m_ptr_parent =
          (m_ptr_low==node_move) ? nullptr : node_move;
      }
      // 高ノードのリンク調整。
      if( m_ptr_high )
      {
        m_ptr_high->m_ptr_parent =
          (m_ptr_high==node_move) ? nullptr : node_move;
      }

      //***** 移動対象のリンク調整。 *****//
      node_move->Detach(); // いったんデタッチ。
      node_move->m_ptr_parent = m_ptr_parent;
      node_move->m_ptr_low    = (m_ptr_low !=node_move) ? m_ptr_low  : nullptr;
      node_move->m_ptr_high   = (m_ptr_high!=node_move) ? m_ptr_high : nullptr;
      //
      node_move->m_node_count =
        (node_move->m_ptr_low  ? node_move->m_ptr_low->GetNum() : 0) +
        (node_move->m_ptr_high ? node_move->m_ptr_high->GetNum() : 0);

      ret_node = node_move;
    }
    //
    this->m_ptr_parent = nullptr;
    this->m_ptr_low    = nullptr;
    this->m_ptr_high   = nullptr;
    this->m_node_count = 0;

    return ret_node;
  }
  
  // _____________________________________________________________________________
  /// @brief コンストラクタ。
  ///
  /// @param[in] in_ptr_parent : 親ノードポインタ。
  /// @param[in] in_ptr_low    : 低位ノードポインタ。
  /// @param[in] in_ptr_high   : 高位ノードポインタ。
  // ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  BinaryTreeElement
  ( type_target_ptr in_ptr_parent
  , type_target_ptr in_ptr_low  = nullptr
  , type_target_ptr in_ptr_high = nullptr
  ) : m_ptr_low   ( in_ptr_low )
    , m_ptr_high  ( in_ptr_high )
    , m_ptr_parent( in_ptr_parent )
    , m_node_count( (in_ptr_low!=nullptr) + (m_ptr_high!=nullptr) + 1 )
  {}

  // _____________________________________________________________________________
  /// @brief デストラクタ。
  // ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  ~BinaryTreeElement()
  {
    Detach();
  }
};




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

