#include <set>
#include <vector>
#include <utility>
#include <iterator>
#include <ranges>
#include <unordered_set>
#include <algorithm>

namespace ojl {
  template <typename T>
  struct bimap_left {
      T val;
  };

  template <typename T>
  struct bimap_right {
      T val;
  };


  template <typename L, typename R>
  struct CompareLeft {
      bool
      operator()(const std::pair<L, R> &lhs, const std::pair<L, R> &rhs) const
      {
          return lhs.first < rhs.first || (lhs.first == rhs.first && lhs.second < rhs.second);
      }

      bool
      operator()(const L &lhs, const std::pair<L, R> &rhs) const
      {
          return lhs < rhs.first;
      }

      bool
      operator()(const std::pair<L, R> &lhs, const L &rhs) const 
      {
          return lhs.first < rhs;
      }

      using is_transparent = L;
  };


  template <typename L, typename R>
  struct CompareRight {
      bool
      operator()(const std::pair<L, R> &lhs, const std::pair<L, R> &rhs) const
      {
          return lhs.second < rhs.second || (lhs.second == rhs.second && lhs.first < rhs.first);
      }

      bool
      operator()(const R &lhs, const std::pair<L, R> &rhs) const 
      {
          return lhs < rhs.second;
      }

      bool
      operator()(const std::pair<L, R> &lhs, const R &rhs) const 
      {
          return lhs.second < rhs;
      }

      using is_transparent = L;
  };


  //TODO: maybe add unkeyed versions of member functions for when L != R
  // (replacing left with L, right with R)

  template <typename L, typename R>
  struct bimap {
      using left = bimap_left<L>;
      using right = bimap_right<R>;

      using relation = std::pair<L,R>;

      using l_relation_set  = std::set<relation, CompareLeft<L,R>>;
      using r_relation_set  = std::set<relation, CompareRight<L,R>>;

      using relation_iterator = typename l_relation_set::iterator;

      //TODO: see if the iterator types are the same

      std::set<L>  left_elements;
      std::set<R>  right_elements;
      l_relation_set l_relations;
      r_relation_set r_relations;

      //TODO: badly named? Maybe should make the sets private if I have accessors...?
      const l_relation_set&
      relations_ref()
      {
          return l_relations;
      }

      std::vector<relation>
      all_relations_vec()
      {
          std::vector<relation> rel;
          for (auto it = l_relations.begin(); it != l_relations.end(); it++){
              rel.push_back(*it);
          }
          return rel;
      }


      // Insert elements
      void
      insert(left l_key)
      {
          left_elements.insert(l_key.val);
      }

      void
      insert(right r_key)
      {
          right_elements.insert(r_key.val);
      }

      void
      l_insert(L l)
      {
          left_elements.insert(l);
      }

      void
      r_insert(R r)
      {
          right_elements.insert(r);
      }

      // Insert relations
      void
      insert(relation rel)
      {
          left_elements.insert(rel.first);
          right_elements.insert(rel.second);
          l_relations.insert(rel);
          r_relations.insert(rel);
      }

      void
      insert(const L &l, const R &r)
      {
          left_elements.insert(l);
          right_elements.insert(r);
          l_relations.insert({l,r});
          r_relations.insert({l,r});
      }

      // Erase relations
      void
      erase(const relation &rel)
      {
          r_relations.erase(rel);
          l_relations.erase(rel);
      }

      void
      erase(const L &l, const R &r)
      {
          relation rel{l,r};
          r_relations.erase(rel);
          l_relations.erase(rel);
      }


      // Erase elements
      void
      erase(left l_key)
      {
          left_elements.erase(l_key.val);
          //Find all relations in l_relations and remove them from r_relations
          auto &[lb, ub] = l_relations.equal_range(l_key.val);
          for (auto it = lb; it < ub; it++){
              r_relations.erase(*it);
          }
          l_relations.erase(l_key.val);
      }

      void
      erase(right r_key)
      {
          right_elements.erase(r_key.val);
          auto &[lb, ub] = r_relations.equal_range(r_key.val);
          for (auto it = lb; it < ub; it++){
              l_relations.erase(*it);
          }
          r_relations.erase(r_key.val);
      }

      void
      l_erase(L l)
      {
          left_elements.erase(l);
          auto &[lb, ub] = l_relations.equal_range(l);
          for (auto it = lb; it < ub; it++){
              r_relations.erase(*it);
          }
          l_relations.erase(l);
      }

