#pragma once

#include <map>
#include <utility>
#include <iostream>
#include <type_traits>

template <typename T>
class Polynomial {
public:
    using coefficient_type = T;

    using exponent_type = int;

    using storage_type = std::map<exponent_type, coefficient_type, std::greater<exponent_type>>;

    using item_type = std::pair<exponent_type, coefficient_type>;

    Polynomial() { }

    Polynomial(const Polynomial& other)
        : data(other.data)
    { }

    Polynomial(Polynomial&& other)
        : data(std::move(other.data))
    { }

    Polynomial(std::initializer_list<item_type> src)
        : Polynomial(src, true)
    { }

    template <typename Seq>
    Polynomial(Seq seq, bool = true) { // "bool = true" for delegation above
        for (auto&& pair : seq) {
            data[pair.first] += pair.second;
        }
    }

    Polynomial copy() const {
        return *this;
    }

    Polynomial& modify_add(const Polynomial& other) {
        for (auto&& pair : other.data) {
            data[pair.first] += pair.second;
        }
        return *this;
    }

    Polynomial& modify_sub(const Polynomial& other) {
        for (auto&& pair : other.data) {
            data[pair.first] -= pair.second;
        }
        return *this;
    }

    Polynomial& modify_mul(coefficient_type k, exponent_type e = 0) {
        storage_type new_data {};
        for (auto&& pair : data) {
            new_data[pair.first + e] = pair.second * k; 
        }
        data = std::move(new_data);
        return *this;
    }

    Polynomial& modify_mul(item_type pair) {
        return modify_mul(pair.second, pair.first);
    }

    Polynomial& modify_mul(const Polynomial& other) {
        return *this = mul(other);
    }

    Polynomial add(const Polynomial& other) const {
        return copy().modify_add(other);
    }

    Polynomial sub(const Polynomial& other) const {
        return copy().modify_sub(other);
    }

    Polynomial mul(const Polynomial& other) const {
        Polynomial<T> result;
        for (auto&& pair : other.data) {
            result += copy().modify_mul(static_cast<item_type>(pair));
        }
        return result;
    }

    void print(std::ostream& os) const {
        bool first = true;

        for (auto&& pair: data) {
            if (pair.second == 0) {
                continue;
            }

            if (!first && pair.second > 0) {
                os << "+";
            }

            os << pair.second;

            if (pair.first != 0) {
                os << "x^";

                if (pair.first < 0) {
                    os << "(";
                }

                os << pair.first;

                if (pair.first < 0) {
                    os << ")";
                }
            }

            first = false;
        }
    }

    Polynomial& operator=(const Polynomial& other) {
        data = other.data;
        return *this;
    }

    Polynomial& operator=(Polynomial&& other) {
        data = std::move(other.data);
        return *this;
    }

private:
    storage_type data;
};


template <typename T>
std::ostream& operator<<(std::ostream& os, const Polynomial<T>& poly) {
    poly.print(os);
    return os;
}

template <typename T>
Polynomial<T>& operator+=(Polynomial<T>& lhs, const Polynomial<T>& rhs) {
    return lhs.modify_add(rhs);
}


template <typename T>
Polynomial<T>& operator-=(Polynomial<T>& lhs, const Polynomial<T>& rhs) {
    return lhs.modify_sub(rhs);
}


template <typename T>
Polynomial<T>& operator*=(Polynomial<T>& lhs, const Polynomial<T>& rhs) {
    return lhs.modify_mul(rhs);
}


template <typename T>
Polynomial<T> operator+(const Polynomial<T>& lhs, const Polynomial<T>& rhs) {
    return lhs.add(rhs);
}


template <typename T>
Polynomial<T> operator-(const Polynomial<T>& lhs, const Polynomial<T>& rhs) {
    return lhs.sub(rhs);
}


template <typename T>
Polynomial<T> operator*(const Polynomial<T>& lhs, const Polynomial<T>& rhs) {
    return lhs.mul(rhs);
}

template <typename T>
Polynomial<T> operator*(const T& lhs, const Polynomial<T>& rhs) {
    return rhs.mul({{1, lhs}});
}

template <typename T>
Polynomial<T> operator*(const Polynomial<T>& lhs, const T& rhs) {
    return lhs.mul({{1, rhs}});
}