#ifndef MAP_H
#define MAP_H

#include "BinarySearchTree.h"
#include <cassert>  //assert
#include <utility>  //pair

template <typename Key_type, typename Value_type,
          typename Key_compare=std::less<Key_type> // default argument
         >
class Map {

private:
  using Pair_type = std::pair<Key_type, Value_type>;
  class PairComp {
    private:
      Key_compare key;
    public:
      bool operator()(const Pair_type &pair1, const Pair_type &pair2) {
        return key(pair1.first, pair2.first);
      }
  };

public:
  using Iterator = typename BinarySearchTree<Pair_type, PairComp>::Iterator;

  bool empty() const {
    return bst.empty();
  }

  size_t size() const {
    return bst.size();
  }

  Iterator find(const Key_type& k) const {
    return bst.find(Pair_type(k, Value_type()));
  }

  Value_type& operator[](const Key_type& k) {
    Iterator found = this->find(k);
    if(found != bst.end()) {
      return found->second;
    } else {
      Pair_type p = {k, Value_type()};
      std::pair<Iterator, bool> p2;
      p2 = insert(p);
      Pair_type &pair_out = *(p2.first);
      return pair_out.second;
    }
  }

  std::pair<Iterator, bool> insert(const Pair_type &val) {
    Iterator found = this->find(val.first);
    if(found != bst.end()) {
      return std::pair<Iterator, bool>(found, false);
    } else 
    {
      // Pair_type p1 = {val, Value_type()};
      // std::pair<Iterator, bool> p2;
      // p2 = insert(p);
      return std::pair<Iterator, bool>(bst.insert(val), true);
    }

  }

  Iterator begin() const {
    return bst.begin();
  }

  Iterator end() const {
    return bst.end();
  }

private:
  BinarySearchTree <Pair_type, PairComp> bst;
};


#endif