#ifndef BINARY_SEARCH_TREE_H_
#define BINARY_SEARCH_TREE_H_
#include <vector>
#include <iostream>
#include "set_interface.h"

template<typename T>
class BinarySearchTree : public SetInterface<T> {
 protected:
  struct TreeNode;
 public:
  class ConstIterator : public std::iterator<std::bidirectional_iterator_tag,
                                             T> {
   public:
    const T& operator*() const;
    const T* operator->() const;

    ConstIterator& operator++();
    ConstIterator operator++(int);

    ConstIterator& operator--();
    ConstIterator operator--(int);

    bool operator==(const ConstIterator&) const;
    bool operator!=(const ConstIterator&) const;

   private:
    ConstIterator(TreeNode* element, bool is_end);
    TreeNode* element_;
    bool is_end_;

    friend class BinarySearchTree;
  };
  BinarySearchTree() : size_(0), top_node_(nullptr), begin_(nullptr) {}
  BinarySearchTree(const std::initializer_list<T>& list);

  BinarySearchTree(const BinarySearchTree<T>& other_tree);
  BinarySearchTree& operator=(const BinarySearchTree& other_tree);

  BinarySearchTree(BinarySearchTree<T>&& other_tree);
  BinarySearchTree& operator=(BinarySearchTree&& other_tree);
  ~BinarySearchTree();

  int size() const override;
  bool empty() const override;
  bool contains(const T& value) const override;
  void insert(const T& value) override;
  void erase(const T& value) override;
  std::vector<T> ToVector() const override;

  bool operator==(const BinarySearchTree& other_tree) const;
  bool operator!=(const BinarySearchTree& other_tree) const;

  virtual int count(const T& value) const;

  ConstIterator begin() const;
  ConstIterator end() const;

  void erase(const ConstIterator& value);

  ConstIterator find(const T& value) const;

 protected:
  TreeNode* GetNode(const T& value) const;
  void ReplaceNode(TreeNode* old_node, TreeNode* new_node);
  TreeNode* GetLowestInSubTree(TreeNode* cur_node) const;
  void CreateVector(TreeNode* current_node, std::vector<T>* result) const;
  void VectorToTree(int l, int r, const std::vector<T>& vector_to_copy);
  void DestroyNode(TreeNode* node);

  struct TreeNode {
    T value;
    TreeNode* parent;
    TreeNode* left;
    TreeNode* right;
   private:
    TreeNode(const T&, TreeNode*, TreeNode*, TreeNode*);
    friend class BinarySearchTree;
  };

  int size_;
  TreeNode* top_node_;
  TreeNode* begin_;
};

template<typename T>
const T& BinarySearchTree<T>::ConstIterator::operator*() const {
  return element_->value;
}

template<typename T>
const T* BinarySearchTree<T>::ConstIterator::operator->() const {
  return &(element_->value);
}

template<typename T>
bool BinarySearchTree<T>::ConstIterator::operator==(
    const BinarySearchTree::ConstIterator& second_itr) const {
  return element_ == second_itr.element_ && is_end_ == second_itr.is_end_;
}

template<typename T>
bool BinarySearchTree<T>::ConstIterator::operator!=(
    const BinarySearchTree::ConstIterator& second_itr) const {
  return !(*this == second_itr);
}

template<typename T>
typename BinarySearchTree<T>::ConstIterator&
BinarySearchTree<T>::ConstIterator::operator++() {
  if (element_->right != nullptr) {
    element_ = element_->right;
    while (element_->left != nullptr) {
      element_ = element_->left;
    }
  } else {
    TreeNode* prev = nullptr;
    while (element_->right == prev && element_->parent != nullptr) {
      prev = element_;
      element_ = element_->parent;
    }
    if (element_->right == prev) {
      is_end_ = true;
    }
  }
  return *this;
}

template<typename T>
typename BinarySearchTree<T>::ConstIterator
BinarySearchTree<T>::ConstIterator::operator++(int) {
  auto temp = *this;
  ++(*this);
  return temp;
}

template<typename T>
typename BinarySearchTree<T>::ConstIterator&
BinarySearchTree<T>::ConstIterator::operator--() {
  if (is_end_) {
    is_end_ = false;
    while (element_->right != nullptr) {
      element_ = element_->right;
    }
  } else {
    if (element_->left != nullptr) {
      element_ = element_->left;
      while (element_->right != nullptr) {
        element_ = element_->right;
      }
    } else {
      TreeNode* prev = nullptr;
      while (element_->left == prev && element_->parent != nullptr) {
        prev = element_;
        element_ = element_->parent;
      }
      assert(element_->left != prev);
    }
  }
  return *this;
}
template<typename T>
typename BinarySearchTree<T>::ConstIterator
BinarySearchTree<T>::ConstIterator::operator--(int) {
  auto temp = *this;
  --(*this);
  return temp;
}

