#ifndef KEYED_QUEUE_H
#define KEYED_QUEUE_H

#include <map>
#include <list>
#include <memory>
#include <exception>
#include <cassert>
#include <vector>


class lookup_error : public std::exception {
    virtual const char* what () const noexcept {
        return "Lookup error";
    }
};


template <class K, class V> class keyed_queue {
private:
    using kv_pair = std::pair<K, V>;
    using kv_queue = std::list<kv_pair>;
    using iterator_list = std::list<typename kv_queue::iterator>;
    using k_map = std::map<K, iterator_list>;

    struct queue_data {
        kv_queue queue;
        k_map map;
        bool shareable;

        queue_data() : queue({}), map({}), shareable(true) {}

        queue_data(queue_data const& other) :
                queue(other.queue),
                map(set_k_maps(queue)),
                shareable(true) {}
    };
    class k_iterator {
        friend class keyed_queue<K, V>;
    private:
        typename k_map::const_iterator k_map_iterator;

    public:
        k_iterator(){}
        k_iterator(k_iterator const & other) : k_map_iterator(other.k_map_iterator){}
        k_iterator(typename k_map::const_iterator k_map_iterator) : k_map_iterator(k_map_iterator) {}
        k_iterator & operator++(){
            ++k_map_iterator;
            return *this;
        }
        bool operator==(k_iterator const & other){ return k_map_iterator == other.k_map_iterator;}
        bool operator!=(k_iterator const & other){ return k_map_iterator != other.k_map_iterator;}
        K const & operator*(){ return k_map_iterator->first;}
    };
    kv_queue key_queue;
    k_map iterators_map;
    std::shared_ptr<queue_data>data_pointer;
    static k_map set_k_maps(kv_queue &queue) {
        k_map map;
        for (auto element_it = queue.begin(); element_it != queue.end(); element_it++) {
            const K& key = element_it->first;
            map[key].push_back(element_it);
        }
        return std::move(map);
    }

    std::pair<std::shared_ptr<unique_data>, bool> foo() {
        if (data_pointer.use_count() > 1) {
            return {std::make_shared<unique_data>(*data_pointer), true};
        } else {
            data_pointer->shareable = true;
            return {data_pointer, false};
        }
    }


public:

    keyed_queue() : data_pointer(std::make_shared<queue_data>()) {}

    keyed_queue(const keyed_queue& other){
        if (other.data_pointer->shareable) {
            data_pointer = other.data_pointer;
        } else {
            data_pointer = std::make_shared<queue_data>(*other.data_pointer);
            data_pointer->shareable = true;
        }
    }

    keyed_queue(keyed_queue &&other) : data_pointer(std::move(other.data_pointer)) {}

    keyed_queue &operator=(keyed_queue other) {
        data_pointer = other.data_pointer;
        return *this;
    }
    void push(K const &k, V const &v) {
        std::shared_ptr<queue_data> new_pointer;
        bool copied = false;
        if (data_pointer.use_count() > 1){
            new_pointer = std::make_shared<queue_data>(*data_pointer);
            copied = true;
        }
        else {
            data_pointer->shareable = true;
            new_pointer = data_pointer;
        }
        new_pointer->queue.push_back(std::make_pair(k, v));
        try {
            new_pointer->map[k].push_back(--new_pointer->queue.end());
        } catch (...) {
            new_pointer->queue.pop_back();
            throw;
        }

        if (copied) std::swap(data_pointer, new_pointer);
    }

    void pop() {
        if (data_pointer->queue.size() == 0) throw lookup_error();

        std::shared_ptr<queue_data> new_pointer;
        bool copied = false;
        if (data_pointer.use_count() > 1){
            new_pointer = std::make_shared<queue_data>(*data_pointer);
            copied = true;
        }
        else {
            data_pointer->shareable = true;
            new_pointer = data_pointer;
        }

        auto& element = data_pointer->queue.front();
        auto map_it = new_pointer->map.find(element.first);
        auto& k_list = map_it->second;
        new_pointer->queue.erase(k_list.front());
        k_list.pop_front();
        if (k_list.empty()) {
            new_pointer->map.erase(map_it);
        }

        if (copied) std::swap(data_pointer, new_pointer);
    }

    void pop(K const &key) {
        bool copied = false;
        std::shared_ptr<queue_data> new_pointer;
        if (data_pointer.use_count > 1){
            new_pointer = std::make_shared<queue_data>(*data_pointer);
            copied = true;
        }
        else {
            data_pointer->shareable = true;
            new_pointer = data_pointer;
        }
        auto it = data_pointer->map.find(key);
        if (it == data_pointer->map.end()) throw lookup_error();
    }

    void move_to_back(const K &key) {
        auto map_iterator = data_pointer->map.find(key);
        if (map_iterator == data_pointer->map.end()) throw lookup_error();

        std::shared_ptr<queue_data> new_pointer;
        bool copied = false;
        if (data_pointer.use_count() > 1){
            new_pointer = std::make_shared<queue_data>(*data_pointer);
            copied = true;
        }
        else {
            data_pointer->shareable = true;
            new_pointer = data_pointer;
        }

        auto &map = new_pointer->map[key];

        for (auto element_it: map) {
            new_pointer->queue.splice(new_pointer->queue.end(), new_pointer->queue, element_it);
        }

        if (copied) std::swap(data_pointer, new_pointer);
    }

    std::pair<K const &, V &> front() {
        if (data_pointer->queue.empty()) throw lookup_error();
        if (data_pointer.use_count() > 1) {
            data_pointer = std::make_shared<queue_data>(*data_pointer);
        }
        data_pointer->shareable = false;
        kv_pair kv = data_pointer->queue.front();
        return {kv.first, kv.second};
    }

    std::pair<K const &, V &> back() {
        if (data_pointer->queue.empty()) throw lookup_error();
        if (data_pointer.use_count() > 1) {
            data_pointer = std::make_shared<queue_data>(*data_pointer);
        }
        data_pointer->shareable = false;
        kv_pair kv = data_pointer->queue.back();
        return {kv.first, kv.second};
    }

    std::pair<K const &, V const &> front() const {
        if (data_pointer->queue.empty()) throw lookup_error();

        kv_pair kv = data_pointer->queue.front();
        return {kv.first, kv.second};
    }

    std::pair<K const &, V const &> back() const {
        if (data_pointer->queue.empty()) throw lookup_error();

        kv_pair kv = data_pointer->queue.back();
        return {kv.first, kv.second};
    }

    std::pair<K const &, V &> first(K const &key) {
        auto map_iterator = data_pointer->map.find(key);
        if (map_iterator == data_pointer->map.end()) throw lookup_error();

        std::shared_ptr<queue_data> new_pointer;
        bool copied = false;
        if (data_pointer.use_count() > 1){
            new_pointer = std::make_shared<queue_data>(*data_pointer);
            copied = true;
        }
        else {
            data_pointer->shareable = true;
            new_pointer = data_pointer;
        }

        auto &pair_ref = *new_pointer->map.at(key).front();
        new_pointer->shareable = false;

        if (copied) std::swap(data_pointer, new_pointer);
        return {pair_ref.first, pair_ref.second};
    }

    std::pair<K const &, V &> last(K const &key) {
        auto map_iterator = data_pointer->map.find(key);
        if (map_iterator == data_pointer->map.end()) throw lookup_error();

        std::shared_ptr<queue_data> new_pointer;
        bool copied = false;
        if (data_pointer.use_count() > 1){
            new_pointer = std::make_shared<queue_data>(*data_pointer);
            copied = true;
        }
        else {
            data_pointer->shareable = true;
            new_pointer = data_pointer;
        }

        auto &pair_ref = *data_pointer->map.at(key).back();
        data_pointer->shareable = false;

        if (copied) std::swap(this->data_pointer, data_pointer);
        return {pair_ref.first, pair_ref.second};
    }

    std::pair<K const &, V const &> first(K const &key) const {
        auto map_iterator = data_pointer->map.find(key);
        if (map_iterator == data_pointer->map.end()) throw lookup_error();

        auto &pair_ref = *data_pointer->map.at(key).front();
        return {pair_ref.first, pair_ref.second};
    }

    std::pair<K const &, V const &> last(K const &key) const {
        auto map_iterator = data_pointer->map.find(key);
        if (map_iterator == data_pointer->map.end()) throw lookup_error();

        auto &pair_ref = *data_pointer->map.at(key).back();
        return {pair_ref.first, pair_ref.second};
    }

    size_t size() const {
        return data_pointer->queue.size();
    }

    bool empty() const {
        return data_pointer->queue.empty();
    }

    void clear() {
        if (data_pointer.use_count() > 1) {
            data_pointer = std::make_shared<queue_data>(*data_pointer);
        }
        data_pointer->shareable = true;
        data_pointer->map.clear();
        data_pointer->queue.clear();
    }

    size_t count(K const &key) const {
        if (data_pointer->map.find(key) == data_pointer->map.end()) return 0;
        return (data_pointer->map.at(key)).size();
    }

    k_iterator k_begin() {
    return k_iterator(data_pointer->map.cbegin());
    }

    k_iterator k_end() {
    return k_iterator(data_pointer->map.cend());
    }

};

