#ifndef TREE_H
#define TREE_H
#include "exc.h"
#include "log.h"
#include <cstdint>
#include <type_traits>
#include <vector>
#include <string>

using namespace std;



template<class T>
class btree{
public:
  struct node;
	btree();
	~btree();

	void insert(T);
	btree<T>::node* remove(T);
	node *search(T);
	void destroy_tree();
	void simmetrichniy();
	void obratniy();
	void pryamoy();

  void vprint( std::ostream& out = std::cout );

  void left_right();
  void right_left();


  struct node{
    T value;
    node *left;
    node *right;
  };


  node*min_element( node* leaf);
	void destroy_tree(node *leaf);
	void insert(T key, node *leaf);
	btree<T>::node* remove(T key, node *leaf);
	node *search(T key, node *leaf);
	void simmetrichniy(node *leaf);
	void obratniy(node *leaf);
	void pryamoy(node *leaf);

	node *root;
	node *_parrent;
};




template<class T>
typename btree<T>::node* btree<T>::remove(T key, node *leaf){
  INFO( "Уладение элемента" );
  if( leaf->value == key ){
    if( leaf->left == nullptr && leaf->right == nullptr ){
      return nullptr;
    }
    if( leaf->left == nullptr ){
      return leaf->right;
    }
    if( leaf->right == nullptr ){
      return leaf->left;
    }

    node* minleaf = min_element(leaf->right);
    leaf->value = leaf->value;

    leaf->right = remove( leaf->value ,leaf->right );

    return leaf;
  }


  if( key < leaf->value ){
    if( leaf->left == nullptr ){
      WARN("Элемент не найден");
      return leaf;
    }
    leaf->left = remove( key, leaf->left );
    return leaf;
  }


  if( key > leaf->value ){
    if( leaf->right == nullptr ){
      WARN("Элемент не найден");
      return leaf;
    }

    leaf->right = remove( key, leaf->right );
    return leaf;
  }

  ERROR("unexpexted behaviour");
  return nullptr;

}

template<class T>
typename btree<T>::node* btree<T>::min_element(node* leaf) {
  INFO( "Поиск левого элемента" );
  if (leaf->left == nullptr) return leaf;

  return min_element(leaf->left);
}

template<class T>
typename btree<T>::node* btree<T>::remove(T key){
  INFO( "Уладение элемента" );
  if (root == nullptr) {
      return nullptr;
  }

  root = remove(key, root );

  ERROR("unexpexted behaviour");
  return nullptr;
}

template<class T>
void btree<T>::left_right(){
  INFO( "Поиск левого элемента правого поддерева" );
  if( root->left == nullptr ){
    cout << "Левого поддерева нет" << endl;
  }else{
    node *n = root->left;
    while( n->right != nullptr ){
      n = n->right;
    }
    cout << "Самый правый в левом поддереве " << n->value << endl;
  }
}



template<class T>
void btree<T>::right_left(){
  INFO( "Поиск правого элемента левого поддерева" );
  if( root->right == nullptr ){
    cout << "Правого поддерева нет" << endl;
  }else{
    node *n = root->right;
    while( n->left != nullptr ){
      n = n->left;
    }
    cout << "Самый левый в правом поддереве " << n->value << endl;
  }
}




