Persistent array implemented in C++ using balanced binary tree.

persistent_array.cpp

/* Copyright 2016 Rafael Rendón Pablo <[email protected]> */
// In this code array means persistent array and will be denoted by "array*".
#include <bits/stdc++.h>
using namespace std;
const int kMax      = 10000;

// Node describes a node in the tree.
struct Node {
    // Array* index.
    int idx;

    // Value stored at index.
    int value;

    // Array* unique indentifier.
    int uid;

    // Reference to left subtree
    Node* left;

    // Reference to right subtree
    Node* right;

    Node() {
        idx = 0;
        value = 0;
        uid = 0;
        left = right = nullptr;
    }

    Node(int i, int v, int u) {
        idx = i;
        value = v;
        uid = u;
        left = right = nullptr;
    }
};

// PersistentArray persistent array using balanced binary tree (through
// randomization).
class PersistentArray {
public:
    PersistentArray() {
        root_ = nullptr;
        detached_ = false;
    }

    PersistentArray(unsigned int size) {
        size_ = size;
        detached_ = true;
        vector<int> ids(size_ - 1);
        iota(begin(ids), end(ids), 1);

        // Randomize indices to raise the chances of having a balanced tree.
        unsigned seed = chrono::system_clock::now().time_since_epoch().count();
        shuffle(begin(ids), end(ids), default_random_engine(seed));

        // Create entries for all indices
        root_ = new Node(0, 0, 0);
        for (int id : ids) {
            root_ = create(root_, id, 0);
        }
    }

    // Copy constructor
    PersistentArray(const PersistentArray& other) {
        this->size_ = other.size_;
        this->detached_ = false;
        this->root_ = other.root_;
    }

    // Asignment operator
    PersistentArray& operator=(const PersistentArray& other) {
        this->size_ = other.size_;
        this->detached_ = false;
        this->root_ = other.root_;
        return *this;
    }

    // Set sets value at index idx, i.e. A[idx] = value.
    void Set(int idx, int value) {
        if (!detached_) {
            // Copy-on-write, detach tree when a write operation is performed.
            root_ = setAndDetach(root_, idx, value);
            detached_ = true;
        } else {
            setValue(root_, idx, value);
        }
    }

    // Get returns the value at index idx, i.e., A[idx].
    int Get(int idx) {
        return get(root_, idx);
    }


    // clean frees tree, it only deletes those nodes that were created for this
    // tree, i.e., it skips shared nodes.
    void clean(Node* root, int uid) {
        if (root == nullptr) {
            return;
        }

        if (root->left && root->left->uid == uid) {
            clean(root->left, uid);
            delete root->left;
        }

        if (root->right && root->right->uid == uid) {
            clean(root->right, uid);
            delete root->right;
        }
    }

    // Destructor
    ~PersistentArray() {
        if (detached_ && root_) {
            clean(root_, root_->uid);
            delete root_;
        }
    }

private:
    // Array* size
    int size_;

    // Flag that indicates if we should create a copy of the array*.
    bool detached_;

    // Entry point to the tree.
    Node* root_;

    // create creates entry for index idx, with value 0 and uid.
    Node* create(Node* root, int idx, int uid) {
        if (root == nullptr) {
            return new Node(idx, 0, uid);
        }

        if (idx < root->idx) {
            root->left = create(root->left, idx, uid);
        } else {
            root->right = create(root->right, idx, uid);
        }
        return root;
    }

    // setValue sets value at index idx, i.e. A[idx] = value.
    void setValue(Node* root, int idx, int value) {
        if (root == nullptr) {
            return;
        }
        if (idx == root->idx) {
            root->value = value;
            return;
        }

        if (idx < root->idx) {
            setValue(root->left, idx, value);
        } else {
            setValue(root->right, idx, value);
        }
    }

    // setAndDetach sets A[idx] = value and copies the path all the way up to
    // the root so that the original array* remains unchanged.
    Node* setAndDetach(Node* root, int idx, int value) {
        if (root == nullptr) {
            return root;
        }
        Node* node = nullptr;
        if (idx == root->idx) {
            node = new Node(idx, value, root->uid + 1);
            node->left = root->left;
            node->right = root->right;
            return node;
        }

        if (idx < root->idx) {
            Node* l = setAndDetach(root->left, idx, value);
            if (l != nullptr) {
                node = new Node(root->idx, root->value, l->uid);
                node->left = l;
                node->right = root->right;
            }
        } else {
            Node* r = setAndDetach(root->right, idx, value);
            if (r != nullptr) {
                node = new Node(root->idx, root->value, r->uid);
                node->left = root->left;
                node->right = r;
            }
        }
        return node;
    }

    // get returns the value at index idx, i.e., A[idx].
    int get(Node* root, int idx) {
        // Returns 0 for non-existent indices.
        if (root == nullptr) {
            return 0;
        }

        if (idx == root->idx) {
            return root->value;
        }

        if (idx < root->idx) {
            return get(root->left, idx);
        } else {
            return get(root->right, idx);
        }
    }
};

int main() {
    // Test
    PersistentArray pa(1000000);
    PersistentArray arrays[kMax];
    for (int i = 0; i < kMax; i++) {
        arrays[i] = pa;
        arrays[i].Set(i, i * i);
    }


    for (int i = 0; i < kMax; i++) {
        cout << arrays[i].Get(i) << "\n";
    }

    return EXIT_SUCCESS;
}