persistent_stack.cpp

#include <iostream>
#include <vector>
#include <cstdlib>
using namespace std;

struct node
{
    int top, par, val, sz;
    
    node(int p = 0, int t = 0, int s = 0, int v = 0) :
        par(p), top(t), sz(s), val(v) {}
};

class pr_stack
{
    int v, maxv;
    vector<node> nodes;
    
public:
    pr_stack()
    {
        v = maxv = 0;
        nodes.push_back(node());
        log();
    }
    
    int size()
    {
        return nodes[v].sz;
    }
    
    int version()
    {
        return v;
    }
    
    void setVersion(int n)
    {
        v = n;
        log();
    }
    
    void historyOf(int n)
    {
        if (n > 0)
            historyOf(nodes[n].par);
        log(n);
    }
    
    void history()
    {
        for (int i = 0; i <= maxv; i++)
            log(i);
    }
    
    void log()
    {
        log(v);
    }
    
    void log(int n)
    {
        if (n == 0)
            cout << "Version 0, Init" << endl;
        else {
            cout << "Version " << nodes[n].par << " -> " << n << ", ";
            if (nodes[n].top == n)
                cout << "Push " << nodes[n].val << ", ";
            else
                cout << "Pop " << nodes[nodes[nodes[n].par].top].val << ", ";
            cout << "Size " << nodes[n].sz << endl;
        }
    }
    
    void push(int n)
    {
        maxv++;
        nodes.push_back(node(v, maxv, size() + 1, n));
        v = maxv;
        log();
    }
    
    int pop(bool save = true)
    {
        int top = nodes[v].top,
            res = nodes[top].val,
            topParent = nodes[top].par,
            subTop = nodes[topParent].top;
        if (top == 0) {
            cout << "Stack is empty" << endl;
            throw -1;
        }
        if (save) {
            maxv++;
            nodes.push_back(node(v, subTop, size() - 1));
            v = maxv;
        } else
            v = subTop;
        log();
        return res;
    }
};

void help()
{
    cout << "p <number>  - Push number"        << endl
         << "x           - Pop"                << endl
         << "v           - Current version"    << endl
         << "j <version> - Set version (jump)" << endl
         << "s           - Current size"       << endl
         << "i           - History (info)"     << endl
         << "q           - Quit"               << endl
         << "h           - Help"               << endl;
}

int main()
{
    help();
    pr_stack p;
    char a;
    int b;
    while (true) {
        cin >> a;
        switch (a) {
            case 'p':
                cin >> b;
                p.push(b);
                cout << "Pushed " << b << endl;
                break;
            case 'x':
                try {
                    int s = p.pop();
                    cout << "Popped " << s << endl;
                } catch (int e) {
                }
                break;
            case 'v':
                cout << "Version " << p.version() << endl;
                break;
            case 'j':
                cin >> b;
                p.setVersion(b);
                break;
            case 's':
                cout << p.size();
                break;
            case 'i':
                p.history();
                break;
            case 'q':
                return 0;
            default:
                help();
        }
    }
    return 0;
}