This is a simple container for implementing a retroactive array. It supports modifying data and querying data online, and also creating branches of versions instantly. The time complexity is \(O(n \log n)\) as well as its memory complexity. However by submitting this version it seemed to have a constant error, id est failure by allocating too much memory.I updated this version this afternoon, and dramatically improved the memory cost and halved the time cost. Currently it runs for 2. 4s on bzoj3674, about 3 times slower than the fastest implementation.
It ‘s quite simple to use this template. All you need to do is to initialize the tree, build it and fork it. To initialize, do the following:
int n = 5000;
int default_value = 0;
retroactive_array<int> array;
array.init(n, default_value);Because we’ ve updated this template for performance issues, the initialization function can be specified with a given value, such that while given the position of this element, the function returns a value for this array to insert.
int n = 5000;
string default_generator(int position) {
if (position % 2 == 0)
return "Even";
return "Odd"; }
retroactive_array<string> array;
array.init(n, default_generator);To create branches, you need to specify the older version by its version number. The version number could be arbitrary integers, but not floating point numbers or 64 bit integers. To maintain maximum compatibility, we advise you against using timestamps of large values or less than 0. If no version number is set, we default the base version to #0:
int old_time = 3;
int new_time = 7;
array.fork(new_time, old_time);
// Creating another from base version
array.fork(new_time);
// array.fork(new_time, 0);To set values, you could either use the faster way, or use the easier way. The easier way is used to deal with simple data structures, such as default data types like integers. If you are dealing with complex classes, then to avoid compile errors we suggest that you should use the other ones.
array.fork(6, 0);
// Setting values
array.set(0, 666, 2333)
array[0][666] = 2333;
// Getting values
std::cout << array[0][666] << std::endl; // Should output "2333"
std::cout << array.get(6, 666) << std::endl; // Should output "0"Also, to check if a position had already been used, you may use the empty function to determine an empty timestamp by specifying the only parameter with the designated timestamp.
int tm_stamp = 1;
while (!array.empty(tm_stamp))
tm_stamp++;
array.fork(tm_stamp, 0);We also created an initialization function for users to override the default settings. The memory allocation can be done in one go, by specifying some flags in the code:
// Handle exceptions. If you know what you are doing, disable this
#define RA_DO_HANDLE_EXCEPTION 1
// Allocate nodes on demand (new). If you know how much you are allocating,
// modify the pool sizes in the template and disable this.
#define RA_MALLOC_ON_DEMAND 1
// If you don't need arbitrary timestamps (consecutively assigned) and you
// know what you are doing, disable this
#define RA_UNLIMITED_TIMESTAMPS 1If you are looking for the template, you can find it by expanding the article and look below. This works perfectly well at most places. But if you find a bug, don ‘t ask me. I don’ t know very clearly about this, and it ‘s not very efficient, though.
#include <cstring>
#include <stdexcept>
#include <map>
#define RA_DO_HANDLE_EXCEPTION 1
#define RA_MALLOC_ON_DEMAND 1
#define RA_UNLIMITED_TIMESTAMPS 1
template <typename _Type>
class retroactive_array
{
private:
// Constants, only used if required
static const int _node_pool_size = 1000100;
static const int _timestamp_size = 20100;
// Segment tree structural implementation
class ra_node {
public:
_Type value;
ra_node *lc, *rc;
};
int _size;
#ifdef RA_UNLIMITED_TIMESTAMPS
std::map<int, ra_node*> root;
#else
ra_node* root[_timestamp_size];
#endif
// Node allocation units
#ifdef RA_MALLOC_ON_DEMAND
ra_node* alloc_node(void)
{
ra_node *p = new ra_node;
return p;
}
#else
ra_node _node_pool[_node_pool_size];
int _node_pool_cntr;
ra_node* alloc_node(void)
{
#ifdef RA_DO_HANDLE_EXCEPTION
if (_node_pool_cntr >= _node_pool_size)
throw std::out_of_range("Memory pool overflow");
#endif
ra_node *p = &_node_pool[_node_pool_cntr++];
return p;
}
#endif
// Recursive tree building unit
typedef _Type gen_function(int);
ra_node* build_tree(int l, int r, gen_function func)
{
ra_node *p = this->alloc_node();
if (l == r) {
p->value = func(l);
return p;
}
int mid = (l + r) >> 1;
p->lc = this->build_tree(l, mid, func);
p->rc = this->build_tree(mid + 1, r, func);
return p;
}
// Querying data from structure
_Type query(ra_node *p, int l, int r, int pos)
{
if (l == r)
return p->value;
int mid = (l + r) >> 1;
if (pos <= mid)
return this->query(p->lc, l, mid, pos);
else
return this->query(p->rc, mid + 1, r, pos);
}
// Modifying data in structure
ra_node* modify(ra_node *p, int l, int r, int pos, _Type val)
{
// Creating clone of this node
ra_node *q = this->alloc_node();
q->value = p->value;
q->lc = p->lc;
q->rc = p->rc;
// Working on segment tree
if (l == r) {
q->value = val;
return q;
}
int mid = (l + r) >> 1;
if (pos <= mid)
q->lc = this->modify(q->lc, l, mid, pos, val);
else
q->rc = this->modify(q->rc, mid + 1, r, pos, val);
return q;
}
private:
// Maintaining functions for invoking upper-level retroactive array
// functions on I/O
size_t get_size(void)
{
return this->_size;
}
bool has_time(int time)
{
if (this->root[time] == NULL)
return false;
return true;
}
void create_fork(int time, int time_old = 0)
{
if (time == time_old)
return ;
#ifdef RA_DO_HANDLE_EXCEPTION
if (this->root[time_old] == NULL)
throw std::out_of_range("Unexpected time of fork source supplied.");
#endif
if (this->root[time] != NULL)
return ;
ra_node *o_root = this->root[time_old];
ra_node *c_root = this->alloc_node();
// Copy data for duplication
c_root->value = o_root->value;
c_root->lc = o_root->lc;
c_root->rc = o_root->rc;
// Putting back into map
this->root[time] = c_root;
return ;
}
_Type get_data(int time, int pos)
{
#ifdef RA_DO_HANDLE_EXCEPTION
if (pos < 0 || pos > this->_size)
throw std::out_of_range("Indexing limits out of bound.");
#endif
// Retrieving root at position
ra_node *c_root = this->root[time];
#ifdef RA_DO_HANDLE_EXCEPTION
if (c_root == NULL)
throw std::out_of_range("Unexpected time supplied.");
#endif
// Getting data
_Type res = this->query(c_root, 1, _size, pos);
return res;
}
void set_data(int time, int pos, _Type val)
{
#ifdef RA_DO_HANDLE_EXCEPTION
if (pos < 0 || pos > this->_size)
throw std::out_of_range("Indexing limits out of bound.");
#endif
// Retrieving root at position
ra_node *c_root = this->root[time];
#ifdef RA_DO_HANDLE_EXCEPTION
if (c_root == NULL)
throw std::out_of_range("Please create a fork before setting data.");
#endif
// Modifying data
c_root = this->modify(c_root, 1, _size, pos, val);
this->root[time] = c_root;
return ;
}
void init_array(int n, gen_function func)
{
this->_size = n;
ra_node *c_root = this->build_tree(1, _size, func);
#ifdef RA_UNLIMITED_TIMESTAMPS
this->root.clear();
#else
memset(root, 0, sizeof(root));
#endif
this->root[0] = c_root;
return ;
}
_Type _default_zero;
_Type _zero_override_func(int in) {
return _default_zero; }
void init_array(int n, _Type zero)
{
this->_default_zero = zero;
this->init_array(n, _zero_override_func);
return ;
}
protected:
// Data wrapper for positions (third-level)
class ra_val_wrapper {
protected:
retroactive_array* _ra;
int _time, _pos;
public:
ra_val_wrapper(retroactive_array* _ra, int _time, int _pos) {
this->_ra = _ra;
this->_time = _time;
this->_pos = _pos;
return ; }
ra_val_wrapper& operator = (ra_val_wrapper in) {
*this = _Type(in);
return *this; }
ra_val_wrapper& operator = (_Type in) {
this->_ra->set_data(this->_time, this->_pos, in);
return *this; }
operator _Type (void) {
_Type val = this->_ra->get_data(this->_time, this->_pos);
return val; }
};
// Data wrapper for time (second-level)
class ra_time_wrapper {
protected:
retroactive_array* _ra;
int _time;
public:
ra_time_wrapper(retroactive_array* _ra, int _time) {
this->_ra = _ra;
this->_time = _time;
return ; }
ra_val_wrapper operator [] (int pos) {
ra_val_wrapper rvw(this->_ra, this->_time, pos);
return rvw; }
};
// Wrapping time
ra_time_wrapper call_time_wrapper(int time)
{
// Checking if fork required
this->create_fork(time);
// Returning wrapper
ra_time_wrapper rtw(this, time);
return rtw;
}
public:
retroactive_array(void) {
this->_size = 0;
#ifndef RA_MALLOC_ON_DEMAND
memset(_node_pool, 0, sizeof(_node_pool));
_node_pool_cntr = 0;
#endif
return ; }
retroactive_array(int n, _Type zero) {
this->init_array(n, zero);
return ; }
void init(int n, gen_function func) {
this->init_array(n, func);
return ; }
void init(int n, _Type zero) {
this->init_array(n, zero);
return ; }
size_t size(void) {
return this->get_size(); }
_Type get(int time, int pos) {
return this->get_data(time, pos); }
void set(int time, int pos, _Type val) {
this->set_data(time, pos, val);
return ; }
void fork(int time, int time_old = 0) {
this->create_fork(time, time_old);
return ; }
ra_time_wrapper operator [] (int time) {
return this->call_time_wrapper(time); }
};The following is a previous template, which costs more memory and time. We advise you against using the deprecated version.
#include <map>
#include <stdexcept>
template <typename _Type>
class retroactive_array
{
private:
// Segment tree structural implementation
class ra_node {
public:
_Type value;
ra_node *lc, *rc;
};
std::map<int, ra_node*> root;
ra_node* alloc_node(void)
{
ra_node *p = new ra_node;
return p;
}
int _size;
// Recursive tree building unit
ra_node* build_tree(int l, int r, _Type zero)
{
ra_node *p = this->alloc_node();
if (l == r) {
p->value = zero;
return p;
}
int mid = (l + r) >> 1;
p->lc = this->build_tree(l, mid, zero);
p->rc = this->build_tree(mid + 1, r, zero);
return p;
}
// Querying data from structure
_Type query(ra_node *p, int l, int r, int pos)
{
if (l == r)
return p->value;
int mid = (l + r) >> 1;
if (pos <= mid)
return this->query(p->lc, l, mid, pos);
else
return this->query(p->rc, mid + 1, r, pos);
}
// Modifying data in structure
ra_node* modify(ra_node *p, int l, int r, int pos, _Type val)
{
// Creating clone of this node
ra_node *q = this->alloc_node();
q->value = p->value;
q->lc = p->lc;
q->rc = p->rc;
// Working on segment tree
if (l == r) {
q->value = val;
return q;
}
int mid = (l + r) >> 1;
if (pos <= mid)
q->lc = this->modify(q->lc, l, mid, pos, val);
else
q->rc = this->modify(q->rc, mid + 1, r, pos, val);
return q;
}
private:
// Maintaining functions for invoking upper-level retroactive array
// functions on I/O
size_t get_size(void)
{
return this->_size;
}
bool has_time(int time)
{
if (this->root[time] == NULL)
return false;
return true;
}
void create_fork(int time, int time_old = 0)
{
if (time == time_old)
return ;
if (this->root[time_old] == NULL)
throw std::out_of_range("Unexpected time of fork source supplied.");
if (this->root[time] != NULL)
return ;
ra_node *o_root = this->root[time_old];
ra_node *c_root = this->alloc_node();
// Copy data for duplication
c_root->value = o_root->value;
c_root->lc = o_root->lc;
c_root->rc = o_root->rc;
// Putting back into map
this->root[time] = c_root;
return ;
}
_Type get_data(int time, int pos)
{
if (pos < 0 || pos > this->_size)
throw std::out_of_range("Indexing limits out of bound.");
// Retrieving root at position
ra_node *c_root = this->root[time];
if (c_root == NULL)
throw std::out_of_range("Unexpected time supplied.");
// Getting data
_Type res = this->query(c_root, 1, _size, pos);
return res;
}
void set_data(int time, int pos, _Type val)
{
if (pos < 0 || pos > this->_size)
throw std::out_of_range("Indexing limits out of bound.");
// Retrieving root at position
ra_node *c_root = this->root[time];
if (c_root == NULL)
throw std::out_of_range("Please create a fork before setting data.");
// Modifying data
c_root = this->modify(c_root, 1, _size, pos, val);
this->root[time] = c_root;
return ;
}
void init_array(int n, _Type zero)
{
this->_size = n;
ra_node *c_root = this->build_tree(1, _size, zero);
this->root.clear();
this->root[0] = c_root;
return ;
}
// protected:
public:
// Data wrapper for positions (third-level)
class ra_val_wrapper {
protected:
retroactive_array* _ra;
int _time, _pos;
public:
ra_val_wrapper(retroactive_array* _ra, int _time, int _pos) {
this->_ra = _ra;
this->_time = _time;
this->_pos = _pos;
return ; }
ra_val_wrapper& operator = (ra_val_wrapper in) {
*this = _Type(in);
return *this; }
ra_val_wrapper& operator = (_Type in) {
this->_ra->set_data(this->_time, this->_pos, in);
return *this; }
operator _Type (void) {
_Type val = this->_ra->get_data(this->_time, this->_pos);
return val; }
};
// Data wrapper for time (second-level)
class ra_time_wrapper {
protected:
retroactive_array* _ra;
int _time;
public:
ra_time_wrapper(retroactive_array* _ra, int _time) {
this->_ra = _ra;
this->_time = _time;
return ; }
ra_val_wrapper operator [] (int pos) {
ra_val_wrapper rvw(this->_ra, this->_time, pos);
return rvw; }
};
// Wrapping time
ra_time_wrapper call_time_wrapper(int time)
{
// Checking if fork required
this->create_fork(time);
// Returning wrapper
ra_time_wrapper rtw(this, time);
return rtw;
}
public:
retroactive_array(void) {
this->root.clear();
this->_size = 0;
return ; }
retroactive_array(int n, _Type zero) {
this->init_array(n, zero);
return ; }
void init(int n, _Type zero) {
this->init_array(n, zero);
return ; }
size_t size(void) {
return this->get_size(); }
_Type get(int time, int pos) {
return this->get_data(time, pos); }
void set(int time, int pos, _Type val) {
this->set_data(time, pos, val);
return ; }
void fork(int time, int time_old = 0) {
this->create_fork(time, time_old);
return ; }
ra_time_wrapper operator [] (int time) {
return this->call_time_wrapper(time); }
};