      void
      r_erase(R r)
      {
          right_elements.erase(r);
          auto &[lb, ub] = l_relations.equal_range(r);
          for (auto it = lb; it < ub; it++){
              r_relations.erase(*it);
          }
          r_relations.erase(r);
      }

      // Contains
      bool contains(relation rel)
      {
          return l_relations.contains(rel);
      }

      bool contains(L l, R r)
      {
          return l_relations.contains({l,r});
      }


      bool contains(left l_key)
      {
          return l_relations.contains(l_key.val);
      }

      bool contains(right r_key)
      {
          return r_relations.contains(r_key.val);
      }

      bool l_contains(L l)
      {
          return l_relations.contains(l);
      }

      bool r_contains(R r)
      {
          return r_relations.contains(r);
      }

      
      // Count
      size_t
      count(left l_key)
      {
          return l_relations.count(l_key.val);
      }

      size_t
      count(right r_key)
      {
          return r_relations.count(r_key.val);
      }

      size_t
      l_count(L l)
      {
          return l_relations.count(l);
      }

      size_t
      r_count(R r)
      {
          return r_relations.count(r);
      }

      // Min elements
      std::optional<L>
      l_min_element()
      {
          auto it = std::min_element(left_elements.begin(), left_elements.end());
          if (it != left_elements.end()){
              return *it;
          }
          return std::nullopt;
      }

      std::optional<R>
      r_min_element()
      {
          auto it = std::min_element(right_elements.begin(), right_elements.end());
          if (it != right_elements.end()){
              return *it;
          }
          return std::nullopt;
      }

      // Max elements
      std::optional<L>
      l_max_element()
      {
          auto it = std::max_element(left_elements.begin(), left_elements.end());
          if (it != left_elements.end()){
              return *it;
          }
          return std::nullopt;
      }

      std::optional<R>
      r_max_element()
      {
          auto it = std::max_element(right_elements.begin(), right_elements.end());
          if (it != right_elements.end()){
              return *it;
          }
          return std::nullopt;
      }

      // Min mapped elements
      std::optional<R>
      min_mapped_element(left l_key)
      {
          auto it = std::ranges::min_element(l_relations | std::views::filter([&l_key](relation rel){return rel.first == l_key.val;}));
          if (it != l_relations.end()){
              return it->second;
          }
          return std::nullopt;

      }

      std::optional<R>
      min_mapped_element(right r_key)
      {
          auto it = std::ranges::min_element(l_relations | std::views::filter([&r_key](relation rel){return rel.second == r_key.val;}));
          if (it != l_relations.end()){
              return it->first;
          }
          return std::nullopt;

      }

      std::optional<R>
      l_min_mapped_element(L l)
      {
          auto it = std::ranges::min_element(l_relations | std::views::filter([&l](relation rel){return rel.first == l;}));
          if (it != l_relations.end()){
              return it->second;
          }
          return std::nullopt;

      }

      std::optional<R>
      r_min_mapped_element(R r)
      {
          auto it = std::ranges::min_element(l_relations | std::views::filter([&r](relation rel){return rel.second == r;}));
          if (it != l_relations.end()){
              return it->first;
          }
          return std::nullopt;

      }

      // Max mapped elements
      std::optional<R>
      max_mapped_element(left l_key)
      {
          auto it = std::ranges::max_element(l_relations | std::views::filter([&l_key](relation rel){return rel.first == l_key.val;}));
          if (it != l_relations.end()){
              return it->second;
          }
          return std::nullopt;

      }

      std::optional<R>
      max_mapped_element(right r_key)
      {
          auto it = std::ranges::max_element(l_relations | std::views::filter([&r_key](relation rel){return rel.second == r_key.val;}));
          if (it != l_relations.end()){
              return it->first;
          }
          return std::nullopt;

      }

      std::optional<R>
      l_max_mapped_element(L l)
      {
          auto it = std::ranges::max_element(l_relations | std::views::filter([&l](relation rel){return rel.first == l;}));
          if (it != l_relations.end()){
              return it->second;
          }
          return std::nullopt;

      }

      std::optional<R>
      r_max_mapped_element(R r)
      {
          auto it = std::ranges::max_element(l_relations | std::views::filter([&r](relation rel){return rel.second == r;}));
          if (it != l_relations.end()){
              return it->first;
          }
          return std::nullopt;

      }