template<typename T>
BinarySearchTree<T>::ConstIterator::ConstIterator(
    BinarySearchTree::TreeNode* element, bool is_end):
    element_(element),
    is_end_(is_end) {}

template<typename T>
BinarySearchTree<T>::TreeNode::TreeNode(const T& value,
                                        BinarySearchTree::TreeNode* parent,
                                        BinarySearchTree::TreeNode* left,
                                        BinarySearchTree::TreeNode* right)
    : value(value), parent(parent), left(left), right(right) {}

template<typename T>
BinarySearchTree<T>::BinarySearchTree(const std::initializer_list<T>& list) {
  size_ = 0;
  for (auto& i : list) {
    insert(i);
  }
}

template<typename T>
BinarySearchTree<T>::BinarySearchTree(const BinarySearchTree<T>& other_tree) {
  std::vector<T> vector_to_copy = other_tree.ToVector();
  size_ = 0;
  VectorToTree(0, other_tree.size() - 1, vector_to_copy);
}

template<typename T>
BinarySearchTree<T>& BinarySearchTree<T>::operator=(
    const BinarySearchTree& other_tree) {
  if (this == &other_tree) {
    return *this;
  }
  DestroyNode(top_node_);
  top_node_ = begin_ = nullptr;
  std::vector<T> vector_to_copy = other_tree.ToVector();
  VectorToTree(0, other_tree.size() - 1, vector_to_copy);
}

template<typename T>
BinarySearchTree<T>::BinarySearchTree(BinarySearchTree<T>&& other_tree) {
  top_node_ = other_tree.top_node_;
  size_ = other_tree.size_;
  begin_ = other_tree.begin_;
  other_tree.top_node_ = other_tree.begin_ = nullptr;
  other_tree.size_ = 0;
}

template<typename T>
BinarySearchTree<T>& BinarySearchTree<T>::operator=(
    BinarySearchTree&& other_tree) {
  if (this == &other_tree) {
    return *this;
  }
  DestroyNode(top_node_);
  top_node_ = other_tree.top_node_;
  size_ = other_tree.size_;
  begin_ = other_tree.begin_;
  other_tree.top_node_ = other_tree.begin_ = nullptr;
  other_tree.size_ = 0;
}

template<typename T>
int BinarySearchTree<T>::size() const {
  return size_;
}

template<typename T>
bool BinarySearchTree<T>::empty() const {
  return size_ == 0;
}

template<typename T>
bool BinarySearchTree<T>::contains(const T& value) const {
  TreeNode* current_node = GetNode(value);
  return current_node != nullptr;
}
template<typename T>
void BinarySearchTree<T>::insert(const T& value) {
  size_++;
  if (size_ == 1) {
    top_node_ = new TreeNode(value, nullptr, nullptr, nullptr);
    begin_ = top_node_;
    return;
  }
  TreeNode* current_node = top_node_;
  TreeNode* prev_node = nullptr;
  while (current_node != nullptr) {
    prev_node = current_node;
    if (current_node->value < value) {
      current_node = current_node->right;
    } else {
      current_node = current_node->left;

    }
  }
  auto* new_node = new TreeNode(value, prev_node, nullptr, nullptr);
  if (prev_node->value < value) {
    prev_node->right = new_node;
  } else {
    prev_node->left = new_node;

  }
  if (begin_->left != nullptr) {
    begin_ = begin_->left;
  }
}

template<typename T>
void BinarySearchTree<T>::erase(const T& value) {
  TreeNode* current_node = GetNode(value);
  if (current_node == nullptr) {
    return;
  }
  size_--;
  if (current_node->left == nullptr || current_node->right == nullptr) {
    TreeNode* new_node;
    if (current_node->left != nullptr) {
      new_node = current_node->left;
    } else {
      new_node = current_node->right;
    }

    ReplaceNode(current_node, new_node);
  } else {
    TreeNode* new_node = GetLowestInSubTree(current_node->right);
    new_node->left = current_node->left;
    ReplaceNode(new_node, nullptr);
    new_node->right = current_node->right;
    ReplaceNode(current_node, new_node);
  }
  if (current_node == begin_) {
    begin_ = top_node_;
    while (begin_ != nullptr && begin_->left != nullptr) {
      begin_ = begin_->left;
    }
  }
  delete current_node;
}

