Spreadsheet

#include <string>
#include <map>
#include <iostream>
#include <queue>
#include <variant>
#include <unordered_set>

using namespace std;

// Talking about trade offs of either read-heavy or write-heavy?
// 1. Update Parent/
// 2. parent can get to child using different path?

class SpreadSheetBFS {
public:
    map<string, variant<int, pair<string, string>>> m;
    SpreadSheetBFS() {}

    // Time: O(n)
    int getCell(string key) {
        if (!m.count(key)) {
            throw runtime_error("Key not found");
        }

        return bfs(key);
    }

    // Time: O(1)
    void setCell(string key, variant<int, pair<string, string>> val) {
        m[key] = val;
    }

    int bfs(string key) {
        queue<string> q;
        q.push(key);

        int res = 0;
        while (!q.empty()) {
            string curr = q.front();
            q.pop();

            if (holds_alternative<int>(m[curr])) {
                res += std::get<int>(m[curr]);
            }
            else {
                auto& children = get<pair<string, string>>(m[curr]);
                if (!children.first.empty()) {
                    q.push(children.first);
                }
                if (!children.second.empty()) {
                    q.push(children.second);
                }
            }
        }

        return res;
    }
};

// Intuition:
// if A dependes on B and C, means B and C's parent is A.
// If we update value on B or C, we also need to update value on A.
// So instead of traversing from A every time we are trying to get A value.
//
// We can traverse from children to parents based on value update on set function.
class SpreadSheetBFSWithCache {
public:
    map<string, variant<int, pair<string, string>>> m;

    // Parent relationship
    unordered_map<string, unordered_set<string>> parents;
    // Values
    unordered_map<string, int> values;

    bool hasCycleUtil(string key, unordered_map<string, int>& visited) {
        for (auto p : parents[key]) {
            if (visited.count(p)) {
                if (visited[p] == 1) continue;
                else if (visited[p] == 2) return true;
            } else {
                visited[p] = 1;
                if (hasCycleUtil(p, visited)) {
                    return true;
                }
            }
        }

        visited[key] = 2;
        return false;
    }

    bool hasCyclic(string key) {
        unordered_map<string, int> visited;
        return hasCycleUtil(key, visited);
    }

    // Time: O(1)
    int getCell(string key) {
        if (!values.count(key)) {
            throw runtime_error("Key not found");
        }

        return values[key];
    }

    // Case 1: key doesn't exist: update parent relationship and val;
    // Case 2: key exist:
    // a. val -> children: update new value based on children, update parent relationship.
    // b. children->val
    // c. val->val
    // d. children -> children
    // Time: O(n)
    bool setCell(string key, variant<int, pair<string, string>> val) {
        // Connect parent and check cycle first.
        pair<int, vector<string>> value = parse(val);
        for (auto i : value.second) {
            parents[i].insert(key);
        }
        if (hasCyclic(key)) {
            for (auto i : value.second) {
                parents[i].erase(key);
            }

            return false;
        }


        if (!m.count(key)) {
            m[key] = val;
            values[key] = value.first;
            for (auto i: value.second) {
                parents[i].insert(key);
            }

            return true;
        }

        variant<int, pair<string, string>> prevVal = m[key];
        pair<int, vector<string>> prevValue = parse(prevVal);

        m[key] = val;
        // Invalidate previous parent relationship or keep track of value diff.
        for (auto i: prevValue.second) {
            parents[i].erase(key);
        }

        // Update parents relationship
        for (auto i: value.second) {
            parents[i].insert(key);
        }

        // Update downstream parent values using BFS.
        int valueDiff = value.first - prevValue.first;
        updateParentValues(key, valueDiff);

        return true;
    }

    pair<int, vector<string>> parse(variant<int, pair<string, string>> val) {
        if (holds_alternative<int>(val)) {
            return {get<int>(val), {}};
        } else {
            auto& children = get<pair<string, string>>(val);
            int value = values[children.first] + values[children.second];
            return {value, {children.first, children.second}};
        }
    }

    void updateParentValues(string key, int diff) {
        queue<string> q;
        q.push(key);

        while (!q.empty()) {
            string curr = q.front();
            q.pop();

            values[curr] += diff;

            for (auto p : parents[curr]) {
                q.push(p);
            }
        }
    }

};   

