course_data_structures/proj1/main.cpp

#include "Utilities.h"
#include <algorithm>
#include <cctype>
#include <functional>
#include <iomanip>
#include <ios>
#include <iostream>
#include <list>
#include <string>
using namespace std;
#ifndef __cpp_if_constexpr
#define constexpr
#endif // !__cpp_if_constexpr
template <typename T>
struct reverse_wrapper
{
    T &iterable;
    auto begin() { return std::rbegin(iterable); }
    auto end() { return std::rend(iterable); }
};
template <typename T>
reverse_wrapper<T> reverse(T &&iterable) { return {iterable}; }
class ios_flags_guard
{
private:
    ios *prev_stat, *curr_stat;

public:
    ios_flags_guard(ios &cur)
    {
        prev_stat = new ios(nullptr);
        curr_stat = &cur;
        prev_stat->copyfmt(*curr_stat);
    }
    ~ios_flags_guard()
    {
        curr_stat->copyfmt(*prev_stat);
        delete prev_stat, curr_stat;
    }
};
template <typename T>
struct _List_Node
{
    using _p_List_Node = _List_Node *;
    T val;
    _p_List_Node pre, nxt;
};
template <typename T>
struct _List_Iterator
{
    using iterator_category = bidirectional_iterator_tag;
    using difference_type = ptrdiff_t;
    using value_type = T;
    using pointer = T *;
    using reference = T &;
    _List_Node<T> *pVal;
    _List_Iterator(_List_Node<T> *p) : pVal(p) {}
    reference operator*() const { return (*pVal).val; }
    pointer operator->() const { return &(operator*()); }
    _List_Iterator &operator++()
    {
        pVal = pVal->nxt;
        return *this;
    }
    _List_Iterator operator++(int)
    {
        auto orig = *this;
        pVal = pVal->nxt;
        return orig;
    }
    _List_Iterator &operator--()
    {
        pVal = pVal->pre;
        return *this;
    }
    _List_Iterator operator--(int)
    {
        auto orig = *this;
        pVal = pVal->pre;
        return orig;
    }

    bool operator==(const _List_Iterator &iter) const { return pVal == iter.pVal; }
    bool operator!=(const _List_Iterator &iter) const { return pVal != iter.pVal; }
};
template <typename T>
class List
{
public:
    using iterator = _List_Iterator<T>;
    List()
    {
        sentinel = new _List_Node<T>();
        sentinel->nxt = sentinel->pre = sentinel;
    }
    ~List()
    {
        clear();
        delete sentinel;
    }
    List &operator=(List &&rhs) noexcept
    {
        swap(sentinel, rhs.sentinel);
        return *this;
    }
    List(List &&rhs) noexcept
    {
        sentinel = new _List_Node<T>();
        sentinel->nxt = sentinel->pre = sentinel;
        swap(sentinel, rhs.sentinel);
    }
    iterator begin() { return iterator(sentinel->nxt); }
    iterator end() { return iterator(sentinel); }
    iterator rbegin() { return iterator(sentinel->pre); }
    iterator rend() { return iterator(sentinel); }
    iterator insert(iterator pos, const T &v)
    {
        auto ptr = new _List_Node<T>();
        ptr->val = v;
        ptr->pre = pos.pVal->pre;
        ptr->nxt = pos.pVal;
        pos.pVal->pre->nxt = ptr;
        pos.pVal->pre = ptr;
        return ptr;
    }
    void erase(iterator pos)
    {
        pos.pVal->pre->nxt = pos.pVal->nxt;
        pos.pVal->nxt->pre = pos.pVal->pre;
        delete pos.pVal;
    }
    bool empty() const
    {
        return sentinel->nxt == sentinel;
    }
    void push_back(const T &v)
    {
        insert(end(), v);
    }
    void pop_back()
    {
        erase(rbegin());
    }
    void clear()
    {
        while (!empty()) erase(begin());
    }

private:
    _List_Node<T> *sentinel;
};