template<typename T>
typename BinarySearchTree<T>::TreeNode*
BinarySearchTree<T>::GetNode(const T& value) const {
  TreeNode* current_node = top_node_;
  TreeNode* ans = nullptr;
  while (current_node != nullptr) {
    if (!(current_node->value < value) && !(value < current_node->value)) {
      ans = current_node;
    }
    if (current_node->value < value) {
      current_node = current_node->right;
    } else {
      current_node = current_node->left;
    }
  }
  return ans;
}
template<typename T>
void BinarySearchTree<T>::ReplaceNode(BinarySearchTree::TreeNode* old_node,
                                      BinarySearchTree::TreeNode* new_node) {
  TreeNode* parent = old_node->parent;
  if (parent != nullptr) {
    if (parent->left == old_node) {
      parent->left = new_node;
    } else {
      parent->right = new_node;
    }
  } else {
    top_node_ = new_node;
  }
  if (new_node != nullptr) {
    new_node->parent = parent;
    if (new_node->left != nullptr) {
      new_node->left->parent = new_node;
    }
    if (new_node->right != nullptr) {
      new_node->right->parent = new_node;
    }
  }
}

template<typename T>
typename BinarySearchTree<T>::TreeNode* BinarySearchTree<T>::GetLowestInSubTree(
    BinarySearchTree::TreeNode* cur_node) const {
  while (cur_node != nullptr && cur_node->left != nullptr) {
    cur_node = cur_node->left;
  }
  return cur_node;
}

template<typename T>
std::vector<T> BinarySearchTree<T>::ToVector() const {
  std::vector<T> result;
  CreateVector(top_node_, &result);
  return result;
}

template<typename T>
void BinarySearchTree<T>::CreateVector(BinarySearchTree<T>::TreeNode* current_node,
                                       std::vector<T>* result) const {
  if (current_node == nullptr) {
    return;
  }
  CreateVector(current_node->left, result);
  result->push_back(current_node->value);
  CreateVector(current_node->right, result);
}

template<typename T>
bool BinarySearchTree<T>::operator==(const BinarySearchTree& other_tree) const {
  if (size_ != other_tree.size_) {
    return false;
  }
  std::vector<T> first_vector = ToVector();
  std::vector<T> second_vector = other_tree.ToVector();
  for (int i = 0; i < first_vector.size(); i++) {
    if (first_vector[i] < second_vector[i]
        || second_vector[i] < first_vector[i]) {
      return false;
    }
  }
  return true;
}

template<typename T>
bool BinarySearchTree<T>::operator!=(const BinarySearchTree& other_tree) const {
  return !(*this == other_tree);
}

template<typename T>
int BinarySearchTree<T>::count(const T& value) const {
  int counter = 0;
  TreeNode* current_node = top_node_;
  while (current_node != nullptr) {
    if (!(current_node->value < value) && !(value < current_node->value)) {
      counter++;
    }
    if (current_node->value < value) {
      current_node = current_node->right;
    } else {
      current_node = current_node->left;
    }
  }
  return counter;
}

template<typename T>
void BinarySearchTree<T>::VectorToTree(int l, int r,
                                       const std::vector<T>& vector_to_copy) {
  if (l > r) {
    return;
  }
  int m = (l + r) / 2;
  insert(vector_to_copy[m]);
  VectorToTree(l, m - 1, vector_to_copy);
  VectorToTree(m + 1, r, vector_to_copy);
}

template<typename T>
void BinarySearchTree<T>::DestroyNode(TreeNode* node) {
  if (node == nullptr) {
    return;
  }
  DestroyNode(node->left);
  DestroyNode(node->right);
  delete node;
  size_--;
}

template<typename T>
BinarySearchTree<T>::~BinarySearchTree() {
  DestroyNode(top_node_);
}

template<typename T>
typename BinarySearchTree<T>::ConstIterator BinarySearchTree<T>::begin() const {
  return ConstIterator(begin_, size_ == 0);
}

template<typename T>
typename BinarySearchTree<T>::ConstIterator BinarySearchTree<T>::end() const {
  return ConstIterator(top_node_, true);
}

template<typename T>
void BinarySearchTree<T>::erase(const BinarySearchTree::ConstIterator& value) {
  erase(value.element_);
}

template<typename T>
typename BinarySearchTree<T>::ConstIterator BinarySearchTree<T>::find(
    const T& value) const {
  TreeNode* node = GetNode(value);
  if (node == nullptr) {
    return ConstIterator(top_node_, true);
  }
  return ConstIterator(node, false);
}

#endif  // BINARY_SEARCH_TREE_H_