int main() {

    // SpreadSheetBFS ss;
    // ss.setCell("A", 6);
    // ss.setCell("B", 7);
    // ss.setCell("C", make_pair("A", "B"));

    // cout << "A: " << ss.getCell("A") << endl; // 6
    // cout << "B: " << ss.getCell("B") << endl; // 7
    // cout << "C: " << ss.getCell("C") << endl; // 13

    // ss.setCell("A", 13);
    // cout << "C: " << ss.getCell("C") << endl; // 20

    // // C -> B, G
    // ss.setCell("C", make_pair("B", "G"));
    // ss.setCell("B", make_pair("G", "D"));
    // ss.setCell("G", make_pair("D", "F"));
    // ss.setCell("D", 1);
    // ss.setCell("F", 2);

    // cout << "B: " << ss.getCell("B") << endl; // 4
    // cout << "C: " << ss.getCell("C") << endl; // 7
    // cout << "D: " << ss.getCell("D") << endl; // 1
    // cout << "G: " << ss.getCell("G") << endl; // 3
    // cout << "F: " << ss.getCell("F") << endl; // 2

    SpreadSheetBFSWithCache ss;
    ss.setCell("A", 6);
    ss.setCell("B", 7);
    ss.setCell("C", make_pair("A", "B"));

    cout << "A: " << ss.getCell("A") << endl; // 6
    cout << "B: " << ss.getCell("B") << endl; // 7
    cout << "C: " << ss.getCell("C") << endl; // 13

    ss.setCell("A", 13);
    cout << "C: " << ss.getCell("C") << endl; // 20

    // C -> B, G
    ss.setCell("D", 1);
    ss.setCell("F", 2);
    ss.setCell("G", make_pair("D", "F"));
    ss.setCell("B", make_pair("G", "D"));
    ss.setCell("C", make_pair("B", "G"));

    cout << "B: " << ss.getCell("B") << endl; // 4
    cout << "C: " << ss.getCell("C") << endl; // 7
    cout << "D: " << ss.getCell("D") << endl; // 1
    cout << "G: " << ss.getCell("G") << endl; // 3
    cout << "F: " << ss.getCell("F") << endl; // 2

    // Cycle detection
    cout << ss.setCell("D", make_pair("C", "A")) << endl; // 0
    cout << "B: " << ss.getCell("B") << endl; // 4
    cout << "C: " << ss.getCell("C") << endl; // 7
    cout << "D: " << ss.getCell("D") << endl; // 1
    cout << "G: " << ss.getCell("G") << endl; // 3
    cout << "F: " << ss.getCell("F") << endl; // 2


    // Cell A = Cell(6);
    // Cell B = Cell(7);
    // Cell C = Cell(13, "A", "B");
    // SpreadSheet sheet;
    // sheet.set("A", A);
    // sheet.set("B", B);
    // sheet.set("C", C);
    // int a = sheet.get("A");
    // cout << a << endl;

    // int b = sheet.get("B");
    // cout << b << endl;

    // int c = sheet.get("C");
    // cout << c << endl;

    // A.val = 13;
    // sheet.set("A", A);

    // c = sheet.get("C");
    // cout << c << endl;

    return 0;
}

class Cell {
public:
    int val;
    string child1;
    string child2;

    Cell() : val(0), child1(""), child2("") {}
    Cell(int val) : val(val), child1(""), child2("") {}
    Cell(int val, string child1, string child2) : val(val), child1(child1), child2(child2) {}
};

// A -> [B, C], C -> [D, E]
// Without Cache
class SpreadSheet {
public:
    unordered_map<string, Cell> m;

    SpreadSheet() {}
    int get(string key) {
        if (!m.count(key)) {
            throw;
        }
        return dfs(key);
    }

    int dfs(string key) {
        Cell cell = m[key];
        if (cell.child1.empty() && cell.child2.empty()) {
            return cell.val;
        }

        int v1 = get(cell.child1);
        int v2 = get(cell.child2);
        return v1 + v2;
    }

    void set(string key, Cell cell) {
        m[key] = cell;
    }
};```