class BigInt
{
private:
    List<int> lst;
    void sanitize()
    {
        const int base = 10;
        lst.push_back(0);
        auto ite2 = lst.begin();
        auto ite1 = ite2++;
        for (; ite2 != lst.end(); ite1++, ite2++)
            *ite2 += *ite1 / base, *ite1 %= base;
        while (!lst.empty() && *lst.rbegin() == 0)
            lst.pop_back();
    }

public:
    BigInt() {}
    BigInt(BigInt &&rhs) noexcept : lst(move(rhs.lst)) {}
    BigInt(const string &s)
    {
        if constexpr (0)
        {
            for (int st = s.length() - 3; st > -3; st -= 3)
            {
                int x = 0;
                for (int i = max(st, 0); i < st + 3; i++)
                    x = x * 10 + s[i] - '0';
                lst.push_back(x);
            }
        }
        else
        {
            if (s.front() == '-')
            {
                for (auto c : reverse(s))
                    lst.push_back('0' - c);
                lst.pop_back();
            }
            else
            {
                for (auto c : reverse(s))
                    lst.push_back(c - '0');
            }
        }
        sanitize();
    }
    BigInt &operator=(BigInt &&rhs) noexcept
    {
        lst = move(rhs.lst);
        return *this;
    }
    BigInt &operator=(const string &s)
    {
        lst.clear();
        if (s.front() == '-')
        {
            for (auto c : reverse(s))
                lst.push_back('0' - c);
            lst.pop_back();
        }
        else
        {
            for (auto c : reverse(s))
                lst.push_back(c - '0');
        }
        return *this;
    }
    BigInt operator+(BigInt &rhs)
    {
        BigInt ret;
        for (auto ite1 = lst.begin(), ite2 = rhs.lst.begin();
             ite1 != lst.end() || ite2 != rhs.lst.end();)
        {
            int v1 = ite1 != lst.end() ? *ite1++ : 0;
            int v2 = ite2 != rhs.lst.end() ? *ite2++ : 0;
            ret.lst.push_back(v1 + v2);
        }
        ret.sanitize();
        return ret;
    }
    friend ostream &operator<<(ostream &out, BigInt &x)
    {
        if (x.lst.empty())
            cout << 0;
        else
        {
            if (*x.lst.rbegin() < 0) cout << "-";

            for (auto ptr = x.lst.rbegin(); ptr != x.lst.rend(); ptr--)
                cout << abs(*ptr);
            // for (auto c : reverse(x.lst))    cout << abs(c);
        }
        return out;
    }
    void insert(int p, int v)
    {
        auto ite = lst.begin();
        if (*ite < 0) v = -v;
        advance(ite, p);
        lst.insert(ite, v);
        sanitize();
    }
    void remove(int p)
    {
        auto ite = lst.begin();
        advance(ite, p);
        lst.erase(ite);
        sanitize();
    }
};
int rep = 200, caps[120], rndres[201];
char buf[1200001];
char *filename =
#ifdef _DEBUG
    "debugres.txt"
#else
    "releaseres.txt"
#endif // _DEBUG
    ;
int main()
{
    auto fp = fopen(filename, "w");
    for (int i = 0; i < 120; i++) caps[i] = (i + 1) * 10000;
    if constexpr (1)
    {
        Timer timer;
        MemoryMonitor mm;
        Random rnd;
        vector<string> ss(sqrt(rep) + 1);
        for (int sz : caps)
        {
            for (auto &s : ss)
            {
                for (int i = 0; i < sz; i++) buf[i] = rnd.next('0', '9' + 1);
                buf[sz] = 0;
                s = buf;
            }
            vector<BigInt> is(ss.size());
            BigInt tmp_;
            for (int i = 0; i < ss.size(); i++) is[i] = ss[i];
            for (int i = 200; i; i--) rndres[i] = rnd.next(0, sz / 2);
            // add test
            timer.start();
            mm.reset();
            ([&] {
                int cnt = rep;
                for (auto &x : is)
                    for (auto &y : is)
                    {
                        tmp_ = x + y;
                        if (--cnt == 0) return;
                    }
            })();
            timer.stop();
            mm.save();
            printf("len %d add %d times time %.6lf ms, mem %lld bytes.\n",
                   sz, rep, timer.diff_in_ms(), mm.max_usage());
            fprintf(fp, "add,%.9lf,%lld\n", timer.diff_in_ms() / 1000, mm.max_usage());
            // del test
            timer.start();
            mm.reset();
            ([&] {
                int cnt = rep;
                for (;;)
                    for (auto &x : is)
                    {
                        x.remove(rndres[cnt]);
                        if (--cnt == 0) return;
                    }
            })();
            timer.stop();
            mm.save();
            printf("len %d del %d times time %.6lf ms, mem %lld bytes.\n",
                   sz, rep, timer.diff_in_ms(), mm.max_usage());
            fprintf(fp, "del,%.9lf,%lld\n", timer.diff_in_ms() / 1000, mm.max_usage());
            // add test
            timer.start();
            mm.reset();
            ([&] {
                int cnt = rep;
                for (;;)
                    for (auto &x : is)
                    {
                        x.insert(rndres[cnt], 0);
                        if (--cnt == 0) return;
                    }
            })();
            timer.stop();
            mm.save();
            printf("len %d ins %d times time %.6lf ms, mem %lld bytes.\n",
                   sz, rep, timer.diff_in_ms(), mm.max_usage());
            fprintf(fp, "ins,%.9lf,%lld\n", timer.diff_in_ms() / 1000, mm.max_usage());
        }
        fclose(fp);
        system("pause");
        return 0;
    }
    const auto filter = [](char c) { return !isdigit(c) && c != '-'; };
    const auto string_sanitize = [&filter](string &s) -> string & {
        s.erase(remove_if(s.begin(), s.end(), filter), s.end());
        return s;
    };
    int T, op;
    string s1, s2;
    cin >> T;
    while (T--)
    {
        cin >> op;
        if (op == 1)
        {
            cin >> s1 >> s2;
            BigInt n1(string_sanitize(s1)), n2(string_sanitize(s2));
            cout << n1 + n2 << endl;
        }
        if (op == 2)
        {
            int x, y;
            cin >> s1 >> x >> y;
            BigInt n1(string_sanitize(s1));
            n1.insert(x, y);
            cout << n1 << endl;
        }
        if (op == 3)
        {
            int x;
            cin >> s1 >> x;
            BigInt n1(string_sanitize(s1));
            n1.remove(x);
            cout << n1 << endl;
        }
    }
    return 0;
}