#include <iostream>
#include <memory>
#include <vector>
#include <string>
#include <unordered_map>
#include <algorithm>
#include <assert.h>

using std::vector;
using std::unordered_map;
using std::weak_ptr;
using std::shared_ptr;
using std::string;
using std::make_shared;
using std::static_pointer_cast;
using std::move;

struct DomElement;

struct DeepCopyContext {
    unordered_map<const void*, shared_ptr<void>> org_copy_map;

    shared_ptr<DomElement> register_element(const DomElement* original, shared_ptr<DomElement> copy) {
        org_copy_map.insert({ original, copy });
        return copy;
    }

    template<typename T>
    weak_ptr<T> resolve(const weak_ptr<T>& original) const {
        auto it = org_copy_map.find(original.lock().get());
        if (it != org_copy_map.end()) {
            // it's safe since it's filled with pairs of the exact same type
            return static_pointer_cast<T>(it->second);
        }
        return original;
    }
};

struct DomElement : std::enable_shared_from_this<DomElement> {
    weak_ptr<DomElement> parent;
    DomElement() = default;
    DomElement(DomElement& src) = delete; // prevent slicing
    virtual ~DomElement() = default;
    virtual shared_ptr<DomElement> deep_copy(DeepCopyContext&) = 0;
    virtual void resolve(DeepCopyContext&) {}
};

template<typename Element, typename Group, typename Parent = DomElement>
struct DomGroup : Parent {
    vector<shared_ptr<Element>> items;
    void add_item(shared_ptr<Element> item) {
        for (DomElement* i = this; i; i = i->parent.lock().get()) {
            if (i == item.get())
                throw std::runtime_error("Cycle in parent chain");
        }
        if (!item->parent.expired())
            throw std::runtime_error("Multiparenting");
        item->parent = Parent::shared_from_this();
        items.push_back(move(item));
    }
    void remove_item(const shared_ptr<Element>& item) {
        items.erase(std::remove(items.begin(), items.end(), item), items.end());
    }
    shared_ptr<DomElement> deep_copy(DeepCopyContext& ctx) override {
        auto result = make_shared<Group>();
        for (const auto& item : items)
            result->add_item(static_pointer_cast<Element>(item->deep_copy(ctx)));
        return ctx.register_element(this, result);
    }
    void resolve(DeepCopyContext& ctx) override {
        for (const auto& item : items)
            item->resolve(ctx);
    }
};

struct Style {
    string font;
    float size;
    int weight;

    Style(string f, float s, int w) : font(move(f)), size(s), weight(w) {}
    shared_ptr<Style> clone() const {
        return make_shared<Style>(*this);
    }
};

struct Bitmap {
    string src;
    Bitmap(string s) : src(move(s)) {}
    shared_ptr<Bitmap> clone() const {
        return make_shared<Bitmap>(*this);
    }
};

struct CardItem : DomElement {};
struct Card : DomGroup<CardItem, Card> {};
struct GroupItem : DomGroup<CardItem, GroupItem, CardItem> {};
struct Document : DomGroup<Card, Document> {};

struct TextItem : CardItem {
    string text;
    shared_ptr<const Style> style;

    TextItem(string t, shared_ptr<const Style> s) : text(move(t)), style(move(s)) {}

    shared_ptr<DomElement> deep_copy(DeepCopyContext& ctx) override {
        return ctx.register_element(this, make_shared<TextItem>(text, style));
    }
};

struct ImageItem : CardItem {
    shared_ptr<Bitmap> bitmap;

    ImageItem(shared_ptr<Bitmap> b) : bitmap(move(b)) {}

    shared_ptr<DomElement> deep_copy(DeepCopyContext& ctx) override {
        return ctx.register_element(this, make_shared<ImageItem>(bitmap));
    }
};

struct ButtonItem : CardItem {
    string caption;
    weak_ptr<Card> target_card;

    ButtonItem(string cap, weak_ptr<Card> target)
        : caption(move(cap)), target_card(move(target)) {}

    shared_ptr<DomElement> deep_copy(DeepCopyContext& ctx) override {
        return ctx.register_element(this, make_shared<ButtonItem>(caption, target_card));
    }

    void resolve(DeepCopyContext& ctx) override {
        target_card = ctx.resolve<Card>(target_card);
    }
};

struct ConnectorItem : CardItem {
    weak_ptr<CardItem> from, to;

    ConnectorItem(weak_ptr<CardItem> f, weak_ptr<CardItem> t) : from(move(f)), to(move(t)) {}

    shared_ptr<DomElement> deep_copy(DeepCopyContext& ctx) override {
        return ctx.register_element(this, make_shared<ConnectorItem>(from, to));
    }
    void resolve(DeepCopyContext& ctx) override {
        from = ctx.resolve(from);
        to = ctx.resolve(to);
    }
};

template<typename T>
shared_ptr<T> deep_copy(const shared_ptr<T>& src) {
    DeepCopyContext ctx;
    auto result = src->deep_copy(ctx);
    result->resolve(ctx);
    return static_pointer_cast<T>(result);
}

int main() {
    auto doc = make_shared<Document>();
    {
        auto style = make_shared<const Style>("Times", 16.5f, 600);
        auto card = make_shared<Card>();
        auto hello = make_shared<TextItem>("Hello", style);
        auto button = make_shared<ButtonItem>("Click me", card);
        auto conn = make_shared<ConnectorItem>(hello, button);
        card->add_item(move(hello));
        card->add_item(move(button));
        card->add_item(move(conn));
        doc->add_item(move(card));
    }
    {
        // "Unshare on modification" enforcement at compile-time.
        auto hello_text = std::dynamic_pointer_cast<TextItem>(doc->items[0]->items[0]);
        // This won't compile:
        // hello_text->style->size++;

        // This compiles and unshares on modification
        auto new_style = hello_text->style->clone();
        new_style->size++;
        hello_text->style = new_style;

        // Object protection by stack pointers:
        doc->items[0]->remove_item(hello_text);
        // Check that hello text is alive and pointed to by weak pointers
        // as long as it's retained by hello_text local
        assert(!std::dynamic_pointer_cast<ConnectorItem>(doc->items[0]->items[1])->from.expired());
        // here it's finally deleted
    }
    // Weaks handling:
    // Let's check that connector is no more pointing to the deleted text:
    assert(std::dynamic_pointer_cast<ConnectorItem>(doc->items[0]->items[1])->from.expired());

    // Topologically correct copy operation:
    // Let's copy the whole doc...
    auto new_doc = deep_copy(doc);

    // ...and check that connector copy points to the button copy
    assert(new_doc->items[0]->items[0] ==
        std::dynamic_pointer_cast<ConnectorItem>(new_doc->items[0]->items[1])->to.lock());

    // Let's check that button copy points to the card copy
    assert(new_doc->items[0] ==
        std::dynamic_pointer_cast<ButtonItem>(new_doc->items[0]->items[0])->target_card.lock());

    // Protection against multiparenting (runtime-only)
    try {
        doc->add_item(new_doc->items[0]);
    } catch (std::runtime_error&) {
        std::cout << "multiparenting\n";
    }

    // Protection against multiparenting (runtime-only)
    try {
        auto group = make_shared<GroupItem>();
        auto subgroup = make_shared<GroupItem>();
        group->add_item(subgroup);
        subgroup->add_item(group);

    } catch (std::runtime_error&) {
        std::cout << "loop\n";
    }

    return 0;
}