#pragma once

// #include <iostream>
#include <cassert>
#include <stdexcept>

#define DECLARE_RULE5(Class, Action) \
  Class(const Class& other) = Action; \
  Class(Class&& other) = Action; \
  Class& operator=(const Class& other) = Action; \
  Class& operator=(Class&& other) = Action

#define DISABLE_COPY(Class) \
  DECLARE_RULE5(Class, delete);

namespace ecci {

// Functor
template <typename DataType>
struct Less {
  inline bool operator()(const DataType& value1, const DataType& value2) {
    return value1 < value2;
  }
};

template <typename DataType>
struct Greater {
  inline bool operator()(const DataType& value1, const DataType& value2) {
    return value1 > value2;
  }
};

// int foo() {
//   Less<int> less;
//   if (less(89, 7)) {    
//   }
// }

template <typename KeyType, typename ValueType
  , typename Comparator = Less<KeyType>>
class Map {
  DISABLE_COPY(Map);

 private:
  struct Node {
   public:
    DECLARE_RULE5(Node, delete);

   public:
    Node* parent;
    KeyType key;
    ValueType value;
    Node* left;
    Node* right;
    // ecci::Array<Node*> children;
    // ecci::List<Node*> children;

   public:
    explicit Node(const KeyType& key, const ValueType& value = ValueType()
      , Node* parent = nullptr, Node* left = nullptr, Node* right = nullptr)
      : parent(parent)
      , key(key)
      , value(value)
      , left(left)
      , right(right) {
    }

    ~Node() {
      delete this->left;
      delete this->right;
    }
    // void print(std::ostream& out) const {
    //   if (this->left) this->left->print(out);  // Left
    //   out << this->key << "=" << this->value << std::endl;  // Node
    //   if (this->right) this->right->print(out);  // Right
    // }
  };  // struct Node

 private:
  size_t count;
  Node* root;

 public:  // Construction, destruction!!!
  /// Default constructor
  Map()
    : count(0)
    , root(nullptr) {
  }
  /// Destrutor
  ~Map() {
    delete this->root;
  }

 public:  // Accessors
  /// Returns true if this map has no elements
  inline bool isEmpty() const { return this->root == nullptr; }
  inline size_t getCount() const { return this->count; }
  // friend std::ostream& operator<<(std::ostream& out, const Map& map) {
  //   if (map.root) {
  //     map.root->print(out);
  //   }
  //   return out;
  // }

 public:  // Insertion, removal
  /// Insert an element to the map
  void insert(const KeyType& key, const ValueType& value = ValueType()) {
    this->insertImpl(key, value);
    // TODO: return an iterator
  }
  /// Get acces to the associated value to the given key. If key does not exist
  /// in the map, it is inserted as a new element
  ValueType& operator[](const KeyType& key) {
    Node* node = this->insertImpl(key);
    return node->value;
  }

 public:
  class Iterator {
   public:
    DECLARE_RULE5(Iterator, default);

   private:
    Node* node;

   public:
    explicit Iterator(Node* node)
      : node(node) {
    }

    inline bool operator!=(const Iterator& other) const {
      return this->node != other.node;
    }

    /// this must not be end()
    inline KeyType& getKey() {
      assert(this->node);
      return this->node->key;
    }

    /// this must not be end()
    inline const KeyType& getKey() const {
      assert(this->node);
      return this->node->key;
    }

    /// this must not be end()
    inline ValueType& getValue() {
      assert(this->node);
      return this->node->value;
    }

    /// this must not be end()
    inline const ValueType& getValue() const {
      assert(this->node);
      return this->node->value;
    }

    inline Iterator& operator++() {
      this->node = Map::findNextNode(this->node);
      return *this;
    }
  };

  Iterator begin() {
    return Iterator(this->findMinimum(this->root));
  }

  Iterator end() {
    return Iterator(nullptr);
  }

 private:
  Node* insertImpl(const KeyType& key, const ValueType& value = ValueType()) {
    if (this->isEmpty()) {
      return this->root = this->createNode(key, value);
    } else {
      Comparator comparator;
      Node* current = this->root;
      while (true) {
        // if (key < current->key) {
        if (comparator(key, current->key)) {
          if (current->left == nullptr) {
            return current->left = this->createNode(key, value, current);
          } else {
            current = current->left;
          }
        // } else if (key > current->key) {
        } else if (comparator(current->key, key)) {
          if (current->right == nullptr) {
            return current->right = this->createNode(key, value, current);
          } else {
            current = current->right;
          }
        } else {
          // Set politics, element must not be twice within the container
          return current;
        }
      }  // while
    }  // if empty
  }

  Node* createNode(const KeyType& key, const ValueType& value = ValueType()
    , Node* parent = nullptr) {
    Node* newNode = new Node(key, value, parent);
    if (newNode == nullptr) {
      throw std::runtime_error("map: no memory to insert node");
    }
    ++this->count;
    return newNode;
  }

  static Node* findMinimum(Node* subtree) {
    if (subtree) {
      while (subtree->left) {
        subtree = subtree->left;
      }
    }
    return subtree;
  }

  static Node* findNextNode(Node* current) {
    Node* original = current;

    if (current->right) {
      return Map::findMinimum(current->right);
    }

    while (current->parent && current == current->parent->right) {
      current = current->parent;
      if (current->parent == nullptr) {
        return nullptr;
      }
    }

    if (current->parent && current == current->parent->left) {
      current = current->parent;
    }

    return current == original ? nullptr : current;
  }
};

}  // namespace ecci