template<class T>
void btree<T>::vprint(std::ostream& out  ){
  INFO( "Горизонтальная печать дерева" );

  vector< vector<string> > some;
  node* p = root;
  vector<node*> depth;
  vector<node*> next_depth;
  depth.push_back( root );
  vector<string> layer;
  bool flag = true;
  while ( flag ) {
    layer.clear();
    next_depth.clear();
    for( auto p : depth ){
        if( p != nullptr ){
        string in;
        in += p->value;
        layer.push_back( in );
        if( p->left != nullptr || 1 ){
          next_depth.push_back( p->left );
        }

        if( p->right != nullptr || 1 ){
          next_depth.push_back( p->right );
        }
      }else{
        layer.push_back("-");
        next_depth.push_back( nullptr );
        next_depth.push_back( nullptr );
      }
    }
    depth = next_depth;
    some.push_back( layer );

    flag = false;
    for( auto i : depth ){
      if( i != nullptr ){
        flag = true;
      }
    }
  }




  //falsy print
  int max_len = -1;
  int len = 0;
  for( auto l : some ){
    len = 0;
    for( auto e: l ){
      len += e.size();
      len ++;
    }
    len--;
    if( len > max_len ){
      max_len = len;
    }
  }


  layer.clear();
  int sep = 0;
  for( int _i = 0; _i < some.size(); _i++ ){
    int index = some.size() - 1 - _i;
    string line = "";
    for( int j = 0; j < sep; j++ ){
      line += ' ';
    }
    sep = 2 * sep + 1;
    for( auto elem: some[ index ] ){
      line += elem;
      for( int j = 0; j < sep; j++ ){
        line += ' ';
      }
    }
    layer.insert( layer.begin(), line);
  }


  for( auto l : layer ){
    out << l << endl;
  }



  out << endl;

}


template<class T>
btree<T>::btree(){
  INFO( "Создание дерева" );
	root = nullptr;
}

template<class T>
btree<T>::~btree(){
  INFO( "Удаление дерева" );
	destroy_tree();
}



template<class T>
void btree<T>::insert(T key, node *leaf){
  INFO( "Вставка в дерево" );

	if(key < leaf->value){
		if(leaf->left != nullptr){
			insert(key, leaf->left);
		}else{
			leaf->left = new node;
			leaf->left->value = key;
			leaf->left->left = nullptr;
			leaf->left->right = nullptr;
		}
	}else if(key > leaf->value){ // ??? >=
		if(leaf->right != nullptr){
			insert(key, leaf->right);
		}else{
			leaf->right = new node;
			leaf->right->value = key;
			leaf->right->right = nullptr;
			leaf->right->left = nullptr;
		}
	}

}

template<class T>
void btree<T>::insert(T key){
  INFO( "Вставка в дерево" );
	if(root != nullptr){
		insert(key, root);
	}else{
		root = new node;
		root->value = key;
		root->left = nullptr;
		root->right = nullptr;
	}
}

template<class T>
typename btree<T>::node* btree<T>::search(T key, btree<T>::node *leaf){
  INFO( "поиск по дереву" );
	if(leaf != nullptr){
		if(key == leaf->value){
			return leaf;
		}
		if(key < leaf->value){
			return search(key, leaf->left);
		}else{
			return search(key, leaf->right);
		}
	}else{
    WARN("Элемент не найден");
		return nullptr;
	}
}

template<class T>
typename btree<T>::node *btree<T>::search(T key){
	return search(key, root);
}

template<class T>
void btree<T>::destroy_tree(){
	destroy_tree(root);
}

template<class T>
void btree<T>::simmetrichniy(){
	simmetrichniy(root);
	cout << "\n";
}

template<class T>
void btree<T>::simmetrichniy(node *leaf){
	if(leaf != nullptr){
		simmetrichniy(leaf->left);
		cout << leaf->value << ",";
		simmetrichniy(leaf->right);
	}
}

template<class T>
void btree<T>::destroy_tree(node *leaf){
  INFO( "Очитка дерева" );
  root = nullptr;
}

template<class T>
void btree<T>::obratniy(){
	obratniy(root);
	cout << "\n";
}

template<class T>
void btree<T>::obratniy(node *leaf){
	if(leaf != nullptr){
		obratniy(leaf->left);
		obratniy(leaf->right);
		cout << leaf->value << ",";
	}
}

template<class T>
void btree<T>::pryamoy(){
	pryamoy(root);
	cout << "\n";
}

template<class T>
void btree<T>::pryamoy(node *leaf){
	if(leaf != nullptr){
		cout << leaf->value << ",";
		pryamoy(leaf->left);
		pryamoy(leaf->right);
	}
}


#endif