      // Equal range
      std::pair<relation_iterator, relation_iterator>
      equal_range(left l_key)
      {
          return l_relations.equal_range(l_key.val);
      }

      std::pair<relation_iterator, relation_iterator>
      equal_range(right r_key)
      {
          return r_relations.equal_range(r_key.val);
      }

      std::pair<relation_iterator, relation_iterator>
      l_equal_range(L l)
      {
          return equal_range(left{l});
      }

      std::pair<relation_iterator, relation_iterator>
      r_equal_range(R r)
      {
          return equal_range(right{r});
      }

      // Convenience function for getting a vector out
      std::vector<R>
      mapped_vector(left l_key)
      {
          std::vector<R> v;
          auto [lb, ub] = equal_range(l_key);
          v.reserve(std::distance(lb,ub));
          for (auto it = lb; it != ub; it++){
              v.push_back(it->second);
          }
          return v;
      }

      std::vector<L>
      mapped_vector(right r_key)
      {
          std::vector<L> v;
          auto [lb, ub] = equal_range(r_key);
          v.reserve(std::distance(lb,ub));
          for (auto it = lb; it != ub; it++){
              v.push_back(it->first);
          }
          return v;
      }

      // Convenience function for getting a set
      std::vector<R>
      mapped_set(left l_key)
      {
          std::set<R> s;
          auto [lb, ub] = equal_range(l_key);
          for (auto it = lb; it != ub; it++){
              s.insert(it->second);
          }
          return s;
      }

      std::vector<L>
      mapped_set(right r_key)
      {
          std::set<L> s;
          auto [lb, ub] = equal_range(r_key);
          s.insert(ub - lb);
          for (auto it = lb; it != ub; it++){
              s.insert(it->first);
          }
          return s;
      }

      std::vector<R>
      l_mapped_vector(L l)
      {
          return mapped_vector(left{l});
      }

      std::vector<L>
      r_mapped_vector(R r)
      {
          return mapped_vector(right{r});
      }

      std::vector<R>
      l_mapped_set(L l)
      {
          return mapped_set(left{l});
      }

      std::vector<L>
      r_mapped_set(R r)
      {
          return mapped_set(right{r});
      }

      // A complement of this bimap (in the set of possible relations between left_elements and right_elements)
      bimap<L,R>
      complement()
      {
          bimap<L,R> ret;
          // Insert elements
          for (const auto &l : left_elements){
              ret.l_insert(l);
          }
          for (const auto &r : right_elements){
              ret.r_insert(r);
          }

          // Insert relations
          for (const auto &l : left_elements){
              for (const auto &r : right_elements){
                  relation rel{l,r};
                  if (!this->contains(rel)){
                      ret.insert(rel);
                  }
              }
          }
          return ret;
      }

      bimap<L,R>
      complement(std::set<L> left_elems, std::set<R> right_elems)
      {
          bimap<L,R> ret;
          // Insert elements
          for (const auto &l : left_elems){
              ret.l_insert(l);
          }
          for (const auto &r : right_elems){
              ret.r_insert(r);
          }

          // Insert relations
          for (const auto &l : left_elems){
              for (const auto &r : right_elems){
                  relation rel{l,r};
                  if (!this->contains(rel)){
                      ret.insert(rel);
                  }
              }
          }
          return ret;
      }



      bimap<L,R>
      complement(std::vector<L> left_elems, std::vector<R> right_elems)
      {
          bimap<L,R> ret;
          // Insert elements
          for (const auto &l : left_elems){
              ret.l_insert(l);
          }
          for (const auto &r : right_elems){
              ret.r_insert(r);
          }

          // Insert relations
          for (const auto &l : left_elems){
              for (const auto &r : right_elems){
                  relation rel{l,r};
                  if (!this->contains(rel)){
                      ret.insert(rel);
                  }
              }
          }
          return ret;
      }


  };

  // Equality comparison
  template<typename L, typename R>
  bool
  operator==(const bimap<L,R> &lhs, const bimap<L,R> &rhs)
  {
      return lhs.left_elements  == rhs.left_elements 
          && lhs.right_elements == rhs.right_elements
          && lhs.l_relations    == rhs.l_relations;
     
      if (lhs.left_elements != rhs.left_elements || lhs.right_elements != rhs.right_elements) {
          return false;
      }
      return lhs.l_relations == rhs.l_relations;
  }

}