#endif

auto f(keyed_queue<int, int> q)
{
  return q;
}

int main()
{
  int keys[] = {3, 1, 2};

  keyed_queue<int, int> kq1 = f({});

  for (int i = 0; i < 3; ++i) {
    kq1.push(keys[i], i);
  }
  auto &ref = kq1.front().second;

  keyed_queue<int, int> kq2(kq1); // Wykonuje się pełna kopia, dlaczego?
  keyed_queue<int, int> kq3;
  kq3 = kq2;

  ref = 10;
  assert(kq1.front().second == 10);
  assert(kq2.front().second != 10);

  kq2.pop(); // Obiekt kq2 dokonuje kopii i przestaje współdzielić dane z kq3.
  assert(kq2.size() == 2);
  assert(kq2.count(3) == 0);
  assert(kq2.count(2) == 1);

  assert(kq3.size() == 3);
  assert(kq3.count(3) == 1);

  kq2.push(1, 3);
  kq2.move_to_back(1);
  assert(kq2.size() == 3);
  assert(kq2.front().second == 2
         && kq2.first(1).second == 1
         && kq2.last(1).second == 3
         && kq2.back().second == 3);

  keyed_queue<int, int> const kq4 = kq2;
  assert(kq4.front().second == 2
         && kq4.first(1).second == 1
         && kq4.last(1).second == 3
         && kq4.back().second == 3);

  int i = 1;
  for (auto k_it = kq1.k_begin(), k_end = kq1.k_end();
       k_it != k_end;
       ++k_it, ++i) {
    assert(i <= 3 && *k_it == i);
  }

  auto kq5 = std::make_unique<keyed_queue<int, int>>();
  kq5->push(4, 0);
  assert(kq5->front().first == 4 && kq5->front().second == 0);
  auto kq6(*kq5);
  kq5.reset();
  assert(kq6.front().first == 4 && kq6.front().second == 0);

  std::swap(kq1, kq2);
  std::vector<keyed_queue<int, int>> vec;
  for (int i = 0; i < 100000; i++) {
    kq1.push(i, i);
  }
  for (int i = 0; i < 1000000; i++) {
    vec.push_back(kq1);  // Wszystkie obiekty w vec współdzielą dane.
  }

  return 0;
}